Programação Linear

Prévia do material em texto

2.2 Solução Gráfica 
Problemas de PL com até três variáveis decisórias permitem solução gráfica, o que possibilita uma melhor 
visualização do problema e interpretação dos resultados. A solução gráfica pode ser sistematizada em um 
conjunto de etapas: 
• representar cada restrição em um gráfico bidimensional; 
• determinar a área das soluções possíveis; 
• representar graficamente a função objetivo, atribuindo valores arbitrários e incrementais à z; 
o maximização → retas paralelas da função z até encontrar o ponto mais afastado da origem no 
polígono da área das soluções possíveis; 
o minimização → retas paralelas da função z até encontrar o ponto mais próximo da origem no 
polígono da área das soluções possíveis; 
• identificar o ponto ótimo para a função objetivo. 
 
Assim, na solução ótima do problema do Exemplo 1 x1= 40, x2= 40 e z = 1*40 + 1,5*40 = 100, ou seja, 
devem ser produzidas 40 unidades do produto P1 e 40 unidades do produto P2 para que o lucro total da 
empresa alcance o valor máximo de $100. Observe que a solução ótima ocorre na intersecção entre as 
restrições de capacidade dos Dpto A e B, que trabalhariam em seu limite, enquanto o Dpto C operaria com 
uma folga de 40 horas homem / semana. 
 
É também importante verificar o atendimento das restrições: 
Capacidade Dpto A: 2*x1 + 2*x2 ≤ 160 ⇒ 2*40 + 2*40 =160 ⇒ ok 
Capacidade Dpto B: x1 + 2*x2 ≤ 120 ⇒ 40 + 2*40 = 120 ⇒ ok 
Capacidade Dpto C: 4*x1 + 2*x2 ≤ 280 ⇒ 4*40 + 2*40 = 240⇒ ok 
 
2.2.1 Casos Especiais 
Algumas vezes a solução ótima de um problema de PL pode não ser um ponto, existindo soluções 
alternativas ou soluções tendendo ao infinito e, até mesmo, não existir soluções. 
Ocorrem soluções ótimas alternativas, ou múltiplas, quando a linha formada pela função objetivo 
(isocusto) intersecciona a linha limítrofe do espaço de soluções viáveis, como ilustrado a seguir. 
 
As soluções tendendo ao infinito, ou ilimitadas, ocorrem quando as restrições formam um espaço aberto 
de soluções viáveis como mostra a Figura abaixo (esquerda), indicando uma formulação incorreta em 
problemas de maximização. 
 
Os problemas sem solução são caracterizados por um conjunto de restrições que não formam um espaço 
de soluções viáveis, como caracterizado na Figura acima (direita). 
 
Exercícios 
Exercício 2. 
Resolva graficamente o problema a seguir, com solução ótima disponível: max z = 8x1 + 11x2; sujeito 
à 5x1 + 4x2 ≤ 40; -4x1 + 2x2 ≤ 12; 8x1 + 10x2 ≤ 80; e x1 ≥ 0, x2 ≥ 0. 
Exercício 3. 
Resolva graficamente o problema a seguir, com solução ótima disponível: max z= 4x1 + 2x2; sujeito à 
3x1 + x2 ≤ 9; x1 + x2 ≤ 6; x1 + x2 ≤ 9; e x1 ≥ 0, x2 ≥ 0. 
Exercício 4. 
Resolva graficamente o problema a seguir, com solução ótima disponível: max z= 5x1 + 4x2; sujeito à 
8x1 + 5x2 ≤ 32; 5x1 + 6x2 ≤ 30; e x1 ≥ 0, x2 ≥ 0. 
Exercício 5. 
Resolva graficamente o problema a seguir, com solução ótima disponível: max z= 2x1 + 3x2; sujeito à 
8x1 + 3x2 ≤ 24; x1 + x2 ≤ 4; 3x1 + 6x2 ≤ 18; e x1 ≥ 0, x2 ≥ 0. 
Exercício 6. 
 
Resolva graficamente o problema a seguir, com solução tendendo ao infinito: max z= 20x1 + 40x2; 
sujeito à 2x1 - 3x2 ≤ 6; -4x1 + 2x2 ≤ 8; 5x1 + 3x2 ≥ 15; e x1 ≥ 0, x2 ≥ 0. 
Exercício 7. 
Demonstre graficamente que o problema a seguir não possui solução viável: max z= 3x1 + 5x2; 
sujeito à 5x1 + 5x2 ≤ 25; 9x1 + 13x2 ≥ 117; e x1 ≥ 0, x2 ≥ 0. 
Exercício 8. 
Resolva graficamente o problema a seguir, com solução ótima disponível: min z= 4x1 + x2; sujeito à -
1x1 + x2 ≤ 2; 4x1 + 5x2 ≥ 20; x1 + x2 ≤ 6; x1 ≤ 3 e x1 ≥ 0, x2 ≥ 0. 
Exercício 9. 
Resolva graficamente o problema a seguir, com solução ótima disponível: min z= 120x1 + 60x2; 
sujeito à 8x1 + 4x2 ≤ 32; 2x1 + 12x2 ≥ 24; 9x1 + 10x2 ≤ 90; x2 ≤ 5 e x1 ≥ 0, x2 ≥ 0. 
Exercício 10. 
Resolva graficamente o problema a seguir, com solução ótima disponível: max z= 20x1 + 40x2; 
sujeito à 2x1 - 3x2 ≤ 6; -4x1 + 2x2 ≤ 8; 5x1 + 3x2 ≥ 15; e x1 ≥ 0, x2 ≥ 0.