Considere os problemas de otimização linear a seguir:
(i) Solucione-os graficamente, caso possível. Caso não, explique as razões;
(ii) Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada;
\begin{gathered} \max \\\ \text { sujeito a } \\\ \\\ \\\ \\\ \\\ \\\ \\\ \\\\ -x_{1}-x_{2}+x_{2} \leq-3 \\\ x_{1}+2 x_{2} \leq 4 \\\ x_{1}, x_{2} \geq 0 \end{gathered}

Passo 1

O enunciado pede duas coisas:
(i) “Solucione-os graficamente, caso possível.” (ou explique por que não é possível).
(ii) “Indique, em cada caso, se a solução, caso exista, é única, múltipla ou ilimitada.”
As informações fornecidas (copiadas do enunciado) são as restrições:
- x_{1} - x_{2} + x_{2} \le -3
x_{1} + 2x_{2} \le 4
x_{1}, x_{2} \ge 0
Observação importante: o enunciado mostra apenas a palavra “max” sem especificar a função objetivo (ou seja, falta a expressão a ser maximizada). Não há outra informação sobre a função objetivo nos dados fornecidos.

Passo 2

Vou primeiro explicar por que a ausência da função objetivo impede uma “solução ótima” numérica e o que ainda é possível fazer:
  • Para resolver graficamente um problema de otimização linear precisa-se da função objetivo, típica forma \; \max\; c_{1}x_{1}+c_{2}x_{2}\; (ou \min). Sem os coeficientes c_{1},c_{2} não dá para dizer qual ponto da região factível é ótimo.
  • Mesmo assim, podemos analisar completa e explicitamente a região factível (conjunto de pontos que satisfazem todas as restrições). Isso é útil porque, com a região em mãos, eu mostro exatamente como se procederia graficamente quando a função objetivo for dada.

Passo 3

Simplifico a primeira desigualdade (faça devagar para não se perder):
A desigualdade é
- x_{1} - x_{2} + x_{2} \le -3.
Os termos -x_{2} e +x_{2} se cancelam: -x_{2}+x_{2}=0. Logo sobra
- x_{1} \le -3.
Multiplicando ambos os lados por -1 (lembre que ao multiplicar por -1 a desigualdade inverte):
x_{1} \ge 3.
Portanto, a primeira restrição é simplesmente \;x_{1}\ge3\;.

Passo 4

Agora escrevo todas as restrições de forma simples:
x_{1} \ge 3,
x_{1} + 2x_{2} \le 4,
x_{1} \ge 0,\quad x_{2} \ge 0.
Mas note que x_{1}\ge3 já implica x_{1}\ge0, então a restrição x_{1}\ge0 é redundante aqui. O que resta efetivamente é:
x_{1}\ge3,\quad x_{2}\ge0,\quad x_{1}+2x_{2}\le4.

Passo 5

Determino os vértices (pontos extremos) da região factível — passo essencial para a solução gráfica de qualquer problema linear (teorema dos vértices: máximo/mínimo linear ocorre em vértice ou aresta):
  • Interseção entre x_{1}=3 e x_{2}=0 dá o ponto \;(3,0)\;.
  • Interseção entre x_{1}=3 e x_{1}+2x_{2}=4. Substituo x_{1}=3 em 3+2x_{2}=4 e obtenho 2x_{2}=1 então x_{2}=\tfrac{1}{2}. Logo o ponto é \;\bigl(3,\tfrac{1}{2}\bigr)\;.
  • Interseção entre x_{2}=0 e x_{1}+2x_{2}=4 x_{1}=4, então o ponto é \;(4,0)\;.
Assim a região factível é o triângulo convexo com vértices
(3,0),\quad \bigl(3,\tfrac{1}{2}\bigr),\quad (4,0).
Esse triângulo é compacto (fechado e limitado), logo qualquer função linear objetivo terá valor máximo e mínimo atingidos nesse triângulo.

Passo 6

