Resolucao Grafica de Programas Lineares - Metodo e Interpretacao Geometrica

Departamento de Engenharia de Produção UFPR 18 Professor Volmir Eugênio Wilhelm Resolução Gráfica de um Programa LinearPL Interpretação geométrica Um programa linear tenta minimizar ou maximizar uma função linear restrito a um conjunto de restrições lineares Seja o seguinte pl de maximização max Z 2x 3y Função objetivo sa x y 5 Restrição 1 x 4y 45 Restrição 2 2x y 27 Restrição 3 3x 4y 24 Restrição 4 x y0 Não negatividade Aqui Zx y 2x 3y é a função objetivo e as desigualdades são as restrições Uma solução viável é um valor para variáveis por exemplo x y 2 0 que satisfaz todas as restrições Chamamos as soluções viáveis de conjunto viável ou região viável ou factível A figura a seguir apresenta graficamente elementos fundamentais do pl acima Solução gráfica de um pl Uma solução de um pl é uma configuração dos valores das variáveis de decisão de tal forma que a solução satisfaz todas as restrições ou seja é viável A solução ótima de um pl é a solução do conjunto de todas as soluções viáveis com o maior valor da função objetivo quanto o pl for de maximização Departamento de Engenharia de Produção UFPR 19 Professor Volmir Eugênio Wilhelm O método gráfico é uma forma de determinar a solução ótima restrito a pl com até 3 variáveis de decisão Apesar desta limitação este método fornece uma ilustração clara das regiões viáveis e não viáveis e também os vértices Ter uma compreensão visual do problema ajuda com um processo de pensamento mais racional para determinação da solução ótima Por exemplo veremos que se um pl tem uma solução ótima limitada a solução ótima é sempre um dos vértices de sua região viável um ponto extremo O que é necessário fazer é encontrar todos os pontos de interseção vértices e depois examinar qual dentre todos os vértices viáveis fornece a solução ótima Para fazer isso usamos conceitos de geometria analítica e de cálculo mais especificamente gradiente e curva de nível fonte link Procedimento da Solução Gráfica i Desenhe a reta de cada restrição no gráfico Identifique a região correspondente à cada restrição ii Identifique a região de soluções viáveis isto é a área do gráfico que simultaneamente satisfaz a todas as restrições iii Encontre a solução ótima pelo seguinte método a Desenhe uma ou mais curvas de nível da função objetivo e determine a direção na qual as curvas paralelas resultam em aumentos no valor da função objetivo b Desenhe o gradiente de Z e curvas paralelas na direção do crescimento indicada pelo gradiente de Z até que a curva toque a região de soluções viáveis em um único ponto ou em um segmento Em suma o método gráfico na programação linear é usado para resolver problemas encontrando o ponto mais alto ou mais baixo de interseção entre a linha de função objetivo e a região factível em um gráfico Exemplos a max Z 6x1 3x2 sa 2x1 4x2 8 x1 4x2 4 x1 x2 2 x1 x2 0 Departamento de Engenharia de Produção UFPR 20 Professor Volmir Eugênio Wilhelm Matlab x 4014 y1 148 2x y2 144 x y3 2 x z 136 6x plotxy1k xy2k xy3k hold on plotxz grid on axis square ylim1 4 xlim1 4 grid minor quiver0 0 2 1 b max Z x1 x2 sa x1 x2 8 4x1 4x2 8 2x1 x2 6 x1 x2 0 Matlab x 4018 y1 118 x y2 148 4x y3 6 2x z 114 1x plotxy1k xy2k xy3k hold on plotxz grid on axis square ylim1 8 xlim1 8 grid minor quiver0 0 3 3 Departamento de Engenharia de Produção UFPR 21 Professor Volmir Eugênio Wilhelm c max Z x1 x2 sa 2x1 x2 5 x1 x2 4 x1 x2 0 Matlab x 4016 y1 115 2x y2 114 x z 111 1x plotxy1k xy2k hold on plotxz grid on axis square ylim1 6 xlim1 6 grid minor quiver0 0 1 1 d max Z x1 2x2 sa x1 2x2 2 2x1 x2 4 x1 x2 0 Matlab x 2016 y1 122 1x y2 114 2x z 124 1x plotxy1k xy2k hold on plotxz grid on axis square ylim1 6 xlim1 6 grid minor quiver0 0 1 2 Departamento de Engenharia de Produção UFPR 22 Professor Volmir Eugênio Wilhelm Sumário Em um programa linearpl temos um conjunto de variáveis e queremos encontrar uma atribuição para as variáveis que satisfazem um determinado conjunto de desigualdades lineares e que maximize ou minimize uma determinada função objetivo linear Uma atribuição que satisfaz as desigualdades é chamada de solução viável É possível que não exista uma solução viável para as desigualdades indicadas nesse caso chamamos o pl de inviável Se o pl for viável é possível que seja do tipo maximização e que haja soluções de lucro arbitrariamente alto ou que seja do tipo minimização e que haja soluções de custo arbitrariamente pequeno Nesse caso dizemos que o programa linear não é limitado Se o pl for viável e não ilimitado ele possui um ótimo finito e estamos interessados em encontrar uma solução viável de custo ótimo Graficamente percebemos que a solução ótima de um pl se ela existir está na fronteiraborda do conjunto das soluções viáveis Em particular percebese que esta solução ótima encontrase na interseção das retas que definem as regiões de abrangência de restrições Exercícios Resolver graficamente PLs a max Z 3x1 2x2 sa x1 12 x1 3x2 45 2x1 x2 30 x1 0 x2 0 b max Z 13x1 5x2 125 sa 15x1 7x2 1200 25x1 45x2 900 x1 37 x2 14 x1 x2 0 Departamento de Engenharia de Produção UFPR 23 Professor Volmir Eugênio Wilhelm c max Z 1036x 38815y sa 13x 19y 2400 20x 29y 2100 x 10 xy 0 d min Z 10a 11b sa a b 11 a b 5 7a 12b 35 a 0 b 0 e f g 0 60 8000 50 100 400 4 2 20 50 max 2 1 1 2 1 2 1 2 1 x x x x x x x a s x x Z 0 9 2 4 3 2 max 2 1 2 1 2 1 2 1 x x x x x x a s x x Z 0 9 2 4 2 5 max 2 1 2 1 1 2 1 x x x x x a s x x Z httpswwwyoutubecomwatchvxY6AlnGZ1bw