CASOS ESPECIALES DE SIMPLEX: SOLUCIONES NO ACOTADAS

METODO SIMPLEX

El Método Simplex publicado por George Dantzig en 1947 consiste en un algoritmo iterativo que secuencialmente a través de iteraciones se va aproximando al óptimo del problema de Programación Lineal en caso de existir esta última.

La primera implementación computacional del Método Simplex es el ano 1952 para un problema de 71 variables y 48 ecuaciones. Su resolución tarda 18 horas. Luego, en 1956, un código llamado RSLP1, implementado en un IBM con 4Kb en RAM, admite la resolución de modelos con 255 restricciones.

El Método Simplex hace uso de la propiedad de que la solución óptima de un problema de Programación Lineal se encuentra en un vértice o frontera del dominio de puntos factibles (esto último en casos muy especiales), por lo cual, la búsqueda secuencial del algoritmo se basa en la evaluación progresiva de estos vértices hasta encontrar el óptimo. Cabe destacar que para aplicar el Método Simplex a un modelo lineal, este debe estar en un formato especial conocido como formato estándar el cual definiremos a continuación.

FORMA ESTÁNDAR DE UN MODELO DE PROGRAMACIÓN LINEAL

Consideremos un modelo de Programación Lineal en su forma estandar, que denotaremos en lo que sigue por:

• Min          c1x1  + c2x2  + ... + cnxn
• sa            a11x1 + a12x2 + ... + a1nxn = b1
•                 a21x1 + a22x2 + ... + a2nxn = b2
•                 ...          ...                  ...
•                 am1x1 + am2x2 + ... + amnxn = bm
•                 xi >=  0,   i = 1, 2, ..., n    y    m <= n
• 
  
Matricialmente escrito como:
Min    cTx 
s.a      Ax = b 
           x >=  0
No existe pérdida de generalidad en asumir que un modelo de PL viene dado en su forma estándar:

• EJEMPLO
• P)            Max        9u + 2v + 5z
•                 sa            4u + 3v + 6z <=  50
•                                 u + 2v - 3z >=  8
•                                2u - 4v + z = 5
•                                u,v >=  0
•                                z e IR

1. Siempre es posible llevar un problema de maximización a uno de minimización. Si f(x) es la función objetivo a maximizar yx* es la solución óptima f(x*) >= f(x), para todo x factible. -f(x*) <= - f(x), para todo x factible. En consecuencia: x* es también mínimo de  -f(x)
2. Cada restricción del tipo <= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de holgurano negativa, con coeficiente nulo en la función objetivo.
3. Cada restricción del tipo >= puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa, con coeficiente nulo en la función objetivo.
4. Siempre es posible escribir una variable libre de signo como la diferencia de dos variables no negativas.

Considerando la siguiente notación: u = x1, v = x2, z = x3 - x4, s1 = x5 (holgura), s2 = x6 (exceso), el problema P) puede ser escrito en forma equivalente como:

• Min         - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6
• sa:              4x1 + 3x2 + 6x3 - 6x4 +    x5          = 50
•                      x1 + 2x2 - 3x3 + 3x4             - x6  =  8
•                    2x1 - 4x2 +  x3   -   x4                     =  5
•                    xi >=  0,    i=1,2,3,4,5,6.  

RESOLUCION GRAFICA

El análisis gráfico es una alternativa eficiente para enfrentar la resolución de modelos de Programación Lineal en 2 variables, donde el dominio de puntos factibles (en caso de existir) se encontrará en el primer cuadrante, como producto de la intersección de las distintas restricciones del problema lineal.

Una de las propiedades básicas de un modelo de Programación Lineal que admite solución, es que ésta se encontrará en el vértice o frontera (tramo) del dominio de puntos factibles. Es decir, si luego de gráficar el dominio y evaluar los distintos vértices de modo de elegir "el mejor" candidato según sea nuestro caso (el valor de la función objetivo será la que nos permitirá discriminar cual es el mejor candidato dependiendo si estamos maximizando o minimizando).

Consideremos un Ejemplo Introductorio en 2 variables:

