aula22 - DMA - Universidade Federal de Viçosa

MAT 475
Tópicos em Matemática Aplicada
Lana M. R. dos Santos
Departamento de Matemática
Universidade Federal de Viçosa
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: métodos de solução
Seja o Problema de Programação Inteira P:
z = max{cx : x ∈ X}, em que X = {x ∈ Zn+ : Ax ≤ b}
Como determinar uma solução factı́vel para P?
Como provar que uma dada solução factı́vel é ótima?
. Usando limitantes primais e duais
limitante primal (inferior): usar heurı́sticas,
meta-heurı́stiscas, arredondamento da solução fracionária etc.
limitante dual (superior): mudar a formulação, fazer
relaxações do modelo, resolver o problema dual, inserir restrições
adicionais (desigualdades válidas) para eliminar soluções fracionárias
da relaxação linear do modelo etc.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
Seja o Problema de Programação Inteira P:
z = max{cx : x ∈ X}, em que X = {x ∈ Zn+ : Ax ≤ b}
Definição (Relaxação)
Seja o problema (PR ) zR = max{zR (x) : x ∈ XR }. Diz-se que PR é
uma relaxaç~
ao do problema P se:
(i) X ⊂ XR
(ii) cx ≤ zR (x), ∀x ∈ X.
Definição (Relaxação linear)
Seja o poliedro P = {x ∈ Rn+ : Ax ≤ b} uma formulação para P. Então
zL = max{cx : x ∈ P } é dita uma relaxação linear de P.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
Seja o problema (PR ) zR = max{zR (x) : x ∈ XR } uma relaxação do
problema (P) z = max{cx : x ∈ X}.
Proposição
(i) Se PR é infactı́vel, então P é infacı́vel.
(ii) Se P é factı́vel e x∗ ∈ X é uma solução ótima de P, então z ≤ zR .
(iii) Se P é ilimitado, então PR é ilimitado.
Demonstração.
(i) Se PR é infactı́vel então X ⊂ XR = ∅.
(ii) Como x∗ ∈ X, pela condição (ii) da definição de relaxação,
z = cx∗ ≤ zR (x∗ ). Como X ⊂ XR , por definição de ótimo global,
zR (x∗ ) ≤ zR . Logo, z ≤ zR .
(iii) Imediato pelo fato de X ⊂ XR e cx ≤ zR (x), ∀x ∈ X.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. Pergunta: Quais relaxações são interessantes?
Relaxações devem ser significativamente mais tratáveis que o
modelo original.
Relaxações devem fornecer bons limitantes duais (limitantes
superiores em problema de maximização).
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. As formas mais comuns de se obter relaxações são:
Relaxar um conjunto de restrições (mantendo a mesma função
objetivo f (x) = cx);
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. Exemplo
max
s.a
20x1 + 30x2 − 550y1 − 720y2
3x1 + 8x2 ≤ 600
x1 ≤ 200y1
x2 ≤ 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
Restriç~
oes relaxadas:
x∗1 = 200, x∗2 = 0
y1∗ = 1, y2∗ = 0
z = 3450
Caracterı́sticas:
elimina a primeira restriç~
ao
x1 ≤ 200y1
x2 ≤ 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
x∗1 = 200, x∗2 = 75, y1∗ = 1, y2∗ = 1
z = 4980
decompõe em problemas independentes
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. As formas mais comuns de se obter relaxações são:
Relaxar um grupo de termos independentes. Por exemplo, a restrição
aT ≤ b poderia ser substituı́da por aT x ≤ αb + β, α ≥ 1, β ≥ 0.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. Exemplo
max
s.a
20x1 + 30x2 − 550y1 − 720y2
3x1 + 8x2 ≤ 600
x1 ≤ 200y1
x2 ≤ 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
Restriç~
oes relaxadas:
x∗1 = 200, x∗2 = 0
y1∗ = 1, y2∗ = 0
z = 3450
Caracterı́sticas:
dobrar capacidades
3x1 + 8x2 ≤ 1200
x1 ≤ 400y1
x2 ≤ 150y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
x∗1 = 400, x∗2 = 0, y1∗ = 1, y2∗ = 0
z = 7450
Não é signicativamente mais tratável que
o problema original.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. As formas mais comuns de se obter relaxações são:
Substituir um conjunto de restrições pela sua combinação linear não
negativa. Em particular, se X = {x : Ax ≤ b}, então para todo
u ≥ 0, X ⊂ XR = {x : uT Ax ≤ uT b}.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. Exemplo
max
s.a
20x1 + 30x2 − 550y1 − 720y2
3x1 + 8x2 ≤ 600
x1 ≤ 200y1
x2 ≤ 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
Restriç~
oes relaxadas:
3x1 + 8x2 ≤ 600
x1 + x2 ≤ 200y1 + 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
x∗1 = 200, x∗2 = 0
y1∗ = 1, y2∗ = 0
z = 3450
Caracterı́sticas:
combinaç~
ao linear n~
ao negativa das
restriç~
oes
x∗1 = 200, x∗2 = 0, y1∗ = 1 y2∗ = 0
z = 3450
solução ótima inteira.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. As formas mais comuns de se obter relaxações são:
Relaxar a condição de integralidade de um grupo de variáveis (no
caso particular de todas as variáveis inteiras tem-se a relaxação
linear) mantendo a mesma função objetivo cx;
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
. Exemplo
max
s.a
20x1 + 30x2 − 550y1 − 720y2
3x1 + 8x2 ≤ 600
x1 ≤ 200y1
x2 ≤ 75y2
x1 , x 2 ≥ 0
y1 , y2 ∈ {0, 1}
Variáveis relaxadas:
3x1 + 8x2 ≤ 1200
x1 ≤ 300y1
x2 ≤ 150y2
x1 , x 2 ≥ 0
y1 , y2 ∈ [0, 1]
x∗1 = 200, x∗2 = 0
y1∗ = 1, y2∗ = 0
z = 3450
Caracterı́sticas:
relaxa a condiç~
ao de integralidade
x∗1 = 200 x∗2 = 0, y1∗ = 1 y2∗ = 0
z = 3450
solução ótima inteira.
MAT 475 - Tópicos em Matemática Aplicada
(Lana Mara R. dos Santos, [email protected])
Aula 22: Relaxações
PI: relaxações
Adicionar ou mudar um conjunto de variáveis.
Como X = {x ∈ Zn+ : Ax ≤ b} é isomorfo a
X0 = {(x, 0) ∈ Zn+p
: Ax ≤ b}, uma relaxação de P é obtida ao
+
0
substituir X0 por Y = {(x, y) ∈ Zn+p
+ × : Ax + A y ≤ b}.
Este tipo de relaxação é útil se a matriz [AA0 ] for mais simples de
lidar que a matriz A.
Este tipo de construção é usada em alguns algoritmos cujo
desenvolvimento é sequencial.