Problema Dual

Vista previa del material en texto

Problema Dual
Problema Primal (PP)- Problema Dual (PD)
La formulación natural de un problema de programación lineal se
denomina directa (primal), asociado tiene un planteo denominado dual,
con interpretación económica del primal.
Considerando al problema original o directo o primal (PP) como:
Maximizar Z =  cj xj ,
j=1 a n
s. a
 aij xj  bi, para i= 1,2,...,m.
j=1 a n
xj  0 , para j= 1,2,....n.
Asociado a este existe un planteo denominado programación dual (PD).
Tiene la forma:
Minimizar G =  bi yi
i=1 a m
s. a
 aij
T yi  cj , para j = 1,2,...,n
i=1 a m
yi  0, para i= 1,2, ....,m.
Es decir que el problema dual usa los mismos parámetros que el problema primal, 
TRASPUESTOS. 
El problema primal en forma estándar es:
Max Z = 3 x1 + 2 x2+ 0 x3 + 0 x4 + 0 x5+ 0 x6
x1 + 2 x2 + x3 = 6
2 x1 + x2 + x4 = 8
- x1 + x2 + x5 = 1
x2 + x6 = 2
x1  0 , x2  0, x3  0,x4  0,x5  0,x6  0
El problema dual, del mismo problema, es:
Min G = 6 y1 + 8 y2 + y3 + 2 y4
y1 + 2 y2 - y3 + 0 y4  3
2 y1 + y2 + y3 + y4  2
y1  0, y2  0, y3 0, y4  0
Si xE = x1 ; xI= x2
Ejemplo
xE + 2 xI  6 (1)
2 xE + xI  8 (2)
xI  xE + 1 (3)
xI  2 (4)
xE  0 (5) , xI  0 (6) 
FO: Max z = 3 xE + 2 xI
Correspondencia de variables
y1 ↔ x3
y2 ↔ x4
y3 ↔ x5
y4 ↔ x6
y5↔ x1
y6↔ x2
•Se puede observar que los coeficientes de la función objetivo en un
problema son los términos independientes del otro y viceversa. Esta
correspondencia es la clave de las aplicaciones de la dualidad y del
análisis de sensibilidad.
Para determinar los restantes elementos del problema dual: sentido de la
optimización, tipo de restricciones y signo de las variables y partiendo de
que el problema primal está en forma estándar; todas las restricciones
son ecuaciones con segundo miembro no negativo y todas las variables
son no negativas, se procede como indica la tabla:
F. Objetivo Dual
estándar del
primal F. objetivo Restricciones Variables
Max Min  Irrestrictas
Min Max  Irrestrictas
Problema Dual
El problema primal en forma estándar es:
Min Z = 15 x1 + 12 x2
x1 + 2 x2  3
2 x1 - 4 x2  5
x1  0 , x2  0
Primal estándar
Min Z = 15 x1 + 12 x2+ 0 x3 + 0 x4
x1 + 2 x2 - x3 = 3
2 x1 - 4 x2 + x4 = 5
x1  0 , x2  0, x3  0, x4  0
El problema dual, del mismo problema, es:
Max G = 3 y1 + 5 y2
y1 + 2 y2  15
2 y1 - 4 y2  12
-y1  0; (o y1  0)
y2  0
y1 ; y2 no restringida (redundante)
• Pasar todas las 
restricciones a ecuaciones 
de “=“ ; con segundo 
miembro no negativo 
• Todas las variables son no 
negativas
y1
y2
Problema Dual
⚫ Expresado en forma matricial:
Problema primal Problema dual
Max Z = c x Min G = b y 
sujeto a sujeto a
A x  b AT y  c
x 0 y  0
⚫ El Problema Dual tiene una variable real (VR) por cada restricción del Problema
Primal.
Nº de Var Reales del Prob Dual = Nº de restricciones del Prob Primal
La Var Reales del PDual se corresponde con la Variable de Holgura (VH) de la
restricción asociada del Prob Primal
⚫ El Problema Dual tiene una restricción por cada variable real del Prob Primal.
Nº de restricciones del Prob Dual = Nº de VReales del Prob Primal.
La variable de superávit de la restricción del PDual se corresponde con la VReal
asociada del PPrimal.
Ejemplo: Construir el Dual
Teorema fundamental de la dualidad.
Se puede demostrar que:
1- Si Z y G son soluciones factibles de un par de problemas
primal- dual, entonces:
Z = c x  b y = G
2- Dado un par de problemas primal- dual, puede ocurrir:
a) Ambos tienen solución óptima y sus funciones objetivo son
iguales Z* = c x = b y = G*
Correspondencia primal-dual
La información generada por la solución de uno de los problemas
permite conocer la solución del otro, sin tener que resolverlo.
G
Z
Optimo
DIRECTO DUAL
FUNCIONAL DE SOLUCION OPTIMA FINITA = FUNCIONAL DE SOLUCION OPTIMA FINITA
SOLUCION OPTIMA ALTERNATIVA ↔ SOLUCION OPTIMA DEGENERADA
SOLUCION INCOMPATIBLE ↔ SOLUCION POLIEDRO ABIERTO
Pasaje de Tabla óptima (TO) del PP al PD
⚫ Si una variable del Problema Primal no está en su Tabla
optima, su correspondiente variable del PDual está en la base del PDual.
⚫ Si una Variable del PP está en la base de la TO, su correspondiente variable
del PD no está en la base del PD.
⚫ El valor del funcional del PP coincide con el valor del funcional del PD.
⚫ Los valores de las variables (columna B) de un problema de maximización
pasan con signo cambiado a la fila del funcional en las columnas de las
variables duales correspondientes.
⚫ Los valores de las variables (columna B) de un problema de minimización
pasan con su signo a la fila del funcional en las columnas de las variables
duales correspondientes.
⚫ Ídem para las columnas Aj.
Pasaje de Tabla óptima (TO) del PP al PD
⚫ Si una variable del PP no está en su TO, su correspondiente
variable del PD está en la base del PD.
⚫ El valor del funcional del PP coincide con el valor del funcional
del PD.
Z=G
Pasaje de Tabla óptima (TO) del PP al PD
⚫ Los coeficientes aij de los vectores columnas asociadas a las
actividades pasan con signo cambiado a la fila de la variable dual
correspondiente.
Ejemplo: tenemos el siguiente planteo
Correspondencia 
de variables
y1 ↔ x3
y2 ↔ x4
y3 ↔ x5
y4 ↔ x1
y5↔ x2
Pasaje de Tabla óptima (TO) del PP al PD
⚫ Ejemplo: Problema de maximización
Tabla optima del primal
Tabla optima dual
x1 x2 x3 x4 x5
y1 y2 y3 y4 y5
Correspondencia 
de variables
y1 ↔ x3
y2 ↔ x4
y3 ↔ x5
y4 ↔ x1
y5↔ x2
Interpretación económica del PD
⚫ Las variables reales del PD son los valores marginales zj-cj de las
restricciones del PP. Representan la modificación que se verifica en el
funcional por cada unidad de relajación (liberación) de la restricción.
⚫ En las restricciones de menor o igual, liberar (relajar) la restricción
implica aumentar la condición en un unidad.
⚫ En las restricciones de mayor o igual, liberar (relajar) la restricción
implica reducir la condición en una unidad
⚫ En las restricciones de ≤ en el PP, el VM representa la “mejora” en el
funcional por cada unidad de recurso que se obtenga.
Precio máximo que se estaría dispuesto a pagar por obtener una
unidad adicional del mismo; o el precio mínimo al que se debería
vender una unidad del recurso.
Cuando el VM es cero, tenemos disponibilidad sobrante , por lo
que no habría necesidad de aumentarlo
Interpretación económica del PD
En las restricciones de ≥ en el PP, que indican un requerimiento mínimo
de fabricación “b” de un producto (ej. Compromisos con el cliente), el
VM representa la mejora que experimentaría el funcional por cada
unidad que se pudiera disminuir la limitación del requerimiento.
Significa que el hecho de cumplir este requerimiento mínimo resulta un
perjuicio, en consecuencia el VM sería el precio máximo que se podría
pagar a un tercero por una unidad del producto, a fin de cumplir con el
requerimiento impuesto.
También representa lo que se debería incrementar el precio de venta de las
unidades que estén por encima de la producción óptima a fin de
cumplir con la restricción.
Interpretación económica del PD
Las Variables Superavit del Problema Dual son los costos de oportunidad
(CO) zj-cj de las variables reales del PP.
El Costo de Oportunidad representa el perjuicio que se obtiene en el funcional
por cada unidad que se active de una variable cuando la solución optima
indica que es nula.
CO nos indica en cuanto habría que modificar el coeficiente de la variable en
el funcional para que convenga activarla.
Si x representara cantidad a fabricar de un producto, y la solución optima
estableciera que no se debe producir, el CO representaría el incremento que
debería realizarse en el precio de venta unitario (o la disminución de costo)
para que convenga producirlo.Si x representara cantidad a adquirir de un producto y la solución optima
determinara no comprarlo, el CO representará el valor que el proveedor
debería disminuir el precio para que sea conveniente adquirir el producto.
Interpretación de la solución óptima
1. Vector B (Base). Da el nivel de actividad óptimo de las variables que
están en la base.
2. Vector Aj asociado a una variable de holgura que no esté en la base:
los aij indican la variación (en el sentido del signo del coeficiente) que se
produciría en las variables xi básicas por cada unidad que se relaja la
restricción.
Los zj-cj muestran la variación que se verificaría en el funcional en el sentido de
su signo por cada unidad que se relaja la restricción. Estos valores zj-cj
relacionados con las restricciones se llaman valores marginales o precios sombra.
3. Vector Aj asociado a una variable real que no está en la base: los aij
indican la variación (en el sentido contrario al signo del coeficiente) que
se produciría en las variables xi básicas por cada unidad que se activara la
variable.
Estos valores zj-cj relacionados con actividades se llaman costos de oportunidad o costos
reducidos.
B
Interpretación de la solución óptima
|Básic
a 
z xE xI s1 s2 s3 s4 Solución 
z 1 0 0 1/3 4/3 0 0 12,66 
xI 0 0 1 2/3 -1/3 0 0 4 / 3 
xE 0 1 0 -1/3 2/3 0 0 10 /3 
s3 0 0 0 -1 1 1 0 3 
s4 0 0 0 -2/3 1/3 0 1 2 / 3 
 
