Método dual simplex

El Problema Dual
Clase 7

0011 0010 1010 1101 0001 0100 1011

Problema Dual
En el desarrollo de la Programación Lineal, se descubrió la existencia de un problema que se encuentra relacionado con un problema de programación lineal dado, este problema de denomina DUAL. Entonces, dado un problema de programación lineal, denominado problema primal, existe otro problema de programación lineal,denominado problema dual. Se dice que ambos problemas son mutuamente duales. Bajo ciertas hipótesis, los problemas primal y dual dan lugar al mismo valor óptimo de la función objetivo, y por tanto se puede resolver indirectamente el problema primal resolviendo el problema dual.

0011 0010 1010 1101 0001 0100 1011

0011 0010 1010 1101 0001 0100 1011

Problema Dual
Si se tiene el siguienteproblema de programación lineal: Max Z = C X s.a. AX≤b X≥0 En donde: C = (C1, …, Cj, …,Cn)
X1 X = Xj a11 ... a1j … a1n A = ai1 ... aij … ain am1 ... amj …amn b1 b = bj

Existe otro problema asociado, el Dual, que se expresa de la siguiente forma: Min Z = b’ Y s.a. A’ Y ≥ C’ Y≥0 b’ = (b1, …, bj, …,bn)
Y1 Y = Yj a11 ... ai1 … am1 A’ = a1j ... aij … amj C1 C’= Cj

Xn

0011 0010 1010 1101 00010100 1011

… …

…

…

…

… …

… …

… …

…

…

…

bm

…

…

Yn

0011 0010 1010 1101 0001 0100 1011

…

a1n ... ajn …amn

…

…

…

Cn

Problema Dual
Utilizando un problema conocido, producción de Zapper y Space Problema Primal: Max Z = 8X1 + 5X2 S.a 2X1 + X2 ≤ 1200 3X1 + 4X2 ≤ 2400 X1 + X2 ≤ 800 X1 – X2 ≤ 450 X 1, X 2 ≥ 0 Problema Dual: Min Z = 1200Y1 +2400Y2 + 800Y3 + 450Y4 S.a 2Y1 + 3Y2 + Y3 + Y4 ≥ 8 Y1 + 4Y2 + Y3 - Y4 ≥ 5 Yi ≥ 0

Cada restricción del primal, representa una variable del dual Cada variable del primal, representa una restricción del dual

0011 0010 1010 1101 0001 0100 1011

0011 0010 1010 1101 0001 0100 1011

Problema Dual
Reglas para la obtención del Dual (Primal Max) La FO del dual es Minimizar Una restricción deigualdad en el primal, genera una variable SRS en el dual. Una restricción del tipo ≤ genera una variable dual no negativa (se deben transformar todas las restricciones del tipo ≥ en ≤) Una variable no negativa en el primal genera una restricción del tipo ≥ en el dual Una variable SRS en el primal en el primal genera una restricción de igualdad en el dual. El dual del dual es el primal Si el primales un problema de minimización se debe cambiar la sentido de la desigualdad
0011 0010 1010 1101 0001 0100 1011 0011 0010 1010 1101 0001 0100 1011

Problema Dual
Encuentre el dual para los siguientes problemas de programación lineal Max Z = 3X1 – 2X2 S.a X1 ≤ 4 X2 ≤ 6 X1 + X2 ≤ 5 X2 ≥ 1 X 1, X 2 ≥ 0 Min Z = X1 + X2 – X3 S.a 2X1 + X2 ≥ 3 X1 – X3 = 2 X3 ≥ 0 X1, X2 SRS Max Z = 3X1 – 2X2 S.a (Y1)X1 ≤4 (Y2) X2 ≤ 6 (Y3) X1 + X2 ≤ 5 (Y4) -X2 ≤ -1 X 1, X 2 ≥ 0 Min Z = X1 + X2 – X3 S.a (Y1) 2X1 + X2 ≥3 (Y2) X1 – X3 = 2 X3 ≥ 0 X1, X2 SRS Min Z = 4Y1 + 6Y2 + 5Y3 – Y4 S.a (X1) Y1 + Y3 ≥ 3 (X2) Y2 + Y3 – Y4 ≥ -2 Yi ≥ 0

Max Z = 3Y1 + 2Y2 S.a (X1) 2Y1 + Y2 = 1 (X2) Y1 = 1 (X3) –Y2 ≤ -1 Y1 ≥ 0 Y2 SRS

0011 0010 1010 1101 0001 0100 1011

0011 0010 1010 1101 0001 0100 1011

Problema Dual
Unavez formulado el problema dual, se debe encontrar su solución, para ello se utiliza el método Dual-Simplex el cual comienza con una solución óptima o mejor que óptima, pero no factible y se mueve hacia el objetivo mediante iteraciones que mejoran su factibilidad. Este método es el contrario del método simplex en donde se empieza mediante una solución factible pero no óptima y mediante iteracionesse mejora la optimalidad. Solución Óptima y Factible

Método Simplex Solución Factible Solución NO Óptima Mejora Optimalidad Conserva Factibilidad

Método Dual - Simplex Solución NO Factible Solución Óptima Mejora Factibilidad Conserva Optimilidad

0011 0010 1010 1101 0001 0100 1011

0011 0010 1010 1101 0001 0100 1011

Dual - Simplex
Para resolver se requiere que el problema dual...