Título Programación lineal Avanzada

Flores Tapia Javier Alexis 85019

Laura Quenta Dalila

Chino Mamani Jonas Alejandro

Huanquiri Aguilar Angel Gabriel

Gomez Mamani Miguel Angel

Ramírez Vasquez Nayla

Valdez Espada Joselyn Maciel

Chura Quiroga Cimar Andres

Autor/es
Mayta Poma Elizabeth 80883

Gonzales Chura Brayan

Donaire Quispe Ruben Duglas 74791

Tapia Mamani Dayner Joel

Salinas Chiri Pablo

Rios Mamani Jorge Luis

Dorval Mamani Jordan

Quisbert Guerrero Yoseth Andrea

Fecha 22/06/2023
 INTRODUCCION

La programación lineal es un método a través del cual se optimiza una función

objetivo, bien sea maximizando o minimizando dicha función, en la cual las variables

están elevadas a la potencia 1. Este campo de la programación lineal es un área de la

programación matemática, dedicada a maximizar o minimizar una función lineal que

recibe el nombre de "función objetivo", de manera que las variables de tal función estén

sujetas a una serie de restricciones expresadas a través de un sistema de ecuaciones o

inecuaciones lineales.

Cuando se estudia lo que es programación lineal en investigación de

operaciones se hace imprescindible señalar que esta se aplica para la administración

eficiente de los procesos en muchos ámbitos de la economía, así como también implica

el conocimiento de que existe una diversidad de software en el mercado, que ayuda a

representar el enfoque o modelo de programación lineal.

Es importante considerar que lo que es programación lineal en investigación

de operaciones está compuesta por dos elementos fundamentales: la región factible y

las restricciones estructurales y de no negatividad.

A las restricciones se les llama restricciones de no negatividad y, se le conocen

como condiciones del modelo que estipulan que las variables de decisión deben tener

solo valores no negativos, es decir, positivos o nulos. Al conjunto de valores que

satisfacen todas las restricciones, se les denomina región factible, que se le cataloga

como un espacio de solución o de todos los puntos posibles de un problema de

optimización que satisface las restricciones del problema, incluyendo las

potencialidades, las igualdades y las restricciones enteras.

 ORIGEN DE LA PROGRAMACIÓN LINEAL

Conocer qué es programación lineal en investigación de operaciones implica

acotar que esta no es procedente de los programas de ordenador, sino que su origen se

sitúa en un término de corte militar, pues programar significa realizar propuestas o

planes de tiempo para el entrenamiento, logística o despliegue de unidades de combate.

Muchos consideran que este término fue utilizado por G. Monge en el año 1776,

pero la verdad es que se considera a L.V Kantoróvich como uno de sus creadores, ya que

lo presentó en su libro de métodos matemáticos para la organización y producción.

La investigación de operaciones, así como la programación lineal, se vieron

impulsadas con la aparición de los ordenadores y uno de los momentos más importante

fue con la aparición del método simplex.

El método simplex

Cuando se trata de la programación lineal, también es importante acotar que

existe un método llamado el método simplex, el cual comprende un medio analítico de

solución de problemas de programación lineal, que es capaz de resolver modelos que

son más complejos que los que se resuelven mediante el método gráfico, sin restricción

en el número de variables.

Tipos de soluciones en la programación lineal

Los programas lineales que tienen dos variables se clasifican de acuerdo al tipo

de solución que presenten y, pueden ser los siguientes:

 Factibles

Cuando existe un conjunto de soluciones o valores que satisfacen las

restricciones, estas pueden dividirse en solución única o con solución múltiple. Además,

se puede encontrar una solución no acotada.

En el área de optimización matemática, una región factible o un conjunto

factible es un espacio de búsqueda o un espacio de solución, es decir, es el conjunto de

todos los puntos posibles de un problema de optimización que satisface las restricciones

del problema.

No factibles

Sucede cuando no existe un conjunto de soluciones que cumplan las

restricciones, es decir, cuando estas son inconsistentes.

2.VECTORES Y BASES
2.1 PL ESTÁNDAR EN FORMA MATRICIAL

En esta sección se usarán matrices para desarrollar la tabla simplex general.

Esta representación será la base para desarrollos posteriores en el capítulo.

Se tiene la programación lineal en forma de ecuación:

Maximizar 𝑧 = 𝐶𝑋, sujeta a 𝐴𝑋 = 𝑏, 𝑋 ≥ 0

El problema se puede escribir en forma equivalente como sigue:

Supongamos que B es una base factible del sistema 𝑨𝑿 = 𝒃, 𝑿 ≥ 𝟎, y sea 𝑿𝐵 el

conjunto correspondiente de variables básicas, con 𝐶𝐵 como su vector objetivo

asociado. Entonces, la solución correspondiente se puede calcular como sigue.

La tabla general simplex en forma matricial se puede derivar de las ecuaciones

originales como sigue:

 Como 𝑃𝐽 es el 𝑗-ésimo vector de 𝐴, la columna de la tabla simplex asociada con

la variable 𝑥𝐽 se puede representar como sigue:

Una propiedad importante de esta tabla es que la inversa 𝑩−𝟏, es el único

elemento cambia de un cuadro al siguiente, y que todo el cuadro se puede generar una

vez conocido 𝑩−𝟏. Este punto es importante, porque se puede controlar el error

computacional de redondeo en cualquier cuadro, si se controla la exactitud de 𝑩−𝟏. Este

resultado fue la razón principal del desarrollo del método simplex modificado

2.2 LA REPRESENTACION VECTORIAL DE UNA BASE

Es la expresión de cualquier vector en función de los vectores base que definen