Por cada Tn adicional que se disponga de materia prima A, se podrá 
producir 2/3 unidades adicionales de pintura para Interiores
Valor marginal
Por cada Tn adicional que se disponga de materia prima A, se producirá 
-1/3 unidades de pintura para Exteriores
Interpretación económica 
(Problema primal de maximización y Problema dual de minimización)
Interpretación económica para el problema primal: Dada una unidad
de valor para cada producto o actividad (cj) y un límite superior para
la disponibilidad de cada insumo o recurso (bi ), lo que se pregunta
es: cuántas unidades de cada producto o actividad deben ser producidas
con el objeto de maximizar el valor del producto total ( Z ), cumpliendo
con las restricciones .
Interpretación económica para el problema dual
Sin embargo el empresario podría plantearse, vender los recursos
involucrados a un tercero interesado. Entonces la interrogante seria el precio
mínimo de venta de esos recursos
Con una disponibilidad dada de cada insumo ( bi) y un límite inferior al valor
unitario para cada actividad (cj) la pregunta es , qué valores deberían ser
asignados a cada insumo (yi) con el objetivo de minimizar el valor del
insumo total de los recursos consumidos (G); cumpliendo con las
restricciones .
•En la función objetivo
yi puede interpretarse como la contribución a la ganancia por
unidad de recurso i cuando se utiliza el actual conjunto de variables
básicas en la solución primal; yi son los precios sombra para el recurso i.
Representan un valor marginal, en este caso la tasa a la que G puede
aumentar si se incrementa en una unidad la cantidad disponible de ese
recurso.
Minimizar G =  bi yi
i=1 a m
se interpreta entonces como la minimización del valor total implícito de
los recursos consumidos por las actividades.
•En las restricciones funcionales
Dado que cada unidad de actividad j en el primal consume aij
unidades del recurso yi , el primer término de las restricciones
 aij yi , para j = 1,2,...,n 
