Og é o líder de uma tribo de homens das cavernas, a Águas Calmas, surpreendentemente avançada matematicamente, embora tecnologicamente da “época roda do moinho”. Ele deve decidir o número de clavas e o número de machados de pedra que devem ser produzidos para a futura batalha contra a tribo vizinha, a Pôr-do-Sol Tranqüilo. A experiência ensinou a ele que cada clava causa em média 0,45 morte e 0,65 mutilação, enquanto cada machado causa 0,70 morte e 0,35 mutilação. A produção de clavas requer 5,1 lb de pedra e 2,1 homens-hora de trabalho, enquanto um machado requer 3,2 lb de pedra e 4,3 homens-hora de trabalho. A tribo de Og tem 240 lb de pedra disponíveis para a produção de armas e um total de 200 homens-hora de trabalho disponíveis antes da data esperada da batalha (que Og tem certeza de que terminará de vez com a guerra). Og avalia que uma morte vale duas mutilações na quantificação do estrago causado ao inimigo e deseja produzir um lote de armas que maximize esse estrago.
(a) Formule esse problema como um problema de programação linear. Certifique-se de definir suas variáveis de decisão.
(b) Represente esse problema graficamente, certificando-se de distinguir os vértices viáveis dos vértices não-viáveis.
(c) Resolva o problema graficamente.
(d) Resolva o problema usando o computador.

Passo 1

O enunciado pede que Og escolha quantas clavas e quantos machados produzir para maximizar o “estrago” medido como 2 mortes +1 mutilação. Cada clava dá em média 0,45 mortes e 0,65 mutilações, cada machado dá 0,70 mortes e 0,35 mutilações. A produção consome pedra e trabalho, com totais disponíveis de 240 lb de pedra e 200 homens-hora. O conteúdo é formulação e solução de um problema de Programação Linear (PL), usando método gráfico e depois solução por computador.

Passo 2

Definimos as variáveis de decisão:
x1 = número de clavas
x2 = número de machados
O valor de “estrago” por clava é
2cdot0,45 + 1cdot0,65 = 1,55
e por machado é
2cdot0,70 + 1cdot0,35 = 1,75
Logo a PL é:
maximizar z = 1,55,x1 + 1,75,x2
sujeito a
5,1,x1 + 3,2,x2 <= 240, 2,1,x1 + 4,3,x2 <= 200, x1>=0,;x2>=0

Passo 3

Para desenhar o região viável no plano (x1,x2), achamos os interceptos:
– Na restrição pedra: x1=0implies x2=240/3,2=75 e x2=0implies x1=240/5,1approx47,06.
– Na restrição trabalho: x1=0implies x2=200/4,3approx46,51 e x2=0implies x1=200/2,1approx95,24.
O polígono viável é limitado por x1>=0, x2>=0, a reta pedra e a reta trabalho. Seus vértices candidatos são
(0,0), l(47,06,0r), l(0,46,51r) e a interseção das duas retas.

Passo 4

Resolvendo
5,1,x1+3,2,x2=240, 2,1,x1+4,3,x2=200,
o determinante é D=5,1cdot4,3-3,2cdot2,1=15,21. Calcula-se
x1=240cdot4,3-3,2cdot20015,21approx25,78, x2=5,1cdot200-2,1cdot24015,21approx33,92

Passo 5

Avalia-se z em cada vértice:
(0,0): z=0.
l(47,06,0r): z=1,55cdot47,06approx73,0.
l(0,46,51r): z=1,75cdot46,51approx81,4.
l(25,78,33,92r):
z=1,55cdot25,78+1,75cdot33,92approx39,96+59,36=99,32
O maior valor é zapprox99,32 no ponto (x1,x2)approx(25,78,,33,92).

Passo 6

Usando um solver de PL (por exemplo Excel Solver, GLPK ou outro), obtém-se exatamente a mesma solução ótima contínua:
x1approx25,78, x2approx33,92, zmaxapprox99,32

Resposta

(a) Variáveis x1,x2 e PL
max z=1,55x1+1,75x2
sujeito a
5,1x1+3,2x2<=240,; 2,1x1+4,3x2<=200,; x1,x2>=0
(b) Região viável é o polígono cujos vértices são (0,0), (47,06,0), (0,46,51) e (25,78,33,92).
(c) Ponto ótimo pelo método gráfico: (x1,x2)approx(25,78,,33,92), com zmaxapprox99,32.
(d) Solver de computador confirma x1approx25,78, x2approx33,92, zmaxapprox99,32.

Exercícios de Livros Relacionados