Resolva o PPI abaixo aplicando o método Branch-and-Bound:
s.a
Passo 1
Beleza, vamos entender primeiro o que rolou:
Enunciado: “Maximizar
sujeito a
Conteúdo: Programação Inteira (PPI) e o método Branch-and-Bound.
O que precisamos:
Resolver a versão contínua (relaxação LP).
Se o ótimo for inteiro, beleza; senão, “ramificar” (branch) numa das variáveis que ficou fracionária.
Em cada nó, calcular um bound (o valor ótimo do LP naquele ramo) e “podar” (fathom) se der inteiro ou se for pior que a melhor solução inteira já achada (incumbent).
Passo 2
Relaxação LP (sem exigir 3x1 + x2 =12, x1 + x2 =5 ;Longrightarrow; x1=3.5,;x2=1.5 inteiros).
As restrições são duas retas; vamos olhar os vértices:
(0,0) ⇒ .
Eixo : em , da segunda restrição vem ⇒ .
Eixo : em , da primeira ⇒ .
Interseção das duas retas:dá .
Esse é o ótimo LP: em , que não é inteiro. Bora ramificar!
Passo 3
Branch em (que ficou ). Dois ramos:
a) .
b) .
Ramo (a) : adiciono essa reta e resolvo LP de novo.
Teto cruza em , ponto com .
Outros candidatos (, etc.) dão menos.
Logo, ótimo desse ramo é em .
Como é inteiro, virou solução viável; incumbente .
Passo 4
Ramo (b) : junto com e , o único ponto possível é .
Se , da primeira: ; da segunda: . Então .
Isso dá com .
Também inteiro, incumbente vira .
Agora não sobrou ramo com valor LP>20 que seja promissor (o ramo inicial tinha 20.5, e já tratamos os dois lados). O melhor inteiro achado é .