un espacio vectorial. Esta representación se logra al expresar el vector que se desea

representar como una combinación lineal de los vectores base, la combinación lineal

implica sumar multiplicar los vectores base por un factor escalar.

Esta técnica puede ser usada para cualquier espacio vectorial, ya sea en dos o tres

dimensiones, además, esta representación es útil en diversos campos de estudio como la

física, la geometría y el álgebra. Existen muchas aplicaciones prácticas de la

representación vectorial en la vida cotidiana. un ejemplo de ello es en la tecnología de

gráficos por computadora, donde los objetos 3d se representan mediante vectores y

pueden ser rotados, escalados y transformados en función de cálculos de vectores. la

representación vectorial también se aplica en la física para representar campos de fuerza

y movimientos, y en la ingeniería para el diseño de estructuras y sistemas mecánicos. en

el campo de la inteligencia artificial, la representación vectorial se utiliza en el

aprendizaje automático para analizar grandes cantidades de datos y generar modelos

predictivos. también se utiliza en la compresión de imágenes y señales de audio.

2.3 SOLUCIONES BASICAS

En la programación lineal avanzada, se trabaja con modelos más complejos que

requieren técnicas sofisticadas para encontrar soluciones óptimas. A pesar de la

complejidad, el concepto de "solución básica" sigue siendo fundamental. Las soluciones

básicas se encuentran dentro de la región factible del espacio de soluciones y satisfacen

todas las restricciones del problema.

 En la programación lineal avanzada, se pueden identificar diferentes tipos de

soluciones básicas en función de la estructura del modelo y las variables presentes. Aquí

se detallan algunos tipos comunes de soluciones básicas en la programación lineal

avanzada:

1. Solución Básica Degenerada: Una solución básica degenerada en la

programación lineal es aquella en la que una o más variables básicas tienen un valor

igual a cero. Esto implica que hay más variables básicas presentes de las necesarias para

definir la solución óptima.

En un modelo de programación lineal, las variables básicas son aquellas que se

establecen en la solución óptima para que todas las restricciones se satisfagan. Sin

embargo, en algunos casos, puede haber variables básicas que no contribuyan

activamente a la solución. Estas variables básicas redundantes pueden tener un valor

igual a cero en una solución básica degenerada.

La presencia de soluciones básicas degeneradas puede complicar los algoritmos

de optimización utilizados para encontrar la solución óptima. Esto se debe a que pueden

generar ciclos o estancamientos en el proceso de búsqueda, ya que ciertas

combinaciones de variables básicas con valores cero pueden parecer una mejora en el

objetivo, pero no conducen a una solución diferente.

Cuando se trabaja con soluciones básicas degeneradas, se pueden aplicar técnicas

adicionales para manejarlas. Algunas de estas técnicas incluyen el método de salida

adecuado, como la regla de Bland o la regla de mínimo índice relativo, que permiten

evitar o salir de las soluciones básicas degeneradas.

 2. Solución Básica Múltiple: Una solución básica múltiple en la

programación lineal es aquella en la que existen múltiples combinaciones lineales de las

variables básicas que satisfacen todas las restricciones del problema y optimizan la

función objetivo.

En otras palabras, hay más de una solución óptima en el modelo de programación

lineal. Estas soluciones básicas múltiples ocurren cuando la función objetivo es paralela

a una restricción o cuando las restricciones forman una región poliédrica en la cual se

encuentran múltiples puntos óptimos.

En una solución básica múltiple, todas las soluciones tienen el mismo valor

óptimo para la función objetivo. Sin embargo, las combinaciones de variables básicas

pueden ser diferentes entre las soluciones, lo que implica diferentes valores para las

variables no básicas.

La existencia de soluciones básicas múltiples puede presentar un desafío en la

programación lineal, ya que se requiere una consideración adicional para determinar

cuál de las múltiples soluciones óptimas es la más deseable en función de criterios

adicionales, como costos o preferencias.

Algunas técnicas utilizadas para abordar las soluciones básicas múltiples

incluyen el análisis de sensibilidad para evaluar cómo los cambios en los coeficientes de

la función objetivo o las restricciones afectan las soluciones óptimas, así como la

incorporación de restricciones adicionales o preferencias para reducir el espacio de

soluciones múltiples y obtener una solución única y preferida.

 3. Solución Básica No Degenerada: Una solución básica no degenerada en

la programación lineal es aquella en la que todas las variables básicas tienen un valor

distinto de cero. A diferencia de una solución básica degenerada, no hay redundancias en

el sistema de ecuaciones que define el problema.

En una solución básica no degenerada, todas las variables básicas son activas y

contribuyen de manera significativa a la solución óptima. Esto implica que cada

restricción del problema se satisface de forma estricta, es decir, sin holguras.

La solución básica no degenerada es considerada más "regular" en comparación

con una solución básica degenerada. Esto se debe a que no hay variables básicas con

valor cero, lo que simplifica los cálculos y el análisis de sensibilidad.

La ventaja de una solución básica no degenerada radica en su mayor estabilidad y

facilidad para el análisis. Las variables básicas tienen valores distintos de cero, lo que

permite una interpretación clara de su significado y su relación con las restricciones del

problema.

Es importante destacar que, en algunos problemas de programación lineal, puede

ser difícil o incluso imposible obtener una solución básica no degenerada. En tales casos,

se pueden aplicar técnicas especiales para manejar las soluciones degeneradas, como el

uso de reglas de salida adecuadas (por ejemplo, la regla de Bland) o métodos avanzados

de optimización.

Estos son solo algunos ejemplos de soluciones básicas que pueden surgir en la

