Pesquisa Operacional e Dualidade

Prévia do material em texto

Extra
D-1
PESQUISA OPERACIONAL I 
– O DUAL EXTRA
Primal
min f = 3*x1 + 4*x2 + 9*x3
s/a x1 + x3 >= 5
3*x2 + x3 = 8 xi>= 0
min f = 3*x1 + 4*x2 + 9*x3
s/a x1 + x3 >= 5
3*x2 + x3 >= 8
3*x2 + x3 <= 8 xi>= 0
min f = 3*x1 + 4*x2 + 9*x3
s/a x1 + x3 >= 5 w1
3*x2 + x3 >= 8 w2’
-3*x2 - x3 >= -8 w2’’ xi>= 0
Dual
max Q = 5*w1 + 8*w2’ - 8*w2’’
s/a w1 <= 3
3*w2’ - 3*w2’’ <= 4
w1 + w2’ - w2’’ <= 9 wi >= 0
max Q = 5*w1 + 8*(w2’ - w2’’)
s/a w1 <= 3
3*(w2’ - w2’’) <= 4
w1 + (w2’ - w2’’) <= 9 wi >= 0
max Q = 5*w1 + 8*w2
s/a w1 <= 3
3*w2 <= 4
w1 + w2 <= 9 w1>= 0 w2 livre
w2 = w2’ – w2’’
Dualidade
Dualidade
D-2 max
<=
min
>=
=
Exercício
Primal
max f = 3*x1 + 5*x2
s/a x1 <= 4
x2 <= 6
3*x1 + 2*x2 <= 18
x1>= 0 x2 livre
max f = 3*x1 + 5*x2’ - 5*x2’’
s/a x1 <= 4 w1
x2’ - x2’’ <= 6 w2
3*x1 + 2*x2’ - 2*x2’’ <= 18 w3
xi>= 0 
Dual
min Q = 4*w1 + 6*w2 + 18*w3
s/a w1 + 3*w3 >= 3
w2 + 2*w3 >= 5
-w2 - 2*w3 >= -5 wi >= 0
min Q = 4*w1 + 6*w2 + 18*w3
s/a w1 + 3*w3 >= 3
w2 + 2*w3 >= 5
w2 + 2*w3 <= 5 wi >= 0
min Q = 4*w1 + 6*w2 + 18*w3
s/a w1 + 3*w3 >= 3
w2 + 2*w3 = 5 wi >= 0
Dualidade
Dualidade
D-3
max
<=
min
>=
x2 = x2’ – x2’’
=
Exercício
Dado o problema abaixo:
max f = x1 - 4*x2 + x3
s/a -x1 + x2 >= 1
-x1 + x3 <= 1
x1, x2, x3 >= 0
a) Resolver com o auxílio do método SIMPLEX Fase 1 - Fase 2.
b) Escrever o DUAL e resolver o DUAL graficamente.
Dualidade
Dualidade
D-4