Dualidad

Universidad Católica del Maule.
Investigación de Operaciones – Análisis de sensibilidad..
DUALIDAD
Supongamos el siguiente problema:
F.O: Max
S.A.

�

Cj Xj

�

aij Xj � bj
Xj � 0
Para

i = 1 .. m
J= 1 .. n

Si a este problema le llamamos primal, el siguiente problema le llamamos dual del
primal anterior.
F.O: Min
S.A.

�

bi Yj

�

aji Yj � Cj
Yi � 0
Para

i = 1 .. m
J = 1 .. n

Después dehaber explicado los términos primal y dual nos preguntamos para qué
hacemos dicha distinción. La razón es que en ocasiones un problema puede simplificarse
mucho al tratar de resolver su dual y mediantelas relaciones existentes entre el priblema
primal y su dual, que posteriormente vamos a ver llegaremos a la solución buscada.
Ejemplo
F.O. Max 7X1 +2X2 + 9X3
S.A.
3X1 – 4X2 + 7X3 � 6
X1 + 3X2 + 2X3 �8
5X1 + 2X2 – 5X3 � 4
El problema dual será:
F.O. Min 6Y1 +8Y2 + 4Y3
S.A.
3Y1 + Y2 + 5Y3 � 7
-4Y1 + 3Y2 + 2Y3 � 2
7Y1 + 2Y2 – 5Y3 � 9

Preparado por Paulo A. González G.120

Universidad Católica delMaule.
Investigación de Operaciones – Análisis de sensibilidad..
Sea el problema primal:
F.O. Max 10X1 +15X2
S.A.
2X1 + 2X2 � 160
X1 + 2X2 � 120
4X1 + 2X2 � 280
Cuya solución es:
LO
L1
L2
L3

X1
0
1
00

X2
0
0
1
0

X3
5/2
1
-1/2
-3

P11
-40
3
-2

P12
-40
-1
1

X4
5
-1
1
2

X5
0
0
0
1

Bi
1000
40
40
40

El problema dual será:
F.O. Min 160Y1 +120Y2 + 280Y3
S.A.
2Y1 + Y2 + 4Y3 � 10
2Y1 + 2Y2 + 2Y3 �15
Cuya solución es:
1
2
3

B1
0
1
0

B2
0
0
1

P21
-40
½
-1

P22
-

P31
-

P32
1000
5/2
5

Observaciones:
1. Se puede observar que el resultado de la función objetivo es el mismo, tanto para elproblema primal como para el dual.
2. Los valores solución de las variables básicas del problema primal (variables de la
solución objetivo), corresponden con los coeficientes de las variables de holgura enla LO
de la tabla solución del problema dual, sólo que cambiado de signo.
Así el valor solución de la variable X1 en el problema primal es 40. X1 tiene
asociada la restricción primera del problema...