5.
DUALIDAD Y SENSIBILIDAD
“La economía consiste en saber gastar y el ahorro consiste en saber guardar” Orison Swett Marden
(1848-1924) escritor estadounidense.
Un programa lineal puede asociarse a otro programa lineal equivalente llamado Dual. En este caso
el programa original se le llama Primal.
Muchas veces es más fácil resolver el programa Dual permitiendo posteriormente encontrar la
solución del programa original.
Además, se puede hacer análisis de sensibilidad del Dual que corresponderá a los precios sombra
de las restricciones del Primal.
Aquí primero aprenderemos a encontrar el Dual de un programa lineal
5.1 FORMULACIÓN DEL PROBLEMA DUAL
Duales simétricos
Supongamos un programa lineal no estándar escrito en forma matricial:
min z=CTX
Sujeto a AX≥B
Con:X≥0
El programa Dual es:
máx. z=BTW
Sujeto a ATW≤C
Con W≥0
A las variables w1, w2, …,wm se les llama precios sombra.
Si el programa primal es como el Dual anterior, entonces su Dual será como el Primal anterior.
Ejemplo
El programa primal:
Min z=3x1+4x2+x3
Sujeto a:
5x1+2x2+x3≥10
3x1+4x2+2x3≥20
4x1+5x2+x3≥30
6x1+2x2+3x3≥40
Con todas las variables no negativas.
El programa Dual es:
Max z=10w1+20w2+30w3+40w4
Sujeto a:
5 w1+3 w2+4 w3+6 w4≤3
2 w1+4 w2+5 w3+2 w4≤4
1 w1+2 w2+1 w3+3 w4≤1
Con todas las variables no negativas.
Ejemplo
El programa primal:
Max z=3x1+x2
Sujeto a:
x1+4x2≤8
x1+5x2≥1
2x1+3x2≤20
Con todas las variables no negativas.
Para encontrar el Dual primero expresamos las restricciones del Primal con ≤.
Max z=3x1+x2
Sujeto a:
x1+4x2≤8
−x1−5x2≤-1
2x1+3x2≤20
Luego el Dual es:
Min z=8 w1−1 w2+20 w3
1 w1−1 w2+2 w3≥3
4 w1−5 w2+3 w3≥1
Con todas las variables no negativas.
Duales asimétricos
Si el programa primal está en forma estándar, el programa Dual se encuentra de la siguiente
manera:
Primal Dual
Min z=CTX Max z=BTW
Sujeto a AX=B Sujeto a ATW≤C
Con X≥0
Primal Dual
Max z=CTX Min z=BTW
Sujeto a AX=B Sujeto a ATW≥C
Con X≥0
Como se puede ver los duales no están en forma estándar.
Igualmente, si los programas primales son los duales anteriores, sus duales son sus primales.
Ejemplo
El programa primal en forma estándar:
Max z=x1+2x2−3x3
Sujeto a:
3x1+6x2+5x3=30
5x1+3x2+7x3=40
Con todas las variables no negativas
El programa dual es:
Min z=30w1+40w2
Sujeto a:
3 w1+5 w2≥1
6 w1+3 w2≥2
5 w1+7 w2≥−3
Notar que para resolver el primal se debe llevar a su forma estándar:
Max z=x1+2x2−3x3−Mx4−Mx5
Sujeto a:
3x1+6x2+5x3+x4=30
5x1+3x2+7x3+x5=40
Con todas las variables no negativas
Para resolver el dual se requiere además que las variables sean no negativas:
Min z=30w1+40w2
Sujeto a:
3 w1+5 w2≥1
6 w1+3 w2≥2
−5 w1−7 w2≤3
w1=w3−w4
w2=w5−w6
Ejemplo
El programa primal en forma estándar:
Min z=x1+2x2+0x3+0x4+Mx5+Mx6
Sujeto a:
3x1+6x2−x3+x5=30
5x1+3x2−x4+x6=40
Con todas las variables no negativas
El programa dual es:
Max z=30w1+40w2
Sujeto a:
3 w1+5 w2≤1
6 w1+3 w2≤2
−1 w1+0w2 ≤0
0w1−1 w2≤0
1 w1+0w2≤M
0w1+1w2≤M
Se puede ver que la tercera y cuarta restricción se pueden colocar como condiciones y la quinta y
sexta son redundantes ya que M es un numero grande, por lo tanto, el dual quedaría:
Max z=30w1+40w2
Sujeto a:
3 w1+5 w2≤1
6 w1+3 w2≤2
Con w1, w2≥0
5.2 RELACIONES PRIMAL DUAL
Existe una relación entre las soluciones del programa primal y su dual, para ello se utilizarán los
siguientes teoremas:
Teorema 5.1
Si el programa primal tiene solución entonces el dual simétrico también tiene solución y la función
objetivo del primal y del dual tienen el mismo valor óptimo.
Para programas simétricos la solución del primal puede observarse en la tabla final del dual.
Ejemplo
El programa primario
Min z=10x1+8x2+7x3
Sujeto a:
3x1+6x2+5x3≥30
5x1+3x2+7x3≥60
Con todas las variables no negativas.
El programa dual
Max z=30w1+60w2
Sujeto a:
3 w1+5 w2≤10
6 w1+3 w2≤8
5 w1+7 w2≤7
Con todas las variables no negativas.
Resolvemos el dual:
Con el método gráfico.
Podemos observar que el máximo se encuentra en w1=0 y w2=1, dando zmax=60
Ahora se resolverá el dual utilizando la tabla simplex pero primero convertimos a su forma
estándar.
Max z=30w1+60w2+0w3+0w4+0w5
Sujeto a:
3 w1+5 w2+w3=10
6 w1+3 w2+w4=8
5 w1+7 w2+w5=7
Con todas las variables no negativas.
La tabla Simplex es:
La última fila se obtiene de zj−cj.
Simplificando tenemos la tabla inicial:
Las razones en la columna pivote:
10/5=2
8/3=2.66
7/7=1
Convirtiendo la columna pivote y cambiando la variable básica w5:
De aquí se puede observar:
w2=1, w1=0 zmax=60
La tabla última del dual permite también encontrar la solución del primal.
Observemos la última fila y los valores correspondientes a las variables de holgura es decir w3, w4 y
w5.
Estos son 0, 0 y 60/7. Estos se llaman precios sombra y corresponden a:
x1=0, x2=0, x3=60/7 y zmin=60
Ahora veamos cómo se vería la solución del dual si resolvemos el primal.
Min z=10x1+8x2+7x3
Sujeto a:
3x1+6x2+5x3≥30
5x1+3x2+7x3≥60
Con todas las variables no negativas.
El programa estándar es:
Min z=10x1+8x2+7x3+0x4+0x5+Mx6+Mx7
Sujeto a:
3x1+6x2+5x3−x4+x6=30
5x1+3x2+7x3−x5+x7=60
Con todas las variables no negativas.
La tabla simplex:
La última fila se formó con cj−zj.
Para dos fases:
Aquí x6 y x7 son variables artificiales. Las razones en la columna pivote:
30/5=6
60/7=8.57
Convirtiendo la columna pivote:
Reemplazando la variable x6 por x3 en la primera columna se tiene:
Convirtiendo la columna pivote:
La solución se puede ver que es:
x1=0, x2=0, x3=60/7
zmin=60
Para observar la solución del dual vemos la penúltima fila y las columnas de las variables
superfluas (x4 y x5)
x4=0
x5=1
Estos se llaman precios sombra.
Podemos interpretar también que si incrementamos en una unidad el lado derecho de la primera
restricción no afecta en el valor óptimo. Si incrementamos en una unidad el lado derecho de la
segunda restricción se incrementa en una unidad el valor óptimo. Esto se comprueba con la z del
dual ya que w1=0 y w2=1:
z=30w1+60w2
Esto se cumple hasta que no cambien las variables básicas.
5.3 ANÁLISIS DE SENSIBILIDAD
Como vimos anteriormente un programa lineal requiere datos para la modelización. No siempre
los datos son exactos y pueden tener cierta incertidumbre.
Ejemplo
Una industria de carpintería produce mesas y armarios. Por cada mesa se obtiene una ganancia de
$200 y por cada armario una ganancia de $300. El tiempo disponible de maquina por semana es
de 30hr para las mesas y 24h para los armarios. Para fabricar una mesa se necesita 3 hora de
maquina y para el armario se necesita 4 h de máquina. Adicionalmente se necesita 2 h obrero para
la fabricar 1 mesa y 4 h obrero para fabricar 1 armario, teniendo una disponibilidad de 26 h obrero
por semana. ¿Cuáles deben ser las cantidades de mesas y armarios que deben producirse por
semana para tener una máxima ganancia?
La ganancia total es:
z=200x1+300x2
Donde:
x1 es la cantidad de mesas
x2 es la cantidad de armarios
Las restricciones se dividen en:
Restricciones de horas de máquina.
3x1≤ 30
4x2≤ 24
Restricciones de horas personal.
2x1+4x2 ≤ 26
Por lo tanto, el modelo matemático es:
Maximizar: z=200x1+300x2
3x1≤ 30
4x2≤ 24
2x1+4x2 ≤ 26
x1, x2 ≥0
Supongamos que la ganancia por cada mesa resulta 180 en vez de 200 ¿Se puede utilizar los
resultados del modelo para analizar resultados?
Por determinadas circunstancias a veces los datos se deben cambiar y entonces es necesario saber
hasta qué cambios una empresa puede soportar y manejar sin que experimente dificultades.
Tener conocimiento previo de estas variaciones ayuda a tomar decisiones más rápidas sin tener
que resolver el programa.
Aquí veremos cómo cambia el resultado del modelo si se tienen cambios en los datos. Para ello
primero veamos el método gráfico para modelos de dos variables.
Los cambios pueden presentarse en los valores de la matriz C, matriz A y matriz B.
Método gráfico para análisis de sensibilidad
Los cambios que veremos en el método gráfico se refieren a:
1. Cambios en la matriz C (Beneficios unitarios o Costos unitarios).
2. Cambios en la matriz B (Disponibilidad de Recursos o requerimientos mínimos de producción).
Si la función objetivo es la función de beneficios y supongamos un cambio en la matriz C (Por
ejemplo, debido a una variación de los costos), se necesita conocer si el cambio de estos
beneficios afecta al modelo del problema.
Por otra parte, supongamos el ejemplo de una producción donde uno de los recursos es la mano
de obra. Aquí se necesita conocer si podría haber un aumento del beneficio si se aumenta el
recurso de mano de obra. Se puede ver que si aumentamos este recurso a partir de un límite no se
incrementa el beneficio, por lo tanto, es un gasto indebido incrementar la mano de obra. Así será
importante conocer en nuestro modelo los límites de los recursos.
1. Cambios en la matriz C
Aquí lo que se trata de encontrar el rango de valores de la matriz C de tal modo que no cambie el
punto óptimo.
Ejemplo
Supongamos el siguiente programa lineal:
Max z=5x1+6x2
Sujeto a:
x1+2 x2≤ 10
8 x1+7 x2≤ 40
x1≤ 3
Con todas las variables no negativas.
Analicemos el efecto de una variación de las constantes de la función objetivo (Costos unitarios).
En el gráfico podemos observar las tres restricciones, la región factible y la función objetivo
cuando z=20. Al incrementar z la función sube así que z máximo se presenta en el punto D que es
la intersección de las restricciones 1 y 2, es decir el punto (1.11, 4.44). Por lo tanto, el valor óptimo
de z se encuentra en x1=1.11 y x2=4.44 con zmax=32.22.
¿Qué ocurre si por ejemplo el valor de c1 tiene otro valor?
El análisis de sensibilidad encuentra el rango en el que c1 puede variar sin que el lugar óptimo
cambie, es decir se mantenga en D.
La función objetivo es:
z=c1x1+6x2
Se puede ver que la pendiente de la recta de z es:
−c1/6
Para que el máximo se mantenga en D es necesario que la pendiente de la función objetivo varie
entre la pendiente de la restricción 2 y la pendiente de la restricción 1 es decir:
−8/7≤−c1/6≤−1/2
Lo que implica que:
3≤c1≤6.86
Ya que inicialmente c1=5, se puede incrementar 1.86 y disminuir 2 unidades. El valor óptimo de z
es 32.22. Manteniendo el punto óptimo los valores de z son:
30≤z≤34.29
Entonces observemos que si c1 cambia de 5 a 6.86 el valor óptimo se incrementa manteniendo la
producción de x1 y x2.
Estos mismos análisis se pueden hacer cambiando la constante c2.
Ejercicio
Realice el análisis de c2 para el siguiente programa:
Max z= 3x1+7x2
Sujeto a:
4x1+3x2≤20
5x1+7x2≤30
x2≤3
Con todas las variables no negativas.
Considerando z=35 la región factible es:
zmax =26.4, x1=1.8, x2=3
z= 3x1+c2x2
La pendiente de z es:
−3/c2
Para que el óptimo siga en el punto C, la pendiente de z debe variar desde la pendiente de g hasta
la pendiente de h.
−5/7≤−3/c2≤0
Resolviendo primero −5/7≤−3/c2:
3/c2−5/7≤0
(21−5c2)/c2≤0
Resolviendo −3/c2≤0:
La intersección es c2 ≥21/5, por lo tanto, no cambia el punto óptimo si c2 es mayor o igual a 21/5.
2. Cambios en la matriz B
Aquí lo que se trata de es de encontrar los límites de variación de la matriz B de forma que no
cambien las variables básicas finales. De este modo puede utilizarse la tabla final para encontrar
los valores de las variables.
Ejemplo
¿Qué ocurre si cambian los valores de la matriz B? Es decir, en el lado derecho de las restricciones.
Max z=5x1+6x2
Sujeto a:
x1+2 x2≤ 10
8 x1+7 x2≤ 40
x1≤ 3
Vimos en este ejemplo que el punto óptimo se encuentra en (1.11, 4.44).
Por ejemplo, b2 actualmente tiene el valor de 40. Para que r2 intercepte con r1 entre 0<x1<3, b2
debe variar de forma que sea paralela a la recta r2 pasando desde el punto B hasta el punto F.
Para encontrar los límites de b2, encontramos las ecuaciones de las rectas que pasan por B y F.
8 x1+7 x2= b2
8 (0)+7 (5)= 35
8 (3)+7 (3.5)= 48.5
Entonces b2 puede reducirse en 5 unidades e incrementar en 8.5 unidades.
Supongamos que b2 se incrementa hasta 60 la gráfica de la región factible es:
Se puede observar que es indebido aumentar el recurso ya que el valor óptimo se mantiene en M.
Para encontrar los mismos valores en forma analítica observemos la tabla final de la tabla simplex:
Para obtener los valores de las variables básicas se multiplica la matriz señalada por la matriz B, es
decir:
Esta matriz señalada puede utilizarse en un cierto rango de la matriz B.
Para obtener los valores máximo y mínimo de b2 resolvemos la inecuación matricial:
Multiplicando y simplificando:
40−d≥0 d≤40
2d+10≥0 d≥−5
17−2d≥0 d≤17/2
La intersección es:
−5≤d≤17/2
Ejercicio
Hallar los valores límites de b1 del anterior ejemplo
Se puede analizar utilizando Excel, para ello introducimos los datos de acuerdo al procedimiento
visto anteriormente.
Con Solver se tiene:
Eligiendo informe de sensibilidad se tiene la hoja de análisis de sensibilidad:
Observemos en la tercera restricción es permisible aumentar 1E+30 lo que quiere decir cualquier
incremento no modifica la base de la solución.
LINDO muestra lo siguiente: