INVESTIGACION
DE OPERACIONES
“Programación Lineal: Dualidad”
Profesor: Pedro Peña Carter
Ingeniero Comercial UTFSM
MBA IEDE ESPAÑA
Facultad de Ingeniería Universidad Mayor
Dualidad
La dualidad es utilizada para transformar un modelo
cualquiera a uno que se pueda aplicar el método
simplex.
(P) Min 3x1 + 4x2 + 5x3
S.a.: x1+ 2x2 + 3x3 5
2x1 + 2x2 + x3 6
x1, x2, x3 0
Como se observa en este caso, no es posible usar el
método simplex directamente.
Dualidad
Transformamos el (P) en (D)
(D) Máx 5 π1 + 6 π 2
S.a: π1 + 2π2 ≤ 3
2π1 + 2π2 ≤ 4
3π1 + 1π2 ≤ 5
π1, π 2 0
El dual se puede resolver por método Simplex, ya
que, es un problema de Máx con restricciones ≤.
Dualidad
Primeramente, se deben agregar 3 variables de
holgura ( introducimos S1 , S2 , S3)
Min - 5π1 - 6π2
sa: π1 + 2π2 + S1 =3
2π1 + 2π2 + S2 =4
3π1 + π2 + S3 = 5
π1 , π2 0 , Si 0, i = 1, 2 y 3.
Dualidad
Primero llevo la información del formato estándar al
tablau inicial S1 3
π1 π2 S1 S2 S3 REC X B S 2 4
1 2 1 0 0 3
2 2 0 1 0 4 S 3 5
3 1 0 0 1 5
-5 -6 0 0 0 0 1 0
XD
2 0
3 4 5
Entra Y a la base, sale el Min , , 1.5
2 2 1
esto nos indica que sale S1. En este caso el 2, que es la
intersección de fila y columna es el pivote. Se debe
multiplicar por 1/2 dicha fila.
Dualidad
π1 π2 S1 S2 S3 REC
Lo que resulta será: 1/2 1 1/2 0 0 3/2
- 2 - - - -
- 1 - - - -
- -6 - - - -
Luego se debe dejar ceros bajo 1. Por lo cual, se utilizarán
operaciones elementales de matrices para lograr el objetivo. En este
caso, se debe multiplicar la Fila 1 por -2 y sumar a la Fila 2 y
multiplicar la Fila 1 por -1 y sumar a la Fila 3 respectivamente,
además se debe multiplicar la Fila 1 por 6 y sumar a la fila 4
π1 π2 S1 S2 S3 REC
1/2 1 1/2 0 0 3/2
1 0 -1 1 0 1
5/2 0 -1/2 0 1 7/2
-2 0 3 0 0 9
Dualidad
Luego debo continuar porque aún hay un costos
reducido negativo. S1 40
π1 π2 S1 S2 S3 REC X B S 2 10
1/2 1 1/2 0 0 3/2
1 0 -1 1 0 1 2 30
5/2 0 -1/2 0 1 7/2
-2 0 3 0 0 9 1 0
XD
S 3 0
3/ 2 1 7 / 2
Min , , 1
Entra X a la base, sale el (1 / 2) 1 (5 / 2)
esto nos indica que sale S2. En este caso el 1, que es la
intersección de fila y columna es el pivote.
Dualidad
Lo que resulta será: π1 π2 S1 S2 S3 REC
1/2 - - - - -
1 0 -1 1 0 1
5/2 - - - - -
-2 - - - - -
Luego se debe dejar ceros sobre el 1 y bajo el. Por lo cual, se
utilizarán operaciones elementales de matrices para lograr el
objetivo. En este caso, se debe multiplicar la Fila 2 por -1/2 y sumar
a la Fila 1, luego se debe multiplicar la Fila 2 por -5/2 y sumar a la
Fila 3, además se debe multiplicar la Fila 2 por 2 y sumar a la fila 4
S3 1
π1 π2 S1 S2 S3 REC
0 0 1 -1/2 0 1 X B 1 1
1 0 -1 1 0 1 2 1
0 1 2 -5/2 1 1
0 0 1 2 0 11 S1 0
XD
S 2 0
Dualidad
X Y S1 S2 S3 REC
0 0 1 -1/2 0 1
1 0 -1 1 0 1
0 1 2 -5/2 1 1
0 0 1 2 0 11
La solución dual es π1 = 1; π2 = 1. Debe quedar claro que la solución
dual son los precios sombras del primal y los precios sombras del Dual
lo valores óptimos del (P), en este caso x1 = 1, x2 =2 y x3 = 0
Z(D)(1,1,1) = 5x1 +6x1= 11 = Z(P)(1,2,0) = 3x1 + 4x2 + 5x0 = 11
Dualidad
En términos mas generales :
n m
P) Min c x
j 1
j j
D) Máx b
i 1
i i
n m
sa : a x
j 1
ij j bi i 1,2,..., n sa : a ij i cj j 1,2,..., n
i 1
xj 0 j 1,2,..., m i 0 i 1,2,..., m
Dualidad
Dualidad
Lo que se puede expresar en forma matricial como:
P) Min cT x
S.a.: Ax ≥ b
x0
D) Máx bT
sa: AT ≤ c
0
Dualidad
Holgura complementaria:
complementaria
(P) Mín z = cj . xj (D) Máx w = yi . bi
s.a αi xj ≥ bi s.a. βj y ≤ cj
xj≥ 0 yi ≥ 0
Sean x* e y* soluciones factibles para los problemas (P) y (D)
respectivamente, x* e y* son óptimos, ssi:
(αi . x* - bi) . yi = 0, con i = 1,…..,m.
(ci – y* . βj) . xj = 0, con j = 1,…..,n.
Dualidad
Holgura complementaria:
complementaria
La holgura complementaria me permite construir
a partir de una solución básica factible óptima
del dual o del primal, la solución del primal o
dual , respectivamente, usando las formulas
anteriores y respetando los principios
matemáticos básicos.
Dualidad
Holgura complementaria:
complementaria
Analicemos con el mismo ejemplo visto
anteriormente.
(P) Min 3x1 + 4x2 + 5x3 (D) Máx 5 π1 + 6 π2
S.a.: x1+ 2x2 + 3x3 5 S.a: π1 + 2π2 ≤ 3
2x1 +2x2 + x3 6 2π1 + 2π2 ≤ 4
x1, x2, x3 0 3π1 + 1π2 ≤ 5
π1, π2, π3 0
Supongamos que nos piden hallar la solución del dual, conociendo la
solución óptima del primal (1 , 2 , 0) y sin tener que resolver por
método simplex el problema.
Dualidad
Como x1= 1; x2= 2 y x3= 0, las ecuaciones
quedarán.
( x1 + 2x2 + 3x3 – 5) π1 = 0 (1 + 4 + 0 – 5 ) π1 = 0; (0)π1 = 0, π1 є IR.
(2x1 + 2x2 + x3 – 6) π2 = 0 (2 + 4 + 0 – 6 ) π2 = 0; (0)π2 = 0, π2 є IR.
Como x1= 1; x2= 2 y x3= 0, las ecuaciones
quedarán.
( π1 + 2π2 – 3) x1 = 0 ( π1 + 2π2 - 3) x 1 = 0; π1 + 2π2 = 3
(2π1 + 2π2 – 4) x2 = 0 (2π1 + 2π2 – 4) x 2 = 0; 2π1 + 2π2 = 4
(3π1 + π2 – 5) x3 = 0 (3π1 + π2 – 5) x 0 = 0; No se cumple.
Finalmente, resolviendo el sistema de ecuaciones
π1 =1 y π2=1
Dualidad
Considere el siguiente problema de Programación Lineal:
Max 10x1 + 24 x2 + 20 x3 + 20 x4 + 25 x5
s.a. x1 + x2 + 2 x3 + 3 x4 + 5 x5 ≤ 19
2 x1 + 4 x2 + 3 x3 + 2 x4 + x5 ≤ 57
x1, x2 , x3 , x4 , x5 ≥ 0
Escriba el problema dual y verifique que (λ1,λ2) = (4,5) es
una solución factible. Usando esta información deduzca una
solución óptima.
Dualidad
MIN 19 1 57 2
1 2 2 10 4 2 x5 14 10
1 4 2 24 4 4 x5 24 24
2 1 3 2 20 2 x 4 3 x5 23 20
3 1 2 2 20 3 x 4 2 x5 22 20
5 1 2 25 5 x 4 5 25 25
1, 2 0
Dualidad
( X1 + X2 + 2X3+3X4+5X5 -19) π1 = 0
(2X1 + 4X2 + 3X3 +2X4 +X5 - 57) π2 = 0
( π1 + 2π2 – 10) x1 = 0 para (π1 , π2)= (4,5) - x1 = 0
( π1 + 4π2 – 24) x2 = 0 para (π1 , π2)= (4,5) - x2 ≠ 0
( 2π1 + 3π2 – 20) x3 = 0 para (π1 , π2)= (4,5) - x3 = 0
( 3π1 + 2π2 – 20) x4 = 0 para (π1 , π2)= (4,5) - x4 = 0
( 5π1 + π2 – 25) x5 = 0 para (π1 , π2)= (4,5) - x5 ≠ 0
( 0 + X2 + 2*0+ 3*0+5X5 -19) *4 = 0
(2x0 + 4X2 + 3x0 +2*0 +X5 - 57) *5 = 0
X2= 14 y X5 = 1, la solución (0, 14, 0, 0, 1)
Z(D) = Z (4,5) = 361= Z(0, 14, 0, 0, 1)
