Problema Primal e Dual em Pesquisa Operacional

Prévia do material em texto

INF 280- Pesquisa Operacional
Problema Dual
Departamento de Informática – DPI
Prof. Renan José dos Santos Viana
CCE 303-B
renanjviana@gmail.com
Baseado no material produzido pelo prof. José Elias C. Arroyo
Problema Primal e Dual
 O problema dual é um problema de PL definido diretamente
e sistematicamente de acordo com o problema de PL primal
(original).
 Os dois problemas guardam uma relação tão estreita que a
solução ótima de um problema fornece automaticamente a
solução ótima do outro.
 Para todo modelo de PL (primal) existe um modelo dual
correspondente.
 O dual do modelo dual é o próprio primal.
Problema Primal e Dual
 O modelo dual é construído da seguinte forma:
• Seja um modelo primal de maximização com todas as restrições ≤, o
modelo dual é de minimização com todas as restrições ≥.
• Para cada restrição do primal existe uma variável no dual (e vice-
versa).
• Os termos independentes (lado direito) do primal são coeficientes da
função objetivo do dual (e vice-versa).
• A matriz de coeficientes das restrições do primal é a transposta da
matriz de restrição do dual (e vice-versa).
Problema Primal e Dual
Primal
Max f(x) = 20x1 + 24x2
S.a.
2x1 + 3x2 ≤ 12
2x1 + 1x2 ≤ 8
x1  0, x2  0
Problema Primal e Dual
Primal
Max f(x) = 20x1 + 24x2
S.a.
2x1 + 3x2 ≤ 12
2x1 + 1x2 ≤ 8
x1  0, x2  0
Dual
Min g(u) = 12u1 + 8u2
S.a.
2u1 + 2u2  20
3u1 + u2  24
u1  0, u2  0
Problema Primal e Dual
Primal
Max f(x) = 30x1 + 20x2 + 50x3
S.a. x1 + x2 + x3 ≤ 18
2x1 + x2 + 2x3 ≤ 30
x1 + x2 + 2x3 ≤ 24
x1  0, x2  0, x3  0
Problema Primal e Dual
Primal
Max f(x) = 30x1 + 20x2 + 50x3
S.a. x1 + x2 + x3 ≤ 18
2x1 + x2 + 2x3 ≤ 30
x1 + x2 + 2x3 ≤ 24
x1  0, x2  0, x3  0
Dual
Min g(u) = 18u1 + 30u2 + 24u3
S.a. u1 + 2u2 + u3  30
u1 + u2 + u3  20
u1 + 2u2 + 2u3 50
u1  0, u2  0, u3  0
Problema Primal e Dual
 Note, que as variáveis de decisão são ≥ 0 tanto no primal
quanto no dual.
 Exceções:
• Em um modelo max as restrições são normalmente ≤; restrições ≥ em
modelo max geram variáveis duais ≤ 0.
• Em um modelo min as restrições são normalmente ≥; restrições ≤ em
modelo min geram variáveis duais ≤ 0.
• Restrições = (igualdade) geram variáveis irrestritas, (e vice-versa).
Problema Primal e Dual
Primal
Max f(x) = 5x1 + 4x2
S.a. 6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x1 - x2  2
x2 ≤ 2
x1  0, x2  0
Problema Primal e Dual
Primal
Max f(x) = 5x1 + 4x2
S.a. 6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x1 - x2  2
x2 ≤ 2
x1  0, x2  0
Dual
Min g(u) = 24u1 + 6u2 + 2u3 + 2u4
S.a. 6u1 + 1u2 + 1u3 + 0u4  5
4u1 + 2u2 - u3 + u4  4
u1, u2, u4  0, u3 ≤ 0
Problema Primal e Dual
Primal
Max f(x) = 5x1 + 4x2
S.a. 6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ -2
x2 ≤ 2
x1  0, x2  0
Problema Primal e Dual
Primal
Max f(x) = 5x1 + 4x2
S.a. 6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ -2
x2 ≤ 2
x1  0, x2  0
Dual
Min g(u) = 24u1 + 6u2 -2u3 + 2u4
S.a. 6u1 + 1u2 - 1u3 + 0u4  5
4u1 + 2u2 + u3 + u4  4
u1, u2 , u3, u4  0
Problema Primal e Dual
 Na prática, muitos problemas de Programação Linear contêm
restrições do tipo ≤, ≥ ou =.
 Além disso, podem existir variáveis livres (irrestritas de sinal)
ou variáveis negativas.
 Regras para construir o Dual de qualquer problema de
Programação Linear:
Problema de 
Maximização
Problema de 
Minimização
Variáveis
 0  
Restrições 0  
Livre  =
Restrições
   0
