Resolva o problema de maximização de programação inteira pelo algoritmo Branch and Boud.
Dado o modelo abaixo, ache a solução ótima.
\begin{aligned} \operatorname{Max} Z= & 4 x_{1}+5 x_{2} \\\ & 5 x_{1}+7 x_{2} \leq 44 \\\ \text { Sujeito a: } & 4 x_{1}+2 x_{2} \leq 27 \\\ & 6 x_{1}+3 x_{2} \leq 24 \\\ & x_{1} ; x_{2} \geq 0 \text { e inteiros } \end{aligned}

Passo 1

O enunciado pede achar a solução ótima inteira do problema de programação inteira (maximização). As informações dadas são:
  • Variáveis de decisão: x_{1}, x_{2} (devem ser não negativas e inteiras).
  • Função objetivo:
\text{Max } Z = 4x_{1} + 5x_{2}
  • Restrições:
\begin{aligned} 5x_{1} + 7x_{2} &\le 44,\\\\ 4x_{1} + 2x_{2} &\le 27,\\\\ 6x_{1} + 3x_{2} &\le 24,\\\ x_{1},x_{2} &\ge 0\text{ e inteiros.} \end{aligned}
O que se quer: encontrar valores inteiros de (x_{1},x_{2}) que satisfaçam as restrições e maximizem Z.

Passo 2

Estratégia: usar Branch and Bound. Primeiro fazemos o relaxamento linear (permitir variáveis contínuas) para obter um limite superior (upper bound). Se a solução do relaxamento for inteira, ela é ótima; se for fracionária, escolhemos uma variável fracionária para ramificar.
Antes de resolver, simplifico as restrições quando possível. Note que
4x_{1}+2x_{2}\le27
pode ser escrito como
2x_{1}+x_{2}\le13{,}5,
enquanto
6x_{1}+3x_{2}\le24
é
2x_{1}+x_{2}\le8.
Como 8 < 13{,}5, a terceira desigualdade ( 2x_{1}+x_{2}\le8) é mais restritiva que a segunda; logo a restrição 4x_{1}+2x_{2}\le27 é redundante no relaxamento (não corta a região factível além do que já corta 6x_1+3x_2\le24). Assim consideramos efetivamente:
\begin{aligned} 5x_{1}+7x_{2} &\le 44,\\\\ 2x_{1}+x_{2} &\le 8,\\\ x_{1},x_{2} &\ge 0. \end{aligned}
Agora encontramos o vértice ótimo do relaxamento LP. Os candidatos são interseções das retas:
  • 5x_{1}+7x_{2}=44,
  • 2x_{1}+x_{2}=8,
  • e os eixos.
Calculo da interseção entre 5x_{1}+7x_{2}=44 e 2x_{1}+x_{2}=8. Da segunda temos x_{2}=8-2x_{1}. Substituindo na primeira:
5x_{1}+7(8-2x_{1})=44.
Resolvendo:
5x_{1}+56-14x_{1}=44 \quad\Rightarrow\quad -9x_{1}=-12 \quad\Rightarrow\quad x_{1}=\frac{4}{3}.
Então
x_{2}=8-2\cdot\frac{4}{3}=\frac{16}{3}.
Avalio o objetivo nesse ponto:
Z = 4\cdot\frac{4}{3} + 5\cdot\frac{16}{3} = \frac{16+80}{3}=\frac{96}{3}=32.
Verifico também o ponto sobre 5x_{1}+7x_{2}=44 com x_{1}=0 (a interseção com o eixo x_2): x_{2}=44/7, que dá
Z = 5\cdot\frac{44}{7}=\frac{220}{7}\approx31{,}4286.
Comparando, o máximo do relaxamento é Z=32 em \left(\dfrac{4}{3},\dfrac{16}{3}\right). Esta solução é fracionária (ambas variáveis não inteiras), então precisamos ramificar.
Resumo do relaxamento:
\text{Relax LP: }(x_{1},x_{2})=\left(\tfrac{4}{3},\tfrac{16}{3}\right),\quad Z^{UB}=32.

Passo 3

Escolha de ramificação: tanto x_{1}=\tfrac{4}{3} quanto x_{2}=\tfrac{16}{3}=5{,}333\ldots são fracionários. Vou ramificar por x_{2} (é comum escolher a variável com componente fracionária), gerando duas subproblemas:
  • Nó A (esquerdo): x_{2}\le 5.
  • Nó B (direito): x_{2}\ge 6.