programación lineal avanzada. Es importante tener en cuenta que la programación lineal

avanzada también puede involucrar técnicas adicionales, como el método del punto
interior y el uso de algoritmos de ramificación y acotamiento, para encontrar soluciones

óptimas en modelos más complejos y realistas.

3.PRUEBA DE VALIDEZ DEL METODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite ir mejorando la

solución a cada paso.

El proceso concluye cuando no es posible seguir mejorando más dicha solución.

Partiendo del valor de la función objetivo en un vértice cualquiera, el método

consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se

hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el

número de variables es mayor). Cómo el número de vértices (y de aristas) es finito,

siempre se podrá encontrar la solución. (Véase método Gráfico)

El método Simplex se basa en la siguiente propiedad: si la función objetivo, “Z”,

no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo

largo de la cual “Z” aumenta. Deberá tenerse en cuenta que este método sólo trabaja

para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes

mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso

de que después de este proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "="

habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.

PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX

La forma estándar del problema expresado matemáticamente, consta de una función

objetivo sujeta a determinadas restricciones:

Para ello, el modelo debe cumplir las siguientes condiciones:

1. El objetivo es de la forma de maximización o de minimización.

2. Todas las restricciones son de igualdad.

3. Todas las variables son no negativas.

4. Las constantes a la derecha de las restricciones son no negativas

TIPOS DE OPTIMIZACIÓN

Como se ha comentado, el objetivo del método simplex consiste en optimizar el

valor de la función objetivo. Sin embargo, se presentan dos opciones: obtener el valor

óptimo mayor (maximizar) u obtener el valor óptimo menor (minimizar).

 Además, existen diferencias en el algoritmo entre el objetivo de maximización y

el de minimización

en cuanto al criterio de condición de parada para finalizar las iteraciones y a las

condiciones de

entrada y salida de la base. Así:

Maximización

1. Condición de parada: cuando en la fila Z no aparece ningún valor negativo.

2. Condición de entrada a la base: el menor valor negativo en la fila Z (o el de mayor

valor absoluto entre los negativos) indica la variable Pj que entra a la base.

3. Condición de salida de la base: una vez obtenida la variable entrante, la variable que

sale se determina mediante el menor cociente P0/Pj de los estrictamente positivos.

Minimización

1. Condición de parada: cuando en la fila Z no aparece ningún valor positivo.

2. Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable

Pj que entra a la base.

3. Condición de salida de la base: una vez obtenida la variable entrante, la variable que

sale se determina mediante el menor cociente P0/Pj de los estrictamente negativos.

Cambio del tipo de optimización.

Si bien el proceso de maximización y minimización tienen sus procedimientos

bien definidos,

siempre resulta más sencillo maximizar que minimizar, en tal sentido, es posible

normalizar el objetivo del problema con el fin de aplicar siempre los mismos criterios en

lo referente a la condición de parada del algoritmo y a las condiciones de entrada y

salida de las variables de la base. De esta forma, si el objetivo es minimizar la solución,

se puede cambiar el problema a otro equivalente de maximización simplemente

multiplicando la función objetivo por "-1". Es decir, el problema de minimizar Z es

equivalente al problema de maximizar “-Z”. Una vez obtenida la solución óptima, será

necesario multiplicarla también por (-1).

Ventajas: No hay que preocuparse por nuevos criterios de parada, condición de entrada

y salida de la base ya que se mantienen.

Inconvenientes: En el caso de que la función tenga todos los coeficientes de sus

variables básicas positivos, y además las restricciones sean del tipo de desigualdad "≤",

al hacer el cambio dichos coeficientes quedan negativos cumpliéndose la condición de

parada en la primera iteración (en la fila del valor de la función objetivo todos los

valores son positivos o cero). Obteniéndose en este caso por defecto un valor óptimo

para la función igual a 0.

Solución: Realmente no existe este problema dado que para que la solución sea superior

a 0 es necesario que alguna restricción tenga impuesta la condición "≥" (y se trataría de

un modelo para el método de las Dos Fases). En el caso planteado, la solución real debe

ser cero. ¿Cómo se comprueba el método simplex?

El método Simplex no recorre explícitamente todos los vértices del conjunto factible,

sino que, en cada iteración, comprueba si existe un cambio de vértice que mejore la

solución actual. Si no existe ningún vértice mejor que el actual, el proceso se detiene

puesto que se ha llegado al óptimo.

 3.1 DEFINICIÓN DE CONJUNTOS CONVEXOS

El concepto de conjunto convexo es fundamental en el estudio de la

programación matemática porque permite obtener resultados teóricos importantes.

Dentro de la programación matemática tienen mucha importancia los problemas

convexos, donde las variables de decisión pertenecen a un conjunto convexo y la

función objetivo es una función convexa, dado que el teorema fundamental de la

programación convexa nos asegura que todo óptimo local es un óptimo global.

Teorema (teorema de representación de conjuntos convexos finitos). Si un

conjunto convexo está acotado y cerrado, cualquiera de sus puntos puede escribirse

como una combinación convexa de sus puntos extremos.

DEFINICIÓN

Un conjunto es convexo si dados dos puntos cualesquiera de un conjunto el

segmento que los une está contenido en el conjunto C, en el sentido de que todos los

puntos del segmento pertenecen a C. Es decir, son conjuntos convexos aquellos que

tienen la propiedad de que al unir con un segmento dos puntos cualesquiera del
conjunto, el segmento queda completamente contenido en el propio conjunto, es decir, si

se puede ir de cualquier punto a cualquier otro en línea recta, sin salir del mismo.

