Programação Linear Solução Gráfica-2020-1

05 Programação Linear – Solução Gráfica © 2020 Prof. Sérgio F. Mayerle 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 2 of 9  Problema de planejamento da produção com 2 produtos  Representação gráfica e solução ótima  Propriedades 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 3 of 9 Problema de planejamento da produção com 2 produtos A WINDOOR GLASS INC. dispõe de capacidade extra para produzir dois novos produtos. A demanda é muito maior que a capacidade disponível, de modo que toda produção poderá ser vendida. Os dados estão na tabela abaixo. Consumo por Produto (horas/unid) Setor Janelas Portas Capacidade (horas/mês) Montagem 1,00 - 4 Laminação - 2,00 12 Corte 3,00 2,00 18 Margem de Contribuição (R$/unid) 3,00 5,00 Pergunta-se: (a) o que produzir? (b) quanto produzir? (c) qual será o lucro? Modelo conceitual Variáveis de decisão: 1x quantidade de janelas, em unid/mês 2x quantidade de portas, em unid/mês Restrições: a) capacidade do setor de montagem b) capacidade do setor de laminação c) capacidade do setor de corte d) não negatividade Objetivo: Maximizar a margem de contribuição total 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 4 of 9 Representação Gráfica e Solução Ótima Para o modelo conceitual proposto tem-se o seguinte modelo matemático: 1 2 1 2 1 2 1 2 3 5 . : 4 2 12 3 2 18 , 0 Max z x x s a x x x x x x        Este problema matemático pode ser representado graficamente no 2 R como segue: 2x2x 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 1x1x 12 2 x2  12 2 2  x x1  4 1  4 x 18 2 3 2 1   x x 18 2 3 2 1   x x x2  0 2  0 x x1  0 1  0 x 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 5 of 9 Sistema de inequações do modelo 1 2 1 2 1 0 4 0 2 12 3 2 18 , 0 x x x x                             Sistema de equações equivalente 1 2 1 2 3 1 2 1 2 3 1 0 1 0 0 4 0 2 0 1 0 12 3 2 0 0 1 18 , , , , 0 x x S S S x x S S S                                       Dado que o sistema de equações equivalente tem n  5 variáveis e m  3 equações, para resolvê-lo é necessário arbitrar 5 3 2 n  m    destas variáveis, para poder calcular as demais. Arbitrando estas n  m variáveis iguais a zero, tem-se uma solução básica. Existem, ao todo: ! 5! 10 !( )! 3!(5 3)! m n n C m n m      diferentes soluções básicas, algumas das quais são vértices do conjunto de soluções viáveis: 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 6 of 9 Resolvendo o sistema, tem-se: 1 2 1 2 3 1 2 1 2 3 1 0 1 0 0 4 0 2 0 1 0 12 3 2 0 0 1 18 , , , , 0 x x S S S x x S S S                                       Solução Básica 1x 2x 1S 2 S 3 S Vértice? z 1 0 0 4 12 18 Sim 0 2 0 ? 0 ? ? Não ? 3 0 6 6 0 6 Sim 30 4 0 9 4 -6 0 Não 2 S  0 5 4 0 0 12 6 Sim 12 6 ? 0 ? 0 ? Não ? 7 6 0 -2 12 0 Não 1 S  0 8 4 6 0 0 -6 Não 3 S  0 9 4 3 0 6 0 Sim 27 10 2 6 2 0 0 Sim 36 No quadro acima, as soluções 1, 3, 5, 9 e 10 correspondem aos vértices da poligonal que define o conjunto de soluções viáveis, onde a solução 10 é ótima. 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 7 of 9 Propriedades  O conjunto de soluções viáveis é um poliedro convexo  Se existe exatamente uma solução ótima, então deve ser uma solução factível em um vértice  Se existem soluções ótimas múltiplas, então ao menos duas delas devem ser soluções factíveis em vértices adjacentes; neste caso, todas as soluções que se encontram no segmento de reta que une estes dois vértices também são soluções ótimas (existem infinitas soluções ótimas)  Existe um número finito de soluções básicas factíveis (vértices), não maior que... ! !( )! m n n C m n m    Se uma solução factível em um vértice é igual ou melhor (segundo o valor de Z) que todas as soluções factíveis nos vértices adjacentes a ela, então é igual ou melhor que todas as demais soluções factíveis existentes nos vértices, isto é, é uma solução ótima 2x2x 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 1x1x 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 8 of 9 Estrutura do Método Simplex  Passo inicial: iniciar com uma solução básica viável (vértice).  Teste de otimalidade: se não existe um vértice adjacente, melhor que o vértice atual, então PARE. O vértice atual corresponde à solução ótima. Em caso contrário, vá ao passo 3.  Passo iterativo: movimente em direção de uma solução factível melhor, em um vértice adjacente; volte ao passo 2. 2x2x 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 1x1x Solução Ótima 05 Programação Linear – Solução Gráfica EPS7005 – Pesquisa Operacional © 2020 Prof. Sérgio F. Mayerle Page 9 of 9 F I M (© 2020 Prof. Sérgio Mayerl)