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

Como resolver graficamente o problema de programação linear?

+2 votos
79 visitas
perguntada Set 26, 2018 em Finanças por Pedro Campelo (46 pontos)  
editado Out 8, 2018 por Pedro Campelo

Resolva graficamente o seguinte problema de programação linear:

\( \underset{x,y}{Minimizar} \text{ } (9x + 8y) \)

s.a.

\( x - 2y \leq 3 \text{ (1)} \)
\( 3 x -4y \geq 5 \text{ (2)} \)
\( 6x - 7y = 3 \text{ (3)} \)
\( x \geq 0 \text{ e } y \geq 0 \text{ (4)} \)

Use e abuse das figuras.

Compartilhe

1 Resposta

0 votos
respondida Set 26, 2018 por Pedro Campelo (46 pontos)  

A questão foi resolvida no Python.

Primeiro, é preciso desenhar o problema de minimização. Fica fácil perceber que sem restrição nenhuma, os valores de \( x \text{ e } y \) que minimizam a função são \( (x,y) \to (-\infty, -\infty )\).

A imagem será apresentada aqui.

Agora, são analisadas todas as restrições:

- Restrição 1 (Verde):

\( x−2y \leq 3 \Longrightarrow y \geq \frac{1}{2}x - \frac{3}{2} \)

Os pontos possíveis de x e y estão representados na área pintada de cinza no gráfico abaixo (lado esquerdo/superior da reta).

A imagem será apresentada aqui.

Juntando esta restrição com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) \to (-\infty, -\infty )\).

A imagem será apresentada aqui.

Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, pode-se observar que o ponto que minimizaria a função é \( (x,y) = (0, 0 )\).

A imagem será apresentada aqui.

- Restrição 2 (Amarela):

\( 3x−4y \geq 5 \Longrightarrow y \leq \frac{3}{4}x - \frac{5}{4} \)

Os pontos possíveis de x e y estão representados na área pintada de cinza no gráfico abaixo (lado direito/inferior da reta).

A imagem será apresentada aqui.

Juntando esta restrição com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) \to (-\infty, -\infty )\).

A imagem será apresentada aqui.

Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, observa-se que o ponto que minimizaria a função é \( (x,y) = \big(\frac{5}{3},0\big) \).

A imagem será apresentada aqui.

- Restrição 3 (Azul):

\( 6x−7y = 8 \Longrightarrow y = \frac{6}{7}x - \frac{8}{7} \)

Os pontos possíveis de x e y serão todos os pontos que pertencem a equação acima, isto é, todos os pontos que estão em cima da reta azul abaixo.

A imagem será apresentada aqui.

Juntando esta restrição com a função a ser minimizada, é possível verificar que os valores otimizam esta função são os menores valores de x e y que satisfazem a equação acima, ou seja, \( (x,y) \to (-\infty, -\infty )\).

A imagem será apresentada aqui.

Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, observa-se que o ponto que minimizaria a função é \( (x,y) = \big(\frac{4}{3},0\big) \).

A imagem será apresentada aqui.

- Restrição 4:

\( x \geq 0 \text{ e } y \geq 0 \)

Esta restrição considera só os valores positivos de x e y. Assim, a área pintada de cinza no gráfico abaixo é todo o primeiro quadrante dos valores positivos.

A imagem será apresentada aqui.

Juntando esta restrição com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) = (0, 0)\).

A imagem será apresentada aqui.

Agora, analiso as combinações das restrições e por fim, todas as restrições em conjunto.

- Restrições 1 e 2:

\( x−2y \leq 3 \Longrightarrow y \geq \frac{1}{2}x - \frac{3}{2} \)
\( 3x−4y \geq 5 \Longrightarrow y \leq \frac{3}{4}x - \frac{5}{4} \)

Os pontos possíveis de x e y serão todos os pontos que pertencem ao cone pintado de cinza entre as retas verde a amarela.

A imagem será apresentada aqui.

Juntando estas restrições com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) = (-1, -2 )\).