C ⊂ Rn es un conjunto convexo si es el vacío, si tiene un solo punto o si para

cada dos puntos distintos del conjunto el segmento que los une está contenido en el

conjunto.

(a), (b) y (c) son convexos y (d) no es convexo.

Aplicación a la programación lineal.

Los conjuntos convexos que aparecen en el estudio de modelos lineales son los

hiperplanos, los semiespacios cerrados y la intersección de un número finito. Estos

conjuntos son del tipo (a), donde los vértices del conjunto se llaman puntos extremos.

Propiedades de los conjuntos convexos

Conjuntos convexos "por definición":

a) El conjunto vacío (∅) es un conjunto convexo.

b) Los conjuntos de un único punto {a}, también son conjuntos convexos.

c) También el conjunto Rn (espacio total) es un conjunto convexo.

La intersección, finita o infinita, de conjuntos convexos es un conjunto convexo.

 La unión de conjuntos convexos, en general, no tiene por qué ser un conjunto

convexo.

La combinación lineal de conjuntos convexos es un conjunto convexo.

• Un hiperplano es un conjunto convexo.

• Un semiespacio cerrado es un conjunto convexo.

• La intersección de un número finito de conjuntos convexos es un

conjunto convexo.

Hiperplano.

Se define un hiperplano como:

es decir, se trata de la expresión: c1 x1 + c2 x2 + ... + cn xn = α, que para el caso

de n=2,

se tiene: c1 x1 + c2 x2 = α, ecuación que corresponde a la de una recta en el

plano.

Por tanto, un hiperplano, es la generalización al espacio n-dimensional del

concepto de recta.

Semiespacio.

A partir del concepto de hiperplano podemos definir el concepto de semiespacio,

como el conjunto de puntos que verifica que:

En el primer caso
 (1) lo denominamos semiespacio inferior y en el segundo (2) semiespacio

superior.

Estas dos definiciones de semiespacio se refieren a semiespacios cerrados, ya

que las desigualdades son de la forma mayor (menor) -igual.

Si las desigualdades son estrictas, es decir, mayor (menor) estrictamente

entonces decimos que se trata de semiespacios abiertos.

Toda combinación lineal con coeficientes positivos de funciones convexas es una

función convexa.

Sea S ⊆ Rn un conjunto convexo y no vacío, y sea f: S → R una función

convexa.

Entonces el conjunto de nivel inferior Sα = { x ∈ S / f(x) ≤ α }, es un conjunto convexo.

Si f es un función cóncava el conjunto de nivel superior Sα ={x ∈ S/f(x)≥ α}, es un

conjunto convexo.

3.2 OPTIMALIDAD DEL ALGORITMO SIMPLEX

QUE ES OPTIMALIDAD

Este principio garantiza que nunca encontraremos soluciones inferiores a la del

punto ya considerado

PRUEBA DE OPTIMALIDAD

Para poder hacer la demostración de la prueba de optimalidad lo que harems es

adaptarlo a un problema de transporte, donde podremos verificar en que nos sirve la

prueba de optimalidad, en este caso es un problema de 4 distribuidores que deben

distribuir sus productos a 5 clientes

En el grafico tenemos representada la cantidad que deben distribuir los

proveedores a sus clientes, dichas cantidades aun n se saben si son las óptimas o no y

nos ayudaremos con la prueba de optimalidad para poder analizar si esas cantidades son

las optimas

Cada una de las columnas representa una restricción al igual que cada fila

T1, T2, T3, T4 representan el número de distribuidores, M1, M2, M3, M4, M5

representan el número de clientes, las cantidades representadas representan las

M1 M2 M3 M4 M5
9 7 12 11 8
T1
25
1 5 9 7 8
T2 5 14 16
2 4 9 3 3
T3 11 15
1 8 11 2 5
T4 2 8
cantidades que deben ser distribuidas, por lo tanto

Tenemos 4 + 5 = 9 restricciones

M + n – 1 variables básicas

Tenemos 9 restricciones y 8 variables básicas

v. básica; Cij = Ui + Vj variables duales, por cada restricción tiene una

variable dual, por lo cual tenemos que V1, V2, V3, V4, V5, lo relacionamos con las

columnas y que U1,…, U4, lo relacionamos con las filas

Para poder hallar el resultado lo primero que haremos es ver que una restricción

es redundante por lo cual una de las variables duales también es redundante

 Entonces tenemos que U1 tendrá un valor de 0

Para poder hallar el valor de las variables realizamos las siguientes operaciones

M1 M2 M3 M4 M5
9 7 12 11 8
T1
25 U1=0
1 5 9 7 8
T2 5 14 16 U2=-3
2 4 9 3 3
T3 11 15 U3=-4
1 8 11 2 5
T4 2 8 U4=-1
V1=4 V2=8 V3=12 V4=3 V5=7

cij=Ui+Vj
T1,M3 12=0+V3 V3=12
T2M3 9=12+U2 U2=-3
T4,M3 11=U4+12 U4=-1
T2,M1 1=-3+V1 V1=4
T2,M2 5=-3+V2 V2=8
T3,M2 4=U3+8 U3=-4
T4,M4 2=-1+V4 V4=3
T3,M5 3=-4+V5 V5=7

Una vez hallada las variables duales debemos hallar las variables no básicas, para

esto debemos hallar el costo reducido con la siguiente formula

VNB= CIJ – (Ui+Vj)

Debemos verificar que el costo reducido sea positiva para todas las variables no

básicas, de ser así esto nos indica que la solución es óptima, para realizar esto

comenzaremos con la primera variable no básica que se presenta en la intersección entre