Variáveis   0
=  Livre
Problema Primal e Dual
Primal
Max f = 5x1 + 2x2
s. a: x1 ≤ 3
x2 ≤ 4 
x1 + 2x2 ≤ 9 
x1  0, x2  0
Problema Primal e Dual
Primal
Max f = 5x1 + 2x2
s. a: x1 ≤ 3
x2 ≤ 4 
x1 + 2x2 ≤ 9 
x1  0, x2  0
Max f = 5x1 + 2x2 + 0x3+ 0x4+ 0x5
S.a. x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 + x5 = 9
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.
Problema Primal e Dual
Primal
Max f = 5x1 + 2x2
s. a: x1 ≤ 3
x2 ≤ 4 
x1 + 2x2 ≤ 9 
x1  0, x2  0
Dual
Min g = 3y1 + 4y2 + 9y3
S.a. y1 + y3 ≥ 5
y2 + 2y3 ≥ 2
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Max f = 5x1 + 2x2 + 0x3+ 0x4+ 0x5
S.a. x1 + x3 = 3
x2 + x4 = 4
x1 + 2x2 + x5 = 9
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.
Problema Primal e Dual
Primal
Max f = 3x1 + 2x2 + x3 + 6x4 + 5x5 + 4x6
S.a. 
x1 + x2 + x3 = 10
x4 + x5 + x6 = 15
3x1 + 2x2 + x4 + 3x5 ≤ 20
x1 + x3 + 2x4 + x6 ≤ 30
x1, x2, x3  0; x4, x5 e x6 livres 
Problema Primal e Dual
Dual
Min g = 10y1 + 15y2 + 20y3 + 30y4
s.a.
y1 + 3y3 + y4  3
y1 + 2y3  2
y1 + y4  1
y2 + y3 + 2y4 = 6
y2 + 3y3 = 5
y2 + y4 = 4
y3  0, y4  0; y1 e y2 livres.
Problema Primal e Dual
 Par primal - dual 
Primal
Max f = cx
S.a.
Ax ≤ b
x ≥ 0
Dual
Min g = yb
S.a.
yA ≥ c
y ≥ 0
Problema Primal e Dual
 Propriedades do par primal - dual 
1) Se x e y são soluções viáveis do problema primal
e dual, respectivamente, então f(x)  g(y).
2) Se x* e y* são soluções viáveis do problema
primal e dual, respectivamente, tal que f(x*) =
g(y*), então ambas são soluções ótimas dos
correspondentes problemas.
* *
F.O.DualF.O. Primal
j j i i
j i
c x b y 
Problema Primal e Dual
 Teorema da existência
Para um par de problemas primal x dual, apenas uma
das situações é possível:
• Ambos possuem solução ótima finita (nesse caso são
iguais).
• Um tem solução ótima ilimitada e o outro não tem solução
viável.
• Nenhum dos problemas tem solução.
Problema Primal e Dual
Propriedade
Suponha que x e y sejam soluções ótimas dos
modelos primal e do dual, respectivamente.
g(y) = yb
f(x) = cx = cBxB + cNxN , xN = 0, 
f(x) = cBxB
f(x) = cBB
-1b
Se g(y) = f(x) então, yb = cBB
-1b
 y = cBB
-1 vetor multiplicador simplex
Problema Primal e Dual
Tabela simplex do primal:
xB xN
-f 0 cj – cBB
-1aj – cBB
-1b
xB I B
-1N B-1b
Custos reduzidos:
zj = cj – cBB
-1aj,  j índice das variáveis não-básicas
zj = cj – yaj
onde y é o vetor multiplicador simplex
(variável do Dual)
Problema Primal e Dual
A seguinte propriedade permite determinar a solução ótima de
um dos problemas (primal ou dual) quando a solução ótima do
outro é conhecida.
Propriedade (Folgas complementares)
As soluções xRn e yRm são ótimas do modelo primal e do
modelo dual, respectivamente, se e somente se:
Ax + s = b, x ≥ 0 (x é variável primal, s variáveis de folga)
ATy + w = c, y ≥ 0 (y é variável dual, w variáveis de folga)
wj xj = 0, j = 1,…,n (folgas complementares)
sj yj = 0, j = 1,…,m (folgas complementares)
Problema Primal e Dual
Exemplo. Considere os problemas Primal e Dual
Primal:
Seja a solução ótima do primal:
x1 = 9, s1 = 5, x2 = s2 = 0, f = 27.
Max f = 3x1 – 4x2
S.a. x1 + x2 ≥ 4
2x1 + 3x2 ≤ 18
x1 ≥ 0 x2 ≥ 0
Dual:
Min g = 4y1 +18y2
S.a. y1 + 2y2 ≥ 3
y1 + 3y2 ≥ -4 
y1 ≤ 0, y2  0
Max f = 3x1 – 4x2 + 0s1 + 0s2
s.a: x1 + x2 – s1 = 4
2x1 + 3x2 + s2 = 18
x1, x2, s1, s2  0
Min g = 4y1 +18y2
S.a. y1 + 2y2 – w1 = 3
y1 + 3y2 – w2 = -4
y1 ≤ 0, y2, w1, w2  0
Problema Primal e Dual
Problema Primal e Dual
Solução ótima do primal:
x1 = 9, s1 = 5, x2 = s2 = 0, f = 27.
Busquemos a solução ótima do dual:
g = 27
wj xj = 0, sj yj = 0 (folgas complementares)
w1 x1 = 0  w1 = 0 (pois, x1 = 9 > 0)
s1 y1 = 0  y1 = 0 (pois, s1 = 5 > 0)
De: y1 + 2y2 – w1 = 3  2y2 = 3  y2 = 1,5 
 w2 = 8,5
