Ejercicios resueltos de Dualidad

Universidad de La Habana
Facultad de matemática y Computación
Licenciatura en Ciencia de la Computación
Modelos de Optimización I Curso 2013-2014
Clase práctica #4
Tema: Dualidad
1.Considere el problema de Optimización Lineal paramétrico resuelto gráficamente
en la clase práctica anterior:
min ax + y
s.a. - 2x + y  3
x+y6
x, y  0
a) Formule el problema dual D.b) Resuelva D para todo valor de a utilizando el Teorema de Holguras
Complementarias.
Respuesta
El problema dual es:
max 3u1-6u2
s.a. -2u1-u2≤a
u1-u2≤1
u1, u2≥0
Para -20, lasegunda restricción del problema dual se cumple en la igualdad y se tiene u1-u2=1.
Como X* satisface la segunda restricción del primal en la desigualdad estricta, la
variable correspondiente enel dual se anula, esto es u2=0. Por tanto la solución óptima
del dual en este caso es U*=(1,0).

Para a=-2 sería válido el análisis anterior y entonces la solución óptima del dual siguesiendo U*=(1,0). Se puede verificar que esta solución también satisface el teorema de
holguras complementarias con X*=(1,5), que también es solución del primal. En este
caso la solución U*cumple las dos desigualdades:
.
-2u1-u2=-2
u1-u2=1
como igualdades.
Para -0

tiene una solución yRm

Hint: Considere el problema min z=0x
s.a. Ax=b,
x0.
Respuesta
En efecto,si se considera el problema P: min z=0x
s.a. Ax=b,
x0.
Su dual es D: max w=yb
s.a. yA≤0.
Si se cumple (I), x es solución óptima de P y por tanto, por el Teorema de Dualidad,
el valoróptimo de la función objetivo de D es cero y por tanto (II ) no tiene solución.
Si no se cumple (I), entonces P no tiene solución factible. Se tienen dos
posibilidades para D: o no tienesolución factible o no tiene óptimo finito. La primera
se descarta, pues obviamente y=0 es una solución factible de D. Por tanto, D no
tiene óptimo finito y en ese caso se cumple (II).