Teorema 2 de dualida
Dado un par de problemas primarios (P1) y su correspondiente dial (D1) únicamente uno y solo uno de los tres siguientes casos, pueden ocurrir.
a) Ambos programatienes soluciones optimas y sus funciones objetivos óptimas son iguales, es decir, si X* es óptimo para (P1) y Y* es optimo para (D1) entonces:
Z*= cX*=bTY*=G*
b) Si el problema primario (P1) notiene soluciones factibles y el problema dual (D1) tiene al menos una, entonces, el dual tiene una solución óptima no acotada y viceversa, si el problema dual no tiene soluciones factibles y elprimario tiene al menos una, entonces, el primario tiene una solución optima no acotada.
c) Ambos problemas (P1) y (D1) no tiene solución.
Este torema es muy importante porque la información generadapor la solución de uno de los problemas (ya sea primario o dual) permite conocer la solución del otr, sin tenerlo que resolver.
Teorema 3
La formulación dual de un problema dual genera larepresentacion primaria.
Prueba. Considere el problema primario:
Máx Z=c1X1+ c2X2+…+ cnXn
Sujeto a
a11X1+ a12X2+….+ a1nXn≤b1
a21X1+ a22X2+….+ a2nXn≤b2
………………………………………….
(P)
am1X1+ am2X2+….+ amnXn≤bm
X1≥ 0, X2 ≥ 0, …, Xn ≥ 0
Cuya formulacion dual es
Mín G= b1Y1+ b2Y2+…+ bmYm
Sujeto a
a11Y1+ a21Y2+….+ am1Ym≥c1
a12Y1+ a22Y2+….+ am2Ym≥c2
………………………………………….
(P)
a1nY1+ a2nY2+….+ amn Ym≥cn
Y1 ≥0, Y2 ≥ 0, …, Ym ≥ 0
Una forma equivalente del programa dual (D) es
Máx -G= -b1Y1 - b2Y2 -…- bmYm
Sujeto a
-a11Y1 - a21Y2 - ….- am1Ym≤ -c1
-a12Y1 - a22Y2 -….- am2Ym≤ -c2
………………………………………….-a1nY1 - a2nY2 -….- amn Ym≤ -cn
Y1 ≥ 0, Y2 ≥ 0, …, Ym ≥ 0
La formulación duel de esra última estructura lienal es
Mín -Z= -c1X1 - c2X2 -…- cnXn
Sujeto a
-a11X1 - a12X2 -….- a1nXn ≥ -b1
-a21X1 -a22X2 -….- a2nXn≥b2
………………………………………….
-am1X1 - am2X2 -….- amnXn≥ -bm
X1 ≥ 0, X2 ≥ 0, …, Xn ≥ 0
Que es equivalente al programa primario (P). El teorema queda demostrado. Cualquier otrea forma se...
Regístrate para leer el documento completo.