Resolución Gráfica en Programación Lineal

Un modelo de Programación Lineal consiste en aquel donde la función objetivo y restricciones son funciones lineales de las variables de decisión. Se consideran como supuestos básicos la linealidad del modelo, la certeza en el conocimiento de los parámetros (modelos deterministas), además que las variables de decisión adoptan valores reales no negativos. A continuación se presenta un sencillo ejemplo introductorio de un modelo de Programación Lineal obtenido de N. Pendegraft (1997). Lego of my Simplex. ORMS Today,Vol. 24, No.1, pp 8.

Considere que se dispone de determinadas piezas para la elaboración de dos productos finales. Se dispone de 8 piezas pequeñas y 6 piezas grandes. Estas piezas son utilizadas para elaborar sillas (usando 2 piezas pequeñas y 1 pieza grande) y mesas (usando 2 piezas de cada tipo).

sillas-y-mesas

Interesa decidir cuántas sillas y mesas fabricar de modo de obtener la máxima utilidad, dado un beneficio neto de $10 por cada silla y de $16 por cada mesa fabricada. Para abordar el problema anterior, se requiere definir lo siguiente:

Variables de Decisión: (Lo que el modelo busca responder)

X: Número de Sillas a elaborar
Y: Número de Mesas a elaborar

Función Objetivo: (Criterio para seleccionar entre alternativas factibles)

Maximizar 10*X+6*Y

Restricciones: (Condiciones que definen los recursos del modelo)

Disponibilidad de Piezas Pequeñas:      2*X + 2*Y ≤ 8
Disponibilidad de Piezas Grandes:        1*X + 2*Y ≤ 6
No Negatividad:                                         X≥0   Y≥0

En consecuencia, el modelo queda definido de la siguiente forma:

modelo-sillas-y-mesas

Las distintas combinaciones de valores que pueden adoptar las variables de decisión que satisfacen en forma simultánea el conjunto de restricciones, definen el dominio o región de puntos factibles, el cual se demarca con color verde en el siguiente gráfico:

solucion-grafica-sillas-y-m

Cabe destacar que un modelo de Programación Lineal que admita solución, ésta se encuentra en un vértice o frontera del dominio de puntos factibles. Luego, se puede evaluar cada uno de los vértices (A, B, C o D en nuestro ejemplo) y ver cuál es el que maximiza el valor de la función objetivo, sin embargo, esta estrategia queda delimitada naturalmente a modelos de menor tamaño.

Una forma más eficiente de resolución consiste en graficar las distintas curvas de nivel asociadas a la función objetivo. En un problema de maximización la dirección del máximo crecimiento se alcanza desplazando las curvas de nivel en la dirección del gradiente de la función objetivo que esta dado por el vector \triangledown f(X,Y)=(10,16).

Al desplazar las curvas de nivel en la dirección del gradiente de la función objetivo, el último punto donde interceptan éstas al dominio de puntos factibles es el punto (X,Y)=(2,2) el cual corresponde a la solución óptima del problema, con valor óptimo asociado igual a 52.

2-sillas-y-2-mesas

Análisis de Sensibilidad

Una vez resuelto el modelo original, interesa saber qué sucede frente a cambios que se produzcan en los parámetros del modelo, sin que esto involucre resolver el modelo nuevamente. En este sentido, para un modelo que considera 2 variables, el análisis gráfico es una herramienta que nos permite realizar este tipo de análisis.

Cambio en los Coeficientes de la Función Objetivo

Se busca encontrar un intervalo de variación para los coeficientes de la función objetivo que garantice que la actual solución siga siendo la óptima.

En nuestro ejemplo, esto implica que la pendiente de las curvas de nivel (función objetivo) se encuentre en el intervalo que define las actuales restricciones activas, es decir, aquellas restricciones que se cumplen en igualdad. El óptimo actual (X,Y)=(2,2) nos indica que las restricciones 1 y 2 (disponibilidad de piezas pequeñas y grandes, respectivamente) se cumplen en igualdad, es decir, al evaluar la solución en el lado izquierdo de la inecuación, ésta coincide con el lado derecho o disponibilidad de recursos (lo que equivale a que no exista «holgura» o recursos ociosos).

Por simple álgebra se puede obtener que las pendientes de las restricciones 1 y 2 son -1 y -1/2 respectivamente.

Adicionalmente, la pendiente de las curvas de nivel queda definida por:

C1*X + C2*Y = K        (K Constante, C1 y C2: Coeficientes que acompañan a X e Y en la Función Objetivo)
C2*Y = -C1*X + K
Y = (-C1/C2)*X + K/C2    (Con C2 distinto de 0)

En consecuencia, la pendiente de las curvas de nivel es: -C1/C2

Si la pendiente de las curvas de nivel varía en el intervalo entre -1 y -1/2, esto garantiza que el modelo de programación lineal mantendrá la actual solución óptima:

– 1 <= -C1/C2 <= -1/2                (Se multiplica por -1)
1 >= C1/C2 >=1/2

Para obtener un intervalo de variación para C1 que mantenga la actual solución, mantenemos fijo el actual valor de C2 y despejamos:

1 >= C1/16 >= 1/2
16 >= C1 >= 8

Para obtener un intervalo de variación para C2 que mantenga la actual solución, mantenemos fijo el actual valor de C1 y despejamos:

1 >= 10/C2 >= 1/2
20 >= C2 >= 10

Notar que en los extremos de éstos intervalos se agregan nuevas soluciones al problema que comparten el mismo valor óptimo y que contienen a la original solución óptima (X,Y)=(2,2). Cuando sucede esta situación se dice que el problema tiene infinitas soluciones óptimas.

Cambio en el «Lado Derecho» de las Restricciones

Lo que se busca responder es cuál es la variación en el actual valor óptimo de la función objetivo si cambiamos en una unidad algún coeficiente del lado derecho de las restricciones.

Resulta natural que si una restricción no se encuentra activa en el óptimo, es decir, no se cumple en igualdad, un aumento del lado derecho no traerá consigo un aumento del valor óptimo ya que si antes habían recursos ociosos, bajo este nuevo escenario se mantendrá la situación. Por tanto, resulta lógico esperar que se produzcan cambios en el valor óptimo cuando la modificación del lado derecho esta asociado a una restricción activa.

En nuestro ejemplo, si consideramos la restricción 1 (activa) lo que debemos hacer es hacer desplazamientos paralelos de esta restricción en dirección de aumento y decrecimiento, preservando la geometría del problema, esto es, que se conserven las mismas restricciones activas de la solución óptima inicial.

Para la Restricción 1:

  • El máximo desplazamiento se alcanza en el punto (X,Y)=(6,0)
  • El mínimo desplazamiento se alcanza en el punto (X,Y)=(0,3)

Al evaluar el máximo y mínimo desplazamiento en la restricción 1 se obtiene:

R1(Max): 2*(6) + 2*(0) = 12
R1(Min): 2*(0) + 2*(3) = 6

Al evaluar el máximo y mínimo desplazamiento en la función objetivo se obtiene:

Z(Max): 10*(6) + 16*(0) = 60
Z(Min): 10*(0) + 16*(3) = 48

El precio sombra de la restricción 1 se obtiene reemplazando los valores en la siguiente fórmula:

P1 = ( Z(Max) – Z(Min) ) / ( R1(Max) – R1(Min) )
P1 = ( 60 – 48 ) / ( 12 – 6 ) = 12 / 6
P1 = 2

El Precio Sombra de la restricción 1 es igual a 2, el cual es válido siempre y cuando el lado derecho de dicha restricción varíe entre 6 y 12

Por ejemplo, si el lado derecho aumenta de 8 a 10 (aumento que esta contenido en el intervalo válido de variación) el nuevo valor óptimo será 52 + P1*(10-8) = 52 + 2*2 = 56.

Se propone al lector calcular el Precio Sombra de la restricción 2, el cual es igual a 6, cuando el lado derecho varíe entre 4 y 8.

MaloRegularBuenoMuy BuenoExcelente (2 Votos, Promedio: 4,50 de un máximo de 5)
Cargando…

, , , ,

Sin Comentarios aun.

Comparte tus Comentarios!