Resolva o problema de programação linear pelo método gráfico e informe as soluções para valores inteiros.
\operatorname{Max} \mathrm{Z}=15 \mathrm{x}_{1}+20 \mathrm{x}_{2}
Sujeito à \left\{\begin{array}{c}x 1+x 2 \leq 10 \\\\ 0,8 x 1+2 x 2 \leq 12 \\\ x 1 ; x 2 \geq 0 \text { e inteiros }\end{array}\right.

Passo 1

O enunciado pede para resolver, pelo método gráfico, o problema de programação linear com variáveis inteiras. Vou listar claramente o que foi dado e o que é pedido.
  • Função objetivo a maximizar: \mathrm{Z}=15\,x_{1}+20\,x_{2}\). - Restrições (peguei-as do enunciado): \[\begin{cases} x_{1}+x_{2}\leq 10,\\[4pt] 0,8\,x_{1}+2\,x_{2}\leq 12,\\[4pt] x_{1}\ge 0,\; x_{2}\ge 0\\ \text{e inteiros.} \end{cases}
  • O que é pedido:
    • Resolver pelo método gráfico (ou seja: identificar a região factível e os vértices relevantes).
    • Informar as soluções quando x_{1}\] e \(x_{2} são inteiros (a solução inteira ótima).]

Passo 2

Entendendo geometricamente as restrições (como se desenharia o gráfico) e determinando os pontos-chave.
  • As duas desigualdades de fronteira são as retas
    x_{1}+x_{2}=10
    e
    0,8\,x_{1}+2\,x_{2}=12.
    Para desenhar cada reta é útil calcular os interceptos com os eixos.
  • Interceptos da reta x_{1}+x_{2}=10:
    \text{se }x_{1}=0\Rightarrow x_{2}=10,\qquad \text{se }x_{2}=0\Rightarrow x_{1}=10.
  • Escrever a segunda reta de forma mais simples: 0,8=\dfrac{4}{5}, então
    \frac{4}{5}x_{1}+2x_{2}=12.
    Interceptos:
    \text{se }x_{1}=0\Rightarrow 2x_{2}=12\Rightarrow x_{2}=6,
\text{se }x_{2}=0\Rightarrow \frac{4}{5}x_{1}=12\Rightarrow x_{1}=15.
Observação: embora essa reta chegue a x_{1}=15 no eixo, a primeira restrição limita x_{1}\le 10, então a região factível terá x_{1}\le 10.
  • O primeiro octante ( x_{1}\ge0,x_{2}\ge0) e as duas desigualdades formam uma região poligonal limitada cujos vértices (candidatos) são:
    • V_{0}=(0,0),
    • V_{1}=(10,0) (interseção de x_{2}=0 com x_{1}+x_{2}\le10),
    • V_{2}=(0,6) (interseção de x_{1}=0 com \tfrac{4}{5}x_{1}+2x_{2}\le12),
    • e a interseção entre as duas retas x_{1}+x_{2}=10 e \tfrac{4}{5}x_{1}+2x_{2}=12 (vou calcular no próximo passo).

Passo 3

Calcular a interseção das duas retas (o vértice interno da região) e avaliar a função objetivo nos vértices (método gráfico clássico).
  • Resolver o sistema \begin{cases} x_{1}+x_{2}=10,\\[4pt] \dfrac{4}{5}x_{1}+2x_{2}=12. \end{cases}Substituindo x_{1}=10-x_{2} na segunda: \frac{4}{5}(10-x_{2})+2x_{2}=12.Desenvolvendo: \frac{4}{5}\cdot 10 - \frac{4}{5}x_{2} + 2x_{2}=12
8 + \left(-\frac{4}{5}+2\right)x_{2}=12.
Calcular o coeficiente de x_{2}:
-\frac{4}{5}+2 = -0,8+2 = 1,2.
Então
8 + 1,2\,x_{2}=12\quad\Rightarrow\quad 1,2\,x_{2}=4\quad\Rightarrow\quad x_{2}=\frac{4}{1,2}=\frac{10}{3}.
Logo
x_{2}=\frac{10}{3}\approx 3{,}333\ldots,\qquad x_{1}=10-x_{2}=10-\frac{10}{3}=\frac{20}{3}\approx 6{,}666\ldots.
  • Avaliar Z nos vértices:
    • Em V_{0}=(0,0): Z=0.
    • Em V_{1}=(10,0): Z=15\cdot 10 +20\cdot 0 =150.
    • Em V_{2}=(0,6): Z=15\cdot 0 +20\cdot 6 =120.
    • Em V_{\text{int}}=\left(\dfrac{20}{3},\dfrac{10}{3}\right): Z=15\cdot\frac{20}{3}+20\cdot\frac{10}{3}=\frac{300}{3}+\frac{200}{3}=\frac{500}{3}\approx 166{,}666\ldots.
  • Conclusão contínua (sem integridade): o ponto interior \left(\dfrac{20}{3},\dfrac{10}{3}\right) é o ótimo contínuo com Z=\dfrac{500}{3}. Como precisamos de variáveis inteiras, deve-se procurar o melhor ponto inteiro dentro da região factível.]