Cada nó tem as demais restrições do problema original (relaxadas para contínuas).

Passo 4

Resolver Nó A (adicionando x_{2}\le 5) como LP contínuo.
Dentro deste nó, como o coeficiente de x_{2} na função objetivo ( 5) é maior que o de x_{1} ( 4), o LP tentará maximizar x_{2} até o limite permitido. Com x_{2}\le5 e a restrição 2x_{1}+x_{2}\le8 temos
2x_{1}+5\le8\quad\Rightarrow\quad x_{1}\le 1{,}5.
Também a restrição 5x_{1}+7x_{2}\le44 5x_{1}+35\le44\Rightarrow x_{1}\le 9/5=1{,}8. O bound mais apertado é x_{1}\le1{,}5.
Logo o LP ótimo neste nó é em x_{2}=5 e x_{1}=1{,}5. O valor objetivo é
Z = 4\cdot 1{,}5 + 5\cdot 5 = 6 + 25 = 31.
Portanto o limite superior desse nó é Z^{UB}=31. A solução (1{,}5,5) ainda tem x_{1} fracionário, então ramificamos nesse nó sobre x_{1}.

Passo 5

Ramificação do Nó A pelo x_{1} fracionário:
Geramos dois filhos:
  • Nó A1: x_{2}\le5 e x_{1}\le1.
  • Nó A2: x_{2}\le5 e x_{1}\ge2.
Resolver Nó A1 (com x_{1}\le1,\\ x_{2}\le5):
Como queremos maximizar e x_{2} tem coeficiente maior, escolhemos x_{2}=5 se permitido. Verifico restrições com x_{1}=1,\\ x_{2}=5:
5x_{1}+7x_{2}=5+35=40\le44,\quad 2x_{1}+x_{2}=2+5=7\le8,
portanto (1,5) é factível e é inteiro. Valor:
Z = 4\cdot1 + 5\cdot5 = 4 + 25 = 29.
Encontramos uma solução inteira factível com Z=29. Guardamos como incumbente (melhor solução inteira atual): Z^{*}=29 em (x_{1},x_{2})=(1,5).

Passo 6

Resolver Nó A2 (com x_{1}\ge2,\\ x_{2}\le5):
A restrição 2x_{1}+x_{2}\le8 implica, para x_{1}\ge2,
x_{2}\le 8-2x_{1}\le 8-4=4.
Então x_{2} na prática fica com \,x_{2}\le4. Para maximizar, escolhemos x_{2} tão grande quanto possível: testar x_{1}=2,\\ x_{2}=4. Verifico factibilidade:
5x_{1}+7x_{2}=10+28=38\le44,\quad 2x_{1}+x_{2}=4+4=8\le8.
Ponto inteiro e factível. Valor:
Z=4\cdot2 + 5\cdot4 = 8 + 20 = 28.
Este nó não melhora o incumbente Z^{*}=29. Além disso, o nó A já tinha limite superior 31, e seus filhos deram soluções inteiras com valores 29 e 28. Concluímos o ramo A está completamente explorado (fathomed), sem superar Z^{*}.

Passo 7

Voltar ao Nó B: x_{2}\ge6. Resolver o LP contínuo deste nó para obter um bound superior.
As restrições ainda são:
5x_{1}+7x_{2}\le44,\quad 2x_{1}+x_{2}\le8,\quad x_{2}\ge6,\\ x_{1}\ge0.
Para analisar, expresso x_{1} a partir de 5x_{1}+7x_{2}\le44:
x_{1}\le \frac{44-7x_{2}}{5}.
Substituir esse limite na função objetivo fornece um valor máximo em função de x_{2} quando a restrição 5x_{1}+7x_{2}\le44 é ativa. Calculando explicitamente, notar que para x_{2}\ge6 a restrição que mais limita x_1 é 5x_1+7x_2\le44. Assim o melhor que o LP pode fazer na prática é escolher x_{2} o mais baixo possível (porque, mantendo a igualdade 5x_{1}+7x_{2}=44, aumentar x_{2} diminui o teto de x_{1} e, no conjunto, o objetivo resultante decresce — ver cálculo abaixo).
Tomando x_{2}=6 como valor mínimo permitido em Nó B, obtemos
5x_{1}+7\cdot6\le44 \Rightarrow 5x_{1}\le2 \Rightarrow x_{1}\le 0{,}4.
Então o LP ótimo para Nó B ocorre em x_{2}=6,\\ x_{1}=0{,}4 (porque aumentar x_2 acima de 6 diminui ainda mais o teto de x_1 e no balanço o valor objetivo cai). Avaliando:
Z = 4\cdot 0{,}4 + 5\cdot 6 = 1{,}6 + 30 = 31{,}6.
Logo o limite superior deste nó é
Z^{UB}= \frac{158}{5} = 31{,}6.
Esse valor é maior que o incumbente 29, então vale a pena explorar o nó B. A solução do LP tem x_{1}=0{,}4 (fracionário) e x_{2}=6 (inteiro). Podemos agora ramificar sobre x_{1}.

