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?

Passo 1

O problema é um PL inteiro bi-variável que busca maximizar Z=220x1+80x2 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 (x1,x2). As arestas da região factível contínua (sem a exigência de integralidade) são:
(0,0),
(2,0) obtido de 2x1 - x2=4 com x2=0,
(8/3,4/3) interseção de
5x1+2x2=16e2x1 - x2=4,
e (0,8) eixo x1=0. Calculando Z nesses vértices temos:
(0,0)to Z=0
(2,0)to Z=440
(8/3,4/3)to Z=2080/3approx693.33
(0,8)to Z=640
O ótimo contínuo é (8/3,4/3) com Zapprox693.33, mas é fracionário.

Passo 3

Como queremos solução inteira, listamos as combinações (x1,x2) inteiras na região contínua. Verificamos rapidamente que as melhores ocorrem em
(0,8)to Z=640,(1,5)to Z=620,(2,3)to Z=680
Logo o ótimo inteiro via gráfico é (2,3) com Z=680.

Passo 4

No Branch-and-Bound, relaxamos primeiro a integralidade e vemos o mesmo ótimo contínuo (8/3,4/3),Z=693.33. Como há variável fracionária ( x1=2.67), escolhemos ramificar em x1:
• Subproblema 1: adicionar x1<=2. Resolve-se o PL e obtém-se ótimo em (2,3) com Z=680, inteiro.
• Subproblema 2: adicionar x1>=3. Não há ponto contínuo que satisfaça todas as restrições, fica inviável.
A melhor solução inteira encontrada é (2,3),Z=680.

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.

Exercícios relacionados