Problema Dual

Definición del Problema Dual. Relaciones

primales-duales. Interpretación económica del
problema dual. Método dual-simplex. Análisis
de sensibilidad o post-óptimo. Análisis
paramétrico de problemas lineales.
Aplicaciones. Utilización de software.
 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 =  c j 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
 aijT 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
El problema primal en forma estándar es: Si xE = x1 ; xI= x2

Ejemplo
Max Z = 3 x1 + 2 x2+ 0 x3 + 0 x4 + 0 x5+ 0 x6FO: Max z = 3 xE + 2 x I

y1 xE + 2 xI  6 (1)
x1 + 2 x 2 + x3 = 6
y2 2 xE + xI  8 (2)
2 x1 + x2 + x4 = 8
y3 xI  xE + 1 (3)
- x1 + x2 + x5 = 1
y4 xI  2 (4)
x2 + x6 =2
xE  0 (5) , xI  0 (6)

x1  0 , x2  0, x3  0,x4  0,x5  0,x6  0

Correspondencia de variables
El problema dual, del mismo problema, es:
y1 ↔ x3
Min G = 6 y1 + 8 y2 + y3 + 2 y4 y 2 ↔ x4
y 3 ↔ x5
y1 + 2 y 2 - y 3 + 0 y 4  3
2 y1 + y2 + y3 + y4  2 y4 ↔ x6
y5↔ x1
y1  0, y2  0, y3 0, y4  0
y6↔ x2
 Problema Dual
•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
El problema primal en forma estándar es:
Min Z = 15 x1 + 12 x2
x 1 + 2 x2  3
2 x1 - 4 x2  5
x 1  0 , x2  0
• Pasar todas las restricciones
Primal estándar a ecuaciones de “=“ ; con
Min Z = 15 x1 + 12 x2+ 0 x3 + 0 x4 segundo miembro no
y1
y2
x1 + 2 x2 - x3 = 3 negativo
2 x1 - 4 x 2 + x4 = 5
• Todas las variables son no
x1  0 , x2  0, x3  0, x4  0
negativas

El problema dual, del mismo problema, es:

Max G = 3 y1 + 5 y2
y1 + 2 y2  15
2 y1 - 4 y 2  12
-y1  0; (o y1  0)
y2  0
 Problema Dual
 Expresado en forma matricial:
Problema primal Problema dual
Max Z = c x Min G = b y
sujeto a sujeto a
Ax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
G

Z=cxby=G Optimo

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*

DIRECTO DUAL
FUNCIONAL DE SOLUCION OPTIMA FINITA = FUNCIONAL DE SOLUCION OPTIMA FINITA
SOLUCION OPTIMA ALTERNATIVA ↔ SOLUCION OPTIMA DEGENERADA
SOLUCION INCOMPATIBLE ↔ SOLUCION POLIEDRO ABIERTO

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.
 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 ↔ x 3
y2 ↔ x4
y3 ↔ x5
y4 ↔ x 1
y5↔ x2
Pasaje de Tabla óptima (TO) del PP al PD
 Ejemplo: Problema de maximización
Tabla optima del primal
x1 x2 x3 x4 x5 Correspondencia
de variables
y1 ↔ x3
y 2 ↔ x4
Tabla optima dual y3 ↔ x5
y1 y2 y3 y4 y5
y4 ↔ x1
y5↔ x2
 Interpretación económica del PD
 Las variables reales del PD son los valores marginales z j-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 z j-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.
 Interpretación de la solución óptima
Valor marginal

|Básic z xE xI s1 s2 s3 s4 Solución
a
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

Por cada Tn adicional que se disponga de materia prima A, se podrá

producir 0.66 (2/3) unidades adicionales de pintura para Interiores

Por cada Tn adicional que se disponga de materia prima A, se producirá

-0.33 (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 (c j) 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
El beneficio que se obtendría al vender los recurso 1 a un precio y 1,
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
I

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* = bT y
o sea, de (1), (2) y (3) cB B-1 b = bT y
es decir y = cB B-1 (4) variables duales
 En forma tabular

1ra. tabla

-c 0 0
A I b

Tabla óptima

cBB-1A- c cB B-1 - 0 Z* = cBxB*=cBB-1 b

B-1A B-1 xB* = B-1 b

 Forma tabular

-c 0
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

A B b

cBB-1A- c yi = cBB-1- 0 Z* = cBxB*=cBB-1 b

|Básica z xE x I s1 s2 s3 s4 Solución
z 1 0 0 1/3 4/3 0 0 12,66
2 xI  0 0 1 2/3 -1/3 0 0 4/3
 
3 xE  0 1 0 -1/3 2/3 0 0 10 /3
CB   

0 s3 
0 0 0 -1 1 1 0 3
0 
 s4  0 0 0 -2/3 1/3 0 1 2/3
B-1A B-1 x B* = B-1 b
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 + x 2  1 (Condiciones de vínculo )
x 1  0 , x2  0 (CNN)
Entrada
SBF X1 X2 X3 X4 X5 solucion
z -3 -2 0 0 0 0
X3 -3 -2 1 0 0 -6 Mas
X4 -2 -1 0 1 0 -8 Salida negativo
X5 1 1 0 0 1 1

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 - - -
Cociente mas pequeño