• D) MIN 8X + 6Y
• S.A. 2X + Y >= 10
• ...... .2X + 2Y >= 16
• ..... ..X>= 0, Y>= 0

Comentario: Nótese que corresponde al Problema Dual de P) cuya resolución se presenta en nuestro sitio como ejemplo introductorio en la utilización de Solver de MS Excel. Para ver el detalle de la resolución gráfica de P) se recomienda al usuario ingresar AQUI.

Para resolver el problema D) graficamos el dominio de puntos factibles y las curvas de nivel asociadas a la función objetivo:

El área achurada en color verde representa el dominio de puntos factibles del problema D), es decir, son las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen las restricciones del problema. Cabe destacar que esto corresponde a un dominio no acotado, lo que no implica que el problema no tenga solución.

Por otra parte sabemos que el óptimo de un problema lineal se encuentra en un vértice o frontera del dominio de puntos factibles. En este caso tenemos 3 vértices candidatos al óptimo los cuales se señalan con flecha blanca y azul. El vértice (X,Y)= (0,10) con V(P)=60; (X,Y)=(2,6) con V(P)=52 y (X,Y)=(8,0) con V(P)=64. El mínimo valor para la función objetivo se alcanza en (X,Y)=(2,6) con V(P)=52, el cual resulta ser la Solución Óptima de D). Sin embargo, una forma más eficiente para obtener el óptimo que no implique evaluar cada vértice en la función objetivo, es desplazando las curvas de nivel de la función objetivo en la dirección del máximo decrecimiento (en el caso de un problema de minimización). Para un problema de minimización, el mayor decrecimiento se alcanza en la dirección del vector " - Gradiente F(X,Y)", en nuestro caso el vector con dirección (-8,-6) (dirección representada por flecha roja). Luego, el óptimo se alcanza en el último punto donde las curvas de nivel intersectan al dominio de puntos factibles en la dirección del máximo decrecimiento, cuya solución obviamente corresponde a (X,Y)=(2,6) con V(P)=52.

ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 2 RESTRICCIONES

Una vez resuelto un modelo de Programación Lineal resulta útil hacer un análisis de sensibilidad que permita identificar cómo afecta en los resultados del problema variaciaciones en los parametros de éste, sin que esto pase por resolver el problema nuevamente. Nuestro sitio considera una sección aparte llamada "Sensibilidad" cuyos resultados principales se pueden consultar AQUI.

1. Variación en los Coeficientes de la Función Objetivo: La pregunta que buscamos responder es cuál es el intervalo de variación para los coeficientes de la función objetivo (cada coeficiente se analiza por separado) que mantiene la actual Solución Óptima.

Un primer acercamiento es considerar las pendientes de las restricciones activas en el óptimo, es decir, aquellas restricciones que se cumplen en igualdad (en nuestro caso restricción 1 y 2). La restricción 1 (2X + Y >=10) tiene pendiente -2. La restricción 2 (2X + 2Y >=16) tiene pendiente -1. Por otra parte la pendiente de la función objetivo dado C1=8 y C2=6 es -4/3.

En consecuencia, se mantiene la actual Solución Óptima si la pendiente de la función objetivo (curvas de nivel) varían en el intervalo de las pendientes de las actuales restricciones activas. Esto es:

-2 <= -C1/C2 <= -1 (Multiplicamos por -1)

2 >= C1/C2 >= 1

Si fijamos C2=6.

2 >= C1/6 >= 1

12 >= C1 >= 6 (Garantiza la actual Solución Óptima con C2 fijo)

Si fijamos C1=8.

2 >= 8/C2 >= 1

8 >= C2 >= 4 (Garantiza la actual Solución Óptima con C1 fijo)

Nótese que en los extremos de los intervalos además de incluir la actual Solución Óptima se consideran nuevas combinaciones del dominio que mantienen el Valor Óptimo y también son Solución Óptima de D). Esta situación determina que el problema tieneinfinitas soluciones óptimas.

APLICACIONES DE PROGRAMACION LINEAL

