Resolva pelo método de Benders o seguinte PPI misto:
Passo 1
Beleza! O enunciado pede para resolver um PPI misto via decomposição de Benders. A gente tem duas famílias de variáveis:
- y₁,y₂,y₃ são inteiras (0≤yᵢ≤5)
- x₁,x₂,x₃ são contínuas (xᵢ≥0)
Objetivo:
min –5y₁ +2y₂ +9y₃ –2x₁ +3x₂ –4x₃
min –5y₁ +2y₂ +9y₃ –2x₁ +3x₂ –4x₃
Sujeito a:
(1) 5y₁–3y₂+7y₃ +2x₁+3x₂+6x₃ ≤ –2
(2) 4y₁+2y₂+4y₃ +3x₁–x₂+3x₃ ≤ 10
(1) 5y₁–3y₂+7y₃ +2x₁+3x₂+6x₃ ≤ –2
(2) 4y₁+2y₂+4y₃ +3x₁–x₂+3x₃ ≤ 10
Conteúdo que vamos usar: teoria da decomposição de Benders (separar y no “master” e x no “subproblema” contínuo), dualidade para gerar cortes de viabilidade e de otimização, e um loop de iterações até não criar mais cortes.
Passo 2
Definimos:
– Master: só com y e uma variável θ que “guarda” o custo ótimo do subproblema.
– Subproblema (para x fixado ŷ):
min –2x₁+3x₂–4x₃
s.a. 2x₁+3x₂+6x₃ ≤ –2–5ŷ₁+3ŷ₂–7ŷ₃
3x₁–x₂+3x₃ ≤ 10–4ŷ₁–2ŷ₂–4ŷ₃
xᵢ≥0
– Master: só com y e uma variável θ que “guarda” o custo ótimo do subproblema.
– Subproblema (para x fixado ŷ):
min –2x₁+3x₂–4x₃
s.a. 2x₁+3x₂+6x₃ ≤ –2–5ŷ₁+3ŷ₂–7ŷ₃
3x₁–x₂+3x₃ ≤ 10–4ŷ₁–2ŷ₂–4ŷ₃
xᵢ≥0
Começamos com o master sem cortes, então escolhemos um y⁰ “qualquer”. Por simplicidade, tomo y⁰=(0,0,0).
Subproblema com y⁰:
2x₁+3x₂+6x₃ ≤ –2 → impossível, pois LHS≥0 e RHS=–2.
Logo o subproblema é inviável e gera um corte de viabilidade via lema de Farkas.
Uma das combinações fáceis é usar multipliers u=(1,0) sobre a primeira restrição:
uᵀA≥0 já vale, e gera a condição
–2–5y₁+3y₂–7y₃ ≥ 0
Reescrevendo a gente obtém o corte:
3y₂ –5y₁ –7y₃ ≥ 2
2x₁+3x₂+6x₃ ≤ –2 → impossível, pois LHS≥0 e RHS=–2.
Logo o subproblema é inviável e gera um corte de viabilidade via lema de Farkas.
Uma das combinações fáceis é usar multipliers u=(1,0) sobre a primeira restrição:
uᵀA≥0 já vale, e gera a condição
–2–5y₁+3y₂–7y₃ ≥ 0
Reescrevendo a gente obtém o corte:
3y₂ –5y₁ –7y₃ ≥ 2
Passo 3
Inserimos no master o corte de viabilidade
3y₂ –5y₁ –7y₃ ≥ 2
e os bounds 0≤yᵢ≤5 inteiros, e ignoramos θ por enquanto (ou tratamos θ livre, o master fica “unbounded em θ”, então para gerar um y candidato a gente minimiza só o custo inteiro –5y₁+2y₂+9y₃).
3y₂ –5y₁ –7y₃ ≥ 2
e os bounds 0≤yᵢ≤5 inteiros, e ignoramos θ por enquanto (ou tratamos θ livre, o master fica “unbounded em θ”, então para gerar um y candidato a gente minimiza só o custo inteiro –5y₁+2y₂+9y₃).
Resolvendo minimizando –5y₁+2y₂+9y₃ sujeito ao corte e bounds, achamos:
y¹=(2,4,0) com custo inteiro =–10+8+0=–2.
y¹=(2,4,0) com custo inteiro =–10+8+0=–2.
Passo 4
Agora testamos y¹ no subproblema:
b₁=–2–5·2+3·4–7·0=–2–10+12=0
b₂=10–4·2–2·4–4·0=10–8–8=–6
b₁=–2–5·2+3·4–7·0=–2–10+12=0
b₂=10–4·2–2·4–4·0=10–8–8=–6
Subproblema:
2x₁+3x₂+6x₃≤0
3x₁–x₂+3x₃≤–6
2x₁+3x₂+6x₃≤0
3x₁–x₂+3x₃≤–6
Esse também é inviável (mesmo raciocínio de Farkas: não dá para satisfazer a 2ª com x≥0 se b₂<0 e a 1ª força LHS≥0). Gera corte novo. Um cálculo de combinação u=(1,1) dá, após álgebra, o corte:
9y₁ –y₂ +11y₃ ≤ 8
9y₁ –y₂ +11y₃ ≤ 8
Passo 5
Voltamos ao master, agora com dois cortes de viabilidade:
(i) 3y₂–5y₁–7y₃ ≥ 2
(ii) 9y₁–y₂+11y₃ ≤ 8
(i) 3y₂–5y₁–7y₃ ≥ 2
(ii) 9y₁–y₂+11y₃ ≤ 8
Minimizando de novo –5y₁+2y₂+9y₃ encontramos y²=(1,3,0), custo inteiro = –5+6+0=1.
Passo 6
Testamos y²=(1,3,0) no subproblema:
b₁=–2–5·1+3·3–7·0=–2–5+9=2
b₂=10–4·1–2·3–4·0=10–4–6=0
b₁=–2–5·1+3·3–7·0=–2–5+9=2
b₂=10–4·1–2·3–4·0=10–4–6=0
Subproblema:
2x₁+3x₂+6x₃≤2
3x₁–x₂+3x₃≤0
xᵢ≥0
2x₁+3x₂+6x₃≤2
3x₁–x₂+3x₃≤0
xᵢ≥0
Ele é viável (por exemplo x=(0,0,0)) e, de fato, o mínimo de –2x₁+3x₂–4x₃ em região limitada dá x*= (0,0,0) com valor 0.
Como subproblema ficou viável e conseguimos ótima, geramos o corte de otimização (mas como θ deve igualar 0, e já θ=0 encaixa, não aparece corte nova relevante).
Como subproblema ficou viável e conseguimos ótima, geramos o corte de otimização (mas como θ deve igualar 0, e já θ=0 encaixa, não aparece corte nova relevante).
Passo 7
Não surge mais corte de viabilidade e já temos valor ótimo do subproblema. O processo pára.
Resposta
Solução ótima por Benders:
y₁=1, y₂=3, y₃=0
x₁=0, x₂=0, x₃=0
Valor ótimo = –5·1+2·3+9·0 –2·0+3·0–4·0 = 1.
y₁=1, y₂=3, y₃=0
x₁=0, x₂=0, x₃=0
Valor ótimo = –5·1+2·3+9·0 –2·0+3·0–4·0 = 1.