Considere o seguinte problema de otimização linear discreta:
Maximizar $\quad Z=220 x_{1}+80 x_{2}$
sujeito a:
$5 x_{1}+2 x_{2} \leq 16$
$2 x_{1}-x_{2} \leq 4$
$-x_{1}-2 x_{2} \leq 4$
$\underline{x} \geq 0$ e inteiros
a) Resolva o problema graficamente.
b) Usando o algoritmo Branch-and-Bound, resolva o problema, indicando os subproblemas avaliados e suas soluções (árvore de soluções).
c) É correto afirmar que a região factível de um problema de otimização inteira é um subconjunto das soluções ótimas possíveis de seu problema relaxado?
Maximizar $\quad Z=220 x_{1}+80 x_{2}$
sujeito a:
$5 x_{1}+2 x_{2} \leq 16$
$2 x_{1}-x_{2} \leq 4$
$-x_{1}-2 x_{2} \leq 4$
$\underline{x} \geq 0$ e inteiros
b) Usando o algoritmo Branch-and-Bound, resolva o problema, indicando os subproblemas avaliados e suas soluções (árvore de soluções).
c) É correto afirmar que a região factível de um problema de otimização inteira é um subconjunto das soluções ótimas possíveis de seu problema relaxado?
Passo 1
O problema é um PL inteiro bi-variável que busca maximizar
sujeito a
Vamos usar dois métodos: solução gráfica e Branch-and-Bound, e depois discutir uma propriedade de regiões factíveis inteiras.
Passo 2
Para a solução gráfica, primeiro desenhamos as restrições no plano
. As arestas da região factível contínua (sem a exigência de integralidade) são:
(0,0),
(2,0) obtido de com
,
interseção de
(0,0),
(2,0) obtido de
e (0,8) eixo
•
•
•
•
O ótimo contínuo é
Passo 3
Como queremos solução inteira, listamos as combinações
inteiras na região contínua. Verificamos rapidamente que as melhores ocorrem em
Logo o ótimo inteiro via gráfico é com
.
Logo o ótimo inteiro via gráfico é
Passo 4
No Branch-and-Bound, relaxamos primeiro a integralidade e vemos o mesmo ótimo contínuo
. Como há variável fracionária (
), escolhemos ramificar em
:
• Subproblema 1: adicionar . Resolve-se o PL e obtém-se ótimo em
com
, inteiro.
• Subproblema 2: adicionar . Não há ponto contínuo que satisfaça todas as restrições, fica inviável.
A melhor solução inteira encontrada é .
• Subproblema 1: adicionar
• Subproblema 2: adicionar
A melhor solução inteira encontrada é
Passo 5
A afirmação “a região factível de um problema inteiro é subconjunto das soluções ótimas do relaxado” está equivocada. Na verdade, a região factível inteira é subconjunto da região factível contínua, mas as soluções ótimas do relaxado podem ser fracionárias e não pertencer ao inteiro. Portanto, a afirmação é falsa.
Resposta
a) Pela análise gráfica e enumeração dos pontos inteiros, o ótimo discreto é em (2,3) com Z=680.
b) Branch-and-Bound:
• Nó raiz: relaxado → (8/3,4/3), Z=693.33
• Ramificação x₁≤2 → ótimo (2,3), Z=680 (inteiro)
• Ramificação x₁≥3 → inviável
Ótimo inteiro final: (2,3), Z=680.
c) A afirmação é falsa. A região inteira é subconjunto da região relaxada, mas nem sempre das soluções ótimas do relaxado.
b) Branch-and-Bound:
• Nó raiz: relaxado → (8/3,4/3), Z=693.33
• Ramificação x₁≤2 → ótimo (2,3), Z=680 (inteiro)
• Ramificação x₁≥3 → inviável
Ótimo inteiro final: (2,3), Z=680.
c) A afirmação é falsa. A região inteira é subconjunto da região relaxada, mas nem sempre das soluções ótimas do relaxado.