1. Problema de la Dieta: (Stigler, 1945). Consiste en determinar una dieta de manera eficiente, a partir de un conjunto dado de alimentos, de modo de satisfacer requerimientos nutricionales. La cantidad de alimentos a considerar, sus características nutricionales y los costos de éstos, permiten obtener diferentes variantes de este tipo de modelos. Por ejemplo:

	Leche (lt)	Legumbre (1 porción)	Naranjas (unidad)	Requerimientos Nutricionales
Niacina	3,2	4,9	0,8	13
Tiamina	1,12	1,3	0,19	15
Vitamina C	32	0	93	45
Costo	2	0,2	0,25

Variables de Decisión:

• X1: Litros de Leche utilizados en la Dieta
• X2: Porciones de Legumbres utilizadas en la Dieta
• X3: Unidades de Naranjas utilizadas en la Dieta

Función Objetivo: (Minimizar los Costos de la Dieta) Min 2X1 + 0,2X2 + 0,25X3

Restricciones: Satisfacer los requerimientos nutricionales

• Niacina: 3,2X1 + 4,9X2 + 0,8X3 >= 13
• Tiamina: 1,12X1 + 1,3X2 + 0,19X3 >=15
• Vitamina C: 32X1 + 0X2 + 93X3 >= 45
• No Negatividad: X1>=0; X2>=0; X3>=0

Compruebe utilizando nuestro Módulo de Resolución que la solución Óptima es X1=0, X2=11,4677, X3=0,483871, con Valor Óptimo V(P)=2,4145.

2. Problema de Dimensionamiento de Lotes: (Wagner y Whitin, 1958). Consiste en hallar una polìtica óptima de producción para satisfacer demandas fluctuantes en el tiempo, de modo de minimizar los costos de producción e inventario, considerando la disponibilidad de recursos escasos.

Considere que una fabrica puede elaborar hasta 150 unidades en cada uno de los 4 periodos en que se ha subdividido el horizonte de planificación y se tiene adicionalmente la siguiente información:

Periodos	Demandas (unidades)	Costo Prod. (US$/unidad)	Costo de Inventario (US$/unidad)
1	130	6	2
2	80	4	1
3	125	8	2.5
4	195	9	3

Adicionalmente considere que se dispone de un Inventario Inicial de 15 unidades y no se acepta demanda pendiente o faltante, es decir, se debe satisfacer toda la demanda del período.

Variables de Decisión:

• Xt: Unidades elaboradas en el período t (Con t =1,2,3,4)
• It: Unidades en inventario al final del período t (Con t =1,2,3,4)

Función Objetivo: (Minimizar los Costos de Producción e Inventarios) Min 6X1 + 4X2 + 8X3 + 9X4 + 2I1 + 1I2 + 2,5I3+ 3I4

Restricciones:

• Capacidad de Producción por Período: Xt <= 150 (Con t =1,2,3,4)
• Satisfacer Demanda Período 1: X1 + I0 - I1 = 130 (I0 = 15)
• Satisfacer Demanda Período 2: X2 + I1 - I2 = 80
• Satisfacer Demanda Período 3: X3 + I2 - I3 = 125
• Satisfacer Demanda Período 4: X4 + I3 - I4 = 195
• No Negatividad: Xt >=0, It >=0

Solución Óptima utilizando Solver de MS Excel (Para ver una aplicación de esta herramienta ingrese AQUI): X1=115,X2=150, X3=100, X4=150, I1=0, I2=70, I3=45, I4=0. Valor Óptimo V(P)=3.622,5

3. Problema de Transporte: (Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).

QUE ES LA PROGRAMACION LINEAL?

La Programación Lineal (PL) es una de las principales ramas de la Investigación Operativa. En esta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión

Los modelos de Programación Lineal por su sencillez son frecuentemente usados para abordar una gran variedad de problemas de naturaleza real en ingeniería y ciencias sociales, lo que ha permitido a empresas y organizaciones importantes beneficios y ahorros asociados a su utilización.

Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.

Los Modelos Matemáticos se dividen básicamente en Modelos Determistas (MD) oModelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Determistas.