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

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

+2 votos
68 visitas
perguntada Set 26 em Finanças por Pedro Campelo (46 pontos)  
editado Out 8 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 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 por Stuart Mill (504 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 por Pedro Campelo (46 pontos)  
editado Out 17 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 por Stuart Mill (504 pontos)  
Com certeza! Ficou bem claro como as várias restrições interagem e o processo de encontrar o ótimo.
comentou Out 8 por Pedro Campelo (46 pontos)  
Muito obrigado!
...