Upload
nathalia-zandomingo
View
232
Download
0
Embed Size (px)
DESCRIPTION
Pesquisa Operacional
Citation preview
Prof. Renan José dos Santos Viana
Departamento de Informática – DPI
Sala: CCE 303-B
INF 280- Pesquisa Operacional
Problema Dual
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 DualPrimal
Max f(x) = 20x1 + 24x2
S.a.
2x1 + 3x2 ≤ 12
2x1 + 1x2 ≤ 8
x1 0, x2 0
Problema Primal e DualPrimal
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 DualPrimal
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 DualPrimal
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 são ≥ 0 no primal e também 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 DualPrimal
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 DualPrimal
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 DualPrimal
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 DualPrimal
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 DualPrimal
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 DualPrimal
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 DualDual
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 = bTy
S.a.
ATy ≥ 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 DualPropriedade
Suponha que x e y sejam soluções ótimas dos
modelos primal e do dual, respectivamente.
g(y) = by = yTb
f(x) = cx = cBxB + cNxN , xN = 0,
f(x) = cBxB
f(x) = cBB-1b
Se g(y) = f(x) então, yTb = cBB-1b
yT = cBB-1 vetor multiplicador simplex
Problema Primal e DualTabela 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 DualA 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 xRn e yRm 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 = -4y1 ≤ 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 = 3
y1 + 3y2 – w2 = -4 y1 ≤ 0, y2 0, w10, w20
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 DualPrimal:
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
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
Simplex Comum
Modelo Primal
Max -z = -18x1 - 30x2 - 24x3
S.a.
-x1 - 2x2 - x3 <= -30
-x1 - x2 - x3 <= -20
-x1 - 2x2 - 2x3 <= -50
x1, x2, x3 >= 0
Dual Simplex
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.
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 LINDOMin 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)