Resolva graficamente o seguinte problema de programação linear

Question

Resolva o seguinte problema (fazendo \( x_1 = x\) e \(x_2 = y\) para simplificar a notação):

\( \max\limits_{x,y}3x + y\)
s.a.
\(R1: -x+y \le -1 \)
\(R2: -3x -y \le -1 \)
\(R3: 4x +2y \le 1 \)
\(R4: 2y \le -1 \)
\(R5: x \ge 0 \)
\(R6: y \ge 0 \)

Comments

Fiz os gráficos com o Maple (acho que pelo formato mais leve utilizado na exportação, a qualidade das imagens não ficou tão boa).

Answer 1

\( \max\limits_{x,y}3x + y\)
s.a.
\(R1: -x+y \le -1 \)
\(R2: -3x -y \le -1 \)
\(R3: 4x +2y \le 1 \)
\(R4: 2y \le -1 \)
\(R5: x \ge 0 \)
\(R6: y \ge 0 \)

• Restrição 1 (R1):

Com a primeira restrição, tem-se:

Com a região azul sendo o espaço de soluções factíveis à restrição. É visível que existem infinitos caminhos ilimitados no espaço azul, e portanto a maximização não tem solução real.

• Restrição 2 (R2):
  Adicionando R2, temos:

Igualmente, ainda existem infinitos caminhos ilimitados para os argumentos da função, implicando na função objetivo assumindo valores tão grandes quanto se queira. Para que haja solução real, uma condição necessária é que a imagem seja limitada por cima nesse caso.

• Restrição 3 (R3):
  
  Adicionando essa restrição, a imagem se torna limitada por cima, e portanto podemos buscar uma solução real. A função objetivo é paralela a R3 e aumenta para cima e para a direita.

• Restrição 4 (R4):
  O espaço de soluções factíveis não se altera:
  

• Restrições R5 e R6 (restrições de não negatividade):
  De fato, adicionando as restrições de não negatividade, o conjunto de possíveis soluções se torna um conjunto vazio. Isso é evidente pela incompatibilidade entre R4 e R6:
  \( R4 \implies y < 0 \)
  \( R6 \implies y \ge 0 \)

As duas condições são contraditórias e, portanto, isso é condição suficiente para não existência de solução real para o problema. Segue abaixo o código usado no Maple 13.

with(plots):
inequal({-x+y <= -1}, x = -3 .. 3, y = -3 .. 3, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white));
inequal({-3*x-y <= -1, -x+y <= -1}, x = -3 .. 3, y = -3 .. 3, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white));
inequal({-3*x-y <= -1, -x+y <= -1, 4*x+2*y <= 1}, x = -3 .. 3, y = -3 .. 3, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white));


inequal({2*y <= -1, -3*x-y <= -1, -x+y <= -1, 4*x+2*y <= 1}, x = -3 .. 3, y = -3 .. 3, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white))
inequal({x >= 0, y >= 0, 2*y <= -1, -3*x-y <= -1, -x+y <= -1, 4*x+2*y <= 1}, x = -3 .. 3, y = -3 .. 3, optionsfeasible = (color = blue), optionsclosed = (color = green), optionsclosed = (color = red), optionsexcluded = (color = white));

Comments

Seria legal vc colocar o código utilizado para traçar as imagens em maple (?).

---

Adicionei o código à resposta!

Answer 2

Olá Stuart Mill, parabéns pela sua questão. Está bem clara e objetiva. Da mesma forma que na minha questão de programação dinâmica (http://prorum.com/?qa=3773/como-resolver-graficamente-problema-de-programacao-linear&show=3776#a3776), as restrições de positividade de x e y, fazem com que o problema não tenha solução.

Talvez se fizer a questão no python, seria possível obter uma imagem com uma resolução um pouco melhor. Caso tenha interesse, fiz um programa para calcular o gráfico com todas as restrições, assim como a sua última imagem:

import numpy as np  
import matplotlib.pyplot as plt  

x = np.linspace(-10,10)                

y1=x-1
y2=-3*x+1
y3=-2*x+(1/2)

yp = (-1/2)
xp = (1/2)

plt.axis([-3, 3, -3, 3])
plt.axhline(0, color='black')
plt.axvline(0, color='black')
plt.axhline((-1/2), color='blue') 
plt.plot(x, y1, color='blue')  
plt.plot(x, y2, color='blue')    
plt.plot(x, y3, color='blue')    
plt.plot(xp, yp, 'ro') 
#plt.fill_between(x, y2, y3, color='lightgrey', alpha=2)
plt.xlabel('eixo x')
plt.ylabel('eixo y')
plt.title('Restrições 1 a 4')
#plt.grid() 
plt.savefig('grafico1.png')    
plt.show() 

Comments

Obrigado! Excelente, Pedro.