Investigacion de opraciones

Dualidad
Todo problema de PL tiene asociado una variable dual.
Las variables duales se denotan como (wi).
Las variables duales indican en cuanto aumenta la función objetivo si se cambia en unaunidad el recurso b.
Relaciones primal dual

Maximización | | Minimización |
variable | >=0 | | >= | Restricciones |
| <=0 | | <= | |
| libre | | = | |
Restricciones |<= | | >=0 | Variables |
| >= | | <=0 | |
| = | | libre | |

Ejemplo:
Prima
Max Z= 2X1 + 3X2
Sa. X1 + X2 <= 3 w1 las variables duales son el numerode restricciones.
2X2 + X2 <=4 w2
X1, X2, >=0

Cambiamos a dual. Como es un problema de maximizar lo cambiamos a minimizar de la siguiente forma:
Min Z= 3W1 + 4W2W1 + 2W2 >= 2
W1 + W2 >= 3

W1>=0
W2>=0

Ejemplo 2:

Primal

Max Z= 3X1 - 4X2 + 5X3

-3X1 + 2X2 + X3 <=1 W1
X1 - X2 - 5X3 >= -8W2

X1+X2+X 3>=0

DUAL
MIN Z= W1 - 8W2
-3W1 + W2 >= 3
2W1 - W2 >= -4
W1 - 5W2 >= 5
W1>= 0
W2<=0

EJEMPLO 3

DUAL

MIN Z= W1 - 8W2

-3W1 + W2 >=3
2W1 - W2 >= -4
W1 - 5W2 >= 5

W1>=0
W2<=0

DUAL
MAX Z = 3X1 – 4X2 + 5X3

-3X1 + 2X2 + X3 <= 1
X1 - X2 - 5X3 >= -8

X1>=0
X2>=0
X3>=0

X= aminimizar
W= a maximizar

Teorema de dualidad débil

Si X° es una solución factible para el problema primal (minimización) y W° es una solución factible del dual ( maximización) entonces:CT X >= WTb

Teorema de dualidad fuerte

Si el problema primal tiene optimo finito entonces el problema dual tiene optimo finito y viceversa. Además el valor de la función objetivo en el optimoen cada uno de los problemas será el mismo.

PRIMAL | | DUAL |
Optimo finito | | Optimo finito |
Optimo acotado | | Infactible |
Infactible | | Optimo acotado |
Infactible | |...