Explico didaticamente como resolver graficamente quando a função objetivo for dada (passo a passo que você pode usar no exame):
  • Suponha a função objetivo \;z=c_{1}x_{1}+c_{2}x_{2}\; que queremos maximizar. Para um valor fixo z_{0} a equação c_{1}x_{1}+c_{2}x_{2}=z_{0} é uma reta (linha de nível) no plano. Varia-se z_{0} e desloca-se essa reta paralelamente até o último ponto em que ela ainda intersecta a região factível; esse último contato é o ótimo.
  • Pelo teorema dos vértices, o ótimo será sempre um dos vértices (3,0),\; (4,0),\; (3,\tfrac{1}{2}) ou possivelmente toda uma aresta inteira se a reta de nível ficar exatamente alinhada (paralela) com uma aresta que contém pontos factíveis ótimos.
  • Para decidir qual vértice é ótimo basta calcular z nesses três vértices e pegar o maior (ou menor, se fosse minimização). Isto dá cálculo rápido sem desenhar muito: calcule c_{1}\cdot3+c_{2}\cdot0, c_{1}\cdot4+c_{2}\cdot0 e c_{1}\cdot3+c_{2}\cdot\tfrac{1}{2}.
Exemplos rápidos para fixar:
  • Se \;z=x_{1}\; (isto é, c_{1}=1,c_{2}=0) então valores nos vértices: 3,4,3\cdot1+\tfrac{1}{2}\cdot0=3. O máximo é 4 em (4,0) — solução única.
  • Se \;z=x_{2}\; (isto é, c_{1}=0,c_{2}=1) então valores: 0,0,\tfrac{1}{2}. O máximo é \tfrac{1}{2} em \bigl(3,\tfrac{1}{2}\bigr) — solução única.
  • Situação de múltiplas soluções: ocorre quando a reta de nível é paralela a uma aresta e o deslocamento máximo alcança toda essa aresta. Ex.: se a reta de nível for paralela à aresta entre (3,0) e (4,0) (essa aresta é horizontal, direção (1,0)), então a função objetivo deve ter coeficiente c_{2}=0 (ou seja, depender só de x_{1}). Nesse caso, se o máximo ocorrer nessa aresta, todos os pontos da aresta teriam o mesmo valor — daí múltiplas soluções. (Note: se c_{2}=0 o valor nos vértices (3,0) e (4,0) são diferentes a menos que c_{1}=0; logo para concretizar múltiplas soluções na aresta horizontal precisa de condições específicas nos coeficientes que façam a mesma avaliação em todos os pontos da aresta e maior que em (3,\tfrac{1}{2}). Em termos gerais, múltiplas soluções ocorrem exatamente quando a direção do gradiente da função objetivo é perpendicular ao vetor normal da aresta, i.e., quando as isolinhas são paralelas à aresta.)

Passo 7

Concluo as consequências relevantes (resumo prático que você usa na prova):
  • A região factível está completamente determinada e é o triângulo com vértices (3,0),\\ (4,0),\\ (3,\tfrac{1}{2}).
  • Como a região é limitada, para qualquer função linear objetivo existe máximo e mínimo finitos atingidos na região.
  • A unicidade ou multiplicidade da solução depende dos coeficientes da função objetivo: tipicamente a solução é única (ocorre em um vértice); é múltipla somente se a reta de nível da função objetivo for paralela a uma aresta factível que seja a fronteira do ótimo; não há caso de solução ilimitada (unbounded) porque a região factível é limitada.

Resposta

(i) Não é possível determinar numericamen­te a solução ótima porque a função objetivo não foi fornecida; entretanto a região factível é o triângulo com vértices \;(3,0),\;\bigl(3,\tfrac{1}{2}\bigr),\;(4,0)\; e, uma vez dada a função objetivo \;z=c_{1}x_{1}+c_{2}x_{2}\;, resolve‑se graficamente deslocando a reta c_{1}x_{1}+c_{2}x_{2}=z até o último contato — o ótimo será um dos vértices (ou uma aresta inteira se houver degenerescência).
(ii) Para qualquer função linear objetivo existe solução e ela é finita (a região é limitada); a solução é normalmente única (ocorre em um vértice) e será múltipla somente se os coeficientes da função objetivo fizerem as isolinhas paralelas a uma aresta que contenha o ótimo; a solução não é ilimitada.

Exercícios relacionados