i=1 a m
se interpreta como la contribución actual a la ganancia de esa mezcla de
recursos, que se consumiría si se produjera una unidad de la actividad j.
El beneficio que se obtendría al vender los recurso 1 a un precio y1, los
recurso 2 a un precio y2 , etc; debe ser mayor que el beneficio que se
obtendría por fabricar y vender la pieza 1… (idem para cada actividad)
Esta mezcla de recursos se podría usar de otras formas, pero no debe
hacerse si este uso es menos rentable que una unidad de la actividad j.
Dado que cj es la ganancia unitaria de la actividad j, cada restricción
funcional en el problema dual
 aij yi  cj , para j = 1,2,...,n 
i=1 a m
puede interpretarse diciendo que la contribución actual a la ganancia de la
mezcla de recursos debe ser por lo menos tanta como si se utilizara por una
unidad de la actividad j, si no, no se estaría haciendo el mejor uso de estos
recursos.
•La condición de no negatividad (en prob. de min.)
yi  0 se interpreta como que la contribución a la ganancia por el
recurso i debe ser no negativa, de lo contrario sería mejor no usar este
recurso.
Análisis Matricial
En el problema primal
Max Z = c x
sujeto a A x  b
x  0
al estandarizarlo y resolverlo:
BxB + NB xNB = b
como xNB = 0
entonces B xB = b
Pre multiplicando por B-1 ; B-1 B xB = B
-1 b
entonces xB* = B
-1 b (1)
En el problema dual G* = bT y, (2)
En el problema primal Z* = c x (3)
En el optimo Z* = G*, entonces cB xB* = b
T y
o sea, de (1), (2) y (3) cB B
-1 b = bT y
es decir y= cB B
-1 (4)
I
-c 0 0
A I b
1ra. tabla
cBB
-1A- c cB B
-1 - 0 Z* = cBxB*=cBB
-1 b
B-1A B-1 xB* = B
-1 b
Tabla óptima
En forma tabular
B
B-1
Forma tabular
|Básica z xE xI s1 s2 s3 s4 Solución 
z 1 0 0 1/3 4/3 0 0 12,66 
xI 0 0 1 2/3 -1/3 0 0 4 / 3 
xE 0 1 0 -1/3 2/3 0 0 10 /3 
s3 0 0 0 -1 1 1 0 3 
s4 0 0 0 -2/3 1/3 0 1 2 / 3 
 