T1 y M1
 Tenemos tres costos reducidos negativos l que nos indica que estos costos

negativos, y estas todavía pueden aportar a seguir reduciendo la función objetivo lo que

nos indica que no es la solución óptima y para hallar la solución optima debemos seguir

iterando, podría ser una iteración más o varias iteraciones más, pero este resultado nos

indica que esta no es la solución optima por lo cual debemos seguir iterando hasta poder

hallar la solución factible

Algoritmos de cálculo eficiente

El análisis algorítmico se puede definir como el estudio que se realiza sobre un

M1 M2 M3 M4 M5
5 9 -1 7 12 8 11 1 8
T1
C11=9-(0+4)=5 C12=7-(0+8)=-1 25 C14=11-(0+3)=8 C15=8-(0+7)=1 U1=0
1 5 9 7 4 8
T2 5 14 16 C24=7-(-3+3)=7 C25=8-(-3+7)=4 U2=-3
2 2 4 1 9 4 3 3
T3 C31=2-(4+4)=2 11 C33=9-(4+12)=1 C34=3-(4+3)=4 15 U3=-4
-2 1 8 11 2 -1 5
T4 C41=1-(-1+4)=-2 C42=8-(-1+8)=1 2 8 C45=5-(-1+7)=-1 U4=-1
V1=4 V2=8 V3=12 V4=3 V5=7
algoritmo para determinar si su rendimiento y comportamiento cumple con los

requerimientos [15]; adicionalmente, permite tomar en cuenta esta información para

determinar la eficiencia del algoritmo. El objetivo del análisis de algoritmos es

cuantificar las medidas físicas: "tiempo de ejecución y espacio de memoria" y comparar

distintos algoritmos que resuelven un mismo problema. En el análisis de algoritmos es

necesario tener en cuenta, inicialmente, que los algoritmos construidos deben ser

correctos, es decir, deben producir un resultado deseado en tiempo finito. Los criterios

para realizar esta evaluación pueden ser eficiencia, portabilidad, eficacia, robustez, etc.
Complejidad algorítmica

La teoría de la complejidad computacional es la parte de la teoría de la

computación que estudia los recursos requeridos durante el cálculo para resolver un

problema. Dado que en las ciencias de la computación los algoritmos son la herramienta

más importante que se presenta, deben dar solución a diferentes problemas, con pasos

concretos, claros y finitos. Cada algoritmo arroja un cálculo correcto a través de la

recepción de datos de entrada y de la generación de información de salida.

Notación asintótica

Dentro del análisis de complejidad existen factores constantes que son poco

relevantes y pueden ser omitidos en la comparación de tasas; para tal fin se utiliza la

notación asintótica [6]. La eficiencia de un algoritmo se puede definir como una función

t(n) [20]. Al analizar un algoritmo, lo relevante es el comportamiento cuando se aumenta

el tamaño de los datos; esto se conoce como eficiencia asintótica de un algoritmo. Para

describir la notación asintótica se hace uso de las matemáticas, definiéndola como

función para cual los números naturales N son su dominio [1].

Algunas reglas sobre esta notación son las siguientes:

Divide y vencerás

Divide y vencerás es una técnica de diseño de algoritmos que consiste en

resolver un problema a partir de la solución de subproblemas del mismo tipo, pero de

menor tamaño. Si los subproblemas son todavía relativamente grandes se aplicará de

nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser

solucionados directamente; ello, naturalmente, sugiere el uso de la recursión en las

implementaciones de estos algoritmos. La resolución de un problema por medio de esta

técnica se da a través de, mínimo, los siguientes pasos:

1. División: Identificar los subproblemas del mismo tipo del problema

original y organizarlos en los diferentes grupos, k.

2. Solución subproblemas: Deben solucionarse de manera independiente

todos los subproblemas que estrictamente son de me

3. Solución problema: Dada una solución de los subproblemas, articular

estas soluciones para construir la solución del problema en genera

Ordenes de Complejidad
 Utilizando la notación asintótica, podemos definir un "orden de complejidad"

básico [8]; de esta forma enumeramos lo siguiente:

D. Recurrencias

En argumentos lógicos o en algoritmos se presenta la necesidad de resolver una

sucesión de casos, para lo cual, a nivel matemático, normalmente se busca estructurar la

conexión de cada caso con el anterior. La recurrencia es un método astuto que busca

enlazar cada caso con el anterior, es decir, generalizar el procedimiento y que al resolver

solo el último caso nos permita encontrar la respuesta de los demás, es decir, al final

solo nos quedará un primer caso por resolver, del que se deducirán todos [9]. En algunos

ejemplos se encuentra el cálculo de series, sucesiones o recorridos, que inicialmente son

problemas iterativos, pero a través del estudio o análisis de complejidad, es posible

plantear una ecuación de recurrencia; uno de los ejemplos nombrados y conocidos es el

cálculo de la serie de Fibonacci: 1-1-2-3-5-813-21-...

Dentro del manejo dado a las ecuaciones de recurrencia, al llevarlas a un proceso

algorítmico aparece una restricción, consistente en que mientras se resuelve el último

caso, todo el proceso está haciendo uso de un gran espacio de memoria y genera

conflictos en ejecución; por tal motivo, antes de hacer uso de esta técnica siempre es

necesario tener presente esto y tomar la decisión de combinarla con otros métodos de

solución o presentar otra posible solución desde el principio.

5.1 METODO SIMPLEX REVISADO

El método Simplex es una técnica matemática utilizada en la optimización de

problemas de programación lineal, es decir, aquellos que buscan maximizar o minimizar

una función objetivo sujeta a restricciones lineales. Este método se basa en la utilización

