Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Resolva graficamente o seguinte problema de programação linear

+2 votos
52 visitas
perguntada Out 4 em Finanças por Stuart Mill (504 pontos)  
editado Out 4 por Stuart Mill

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 \)

Compartilhe
comentou Out 4 por Stuart Mill (504 pontos)  
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).

2 Respostas

+1 voto
respondida Out 4 por Stuart Mill (504 pontos)  
editado Nov 21 por Stuart Mill

\( \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:
A imagem será apresentada aqui.
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:

A imagem será apresentada aqui.

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):
    A imagem será apresentada aqui.
    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:
    A imagem será apresentada aqui.

  • Restrições R5 e R6 (restrições de não negatividade):A imagem será apresentada aqui.
    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));
comentou Out 13 por danielcajueiro (5,376 pontos)  
Seria legal vc colocar o código utilizado para traçar as imagens em maple (?).
comentou Out 18 por Stuart Mill (504 pontos)  
Adicionei o código à resposta!
0 votos
respondida Nov 20 por Pedro Campelo (46 pontos)  
editado Nov 20 por Pedro Campelo

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() 

A imagem será apresentada aqui.

comentou Nov 21 por Stuart Mill (504 pontos)  
Obrigado! Excelente, Pedro.
...