Resolva o PPI abaixo aplicando o método Branch-and-Bound:
Max z=5 x1+2 x2
s.a 3 x1+x2 <= 12
x1+x2 <= 5 x1, x2 in Z+ x1, x2 >= 0

Passo 1

Beleza, vamos entender primeiro o que rolou:
Enunciado: “Maximizar
z = 5x1 + 2x2
sujeito a
3x1 + x2 <= 12, x1 + x2 <= 5, x1,x2inZ+
Conteúdo: Programação Inteira (PPI) e o método Branch-and-Bound.
O que precisamos:
  1. Resolver a versão contínua (relaxação LP).
  2. Se o ótimo for inteiro, beleza; senão, “ramificar” (branch) numa das variáveis que ficou fracionária.
  3. 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: .
    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 é .

Resposta

A solução ótima inteira é
x1=4, x2=0, zmax=20

Exercícios relacionados