de tablas simplex, que son matrices que recogen los coeficientes de las variables de la

función objetivo y de las restricciones.

El proceso para encontrar la solución óptima mediante el método Simplex

implica varias iteraciones en las que se identifica una variable que entra (es decir, que

puede ser modificada para mejorar la función objetivo) y otra que sale (es decir, que ya

no será utilizada), a través de cálculos algebraicos y reglas específicas. Estas iteraciones

se continúan hasta que se alcanza la solución óptima que cumple todas las restricciones.

Algunas ventajas del método Simplex son su eficacia, rapidez y flexibilidad para

resolver problemas de programación lineal en diferentes ámbitos, como la economía, la

ingeniería, entre otros. Sin embargo, el método también tiene algunas limitaciones, como

su capacidad para resolver problemas muy grandes y complejos, y la posibilidad de

encontrar múltiples soluciones óptimas o ninguna solución si el problema incluye ciertas

características especiales.
 Como modelo matemático, el método Simplex es un enfoque determinista, lo que

significa que no puede modelar la incertidumbre y el riesgo inherentes a muchos

problemas del mundo real. Además, el método se concentra únicamente en la

maximización o minimización de una única función objetivo, lo que puede dejar de lado

otros objetivos importantes que pueden tener un impacto significativo en la toma de

decisiones.

Otro aspecto menos conocido del método Simplex es su relación con el álgebra

matricial. Las tablas simplex son equivalentes a sistemas de ecuaciones lineales, y las

operaciones que se realizan en las tablas se pueden representar como transformaciones

de matrices. Esta conexión matricial es un aspecto fundamental del método Simplex y

permite su aplicación en una amplia variedad de problemas.

Finalmente, cabe mencionar que el método Simplex ha evolucionado desde su

concepción original y existen varios algoritmos y versiones modificadas de él que

abordan sus limitaciones y extendiendo su aplicación a otros tipos de modelos

matemáticos. Por lo tanto, se trata de un método aún en desarrollo y evolución constante.

5.2 ALGORITMO DE VARIABLES ACOTADAS

En la mayoría de los problemas de Programación Lineal las variables están

acotadas, en algunos casos esto se debe a una disponibilidad limitada de recursos, en

otros casos por cuestiones tácticas o políticas se acotan las variables y en otros, como en

el caso de las dietas, es muy natural que se tengan restricciones de mínimo y máximo en
los nutrientes, las cuales dan origen a variables de holgura con cotas superiores e

inferiores.

Se presenta la forma general de los problemas con variables acotadas y como se

resuelven de tal forma que no se incremente significativamente el número de variables.

Para esto presentamos los aspectos principales como lo son: la definición de solución

básica factible, el criterio de optimalidad y no acotamiento, el criterio de pivotaje y la

actualización.

La forma general de un PPL con variables acotadas es:

Min Z = Ct X

Sujeto a AX = b

con L≤X≤U

donde las componentes de L y U pueden ser positivos o negativos, incluso ∞o -

∞.

En lo que sigue supondremos que las componentes de L y U son finitas, los

casos de ∞ y -∞ no se tratarán pues el problema a resolver no lo requiere.

El método más directo de manejar las restricciones L ≤ X ≤ U consiste

en introducir vectores de holgura X1 y X2 que hagan:

X + X1 = U y X - X2 = L

Pero esto incrementa el número de restricciones de m a m + 2n y el

número de variables de n a 3n. Lo cual nos indica que usar esta forma sería mucho
esfuerzo computacional. Con la técnica de variables acotadas se mantiene el número de

restricciones y las variables se manejan implícitamente de manera similar como lo hace

el método Simplex normal para mantener las restricciones X ≥ O.

5.3 ALGORITMO DE DESCOMPOSICION

Descomposición de DantzigWolfe Uno de los métodos de resolución de

problemas de programación lineal es el método de Descomposición de DantzigWolfe, es

uno de los favoritos debido a su capacidad de solución de la mayoría de problemas de

Programación Lineal (LP), entre los ejemplos que utilizan este método o se basan en

ello, se encuentran: el uso de la optimización en la gestión financiera, debido a que

bancos y empresas utilizan ampliamente modelos de optimización de cartera para

ofrecer sus servicios financieros, para la solución de problemas de cómo diversificar

adecuadamente la inversión en diferentes clases de activos, tales como acciones, bonos,

bienes raíces y alternativas para cumplir con los pasivos y maximizar los rendimientos

deseados [26]; en la producción del papel, donde existen dos procesos diferentes, el

primero en la producción de la materia prima, es decir el papel en rollos; y la segunda,

en cortar estos rollos en otros de menor tamaño de acuerdo a los requisitos del cliente,

sin embargo, ambos procesos se tratarán como al mismo tiempo [27]; en las

telecomunicaciones, específicamente para el funcionamiento de una considerable

cantidad de máquinas simultáneamente, donde se deben sincronizar adecuadamente para

que se pueda almacenar la información de los Figura 1 - Caso típico de Generación

Distribuida propuesto para la Optimización 7 procesos y por otro lado que permita la

distribución de los análisis científicos, como lo es el programa de física El Gran

Colisionador de Hadrones (LHC) de la Organización Europea para la Investigación

Nuclear (CERN) [28]; en sistemas de Distribución, para el control predictivo del modelo

económico de subsistemas dinámicamente desacoplados, en donde el problema de

control óptimo restringido en cada tiempo de muestreo es considerado como un

programa lineal de espacio de estado, límites de entrada, límites de tasa de entrada y

límites de salida flexibles. De esta manera se relaciona la función objetivo del programa

