Pesquisa operacional/Introdução à Programação Linear: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
Sem resumo de edição |
|||
Linha 83:
Pronto! Terminamos de construir o nosso modelo!
==Solução Gráfica==
Muito bem! Já sabemos como criar os modelos de Programação Linear. Mas... Como podemos resolvê-los? Como usar todos aqueles algoritmos comentados na seção sobre a história da Programação Linear? Bem, vamos com calma. Vamos ver primeiro uma das formas mais simples de se resolver este problema (embora não seja computacionalmente eficiente). Vamos fazer um gráfico analizando o Domínio da função-objetivo mostrada no exempo acima:
[[Imagem:Grafico_programacao_linear.png]]
As linhas mais finas representam o eixo X e Y, os quais representam respectivamente o número de mesas (M) e cadeiras (C). Todos os pontos dentro ou abaixo àquela reta grossa mais inclinada verticalmente representam pontos que satisfazem a Restrição 2. Todos os pontos deitro ou abaixo àquela reta grossa inclinada mais horizontalmente satisfazem a Restrição 1. Pontos à direita da reta Y e àcima do eixo X satisfazem a exigência de que não podemos fabricar um número negativo de objetos. Quanto mais restrições um ponto no gráfico acima satisfaz, mais escuro ele aparece. A única região onde todas as restrições são satisfeitas é aquele triângulo escuro localizado próximo ao centro do gráfico. Os vértices do triângulo são os pontos (0,0), (0,10) e (5,0).
No ponto (0,0), o nosso lucro é nulo, pois não fabricamos nenhum produto. No ponto (0,10), nosso lucro é 80$. No ponto (5,0), nosso lucro é 30$. No exemplo dado acima, a forma de obter o maior lucro possível é abandonar completamente a fabricação de mesas e se dedicar apenas às cadeiras. E devemos produzir exatamente 10 cadeiras para termos o maior lucro possível.
Perceba que no exemplo acima, o Domínio da função-objetivo era uma região triangular. Como estamos sempre lidando com eqüações e ineqüações lineares, o domínio sempre será um polígono. Nunca conseguiremos obter curvas no gráfico do Domínio da função-objetivo. Outra coisa interessante é que o ponto ótimo que estávamos buscando coincidiu com um dos vértices do polígono. No caso de modelos de programação linear, isso sempre será verdade.
Sabendo disso, você já cohece a forma mais rudimentar de encontrarmos a solução de um modelo de programação Linear. Basta fazermos o gráfico do Domínio da função-objetivo e checarmos os valores da função em todos os seus vértices. Entretanto, essa não é a melhor forma de resolver este tipo de problema. No exemplo acima, haviam apenas duas variáveis (M e C). Mas e se houvessem mais? Como esboçar o gráfico do Domínio? E se o nosso Domínio fôsse representado por um polígono com 300 vértices? Seria trabalhoso demais calcular o valor da função em 300 pontos diferentes!
Bem, veremos métodos melhores de se resolver este tipo de problemas nos próximos capítulos.
| |||