Resolva o problema de maximização de programação inteira pelo algoritmo Branch and Boud.
Dado o modelo abaixo, ache a solução ótima.
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:
(devem ser não negativas e inteiras). - Função objetivo:
- Restrições:
O que se quer: encontrar valores inteiros de
que satisfaçam as restrições e maximizem
.
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
pode ser escrito como
enquanto
é
Como
, a terceira desigualdade (
) é mais restritiva que a segunda; logo a restrição
é redundante no relaxamento (não corta a região factível além do que já corta
). Assim consideramos efetivamente:
Agora encontramos o vértice ótimo do relaxamento LP. Os candidatos são interseções das retas:
-
, -
, - e os eixos.
Calculo da interseção entre
e
. Da segunda temos
. Substituindo na primeira:
Resolvendo:
Então
Avalio o objetivo nesse ponto:
Verifico também o ponto sobre
com
(a interseção com o eixo
):
, que dá
Comparando, o máximo do relaxamento é
em
. Esta solução é fracionária (ambas variáveis não inteiras), então precisamos ramificar.
Resumo do relaxamento:
Passo 3
Escolha de ramificação: tanto
quanto
são fracionários. Vou ramificar por
(é comum escolher a variável com componente fracionária), gerando duas subproblemas:
- Nó A (esquerdo):
. - Nó B (direito):
.
Cada nó tem as demais restrições do problema original (relaxadas para contínuas).
Passo 4
Resolver Nó A (adicionando
) como LP contínuo.
Dentro deste nó, como o coeficiente de
na função objetivo (
) é maior que o de
(
), o LP tentará maximizar
até o limite permitido. Com
e a restrição
temos
Também a restrição
dá
. O bound mais apertado é
.
Logo o LP ótimo neste nó é em
e
. O valor objetivo é
Portanto o limite superior desse nó é
. A solução
ainda tem
fracionário, então ramificamos nesse nó sobre
.
Passo 5
Ramificação do Nó A pelo
fracionário:
Geramos dois filhos:
- Nó A1:
e . - Nó A2:
e .
Resolver Nó A1 (com
):
Como queremos maximizar e
tem coeficiente maior, escolhemos
se permitido. Verifico restrições com
:
portanto
é factível e é inteiro. Valor:
Encontramos uma solução inteira factível com
. Guardamos como incumbente (melhor solução inteira atual):
em
.
Passo 6
Resolver Nó A2 (com
):
A restrição
implica, para
,
Então
na prática fica com
. Para maximizar, escolhemos
tão grande quanto possível: testar
. Verifico factibilidade:
Ponto inteiro e factível. Valor:
Este nó não melhora o incumbente
. Além disso, o nó A já tinha limite superior
, e seus filhos deram soluções inteiras com valores
e
. Concluímos o ramo A está completamente explorado (fathomed), sem superar
.
Passo 7
Voltar ao Nó B:
. Resolver o LP contínuo deste nó para obter um bound superior.
As restrições ainda são:
Para analisar, expresso
a partir de
:
Substituir esse limite na função objetivo fornece um valor máximo em função de
quando a restrição
é ativa. Calculando explicitamente, notar que para
a restrição que mais limita
é
. Assim o melhor que o LP pode fazer na prática é escolher
o mais baixo possível (porque, mantendo a igualdade
, aumentar
diminui o teto de
e, no conjunto, o objetivo resultante decresce — ver cálculo abaixo).
Tomando
como valor mínimo permitido em Nó B, obtemos
Então o LP ótimo para Nó B ocorre em
(porque aumentar
acima de
diminui ainda mais o teto de
e no balanço o valor objetivo cai). Avaliando:
Logo o limite superior deste nó é
Esse valor é maior que o incumbente
, então vale a pena explorar o nó B. A solução do LP tem
(fracionário) e
(inteiro). Podemos agora ramificar sobre
.
Passo 8
Ramificação do Nó B (que tem
):
Primeira divisão natural: separar
em
e
. Faço isso porque
já é inteiro em uma solução candidata e
no relaxamento da raiz tomou valor entre
e
(no relaxamento do Nó B o melhor é
; mas o relaxamento global anterior sugeria
até
). Então:
- Nó B1:
(combinado com dá fixo). - Nó B2:
.
Resolver Nó B2: se
, então
, impossível. Então Nó B2 é inviável (podemos fathomar por inviabilidade).
Resolver Nó B1: com
fixo, o LP reduz a escolher
sujeito a:
e
. Logo
no relaxamento. Para maximizar o objetivo escolhemos
(como já vimos), obtendo
como bound do nó. Mas agora
é fracionário; ramificamos sobre
:
Geramos:
- Nó B1a:
. - Nó B1b:
.
Analisando Nó B1b: com
e
,
não há
que satisfaça isso. Portanto Nó B1b é inviável.
Analisando Nó B1a:
é um ponto inteiro candidato. Verifico as restrições:
É factível. O valor objetivo é
Encontramos solução inteira com
.
Passo 9
Comparação e conclusão dos ramos:
- Do ramo A (
) obtivemos as soluções inteiras com e com . Melhor deste ramo: . - Do ramo B (
) obtivemos a solução inteira com . O outro subnó com foi inviável.
Verificação por enumeração rápida (controle mental): para
e
inteiro respeitando
e
, os melhores pares inteiros são exatamente aqueles testados:
dá
,
etc., e o melhor encontrado é
com
. Não existe par inteiro factível com
porque todos nós do Branch and Bound tiveram limites superiores ≤
na raiz e nós com limite
foram explorados e não produziram inteiro melhor que
.
Portanto a solução inteira ótima é