Solução Ótima em Programação Linear: Método Gráfico e Estudo de Caso do Desenhista

1 Pesquisa Operacional 41 Em busca da solução ótima método gráfico Faculdade de Engenharia Eng Celso Daniel Engenharia de Produção Profa Dra Lilian Kátia de Oliveira Programação Linear Solução Gráfica Não é simples obter a solução ótima de um problema de Programação Linear Existem diversas maneiras de obter esta solução ótima Quando o problema envolver apenas duas variáveis de decisão a solução ótima pode ser encontrada graficamente Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 2 Um desenhista faz quadros artesanais para vender numa feira que acontece todo dia à noite Ele faz desenhos grandes e desenhos pequenos e vendeos por R500 e R200 respectivamente Só é possível vender 4 desenhos grandes e 3 desenhos pequenos por noite O desenho grande é feito em uma hora grosseiro e o pequeno é feito em duas horas detalhado Além disso o desenhista desenha 8 horas por dia antes de ir para a feira O Problema do Desenhista Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira O que o desenhista precisa decidir O que ele pode fazer para aumentar ou diminuir a sua receita A decisão dele é como usar as 8 horas diárias quantos desenhos pequenos e grandes ele deve fazer Chamemos de x1 e x2 as quantidades de desenhos grandes e pequenos que ele faz por dia respectivamente A Decisão do Desenhista Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 3 faturamento Máximo de desenhos grandes Máximo de desenhos pequenos Restrição de tempo Não negatividade Determine o Modelo Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 1 2 1 2 1 2 1 2 M a x Z 5 2 s a 4 a 3 b 2 8 c 0 0 d x x x x x x x x x2 x1 1 2 3 4 1 2 4 3 Programação Linear Solução Gráfica x1 ocupa o eixo das abcissas e x2 o eixo das ordenadas Todos os valores para x1 e x2 são considerados inicialmente Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 4 Programação Linear Solução Gráfica x2 x1 x2 é não negativa 2 0 x Logo Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Programação Linear Solução Gráfica A região viável é reduzida O mesmo raciocínio para x1 resulta x2 x1 2 0 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 5 A região viável é reduzida mais ainda Programação Linear Solução Gráfica x2 x1 2 0 x 1 0 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Programação Linear Solução Gráfica Agora pensemos na restrição a 1 4 x x2 x1 1 2 3 4 1 2 4 3 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 6 Programação Linear Solução Gráfica x2 x1 1 2 3 4 1 2 4 3 1 4 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Programação Linear Solução Gráfica x1 1 2 3 4 1 2 4 3 x2 E a restrição b 2 3 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 7 Programação Linear Solução Gráfica x2 x1 1 2 3 4 1 2 4 3 2 3 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Agora precisamos colocar a restrição c Solução Gráfica Região Viável Parcial x1 1 2 3 4 1 2 4 3 2 3 x 1 4 x 1 0 x 2 x 0 1 2 2 8 x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 8 Região Viável Parcial é Compreendida entre as retas x1 1 2 3 4 1 2 4 3 É importante ver aonde a nova reta vai passar Vamos ver sua interseção com os eixos principais 2 3 x 1 4 x 1 0 x 2 0 x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Toda Interseção é determinada resolvendo um sistema de equações 1 2 2 8 x x 1 0 x 1 2 2 8 x x 2 0 x 2 4 x 04 1 8 x 80 Intersecção com os Eixos Principais Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 9 1 2 3 4 1 2 4 3 x2 x1 04 80 Um Esboço da Nova Reta Para uma maior precisão é importante definir os pontos vermelhos Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 1 2 1 2 8 4 x x x 2 2 x 42 1 2 x 23 Definindo os Pontos de Intersecção 1 2 2 2 8 3 x x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 10 A Nova Reta 23 42 1 2 3 4 1 2 4 3 x2 x1 Como toda restrição uma parte da antiga região viável será desprezada Qual Esta pergunta é a mesma Para onde a restrição aponta Para baixo ou para cima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Como a restrição é as pessoas costumam dizer que aponta para baixo Está errado raciocinar assim Devemos investigar algum ponto que esteja na região acima ou abaixo da reta Decidindo sobre a Restrição 23 42 1 2 3 4 1 2 4 3 x2 x1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 11 Vamos escolher por facilidade o ponto 00 1 2 2 8 x x 0 2 0 0 Aplicando Logo 00 está dentro da restrição Portanto a reta aponta para baixo 0 8 Decidindo sobre a Restrição Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira E portanto Decidindo sobre a Restrição 1 2 3 4 1 2 4 3 x2 x1 23 42 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 12 23 42 Região Viável A região viável é o conjunto de todas as soluções viáveis do problema Região Viável 1 2 3 4 1 2 4 3 x2 x1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Conjunto Convexo Conjunto não Convexo Programação Linear e Convexidade Conjunto Convexo em R2 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 13 Teorema Fundamental da Convexidade Teorema 1 O conjunto de todas as soluções viáveis de um problema de Programação Linear é um conjunto convexo Graficamente podemos verificar o teorema observando que a região viável é obtida como a interseção de vários semiespaços e é portanto convexa Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 1 x 0 2 0 x Verificação Geométrica do Teorema 1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 14 1 4 x Verificação Geométrica do Teorema 1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 2 3 x Verificação Geométrica do Teorema 1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 15 1 2 2 8 x x cqd Verificação Geométrica do Teorema 1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira São pontos especiais nos vértices da região viável Pontos Extremos D23 C42 A00 B40 E03 1 2 3 4 1 2 4 3 x2 x1 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 16 A solução ótima é um dos pontos da região viável Basta procurar dentro da região viável o ponto que dará o maior valor para Z Investiguemos o valor de Z em alguns pontos da região viável A Solução Ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Vamos investigar por acaso o valor de Z em 20 5 2 2 0 10 Z Entretanto outros pontos também fornecem Z 10 16 1 5 16 2 1 10 Z 1 25 5 1 2 25 10 Z Investigando valores para Z Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 17 Em todos estes pontos temos Z 10 A Como obter estes pontos O Conjunto de Pontos para Z10 1 2 3 4 1 2 4 3 x2 x1 20 D C E B 083 20 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Quando Z assume um valor fixo temos uma reta Entretanto é possível que vários pontos da região viável possuam um mesmo valor para Z como foi o caso anterior Também é possível que nenhum ponto assuma um determinado valor de Z Por exemplo que pontos dariam Z 30 O Valor Fixo de Z Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 18 60 015 4 5 55 125 O Conjunto de Soluções para Z30 O Conjunto de Soluções para Z 30 é vazio Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Sempre que aumentarmos o valor de Z a reta irá para a direita Z 10 Z 30 A reta se deslocou para a direita Variando o Valor de Z O que aconteceu do ponto de vista da reta quando mudamos o valor de Z Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 19 Como é um problema de maximizar a solução ótima será o ponto da região viável que esteja mais à direita Também é importante saber o valor da função objetivo no ponto ótimo A Solução Ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira C42 Calculase então 5 4 2 2 24 Z Podemos então concluir que desenhando 4 quadros grandes e 2 quadros pequenos por dia o Desenhista terá seu faturamento máximo de R2400 na feira O Valor da Função Objetivo na Solução Ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 20 Para obter a solução de forma gráfica siga os passos Desenhe a região viável que depende exclusivamente das restrições Descubra a inclinação da função objetivo desenhe em algum ponto interno à região viável aleatoriamente Descubra para que lado a função objetivo melhora Projete a função nesta direção em caso de dúvidas você sempre pode aplicar a função objetivo em mais de um ponto escolhendo o ponto mais adequado Solução Gráfica Resumo Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Considere o seguinte o problema de PL a Encontre a solução ótima b Se a função objetivo fosse alterada para 2x16x2 qual seria a solução ótima c Quantos pontos extremos existem 1 2 1 2 1 2 1 2 Max 3 3 sa 2 4 12 6 4 24 0 x x x x x x x x Solução Gráfica de um PL Exercício Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 21 Solução Gráfica de um PL Exercício 00 1 2 0 1 2 3 4 5 6 3 x2 2 0 x 1 x 0 x1 03 60 1 2 2 4 12 x x 40 06 1 2 6 4 24 x x 5 4 6 7 Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Solução Gráfica de um PL Exercício 00 1 2 0 1 2 3 4 5 6 X1 03 60 40 06 3 4 5 6 x2 7 332 x1 2 1 3 3 0 x x Z 2 1 3 3 6 x x Z 2 1 3 3 0 x x Z 2 1 3 3 6 x x Z 2 1 3 3 0 x x Z 2 1 3 3 9 x x Z 1 2 6 3 3 Z x x 1 2 0 3 3 Z x x 1 2 9 3 3 Z x x 1 2 135 3 3 Z x x Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 22 Encontre a solução ótima do seguinte o problema de PL 1 2 1 2 1 2 1 2 1 2 1 2 Min 7 9 sa 2 5 6 3 5 15 5 4 20 0 x x x x x x x x x x x x Solução Gráfica de um PL Exercício Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 10 x1 8 6 1 5 x 4 2 2 6 x 1 2 2 x x 10 14 12 x2 8 6 4 2 2 2 1 2 3 5 15 x x 1 2 5 4 20 x x 2 0 x 1 0 x Solução Gráfica de um PL Exercício Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 23 10 x1 8 6 4 2 10 14 12 x2 8 6 4 2 2 2 1 5 x 2 6 x 2 2 1 x x 20 4 5 2 1 x x 2 0 x 1 0 x 15 5 3 2 1 x x Solução Gráfica de um PL Exercício Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Uma restrição é dita redundante quando a sua exclusão do conjunto de restrições de um problema não altera o conjunto de soluções viáveis deste É uma restrição que não participa da determinação do conjunto de soluções viáveis Existe um outro problema sem esta restrição com a mesma solução ótima Programação Linear Restrições Redundantes Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 24 Considere o problema 1 2 1 2 1 2 1 2 1 2 1 2 1 2 Min 6 10 sa 2 2 1 5 6 3 5 15 5 4 20 0 x x x x x x x x x x x x x x Programação Linear Restrições Redundantes Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 10 x1 8 6 1 5 x 4 2 2 6 x 1 2 2 x x 10 14 12 x2 8 6 4 2 2 2 1 2 5 4 20 x x 2 0 x 1 0 x 1 2 2 1 x x 1 2 3 5 15 x x Restrição Redundante Programação Linear Restrições Redundantes Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 25 Um problema de Programação Linear com solução múltipla é aquele que possui mais de uma solução ótima ou seja existe na região viável mais de um ponto que dá o Z ótimo Isto acontece somente quando a função objetivo tem coeficientes proporcionais ao de alguma restrição Programação Linear Solução Múltipla Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Considere o seguinte o problema de PL Encontre a solução ótima 1 2 1 2 1 2 1 2 1 2 1 2 Min 6 10 sa 2 5 6 3 5 15 5 4 20 0 x x x x x x x x x x x x Programação Linear Solução Múltipla Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 26 10 x1 8 6 1 5 x 4 2 2 6 x 1 2 2 x x 10 14 12 x2 8 6 4 2 2 2 1 2 3 5 15 x x 1 2 5 4 20 x x 2 0 x 1 0 x Programação Linear Solução Múltipla Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Soluções Ótimas Múltiplas 1 2 1 2 2 1 2 1 2 1 2 Max 6 10 sa 2 6 3 5 15 5 4 20 0 x x x x x x x x x x x Programação Linear Solução Ilimitada Considere o seguinte o problema de PL Encontre a solução ótima Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 27 x1 10 8 6 4 2 2 6 x 1 2 2 x x 10 14 12 x2 8 6 4 2 2 2 1 2 3 5 15 x x 1 2 5 4 20 x x 1 0 x 2 0 x Programação Linear Solução Ilimitada Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira Um problema de programação linear é dito inviável quando o conjunto de soluções viáveis é vazio Considere o problema 1 2 1 2 1 2 1 2 Max sa 12 20 0 x x x x x x x x Programação Linear Solução Inviável Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira 28 2 0 x 1 0 x 2 2 2 4 6 8 10 12 14 2 4 6 8 10 2 2 2 4 6 8 10 12 14 2 4 6 8 10 x2 x1 1 2 20 x x 2 2 2 4 6 8 10 12 14 2 4 6 8 10 x2 x1 1 2 12 x x 1 2 12 x x 1 2 20 x x 2 2 2 4 6 8 10 12 14 2 4 6 8 10 x2 x1 Programação Linear Solução Inviável Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira LACHTERMACHER G Pesquisa operacional na tomada de decisão modelagem em Excel 2ª edição revista e atualizada Editora Campus 2004 HILLIER F S Introdução à pesquisa operacional Rio de Janeiro Editora Campus 1988 ARENALES M ARMENTANO V MORABITO R e YANASSE H Pesquisa Operacional Rio de Janeiro Editora Campus 2007 Referências Bibliográficas Pesquisa Operacional I Profa Dra Lilian Kátia de Oliveira