Dual:
Min g(y) = 4y1 + 18y2
s. a: y1 + 2y2 – w1 = 3y1 + 3y2 – w2 = -4 
y1 ≤ 0, y2  0, w10, w20 
Problema Primal e Dual
Relação de Variáveis
Problema Primal Relação Problema Dual
 Variável original
 Variável de folga
 Variável Básica
 Variável Não-básica




 Variável de folga
 Variável original
 Variável Não-básica
 Variável Básica
Problema Primal e Dual
Primal:
Max f = 5x1 + 2x2
S.a.
x1  3
x2  4
x1 + 2x2  9
x1, x2  0.
Max f = 5x1 + 2x2
S.a.
x1 + 0x2 + s1 + 0s2 + 0s3 = 3
0x1 + x2 + 0s1 + s2 + 0s3 = 4
x1 + 2x2 + 0s1 + 0s2 + s3 = 9
x1, x2, x3, s1, s2, s3,  0
Dual:
Min g = 3y1 + 4y2 + 9y3
S.a.
y1 + y3  5
y2 + 2y3  2
y1, y2, y3  0
Min g = 3y1 + 4y2 + 9y3
S.a.
y1 + 0y2 + y3 – w1 + 0w2 = 5
0y1 + y2 + 2y3 + 0 w1 – w2= 2
y1, y2, y3,w1, w2  0
Problema Primal e Dual
xB x1 x2 s1 s2 s3
-f 0 0 -4 0 -1 -21
x1 1 0 1 0 0 3
s2 0 0 1/2 1 -1/2 1
x2 0 1 -1/2 0 1/2 3
w1 w2 y1 y2 y3
Tabela ótima do primal:
xB = (x1, s2, x2) xN = (s1, s3)
xB = (3, 1, 3)
yB = (y1, y3) yN = (w1, y2, w2)
yB = (4, 1)
g = f = 21
Problema Primal e Dual
Modelo Primal Modelo Dual
Problema Primal e Dual
Modelo Primal Modelo Dual
Problema Primal e Dual
Modelo Primal Modelo Dual
Problema Primal e Dual
Modelo Primal Modelo Dual
Problema Primal e Dual
Modelo Primal Modelo Dual
Inspiração para o Método Dual Simplex
Modelo Dual
Max g = 30u1 + 20u2 + 50u3
S.a. 
u1 + u2 + u3 <= 18
2u1 + u2 + 2u3 <= 30
u1 + u2 + 2u3 <= 24
u1, u2, u3 >= 0
Seu dual, entretanto, pode ser
resolvido diretamente pelo
Simplex comum.
Modelo Primal
Min z = 18x1 + 30x2 + 24x3
S.a. 
x1 + 2x2 + x3 >= 30
x1 + x2 + x3 >= 20
x1 + 2x2 + 2x3 >= 50
x1, x2, x3 >= 0
Simplex requer variáveis
artificiais, 2 fases, ...
Inspiração para o Método Dual Simplex
 O quadro do modelo primal apresenta uma solução inviável.
 Já no quadro do modelo dual, u3 entra na base e g3 sai.
 Pela complementaridade de folga, no quadro do modelo primal:
 Sai f3 (u3 deixara de ser zero, então f3 deverá ser zero).
 Entra x3 (g3 será zero, então x3 é livre para ser >= 0).
Inspiração para o Método Dual Simplex
 No quadro do modelo dual, u1 entra na base e g2 sai.
 Pela complementaridade de folga, no quadro do modelo primal:
 Sai f1 (u1 deixara de ser zero, então f1 deverá ser zero).
 Entra x2 (g2 será zero, então x2 é livre para ser >= 0).
Inspiração para o Método Dual Simplex
 Dual chegou na solução ótima.
 Primal chegou em uma solução viável (e ótima).
 A correspondência entre os quadros gera o método dual simplex.
Dúvidas
Problema Primal e Dual
Resolva o seguinte modelo:
Min 12x1 + 18x2 + 20x3
S.a. 
2x1 + 4x2 + 2x3 >= 20
3x1 + 4x2 + 4x3 >= 24
x1, x2, x3>=0
Problema Primal e Dual
O seguinte modelo foi resolvido pelo LINDO
Min 12x1 + 18x2 + 20x3
S.a. 
2x1 + 4x2 + 2x3 >= 20
3x1 + 4x2 + 4x3 >= 24
x1, x2, x3>=0
OBJECTIVE FUNCTION VALUE
1) 102.0000
VARIABLE VALUE REDUCED COST
X1 4.000000 0.000000
X2 3.000000 0.000000
X3 0.000000 5.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 -1.500000
3) 0.000000 -3.000000
NO. ITERATIONS= 2
Determine a solução do modelo Dual (valores de todas as variáveis)