Passo 8

Ramificação do Nó B (que tem x_{2}\ge6):
Primeira divisão natural: separar x_{2}\ge6 em x_{2}\le6 e x_{2}\ge7. Faço isso porque x_{2} já é inteiro em uma solução candidata e x_{2} no relaxamento da raiz tomou valor entre 6 e 7 (no relaxamento do Nó B o melhor é x_2=6; mas o relaxamento global anterior sugeria x_2 até 44/7\approx6{,}2857). Então:
  • Nó B1: x_{2}\le6 (combinado com x_{2}\ge6 x_{2}=6 fixo).
  • Nó B2: x_{2}\ge7.
Resolver Nó B2: se x_{2}\ge7, então 5x_{1}+7x_{2}\ge 7\cdot7=49>44, impossível. Então Nó B2 é inviável (podemos fathomar por inviabilidade).
Resolver Nó B1: com x_{2}=6 fixo, o LP reduz a escolher x_{1} sujeito a:
5x_{1} + 7\cdot 6 \le 44 \Rightarrow x_{1}\le 0{,}4,
e 2x_{1}+6\le8 \Rightarrow x_{1}\le1. Logo x_{1}\in[0,0{,}4] no relaxamento. Para maximizar o objetivo escolhemos x_{1}=0{,}4 (como já vimos), obtendo Z=31{,}6 como bound do nó. Mas agora x_{1} é fracionário; ramificamos sobre x_{1}:
Geramos:
  • Nó B1a: x_{2}=6,\\ x_{1}\le0 \Rightarrow x_{1}=0.
  • Nó B1b: x_{2}=6,\\ x_{1}\ge1.
Analisando Nó B1b: com x_{1}\ge1 e x_{2}=6,
5x_{1}+7\cdot6 \le 44 \Rightarrow 5x_{1}\le 2 \Rightarrow x_{1}\le 0{,}4,
não há x_{1}\ge1 que satisfaça isso. Portanto Nó B1b é inviável.
Analisando Nó B1a: x_{1}=0,\\ x_{2}=6 é um ponto inteiro candidato. Verifico as restrições:
5\cdot 0 + 7\cdot 6 = 42 \le 44,\quad 4\cdot 0 + 2\cdot6 = 12 \le 27,\quad 6\cdot0 +3\cdot6=18\le24.
É factível. O valor objetivo é
Z=4\cdot0 + 5\cdot6 = 30.
Encontramos solução inteira com Z=30.

Passo 9

Comparação e conclusão dos ramos:
  • Do ramo A ( x_{2}\le5 ) obtivemos as soluções inteiras (1,5) com Z=29 e (2,4) com Z=28. Melhor deste ramo: Z=29.
  • Do ramo B ( x_{2}\ge6 ) obtivemos a solução inteira (0,6) com Z=30. O outro subnó com x_{2}\ge7 foi inviável.
Verificação por enumeração rápida (controle mental): para x_{2}=0,1,2,\dots,6 e x_{1} inteiro respeitando 2x_1+x_2\le8 e 5x_1+7x_2\le44, os melhores pares inteiros são exatamente aqueles testados: (4,0) Z=16, (3,2) etc., e o melhor encontrado é (0,6) com Z=30. Não existe par inteiro factível com Z>30 porque todos nós do Branch and Bound tiveram limites superiores ≤ 32 na raiz e nós com limite >30 foram explorados e não produziram inteiro melhor que 30.
Portanto a solução inteira ótima é
(x_{1},x_{2})=(0,6),\qquad Z_{\max}=30.

Resposta

x_{1}=0,\\ x_{2}=6,\\ Z_{\max}=30

Exercícios relacionados