Passo 4

Estratégia para encontrar a solução inteira ótima e justificativa: enumeração por linha (fácil aqui porque x_{1} tem limite pequeno).
  • Observação: a primeira restrição dá x_{1}\le 10. Assim x_{1} pode ser apenas os inteiros 0,1,\dots,10. Para cada x_{1} inteiro, a maior x_{2} inteira permitida é
    x_{2}\le \min\bigl(10-x_{1},\;6-0,4\,x_{1}\bigr),
    porque a segunda restrição pode ser escrita como
    0,8\,x_{1}+2\,x_{2}\le 12 \iff x_{2}\le \frac{12-0,8\,x_{1}}{2}=6-0,4\,x_{1}.
    Então, para cada x_{1} inteiro tomo x_{2}=\biggl\lfloor\min\bigl(10-x_{1},\,6-0,4x_{1}\bigr)\biggr\rfloor como o candidato que maximiza x_{2} (e por consequência tende a maximizar Z dado que coeficiente de x_{2} é positivo).
  • Agora faço a enumeração (para cada x_{1}=0,\dots,10 calculo o máximo x_{2} inteiro permitido e Z). Vou listar cada caso com os cálculos.
    • x_{1}=0: 10-x_{1}=10,\;6-0,4x_{1}=6\Rightarrow x_{2}^{\max}=6.
      Z=15\cdot 0+20\cdot 6=120.
    • x_{1}=1: 10-x_{1}=9,\;6-0,4\cdot1=5,6\Rightarrow x_{2}^{\max}=\lfloor5,6\rfloor=5.
      Z=15\cdot1+20\cdot5=15+100=115.
    • x_{1}=2: 10-x_{1}=8,\;6-0,4\cdot2=5,2\Rightarrow x_{2}^{\max}=5.
      Z=15\cdot2+20\cdot5=30+100=130.
    • x_{1}=3: 10-x_{1}=7,\;6-0,4\cdot3=4,8\Rightarrow x_{2}^{\max}=4.
      Z=15\cdot3+20\cdot4=45+80=125.
    • x_{1}=4: 10-x_{1}=6,\;6-0,4\cdot4=4,4\Rightarrow x_{2}^{\max}=4.
      Z=15\cdot4+20\cdot4=60+80=140.
    • x_{1}=5: 10-x_{1}=5,\;6-0,4\cdot5=4,0\Rightarrow x_{2}^{\max}=4.
      Z=15\cdot5+20\cdot4=75+80=155.
    • x_{1}=6: 10-x_{1}=4,\;6-0,4\cdot6=3,6\Rightarrow x_{2}^{\max}=3.
      Z=15\cdot6+20\cdot3=90+60=150.
    • x_{1}=7: 10-x_{1}=3,\;6-0,4\cdot7=3,2\Rightarrow x_{2}^{\max}=3.
      Z=15\cdot7+20\cdot3=105+60=165.
    • x_{1}=8: 10-x_{1}=2,\;6-0,4\cdot8=2,8\Rightarrow x_{2}^{\max}=2.
      Z=15\cdot8+20\cdot2=120+40=160.
    • x_{1}=9: 10-x_{1}=1,\;6-0,4\cdot9=2,4\Rightarrow x_{2}^{\max}=1.
      Z=15\cdot9+20\cdot1=135+20=155.
    • x_{1}=10: 10-x_{1}=0,\;6-0,4\cdot10=2,0\Rightarrow x_{2}^{\max}=0.
      Z=15\cdot10+20\cdot0=150.

Passo 5

Determinar a(s) melhor(es) solução(ões) inteiras a partir da enumeração e validar.
  • Dos valores calculados acima os Z obtidos foram:
    120,\;115,\;130,\;125,\;140,\;155,\;150,\;165,\;160,\;155,\;150
    O maior valor é Z=165, obtido no caso x_{1}=7,\;x_{2}=3.
  • Verificação das restrições para (x_{1},x_{2})=(7,3):
    x_{1}+x_{2}=7+3=10\le 10,\qquad 0,8\cdot 7+2\cdot 3=5,6+6=11,6\le 12,
    e as variáveis são não negativas inteiras. Portanto (7,3) é factível e dá Z=165.
  • Não há outro par inteiro factível com Z\ge 165 segundo a enumeração, logo a solução inteira ótima é única e é (x_{1},x_{2})=(7,3).

Resposta

x_{1}=7,\\ x_{2}=3,\\ Z=165

Exercícios relacionados