lineal con el costo de operar los subsistemas y el costo de no cumplir con las

restricciones de salida del muestreo [29]; o el mejoramiento del transporte en aerolíneas,

en donde se toma de gran importancia la inclusión de una cuarta dimensión para la

localización de cada avión es más precisa, mejorando significativamente la capacidad de

vuelos y adecuando la gestión del tiempo que tardan en realizar los viajes,

consecuentemente, estableciendo un control más preciso de la maniobrabilidad de los

aviones, minimizando consumo y posteriormente, reduciendo las emisiones

contaminantes [30]. La descomposición de Dantzig-Wolfe es un método de

descomposición basado en el método Simplex, del cual toma su característica primordial

de realizar iteraciones cada vez más ajustadas al valor deseado resultante, con la

añadidura de una columna adicional en el proceso a la cual se denomina generación de

columna [31], dicha columna permitirá evaluar constantemente los nuevos valores

obtenidos hasta lograr el resultado factible, sea de una minimización o de una

maximización.
 El método de Dantzig-Wolfe considera un problema de programación lineal de la

siguiente forma: Minimizar 𝑐 𝑇𝑥 (1) Sujeto a 𝐴𝑥 ≤ 𝑏 (2) 0 ≤ 𝑥 Donde 𝑐 ∈ ℝ𝑛 , 𝑏 ∈ ℝ𝑚,

𝐴 ∈ ℝ𝑚×𝑛 y las inecuaciones 𝐴𝑥 ≤ 𝑏 y 0 ≤ 𝑥, deben ser interpretadas en forma de

componentes. A, b y c son matrices las cuales su estructura dentro del método de

DantzigWolfe se explicará más adelante. Sin embargo, a diferencia del método Simplex,

la matriz A internamente se descompone en un problema maestro y subproblemas; un

problema maestro es aquel que contiene la matriz de coeficientes que involucran a la

mayor parte de las variables de las inecuaciones, mientras que un subproblema es un

conjunto o matriz reducida que contiene a un sistema de ecuaciones con el mismo

número de incógnitas o variables de permitan la reestructuración del problema [32],

[33]. La matriz A junto con la matriz b resulta ser un sistema de ecuaciones de primer

orden donde cada ecuación de A será cada valor de b, sin embargo, cuando es extenso el

número de variables dentro de este sistema de ecuaciones, los métodos tradicionales se

tornan más complejos; es así como el método de 8 descomposición de Dantzig-Wolfe

optimiza dividiendo este sistema de ecuaciones en otros sistemas más manejables, por lo

que al final, estos valores iterarán hasta converger en una solución. La función objetivo

se describe en la función 1, es la que contiene las variables a optimizar (minimización o

maximización), y la ecuación 2 representa al conjunto de todas las ecuaciones de

condición y restricción que contenga el sistema, permitiendo la solución a la función

objetivo

De forma generalizada, un problema de programación lineal que contenga un

extenso número de variables definido como: mín 𝑧 = (𝑐 1) 𝑇 . 𝑥 1 + (𝑐 2) 𝑇 . 𝑥 2 + ⋯ +

…𝐾) 𝑇 . 𝑥 𝐾 Sujeto a las condiciones y restricciones siguientes: s.a 𝐿1. 𝑥 1 + 𝐿2. 𝑥 2 +

⋯ + 𝐿𝐾. 𝑥 𝐾 ≤ 𝑏 0 𝐴1. 𝑥 1 ≤ 𝑏 1 𝐴2. 𝑥 2 ≤ 𝑏 2 ⋱ ⋮ ⋮ 𝐴𝐾. 𝑥 𝐾 ≤ 𝑏 𝐾 𝑥 1 ≥ 0 𝑥 2 ≥ 0 ⋯ 𝑥 𝐾

≥ 0 Donde: 𝐾: es el número de subproblemas 𝐿𝐾: son los submatrices del problema

maestro dependientes de 𝐾 𝑐 𝐾: son los coeficientes de la función objetivo 𝑧 𝑏 𝐾: son los

valores delimitadores de las condiciones y restricciones del problema [34], [35].

 6. DUALIDAD

La dualidad es una idea clave en la investigación de operaciones que describe la

conexión entre un problema primario y su problema dual correspondiente. La capacidad

de resolver problemas de optimización utilizando la programación lineal, un método

ampliamente utilizado en la investigación de operaciones, depende de la dualidad.

El desafío principal en la programación lineal es maximizar o minimizar una

función objetivo teniendo en cuenta una serie de restricciones lineales. La maximización

o minimización de una función objetivo alternativa bajo un conjunto de restricciones

duales es parte del problema dual, que se deriva del problema primal.

Según la relación entre dualidad y problemas primales, todo problema dual tiene

un problema primal equivalente. El valor óptimo del problema dual también es igual al

valor óptimo del problema primario, según la dualidad. En otras palabras, una vez que se

resuelve uno de los problemas, la solución ideal del otro problema sigue su ejemplo.
 Las aplicaciones prácticas de la dualidad son sustanciales. La solución al

problema dual puede, por un lado, revelar más detalles sobre el problema primario,

como los intervalos de sensibilidad de las variables o las tasas marginales de

transformación. Por otro lado, la dualidad permite obtener cotas superior e inferior para

el valor óptimo del problema primal, lo que puede ser útil para evaluar la efectividad de

la solución descubierta.

El concepto de dualidad de la investigación de operaciones, que ofrece más detalles y

resultados prácticos para la optimización de problemas, es básicamente la relación entre
un problema primario y su problema dual correspondiente.
7.DEFINICION MATRICIAL DEL PROBLEMA DUAL
la dualidad es un concepto importante que se refiere a la relación entre un problema de

