05 - Dualidade PPL

Prévia do material em texto

Pesquisa Operacional 
 
Dualidade em Programação Linear 
Geraldo Robson Mateus 
DCC - UFMG 
Definição 
 Dado um PPL, que é denominado de 
primal, 
 
 
 
 o problema dual do anterior é dado por 






0
 
max
x
bAx
S
xcz
p
t






0
 
min
u
cuA
S
ubs
t
d
t
Observações 
 Se o primal é de minimização, o 
dual é de maximização. 
 Os termos independentes do primal 
são os coeficientes da função 
objetivo do dual. 
 A cada restrição do primal 
corresponde a uma variável no 
dual. 
Relações 
Funcão Obj c
t
x max min max max max min
Primal Restr. Ax b b b b b b
Variáveis x 0 0 0 ñ rest. 0 0
Funcão Obj b
t
u min max min min min max
Dual Restr. A
t
u c c c c c c
Variáveis u 0 0 ñ rest. 0 0 0
 




 




 
  


Propriedade 1 
O dual do dual é o primal 
 
Seja, 
 
 
 
 
 






0
 
max
x
bAx
S
xcz
p
t






0
 
min
u
cuA
S
ubs
t
d
t
Teorema 
Se o primal tem solução viável x finita e 
o dual também tem solução viável 
finita u então: 
 
Os valores ótimos das var. duais são os 
custos marginais das restrições primal. 
Se o primal viável não tem solução 
ótima finita, então o dual é inviável. 
Se o primal é inviável então o dual não 
tem solução finita ou é inviável. 
ubxc tt 
Corolário 
Propriedade dual fraca. 
 A função objetivo do problema de 
maximização é sempre menor o igual que a 
função objetivo do problema de 
minimização para todo par de soluções 
viáveis. 
ubxc tt 
Obs. 
 Qualquer solução do problema de 
maximização é um limite inferior 
para o ótimo da função objetivo do 
problema de minimização e qualquer 
solução do problema de minimização 
é limite superior para o ótimo da 
função objetivo do problema de 
maximização. 
Propriedade 2 
Propriedade Dual forte. 
 Se x* e u* são soluções viáveis do 
primal e dual respectivamente e 
 
 
então as soluções são ótimas em seus 
respectivos problemas. 
** ubxc tt 
Teorema Folgas Complementares 
Sejam x*e u*soluções viáveis do primal e dual 
respectivamente. Então são soluções ótimas 
dos seus respectivos problemas se e somente 
se, 
0ou 0).( ****  uxuAxb f
ttt
0ou 0)( ***  xuxcAu f
ttt
Obs. 
 Se uma variável estrutural em um 
problema é não nula, a 
correspondente restrição no outro 
problema deve ser ativa (folga nula); 
e se uma restrição é não ativa em 
um problema (folga não nula), a 
correspondente variável estrutural no 
outro problema deve ser nula. 
Exemplo 
 Se num problema primal um recurso 
tem folga não nula (restrição não ativa), 
seu custo marginal (variável 
correspondente dual) é zero. 
 Se uma atividade primal tem valor não 
nulo, sua correspondente restrição dual 
é ativa (seu custo marginal é igual a sua 
contribuição marginal). 
Exemplo 
321 23max xxxz 








0 , ,
5 3
4 2
321
31
21
xxx
xx
xx











0 , 
2
3
132
21
2
1
21
uu
u
u
uu
uus 54min 1 
Problemas duais com restrições tipo 
equações 






0
 
max
x
bAx
S
xcz
p
t


 

livre 
 
min
u
cuA
S
ubs
t
d
t
Condições de Otimalidade em PL 
 Solução viável no Primal (P) 
 Solução viável no Dual (D) 
 Complementaridade de folga 
ctx = utb ou ut(b – Ax) =0 e 
 xt(Atu – c) = 0 
 Algoritmo primal, dual, primal-dual 
 
 
Método Simplex 
xB xN 
cB cN z 
B N b 
xB xN 
 0 cN - cB B
-1 N Z=cB B
-1 b 
xB I B
-1 N B-1 b 
 - cB B
-1 Z=cB B
-1 b 
xB B
-1 B-1 b 
duais variáveis-u 
básicas não variáveis- x
básicas variáveis- x
N
B
jt
j
j1-t
Bjjjj
au - c ou 
 aBc - c z-cbásica não x
reduzido Custo


Método Simplex 
1
1
1
 







Bcu
sbubBcxcz
bBx
xcxcz
t
B
tt
BB
t
B
B
B
t
B
t
Interpretação Econômica 
 
 
Dada uma solução ótima para o 
problema primal e a correspondente 
solução ótima do dual, analisá-las 
sob os aspectos econômicos 
Empresa de Exploração de Petróleo 
Uma empresa explora três tipos de 
petróleo: nacional, importado e o xisto, 
com o objetivo de atender a demanda por 
óleo e gasolina. Os parâmetros de 
referência são dados pela tabela abaixo: 
 
PN PI Xisto Demanda 
Óleo 1 2 2 5 
Gasolina 1 1 3/2 3 
Custo 8 12 15 
2 x 
5 
4 
3 
2 
1 
0 
0 1 2 3 4 5 
Solução 
Ótima 
1 x 
Solução gráfica para PN e PI 
2 y 
10 
8 
6 
4 
2 
0 
0 2 4 6 8 10 
Solução 
Ótima 
1 y 
Primal Dual 
 x1 x2 x3 x4 x5 
min 0 0 1 4 4 f(x)-32 
x2 0 1 0,50 -1 1 2 
x1 1 0 1 1 -2 1 
 y1 y2 y3 y4 y5 
max 0 0 -1 -2 0 g(y)-32 
y2 0 1 2 -1 0 4 
y1 1 0 -1 1 0 4 
y5 0 0 -1 -0,5 1 1 









0 , ,
32311
5221
 
15128)(min 
321
321
321
321
xxx
xxx
xxx
xxxxf












0 ,
15232
1212
811
 
35)(max 
21
21
21
21
21
yy
yy
yy
yy
yyyg
Problema da Dieta 
 Um nutricionista precisa 
estabelecer uma dieta 
contendo, pelo menos, 10 
unidades de vitamina A, 30 de 
vitamina B e 18 de vitamina C, 
que estão contidas em 
quantidades variadas em cinco 
alimentos (tabela). O custo 
unitário de cada alimento é: 4, 
2, 1,10 e 5. A quantidade de 
A2 mais A3 tem de superar A4. 
Se usar A1 tem de usar A3. A1 
≥ 2 ou A5 ≥ 3. Qual é a dieta 
de menor custo. 
 
A1 A2 A3 A4 A5 
A 0 1 5 4 3 
B 2 1 0 3 2 
C 3 1 0 9 0