Básica z xE xI s1 s2 s3 s4 Solución
z 1 -3 -2 0 0 0 0 0 Razón
s1 0 1 2 1 0 0 0 6 6
s2 0 (2) 1 0 1 0 0 8 4
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
cBB
-1A- c yi = cBB
-1- 0 Z* = cBxB*=cBB
-1 b
B-1A xB* = B
-1 b














=
0
0
3
2
BC
Aplicaciones del problema dual
El problema dual permite:
- Resolver problemas lineales que tienen más restricciones que
actividades
- Hacer interpretaciones económicas
- Generar métodos como el dual simplex para el análisis de sensibilidad
- Generar nuevos algoritmos para redes de optimización.
Método Dual Simplex
Nuevo método: comienza en un optimo no factible . La iteraciones
sucesivas avanzan hacia la factibilidad , sin violar la optimalidad.
Cuando se restaura la factibilidad , el algoritmo termina.
El MDS conserva la optimalidad y va anulando la infactibilidad
Convertir a  y agregar variables de holgura
1. Condición de factibilidad: sale la variable básica con valor más
negativo. Si todas son no negativas se alcanza la solución
óptima
2. Condición de optimalidad: se consideran los cocientes con
denominador negativo. Entra a la base la variable de cociente
mas pequeño (min) o el valor absoluto más pequeño (max)
Se utiliza para devolver la factibilidad en modificaciones que se
realizan en el análisis de sensibilidad
Ejemplo: Método Dual Simplex
Max Z = 3x1 + 2 x2 (Función Objetivo)
sujeto a: 1. 3 x1 + 2 x2 ≥ 6
2. 2x1+ x2 ≥ 8
3. x1+ x2  1 (Condiciones de vínculo )
x1 0 , x2  0 (CNN)
Salida
Variable X1 X2 X3 X4 X5
renglon zj-cj -3 -2 0 0 0
renglon x4, a4j -2 -1 0 1 0
proporcion (zj-cj)/a4j ´3/2 ´2/1 - - -
SBF X1 X2 X3 X4 X5 solucion
z -3 -2 0 0 0 0
X3 -3 -2 1 0 0 -6
X4 -2 -1 0 1 0 -8
X5 1 1 0 0 1 1
Entrada
Pasaje de Tabla óptima (TO) del PP al PD
⚫ Ejemplo: Problema de minimización
Tabla optima del primal
Tabla optima dual
Correspondencia 
de variables
y1 ↔ x3
y2 ↔ x4
y3 ↔ x5
y4 ↔ x6
y5↔ x1
y6↔ x2