UNIVERSIDAD TECNOLGICA DEL PER
UNIVERSIDAD TECNOLGICA DEL PER
Facultad de Ingeniera Industrial y de Sistemas
Curso: Optimizacin de Sistemas
Profesor : Ing. Mario Cieza C
Ciclo 2011 III Ing. Indust/Sistemas
Fecha :Enero 2012TEMA: DUALIDAD
El concepto de dualidad tiene un rol muy importante, no solo en
programacin lineal, sino en teora de optimizacin en general.
Todo programa matemtico, lineal o no lineal, existe asociado con
otro llamado programa dual. En particular, todo programa lineal
tiene su correspondiente programa dual.
PROGRAMAS PRIMAL Y DUAL
Considerando el programa lineal definimos el Programa Primal de
la siguiente manera:
En forma cannica:Maximizar Zx = c1X 1 + c2 X2 +.......+ cj xj
+.........+ cnxn s.a.:
a11X 1 + a12 X2 +.........+ a1j xj +.........+ a1nxn =
cj.................................................................................................................
a1n y1 + a2n y2 +.........+ ain yi +.........+ amn ym >=
cn
yi >= 0
Con representacin Matricial:
PRIMAL
Se define el:
DUAL
X1
y1
X2
y2Max Zx = C1,C2.Cj. Cn * .
Min Zy = b1,b2.bj. bm * .
Xj
yi
.
.
Xn
yms.a.:
s.a.:
a11, a12.a1j..a1n x1 b1
a11, ..ai1..am1 y1 c1 . . . .
. .
. . . . . . . . .
. .
. . . . . ai1, ai2..aijain * xj= c j . . . .
. .
. . . . . . . . .
. .
. . . . . am1, am2amj..amn xn bm
a1n, ..ain.amn ym cnCon representacin Simblica:
PRIMAL
Se define el:
DUAL
Max Zx = c * X
Min Zy = b * y
s.a.:
s.a.:
A * X = c
X >= 0
y >= 0Donde:
c : Vector n componentes
c: Vector traspuesto de c
X: ,, n ,,
y: ,, m componentes
b: ,, m componentes
b: ,, traspuesto de b
A: Matriz (mxn)
A: Matriz traspuesta de A (nxm)De acuerdo a las definiciones
dadas, cada Primal tiene su Dual, cambiando c por b y minimizando
en vez de maximizar. Se cambi el sentido de la desigualdad y se
hizo la trasposicin de la matriz. Luego podemos deducir las
siguientes:Propiedades Primal Dual:
a) La funcin econmica o funcional Zx, del Programa Primal est
dado por:
Zx = c1X 1 + c2 X2 +.......+ cj xj +.........+ cnxn
Las restricciones del Dual, estn dadas por:
a1j y1 + a2j y2 +..........+ aij yj +.........+ amj ym >=
ciEl Primal tiene n variables (X 1, X 2..... X n); mientras que el
Dual tiene n restricciones. Por lo tanto a cada variable del Primal
corresponde una restriccin en el Dual
b) El Primal tiene m restricciones, mientras que el Dual tiene m
variables ( y1, y2 ...... ym); por
lo tanto a cada restriccin del primal le corresponde una
variable en el dual.
c)En el primal, el objetivo es maximizar el funcional Zx,
mientras que en el Dual, el objetivo es minimizar el funcional
Zy
d)El rol del vector c en el Primal, corresponde al rol de b del
programa Dual y viceversa
e)A todo programa lineal Primal corresponde un programa
Dual.
f) El Dual del Dual es el Primal.
Ejemplo 1: Hallar el Dual del siguiente programa:
Max Z = 4X1 + 3X2
s.a.:
X1 + 5X2 = 4
5 y1 + 3 y2 >= 3
y1, y2 >=0
Ejemplo 2:
Max Z = 7 X1 + 2 X3 + 3 X3
s.a.:
X1 + 8X2 + 9X3 = 3
yi >= 0 ( i = 1....4 )
Ejemplo 3:
Max Z = 4 X1 + 3X2
s.a.:
9X1 + 7 X2 = 3
y1, y2, y3 >=0
Primer Lema de dualidad
Si Xo es una solucin factible y ptimo del Primal, yo es una
solucin factible ptima del Dual
Segundo Lema de dualidad
Al obtener el ptimo del dual, hemos encontrado el ptimo del
primal
Tercer Lema de dualidad
Los coeficientes de las variables libres de la funcin Z final en
la tabla Simplex, son los valores ptimos del problema dual. As por
ejemplo en el programa:
Primal:
Dual:
Max Z = 3X1+5X2
Min Zy = 4 y1 + 6 y2 + 18 y3
s.a.:
s.a.:
X1 = 3
X2 = 5
3X1+ 2X2 = 0
y1, y2 >= 0
La ltima Tabla Simplex nos da
la tabla de solucin ptima sgte:
Zj + + 3 X4 + X5 = 36
Z + 0 X3 + 3X4 + X5 = 36
X3 + 2/3 X4 1/3 X5 = 2
X2 + X4 = 6
X1 2/3 X4 + 1/3 X5 = 2
Los coeficientes de las variables libres introducidas X3, X4, X5
de la Z final son los valores ptimos en la Funcin Objetivo Dual
As para:
X3 = 0
X4 = 3 Luego: Min Zy = 4 y1 + 6y2 + 18 y3
= 4*0 + 6*3 + 18*1 X5 = 1
= 36Es decir que una vez solucionado uno de los problemas
(primal o dual), tenemos la respuesta para el otro problema.
Podemos entonces graficar las:Relaciones Primal Dual:
Primal
+
Dual
Mx. Z x = Cj Xj
Min Z = bi yi
Soluciones no factibles,
Soluciones factibles, no optimas
mejor que optima
( + )
(bi = -)
+
Zx
Min Zy
Zy
Max Zx
Soluciones factibles,
Soluciones no factibles,
pero no optimas
mejor que optima
( + )
(bi = -)
-
Formas especiales de presentacin del Primal y del Dual
Caso 1.- Si el programa primal es uno expresado en forma
estandarizada Pe. En expresin matricial:
Max. Zx = c x
s.a.:
A x 0Siendo:
c : vector de n componentes, c : traspuesta de c
x : vector de n componentes
b : vector de m componentes, b traspuesta de b
A : matriz de orden m x n , A : transpuesta de A
y : vector de m componentes y sin restricciones de signo
Caso 2.- Si el programa primal es uno expresado en forma
estandarizada Pe. En expresin matricial:
Max. Zx = c x
s.a.:
A x = b
x 0
Tiene el dual dado por De:
Min Zy = b y
s.a.:
A y c
y sin restriccin de signo
Siendo:
c : vector de n componentes
x : vector de n componentes
b : vector de m componentes
A : matriz de orden m x n , A : transpuesta de A
y : vector de m componentes y sin restricciones de signo
Ejemplo: hallar el dual del sgte. Programa:
Max Zx = 4
+ 3+ 5
s.a.:
+ + = 10
2+ 7+ = 50
4+ + 3= 80
+ 2+ 7= 100
, ,
EMBED Equation.3 0
Solucin: El dual ser:
Min Zy = 10 + 50 + 80 + 100
s.a.:
+ 2+ 4 + 4
+ 7+ + 2 3
+ + 3 + 7 5
: sin restricciones de signo, (= 1....4)
Caso 3.- Si el programa primal P es uno expresado, como:
Max Zx = c x
s.a.
A x < b (x : sin restriccin de signo)
Tiene el dual D, expresado como:
Min Zy = b y
s.a. :
A y = c
x > 0
Ejemplo: Hallar el dual del siguiente programa:
Max Zx = 4+ 7+ 8
s.a.:
4+ 2+ =
i-sima variable s/r signo i-sima restriccin: =
i-sima variable Xi
