Dualidad y
Sensibilidad
Lic. Guissela Guzmán
/9
El Problema Dual
INTRODUCCION
Todo modelo de programación lineal tiene un segundo
modelo que se llama modelo dual. Al problema original se
denomina “Problema Primal (PP)” y al otro
“Problema Dual (PD)”.
Los dos problemas poseen propiedades muy relacionadas
de tal manera que la solución óptima a un problema
proporciona información completa sobre la solución
óptima para el otro.
Las soluciones a ambos programas se obtiene al resolver
cualquiera de ellos.
Lic. Guissela Guzmán
Reglas de transformación para obtener el dual
El programa dual se obtiene a partir del programa primal (y
viceversa) de la manera siguiente:
1. Se invierte la dirección de la optimización. Un programa
busca maximizar y el otro busca minimizar (o viceversa).
n m
Max Z = Ʃ CJ XJ Min W= Ʃ bi Yi
i=1
J=1
2. Las variables de decisión del primal Xj se reemplaza con
variables de decisión del dual Yi. Por cada restricción en el
primal se tiene una variable de decisión en el dual.
3. Los signos de desigualdad se invierten, pero la restricción
de no negatividad sobre la variable de decisión se
mantiene.
Lic. Guissela Guzmán
4. Los elementos que constituyen el vector de recursos del
primer programa de maximización aparecen en el
segundo programa de minimización como coeficientes de
la función objetivo.
5. Los coeficientes de la función objetivo del programa de
maximización aparecen como los elementos del vector de
términos independientes en el segundo programa de
minimización.
PRIMAL DUAL
n m
Max Z= Ʃ CJXJ Min W= Ʃ biYi
J=1 i=1
n m
Ʃ aij Xj ≤ bi i= 1,2,3,….. m Ʃ aij Yi Cj j= 1,2,3,….. n
j=1 i=1
Xj 0 j = 1,2,3 ….. n Yi 0 i = 1,2,3 ….. m
Lic. Guissela Guzmán
6. Los elementos de un programa aparecen invirtiendo su
papel en el otro, la matriz principal de coeficientes aparece
transpuesta en el otro.
Teoremas del dual
1. El valor óptimo de la función objetivo del primal es siempre
igual al valor óptimo de la función objetivo del dual.
Max Z = Min W
2. Si en la solución óptima factible, una variable de decisión en
el programa primal tuviera un valor distinto de cero, la
variable de holgura correspondiente en el programa dual
deberá tener un valor optimo cero
3. Las variables duales Yi pueden interpretarse como la
contribución por unidad del recurso i-ésimo al valor de la
función objetivo. Ejm Y1 = 2 significa que por cada unidad
que se incrementa el primer recurso, el valor de la función
objetivo del primal se incrementa en 2 unidades monetarias.
Lic. Guissela Guzmán
Ejemplo 1:
PRIMAL:
Max Z= 200 X1 + 240 X2
Sujeto a: 6 X1 + 12 X2 ≤ 120
8 X1 + 4 X2 ≤ 64
DUAL: X1, X2 ≥ 0
Min W = 120 Y1 + 64 Y2
Sujeto a: 6 Y1 + 8 Y2 ≥ 200
12 Y1 + 4 Y2 ≥ 240
Y1, Y2 ≥ 0
Resolviendo ambos problemas con solver se tiene:
Lic. Guissela Guzmán
Lic. Guissela Guzmán
La variable dual Y1 es 15,5556 indica que la utilidad total
óptima aumentará en 15,56 unidades monetarias por cada
hora en construcción que se incremente.
La variable dual Y2 es de 13,33 indica que la utilidad total
óptima aumentará en 13,33 unidades monetarias por
cada hora de pintado que se incremente.
Básica x1 x2 x3 x4 Sol
x2 0 1 1/9 -1/12 8
x1 1 0 -1/18 1/6 4
Z 0 0 140/9 40/3 2720
Lic. Guissela Guzmán
Ejemplo 2:
En una granja se da una dieta para engordar los pollos
con una composición mínima de 14 unidades de una
sustancia A, 12 de una sustancia B y 18 de una sustancia
C. En el mercado se encuentran dos tipos de compuestos,
el del tipo M con una composición de 2 unidades de la
sustancia A, una unidad de B y una unidad de C y el del
tipo N con una composición de una unidad de la sustancia
A, una unidad de B y 3 unidades de C. El costo del
compuesto de tipo M es de $ 2 el kilo y el del tipo N de $
4. ¿Qué cantidades se deben comprar de cada tipo de
compuesto para cubrir las necesidades con un costo
mínimo?
Lic. Guissela Guzmán
Variables de decisión:
X1 = Cantidad de kilos a comprar del tipo M
X2 = Cantidad de kilos a comprar del tipo N
Primal:
Min Z= 2X1 + 4X2
Sujeto a: 2X1 + X2 ≥ 14
X1 + X2 ≥ 12
X1 + 3X2 ≥ 18
X1, X2 ≥0
Dual:
Max W = 14Y1 + 12Y2 + 18 Y3
Sujeto a: 2Y1 + Y2 + Y3 ≤ 2
Y1 + Y2 + 3Y3 ≤ 4
Y1, Y2 ,Y3 ≥ 0
Lic. Guissela Guzmán
Análisis de sensibilidad
Llamado también análisis post-optimización.
Es el estudio de cómo los cambios que pueden ocurrir
en los elementos componentes del modelo de
programación lineal afectan a la solución óptima.
Por ejemplo: ¿Cómo afectará el cambio de un coeficiente
de la función objetivo a la solución óptima? Cj
¿Cómo afectará el cambio de un valor del lado derecho
de la restricción a la solución óptima? bi
También puede cambiar:
El número de restricciones
La matriz A, o sea cambios en los coeficientes aij
El Vector X, o sea cambios en el número de actividades
Por tanto, permite conocer cuan sensible es la solución
óptima a cambios que ocurran en alguno de los
componentes.
El solver una vez que se hace clic en resolver, presenta tres
tipos de informe en una hoja independiente, Informe de
respuestas, informe de sensibilidad e informe de límites,
puede seleccionarse los tres:
Lic. Guissela Guzmán
Informe de Respuestas: muestra una lista con la celda
objetivo y las celdas ajustables con sus valores originales y sus
valores finales, las restricciones y la información acerca de las
mismas.
Lic. Guissela Guzmán
Informe de Sensibilidad: facilita información acerca de la
sensibilidad de la solución a que se realicen pequeños
cambios en la fórmula de la celda objetivo o de las
restricciones.
Lic. Guissela Guzmán
Informe de Límites: muestra una lista con la celda objetivo y las
celdas ajustables con sus valores correspondientes, los límites
inferior y superior así como los valores del objetivo. No se genera
este informe para los modelos que tengan restricciones enteras.
El límite inferior es el valor mínimo que puede tomar la celda
ajustable mientras se mantienen todas las demás celdas ajustables
fijas y se continúa satisfaciendo las restricciones. El límite superior
es el valor máximo.
Lic. Guissela Guzmán
Informe de resultados
Solución óptima:
Producir 4 sillas y 8 escritorios cada día
La utilidad máxima obtenida por la producción alcanza a
Bs. 2.720
Holguras
Restricción 1: Holgura cero. No quedan horas para
construcción,
Restricción 2: Holgura cero. No quedan horas para
pintado.
La utilidad total óptima aumentará en 15,56
unidades monetarias por cada hora que se
incremente en construcción.
La utilidad total óptima aumentará en 13,33 unidades
monetarias por cada hora que se incremente en
pintado.
Utilzando winQSB
Cuando cambia un número, insumo del modelo, tal
como un coeficiente o parámetro, o un lado derecho de
la restricción, el análisis de sensibilidad de la solución
muestra un rango de valores dentro de los cuales ese
número puede cambiar sin cambiar la solución obtenida.
Los rangos de variación dentro de los cuales la base No
cambia.
a) Para los coeficientes de la función Objetivo se
muestra en (Allowable Min y Allowable Max) Así
El coeficiente de la variable X1 en la función objetivo
es de 200 es decir la utilidad que proporciona cada
silla y puede variar entre 120 ≤ C1 ≤ 480
Lic. Guissela Guzmán
Y la solución básica seguirá siendo la misma. El valor de la
función objetivo puede variar dependiendo del valor que tome
ese coeficiente dentro de ese rango.
El coeficiente de X2 es de 240 u.m. entonces, la utilidad
que proporciona cada escritorio puede variar entre
100 ≤ C2 ≤ 400
Lic. Guissela Guzmán
b) Rangos para los lados derechos de las restricciones se
muestra en (Allowable Min RHS y Allowable Max RHS) El
análisis presenta la cantidad permitida de crecimiento y la
cantidad de decrecimiento permitido para cada lado
derecho de las restricciones Así:
La cantidad máxima de horas (120) disponibles para la
construcción puede variar entre 48≤ b1 ≤ 192 y la
solución básica seguirá siendo la misma
La cantidad máxima de horas disponibles para el pintado
(64) puede variar entre 40 ≤ b2 ≤ 160 y la solución
básica seguirá siendo la misma
Lic. Guissela Guzmán
c) Cuando aparece una restricción.
Si la nueva restricción es satisfecha con los valores actuales
entonces debe concluirse que la solución actual sigue siendo
la misma .
La solución no es sensible cuando aparecen restricciones de
ese tipo. Se incorpora al modelo y se continúa con la misma
solución básica.
Si la nueva restricción no es satisfecha con los valores
óptimos actuales, entonces debe concluirse que la solución
actual cambiará y deberá resolverse el nuevo problema.
Lic. Guissela Guzmán
Informe de resultados
Solución óptima:
Producir 4 sillas y 8 escritorios cada día
La utilidad máxima obtenida por la producción alcanza
Bs. 2.720 diario
Holguras (Slack or Surplus)
Restricción 1: Holgura cero. No quedan horas para
construcción,
Restricción 2: Holgura cero. No quedan horas para
pintado
El coeficiente de la variable X1 en la función objetivo es de
200 es decir la utilidad que proporciona cada silla y puede
variar entre 120 ≤ C1 ≤ 480
Lic. Guissela Guzmán
El coeficiente de X2 es de 240 Bs. entonces, la utilidad
que proporciona cada escritorio puede variar 100 ≤ C2 ≤
400
La cantidad máxima de horas (120) disponibles para la
construcción puede variar entre 48≤ b1 ≤ 192 y la
solución básica seguirá siendo la misma
La cantidad máxima de horas disponibles para el pintado
(64) puede variar entre 40 ≤ b2 ≤ 160 y la solución
básica seguirá siendo la misma
La utilidad total óptima aumentará en 15,56 unidades
monetarias por cada hora de construcción que se
incremente.
La utilidad total óptima aumentará en 13,33 unidades
monetarias por cada hora de pintado que se
incremente.
Lic. Guissela Guzmán
