Bienvenido a ProgramaciónLineal.net un sitio enfocado exclusivamente a los contenidos de esta importante área de la Investigación de Operaciones. Se busca presentar los contenidos de una forma simple y didáctica, que permita al estudiante complementar su estudio formal de esta disciplina. Invitamos a los usuarios a plantear sus consultas y comentarios escribiendo a info@programacionlineal.net
SEP
2018
Resolución Gráfica
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 tiene infinitas soluciones óptimas.
2. Variación en los lados derechos de las restricciones (cálculo del "precio sombra"): Una pregunta común en el análisis de sensibilidad resulta ver el impacto que tiene en el valor óptimo una variación marginal del lado derecho de alguna de sus restricciones (tanto aumento o decrecimiento). El impacto en el valor óptimo por unidad de variación del lado derecho de una restricción (manteniendo el resto constante) es el precio sombra asociado a dicha restricción. En nuestro ejemplo, considere que el lado derecho de la restricción 1 (actualmente b1=10) corresponde a un recurso escaso (ejemplo: horas hombre, dinero, tiempo, etc). Si sabemos que el actual valor óptimo V(P)=52, quisieramos saber por ejemplo, cuánto aumentaría el valor óptimo se dispusiéramos de una unidad adicional del recurso escaso (es decir, pasando a b1*=11). En forma equivalente frecuentemente se plantea esta inquietud como ¿Cuánto es lo máximo que se estaría dispuesto a pagar por unidad adicional del recurso asociado a la primera restricción?. Este valor corresponde al precio sombra.
Precio Sombra Restricción 1: Primero se considera el desplazamiento paralelo de la Restricción 1 (tanto en el sentido de crecimiento o decrecimiento del lado derecho), de modo que la Solución Óptima se siga encontrando con las actuales restricciones activas (en nuestro caso R1 y R2). Por ejemplo, desplazando R1 en la dirección de su decrecimiento, el último punto donde se intersecta R1 con R2 sería en el par ordenado (X,Y)=(0,8). Se propone al usuario el cálculo de la máxima variación para R1 que se produce en (X,Y)=(8,0).
En consecuencia, el Precio Sombra asociado a la Restricción 1 queda dado por:
Un Precio Sombra igual a 2 indica por ejemplo que si el lado derecho aumenta en 1 unidad, el beneficio adicional (incremento en el Valor Óptimo) es de 2 unidades. Adicionalmente, una pregunta frecuente resulta en identificar el intervalo de variación donde el precio sombra calculado es válido. El máximo valor al que puede adoptar el lado derecho de R1 es b1*, de modo que la nueva solución se siga encontrando con R1 y R2 activas. El valor de b1* se obtiene al evaluar (X,Y)=(8,0) en la Restricción 1: 2*(8) + 1*(0)=16. Siguiendo similar razonamiento el mínimo valor que puede alcanzar el lado derecho de R1 es b1, que evaluado en (X,Y)=(0,8) en R1 se obtiene: 2*(0) + 1*(8)=8.
Se recomienda al usuario hacer el cálculo del Precio Sombra para la Restricción 2, el cual corresponde a 2. Si desea consultar un nuevo ejemplo ingrese a Resolución Gráfica en Programación Lineal. (Sitio: Investigación Operativa)
ANÁLISIS DE SENSIBILIDAD GRÁFICO PARA 3 RESTRICCIONES
La metodología y conceptos presentados para el caso de 2 restricciones no difiere, sin embargo, hay que tener especial cuidado cómo la inclusión de una tercera restricción afecta el análisis. Veamos el siguiente ejemplo:
- P) MAX 4X + 3Y
- S.A. 6X + 2Y <= 120
- ...... .1X + 4Y <= 100
- ........5X + 5Y <= 150
- ..... ..X>= 0, Y>= 0
La resolución gráfica de este ejemplo permite obtener la solución óptima X=15, Y=15 con valor óptimo V(P)=105, tal como se observa en el gráfico a continuación:
Antes de proceder con el análisis de sensibilidad es conveniente verificar si las actuales restricciones del problema estan activas en el óptimo, es decir, si se cumplen en igualdad:
- R1: 6*(15) + 2*(15) = 120 => R1 es una restricción activa
- R2: 1*(15) + 4*(15) < 100 => R2 no es una restricción activa
- R3: 5*(15) + 5*(15) = 150 => R3 es una restricción activa
En el caso que el lado derecho de la restricción sea un recurso, resulta lógico tener una disposición a pagar por unidad adicional en la medida que dicho recurso se este ocupando a máxima capacidad. En consecuencia, una restricción no activa tiene por definición un precio sombra igual a cero (caso de R2) ya que un aumento del lado derecho no aumentará el valor óptimo actual V(P)=150. Sin embargo, sólo en casos muy particulares podemos encontrar restricciones activas con precio sombra (o costo reducido) igual a cero, lo que es más la excepción que la regla.
Luego de esta introducción veamos el cálculo del precio sombra o costo reducido para la restricción 1 (R1). Primero, debemos desplazar en forma paralela la restricción 1 hasta el punto máximo donde la solución óptima se siga encontrando con las actuales restricciones activas R1 y R3. Dicho punto es (X,Y)=(30,0). Posteriormente, desplazamos en forma paralela la restricción 1 (R1) hasta el punto mínimo donde la solución óptima se siga encontrando con las actuales restricciones activas R1 y R3. Nótese que este desplazamiento queda acotado hasta el punto donde la restricción 2 (R2) se vuelve activa, que corresponde al punto (X,Y)=(6,666, 23,333) como se muestra en la siguiente gráfica:
Por consiguiente, el precio sombra asociado a la restricción 1 queda dado por:
Siguiendo un procedimiento similar se pueden obtener los precios sombras asociadas a las restantes restricciones. A continuación se presenta una tabla resumen del análisis de sensibilidad obtenido con Solver de Excel:
NUESTROS REFERIDOS
A continuación se presenta un compendio de Links de Interés para el usuario.
DUALIDAD EN PROGRAMACIÓN LINEAL
El problema Dual de un problema de Programación Lineal, corresponde a una formulación alternativa que nos permite conseguir similares resultados de los que obtendríamos al resolver directamente el problema original o primal.
Esta formulación dual nos permite rescatar la solución del problema primal, luego es una alternativa eficiente de usar a nuestro juicio cuando el esfuerzo en identificar el problema dual y resolverlo es menor a resolver directamente el problema primal.
La bibliográfia nos provee los fundamentos teóricos y prácticos en la utilización de la dualidad en Programación Lineal y básicamente componen un capítulo o aparto especial en los libros de introducción a la Investigación de Operaciones como Hiller y Libermann.
En términos matriciales la relación entre el problema primal y dual de un modelo de Programación Lineal se resume por:
Uno de los resultados teóricos más importantes al respecto es el que nos entrega el Teorema de Dualidad Fuerte.
Si x* = (x1*, x2*, ..., xn*)T, es una solución óptima problema primal P), entonces el problema dual D) tiene solución óptima p* = (p1*, p2*, ..., pm*)T que satisface:
Además, si P) es no acotado, entonces D) es infactible.
Si D) es no acotado, entonces P) es infactible. Para una revisión detallada de la teoría de dualidad se recomienda visitar Dualidad en Programación Lineal.
EJEMPLO:
Considere el siguiente problema de Programación Lineal. Luego formule su problema dual y mediante su resolución obtenga la solución y valor óptimo de P).
- P) MAX 10X + 16Y
- S.A. 2X + 2Y <= 8
- ...... .1X + 2Y <= 6
- ..... ..X>= 0, Y>= 0
Siguiendo la notación y resultados anteriores podemos identificar:
1. Dado que P) es de Max, D) será de Min.
2. El vector de "lados derechos" de P) será el vector de los coeficientes de la función objetivo de D).
3. Los coeficientes de la función objetivo de P) serán los lados derechos de D).
4. Restricciones del tipo "<=" en el primal de Maximización definen variables ">=0" en el dual de Minimización.
5. Variables ">=0" en el primal de Maximización definen restricciones ">=" en el dual de Minimización.
En consecuencia, el modelo dual de P) sería:
- D) MIN 8X + 6Y
- S.A. 2X + Y >= 10
- ...... .2X + 2Y >= 16
- ..... ..X>= 0, Y>= 0
Con Solución Óptima X=2, Y=6 y Valor Óptimo V(P)=52. Luego, por el Teorema de Dualidad Fuerte V(P)=V(D)=52. La Solución Óptima de P) corresponderá a los Precios Sombra de las restricciones 1 y 2 respectivamente en el Dual (en ambos casos es igual a 2). Finalmente, la Solución Óptima del primal es X=2 e Y=2.
Sugerencia: Verifique utilizando el Método Simplex que los costos reducidos asociados a las variables de holgura de las restricciones 1 y 2 de P) corresponde a las variables duales óptimas en D)
PREGUNTAS FRECUENTES DUALIDAD (FAQ)
1. ¿Qué se obtiene al definir el dual de un problema dual?
R: El dual de un problema dual resulta ser el problema primal o uno equivalente a este.
2. Si se resuelve directamente el problema primal y se verifica que una de las restricciones no esta activa en el óptimo, ¿Qué implicancias tiene esto en el modelo primal?
R: El Teorema de Holguras Complementarias nos señala que de verificarse esta situación, la variable primal asociada a la restricción dual no activa vale cero en el óptimo.
3. Si resuelvo el problema primal directamente, ¿Dónde puedo obtener las variables duales óptimas?
R: Hay varias opciones que difieren en su complejidad y conveniencia de aplicación según sea el caso. Por ejemplo, al obtener gráficamente el precio sombra asociado a una restricción (primal), dicho valor corresponde al valor de la variable dual asociada a dicha restricción. Ahora si utilizamos el Método Simplex, podemos rescatar las variables duales óptimas observando los costos reducidos o precios sombra asociados a las variables de holgura en el caso de un problema primal de maximización.
Ejemplo: Tabla Final del Simplex para el ejemplo de 3 restricciones:
X1 |
X2 |
S1 |
S2 |
S3 |
|
1 |
0 |
1/4 |
0 |
-1/10 |
15 |
0 |
0 |
3/4 |
1 |
-11/10 |
25 |
0 |
1 |
-1/4 |
0 |
3/10 |
15 |
0 |
0 |
1/4 |
0 |
1/2 |
105 |
Comparte tus consultas y sugerencias.
Ingresa a nuestro Formulario de Contacto