Dual Simplex

El método Dual (Simplex Dual)
Asociado a todo problema de PL existe otro problema llamado Dual. Las relaciones entre problemas Dual y el original (llamado Primal) son utilidades en gran variedad deproblemas. Reduce el esfuerzo de computo en ciertos problemas y obtiene información adicional sobre las variaciones optimas.
Características:
1. El problema primal busca maximizar y el problemadual minimizar.
2. El problema de maximización posee restricciones de tipo menor o igual que, mientras que el de minimización es mayor o igual que.
3. Los elementos de lado derecho de lasrestricciones del primal son iguales a los coeficientes de la función objetivo del dual.
4. Cada restricción del primal corresponde a una variable del dual y viceversa.
5. Las variables para ambosproblemas son no negativas.
Primal (original)
Max X0 = AX1 + BX2
s.a.:
CX1 + DX2 ≤ E
FX1 + GX2 ≤ H
Xi ≥ 0

Dual (problema asociado)
Min Y0 = EY1 + HY2
s.a.:
CY1 + FY2 ≥ A
DY1 + GY2 ≥ BYi ≥ 0

EJEMPLO:
Primal (original)
Max X0 = 3X1 + 5X2
s.a.:
X1 ≤ 4
2X2 ≤ 12
3X1 + 2X2 ≤ 18
Xi ≥ 0E
Dual (problema asociado)
Min Y0 = 4Y1 + 12Y2 + 18Y3
s.a.:
Y1 + 3Y3 ≥ 3
2Y2 + 2Y3 ≥ 5Yi ≥ 0

EJEMPLO
F.O.
Primal (original)
Max X0 = X1 + X2
s.a.:
0.2X1 + 0.08X2 ≥ 0.5
100X1 + 150X2 ≥ 150
Xi ≥ 0
Dual (problema asociado)
Min Y0 = 0.5Y1 + 150Y2
s.a.:
0.2Y1 + 100Y2 ≤ 10.08Y1 + 150Y2 ≤ 1
Yi ≥ 0

Pasar a la forma estándar.
(I) 0.2Y1 + 100Y2 ≤ 1
(II) 0.08Y1 + 150Y2 ≤ 1
Yi ≥ 0

(I) 0.2Y1 + 100Y2 + 0S1≤ 1
(II) 0.08Y1 + 150Y2 + 0S2≤ 1
Yi, Si ≥ 0

Y0 = 0.5Y1 +150Y2 + 0S1 + 0S2
Y0 - 0.5Y1 - 150Y2 - 0S1 - 0S2 = 0
V.B. | Y0 | Y1 | Y2 | S1 | S2 | SOL |
Y0 | 1 | -0.5 | -150 | 0 | 0 | 0 |
Y1 | 0 | 0.2 | 100 | 1 | 0 | 1 |
S2 | 0 | 0.08 | 150 | 0 | 1 | 1 |Dividir S1 entre 0.2 y cambiar la variable que entra por la que sale
V.B. | Y0 | Y1 | Y2 | S1 | S2 | SOL |
Y0 | 1 | -0.5 | -150 | 0 | 0 | 0 |
Y1 | 0 | 1 | 500 | 5 | 0 | 5 |
S2 | 0 | 0.08 |...