A imagem será apresentada aqui.

Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, observa-se que o ponto que minimizaria a função é \( (x,y) = \big(\frac{5}{3},0\big) \):

A imagem será apresentada aqui.

- Restrições 1 e 3:

\( x−2y \leq 3 \Longrightarrow y \geq \frac{1}{2}x - \frac{3}{2} \)
\( 6x−7y = 8 \Longrightarrow y = \frac{6}{7}x - \frac{8}{7} \)

Os pontos possíveis de x e y serão todos os pontos ao lado esquerdo e superior da reta verde e em cima da reta azul.

A imagem será apresentada aqui.

Juntando estas restrições com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) = (-1, -2 )\).

A imagem será apresentada aqui.

Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, observa-se que o ponto que minimizaria a função é: \( (x,y) = \big(\frac{4}{3},0\big) \).

A imagem será apresentada aqui.

- Restrições 2 e 3:

\( 3x−4y \geq 5 \Longrightarrow y \leq \frac{3}{4}x - \frac{5}{4} \)
\( 6x−7y = 8 \Longrightarrow y = \frac{6}{7}x - \frac{8}{7} \)

Os pontos possíveis de x e y serão todos os pontos ao lado direito e inferior da reta amarela e em cima da reta azul . É possível verificar que o primeiro ponto possível entre as duas restrições é o \( (x,y) = (-1,-2)) \), e os próximos pontos factíveis são todos negativos.

A imagem será apresentada aqui.

Juntando estas restrições com a função a ser minimizada, é possível verificar que os valores otimizam esta função são \( (x,y) \to (-\infty, -\infty ) \).

A imagem será apresentada aqui.
Porém, considerando só os valores positivos de x e y, isto é, juntando com a restrição 4, observa-se que não existe nenhum ponto que satisfaça as duas restrições (visto que o primeiro ponto possível é \( (x,y) = (-1,-2) \)).

A imagem será apresentada aqui.

- Todas as restrições:

\( x−2y \leq 3 \Longrightarrow y \geq \frac{1}{2}x - \frac{3}{2} \)
\( 3x−4y \geq 5 \Longrightarrow y \leq \frac{3}{4}x - \frac{5}{4} \)
\( 6x−7y = 8 \Longrightarrow y = \frac{6}{7}x - \frac{8}{7} \)
\( x \geq 0 \text{ e } y \geq 0 \)

Agora, juntando todas as restrições, vemos que todos os pontos possíveis de x e y estão no cone pintada de cinza entre as retas verde e amarelo, em cima da reta azul, e os valores positivos de x e y. Então, fica fácil perceber que não existe nenhum ponto factível que satisfaça as 4 restrições.

A imagem será apresentada aqui.

Caso não existisse a restrição 4, que considera os valores positivos de x e y, o ponto que minimizaria a função em questão é \( (x,y) = (-1,-2) \), que é a interseção entre as 3 retas.

A imagem será apresentada aqui.

comentou Out 8, 2018 por Stuart Mill (704 pontos)  
Resolução bem detalhada!

Uma dúvida, eu não tenho experiência com programação linear. Neste caso, não será condição suficiente analisar a situação com todas as restrições e verificar que o único conjunto de pontos que satisfazem todas é o conjunto vazio (graficamente, como se não existisse um espaço delimitado pelas restrições)?
comentou Out 8, 2018 por Pedro Campelo (46 pontos)  
editado Out 17, 2018 por Pedro Campelo
Olá Stuat Mill, obrigado pelo comentário.

Sim, bastaria fazer um gráfico com todas as restrições juntas e verificar que não existe solução para o problema.  Bastaria colocar a penúltima imagem na resposta e seria possível verificar a inexistência de solução.

Porém, como a questão pede para "usar e abusar" das figuras, criei diversas combinações das restrições que tornam a resposta mais fácil de ser visualizada.
comentou Out 8, 2018 por Stuart Mill (704 pontos)  
Com certeza! Ficou bem claro como as várias restrições interagem e o processo de encontrar o ótimo.
comentou Out 8, 2018 por Pedro Campelo (46 pontos)  
Muito obrigado!
...