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;
\max z=2 x_{1}+x_{2}
sujeito a 2 x_{1}+x_{2} \leq 4
2 x_{1}+3 x_{2} \leq 3
4 x_{1}+x_{2} \leq 5
x_{1}+5 x_{2} \leq 1
x_{1}, x_{2} \geq 0

Passo 1

O enunciado pede duas coisas: (i) resolver graficamente o problema de otimização linear dado, se for possível; (ii) dizer se a solução, quando existir, é única, múltipla ou ilimitada. Os dados do problema são: a função objetivo e as restrições
\text{max } z = 2x_{1} + x_{2}
sujeito a
2x_{1}+x_{2}\le 4,
2x_{1}+3x_{2}\le 3,
4x_{1}+x_{2}\le 5,
x_{1}+5x_{2}\le 1,
x_{1}\ge 0,\quad x_{2}\ge 0.
Listei todas as desigualdades e a função objetivo; a resolução começa a seguir.

Passo 2

Vamos transformar cada desigualdade em sua reta correspondente (caso de igualdade) para poder desenhar o gráfico e identificar a região factível. Para cada reta eu calculo os interceptos com os eixos, porque isso facilita desenhar à mão num papel:
  • Para 2x_{1}+x_{2}=4: intercepto em x_{1}=0 x_{2}=4; intercepto em x_{2}=0 x_{1}=2.
  • Para 2x_{1}+3x_{2}=3: intercepto em x_{1}=0 x_{2}=1; intercepto em x_{2}=0 x_{1}=3/2.
  • Para 4x_{1}+x_{2}=5: intercepto em x_{1}=0 x_{2}=5; intercepto em x_{2}=0 x_{1}=5/4.
  • Para x_{1}+5x_{2}=1: intercepto em x_{1}=0 x_{2}=1/5=0{,}2; intercepto em x_{2}=0 x_{1}=1.
A regra do gráfico: a região factível é o conjunto de pontos com x_{1}\ge0, x_{2}\ge0 que satisfazem todas as desigualdades (ou seja, ficam “abaixo” de cada uma das retas, porque todas são do tipo \le). Observação útil: na origem dos eixos (quando x_{1}=0 ou x_{2}=0) a restrição mais restritiva (a que dá o menor valor) geralmente “domina” — isso nos dá uma ideia de qual reta limita o conjunto perto dos eixos.

Passo 3

Compare os interceptos nas bordas dos eixos para ver qual desigualdade é a mais restritiva perto do eixo:
  • Em x_{1}=0 temos os valores máximos permitidos de x_{2}:
    x_{2}\le 4,\; x_{2}\le 1,\; x_{2}\le 5,\; x_{2}\le 0{,}2.
    O menor é 0{,}2 (da reta x_{1}+5x_{2}=1). Logo, na interseção com o eixo x_{1}=0 a restrição x_{1}+5x_{2}\le1 é a mais forte.
  • Em x_{2}=0 temos os valores máximos permitidos de x_{1}:
    x_{1}\le 2,\; x_{1}\le 1{,}5,\; x_{1}\le 1{,}25,\; x_{1}\le 1.
    O menor é 1 (novamente da reta x_{1}+5x_{2}=1). Logo, na interseção com o eixo x_{2}=0 a restrição x_{1}+5x_{2}\le1 é a mais forte.
Conclusão intuitiva: perto dos eixos a reta x_{1}+5x_{2}=1 (vou chamá-la de L_{4}) é a que “fecha” a região mais perto da origem. Precisamos verificar se L_{4} também é a restrição dominante para pontos entre esses interceptos (isto é, para x_{1} entre 0 e 1).

Passo 4