optimización primaria y su correspondiente problema de optimización dual. La

definición matricial del problema de dualidad se basa en el uso de matrices y vectores.

Consideremos un problema de optimización primaria general en forma estándar:

Minimizar: c^T x Sujeto a: Ax = b x >= 0

Dónde:

c es un vector columna de coeficientes de la función objetivo.

x es un vector columna de variables de decisión.

A es una matriz de restricciones.

b es un vector columna de términos constantes.

El problema de dualidad se define como:

Maximizar: b^T y Sujeto a: A^T y <= c y >= 0

Dónde:
y es un vector columna de variables duales.

En la formulación matricial, la matriz A^T es la traspuesta de la matriz A. El vector y es

el vector de variables duales correspondiente al problema dual.

La formulación matricial del problema dualidad permite expresar de manera más

compacta las condiciones de dualidad y las relaciones entre los problemas primal y dual.

7.1SOLUCIO OPTIMA DUAL

La solución óptima del problema de dualidad se obtiene al encontrar los valores óptimos

de las variables duales y verificar las condiciones de optimalidad dual. A continuación,

se presenta un proceso general para encontrar la solución óptima del problema de

dualidad:

Resolver el problema primario: Primero, resuelve el problema primario utilizando

cualquier método de optimización adecuado para obtener la solución óptima del

primario. Esto implica encontrar los valores óptimos de las variables de decisión,

denotados como x*.

Construir la función objetivo dual: Utilizando la solución óptima x* obtenida del paso

anterior, construye la función objetivo dual, que se define como:

Maximizar: b^T y Sujeto a: A^T y <= c y >= 0

Donde b es el vector de constantes de las restricciones del primario yc es el vector de

coeficientes de la función del objetivo primario.

Resolver el problema dual: Resuelve el problema dual utilizando un método de

optimización adecuado para encontrar la solución óptima del dual. Esto implica

encontrar los valores óptimos de las variables duales, denotados como y*.

Verificar las condiciones de optimidad dual: Una vez que se ha obtenido la solución

óptima y*, se deben verificar las condiciones de optimidad dual para asegurar que la

solución sea realmente óptima. Estas condiciones pueden variar dependiendo del

problema específico, pero generalmente incluyen:

Condición de factibilidad dual: A^T y* <= c (restricciones duales deben ser factibles).

Condición de optimalidad dual: b^T y* = c^T x* (el valor óptimo del dual es igual al

valor óptimo del primal).

Si todas las condiciones de optimalidad dual se cumplen, entonces se ha encontrado la

solución óptima del problema dual. Las variables duales óptimas proporcionan

información sobre los precios relativos o las sombras de las restricciones del primal, y

pueden tener interpretaciones económicas o de otro tipo dependiendo del contexto del

problema.

8. PROGRAMACIÓN LINEAL PARAMÉTRICA

El análisis de sensibilidad requiere el cambio de un parámetro a la vez en el

modelo original para examinar su efecto sobre la solución óptima. Por el contrario, la

programación lineal paramétrica (o programación paramétrica en forma más corta) se

refiere al estudio sistemático de los cambios en la solución óptima cuando cambia el

valor de muchos parámetros al mismo tiempo, dentro de un intervalo. Este estudio

proporciona una extensión muy útil al análisis de sensibilidad; por ejemplo, se puede
verificar el efecto de cambios simultáneos en parámetros "correlacionados", causados

por factores exógenos tales como el estado de la economía. sin embargo, una aplicación

más importante es la investigación de los trueques entre los valores de los parámetros.

por ejemplo, si los valores de cj representan la ganancia unitaria de las actividades

respectivas, es posible aumentar el valor de alguna cj a costa de disminuir el de otras

mediante un intercambio apropiado de personal y equipo entre las actividades. De

manera parecida, si los valores de bi representan las cantidades disponibles de los

respectivos recursos, es imposible aumentar alguna bi si se está de acuerdo en disminuir

algunas otras.

En algunos casos, el propósito del estudio es determinar el trueque más apropiado entre

dos factores básicos como costos y beneficios. la forma usual de hacerlo es expresar uno

de estos factores en función objetivo (como minimizar el costo total) e incorporar el otro

a las restricciones (por ejemplo, beneficio >= nivel mínimo aceptable).

La técnica algorítmica para programación lineal paramétrica es una extensión natural del

análisis de sensibilidad, por lo que también está basada en el método simplex.

8.1 CAMBIOS PARAMETRICOS EN “C”

Programación lineal paramétrica, el análisis de sensibilidad requiere el cambio

de un parámetro a la vez en el modelo original para examinar su efecto sobre la solución

óptima. Por el contrario, la programación lineal paramétrica (o programación

paramétrica en forma más corta) se refiere al estudio sistemático de los cambios en la

solución óptima cuando cambia el valor de muchos parámetros al mismo tiempo, dentro

de un intervalo.

8.2 CAMBIOS PARAMETRICOS EN “B”

Programación lineal paramétrica, el análisis de sensibilidad requiere el cambio de

un parámetro a la vez en el modelo original para examinar su efecto sobre la solución

óptima. Por el contrario, la programación lineal paramétrica (o programación

paramétrica en forma más corta) se refiere al estudio sistemático de los cambios en la

solución óptima cuando cambia el valor de muchos parámetros al mismo tiempo, dentro

de un intervalo.

Por cambios paramétricos en B se puede entender: que son los cambios continuos

en el vector de Disponibilidades “B” y por cambios paramétricos en “C” se entiende que

son cambios continuos en el vector de Costos” C”.