Para ter certeza que a região factível é realmente limitada por L_{4} entre os eixos, comparo x_{2} dado por L_{4} com x_{2} dado pelas outras retas para um mesmo x_{1}. A expressão de L_{4} é
x_{2}=\frac{1-x_{1}}{5}.
Comparo com as demais expressões:
L_{1}:\; x_{2}=4-2x_{1},\qquad L_{2}:\; x_{2}=1-\tfrac{2}{3}x_{1},\qquad L_{3}:\; x_{2}=5-4x_{1}.
Faço as desigualdades (exemplo) para x_{1}\in[0,1]:
\frac{1-x_{1}}{5}\le 4-2x_{1}\quad\text{vale para }x_{1}\le 19/9,
\frac{1-x_{1}}{5}\le 1-\tfrac{2}{3}x_{1}\quad\text{vale para }x_{1}\le 12/7,
\frac{1-x_{1}}{5}\le 5-4x_{1}\quad\text{vale para }x_{1}\le 24/19.
Todas essas desigualdades são verdadeiras em particular para todo x_{1}\in[0,1]. Assim, no intervalo entre os interceptos com os eixos, L_{4} produz valores de x_{2} menores ou iguais aos das outras retas; logo L_{4} efetivamente é a restrição que define a fronteira superior da região factível naquele trecho. Portanto a região factível é o triângulo formado por:
  • o ponto A=(0,0) (origem),
  • o ponto B=(1,0) (interseção de L_{4} com o eixo x_{2}=0),
  • o ponto C=(0,\tfrac{1}{5}) (interseção de L_{4} com o eixo x_{1}=0).

Passo 5

Verificação extra: calculei as interseções de L_{4}\) com as outras retas para checar se alguma delas cruzava o segmento entre \(B\) e \(C\). Resolver, por exemplo, \(x_{1}+5x_{2}=1\) com \(2x_{1}+3x_{2}=3\) dá \[\begin{cases} x_{1}+5x_{2}=1,\\[4pt] 2x_{1}+3x_{2}=3. \end{cases}
Multiplicando a primeira por 2\] e subtraindo a segunda obtemos \(7x_{2}=-1, logo x_{2}=-1/7<0. Igual para as interseções com L_{1} e L_{3}: todas resultaram em x_{2}<0. Isso confirma que as interseções entre L_{4} e as outras retas ficam fora do primeiro quadrante, então dentro do primeiro quadrante a fronteira é realmente o segmento BC (mais os eixos formando o triângulo ABC).]

Passo 6

Agora aplico a propriedade fundamental da programação linear (explicada didaticamente): quando a região factível é poligonal e a função objetivo é linear, o máximo (ou mínimo) ocorre em algum vértice (ponto extremo) do polígono factível. Aqui os vértices são:
A=(0,0),\quad B=(1,0),\quad C=\Big(0,\tfrac{1}{5}\Big).
Calculo o valor da função objetivo z=2x_{1}+x_{2} em cada vértice:
  • Em A=(0,0): z(A)=2\cdot 0 + 0 = 0.
  • Em B=(1,0): z(B)=2\cdot 1 + 0 = 2.
  • Em C=\Big(0,\tfrac{1}{5}\Big): z\text{(C)}=2\cdot 0 + \tfrac{1}{5} = 0{,}2.
Portanto o maior valor é z(B)=2, alcançado em B=(1,0).

Passo 7

Motivo da unicidade: a função objetivo é linear e, ao restringi-la ao segmento BC (o segmento da reta L_{4} entre os eixos) ela é uma função afim de x_{1}. Parametrizando o segmento por x_{1}=t com t\in[0,1], temos x_{2}=(1-t)/5 e
z(t)=2t + \frac{1-t}{5} = \frac{9}{5}t + \frac{1}{5} = 1{,}8\,t + 0{,}2.
Isto é uma função estritamente crescente em t, portanto no segmento BC o máximo ocorre apenas em t=1, isto é, em B. Nos outros dois segmentos da fronteira (entre A e B e entre A e C) também o máximo ocorre em B. Logo a solução ótima é única.

Resposta

Solução ótima: x_{1}=1,\;x_{2}=0 com z_{\max}=2.
Tipo: solução única.

Exercícios relacionados