Slide - Programação Linear - Método Simplex - 2022-1

07 Programação Linear Método Simplex 2022 Prof Sérgio F Mayerle 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 2 of 13 Método Simplex Matricial Exercício 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 3 of 13 Método Simplex Matricial Seja o PPL na forma padrão 0 T Max z c x s a Ax b x 1a 1b 1c onde 0 n c x m b e A é uma matriz m n de posto m Obtenção de uma solução No sistema de equações lineares 1b para que uma solução seja determinada é necessário considerando que n m arbitrar o valor de n m variáveis Particionando o vetor de variáveis de modo a caraterizar as variáveis que serão arbitradas e aquelas que serão calculadas e seguindo esta partição para os demais elementos do PPL temse B B R R x c x c A B R x c 2 onde m B B c x n m R R c x B é uma matriz m m nãosingular e R é uma matriz m n m Com isto o PPL poderá ser reescrito na forma 0 0 T T B B R R B R B R Max z c x c x s a B x R x b x x 3a 3b e 3c Arbitrando o valor das n m componentes do vetor de variáveis R x os valores das componentes do vetor B x poderão ser obtido a partir da equação 3b 1 1 1 1 B R B R B R B x b R x B B x B b R x x B b B R x 4a 4b 4c 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 4 of 13 No caso particular em que se arbitra ˆ 0 R x temse uma solução básica e o valor das componentes do vetor B x poderá ser obtido através de 1 ˆB x B b 5 Os vetores ˆB x e ˆR x são denominados de vetor de variáveis básicas e vetor de variáveis nãobásicas respectivamente Considere que a solução assim obtida satisfaça as condições de nãonegatividade apresentadas em 3c isto é que ˆ 0 B x Neste caso dizse que esta solução é uma solução básica viável um vértice Cálculo do valor da função objetivo O valor da função objetivo poderá ser calculado através da equação 3a que no caso particular de uma solução básica resumese a ˆ ˆ T B B z c x 6 Até agora mostrouse como o valor das variáveis B x pode ser obtido a partir do arbítrio das variáveis R x Variandose o valor destas obtémse diferentes soluções para B x Substituindo 4c na expressão 3a obtémse 1 1 1 1 1 1 1 ˆ ˆ ˆ T T B R R R T T T B B R R R T T T B B R B R T T R B R T T R B R z c B b B R x c x z c B b c B R x c x z c x c c B R x z z c c B R x z z c c B R x 7a 7b 7c 7d 7e Com esta expressão podese calcular o valor da função objetivo de novas soluções como função dos valores arbitrados para R x Portanto diferente valores de R x produzem diferentes valores para a função objetivo 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 5 of 13 Condição de otimalidade Com o objetivo de maximizar o valor da função objetivo é necessário encontrar algum 0 R x tal que ˆ 0 z z isto é 1 1 0 0 T T R B R T T B R R c c B R x c B R c x 8a ou 8b Dado que na solução básica corrente 0 R x e que a condição de nãonegatividade deve ser mantida para satisfazer a condição 8b é necessário aumentar as componentes de R x associadas a componentes negativas do vetor 1 T T B R z c B R c 9 Obviamente se não existirem componentes negativas em z isto é se 0 jz não será possível aumentar o valor de z Neste caso dizse que a solução básica viável corrente é a solução ótima do PPL Troca de base Mesmo que exista mais do que uma componente 0 jz o Método Simplex considera que apenas uma componente de R x é aumentada a cada iteração Neste caso diversas estratégias de escolha poderão ser adotadas A única condição para que se obtenha uma solução melhor é que se escolha uma componente 0 jz Na prática escolher min 0 k j j j z z z 10 é uma boa estratégia para aumentar o valor da função objetivo pois é a que produz o maior incremento em z por aumento unitário da respectiva componente em R x Dado a variável nãobásica xRk que será aumentada devese determinar o quanto incrementála Em princípio quanto maior o incremento maior será o z e para manter a viabilidade da solução é necessário que a nova solução calculada pela expressão 4c satisfaça a condição 1 1 0 B R x B b B R x 11 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 6 of 13 Considerando que apenas uma componente do vetor de variáveis nãobásicas é incrementado por vêz esta expressão resumese a 1 ˆ 0 ˆ 0 k k B B k R B B k R x x B R x x x R x 12a 12b ou ainda considerando as várias linhas desta condição ˆ 0 1 i i k B B ik R x x R x i m 13 onde ik R é a iésima componente de 1 k k R B R Considerando que a variável nãobásica será aumentada positiva é necessário verificar a condição 13 somente para 0 Rik Com isto o incremento da variável nãobásica será limitado em ˆ min min 0 iB s i ik i i ik x R R 14 Não existindo 0 Rik não haverá limites para o incremento da variável nãobásica Neste caso dizse que não existe solução ótima finita ou que a solução é ilimitada pois o valor da função objetivo z Por outro lado encontrado um limite s para o incremento da variável nãobásica uma nova solução poderá ser obtida fazendose Rk s x 15 Com isto 0 xBs e o valor da função objetivo aumentará para ˆ k s z z z Esta nova solução poderá ser representada por uma nova partição no vetor de variáveis x na qual a variável básica que foi anulada passa a fazer parte do vetor de variáveis nãobásicas R x e a variável nãobásica que foi incrementada passa a fazer parte do vetor de variáveis básicas B x A esta operação dáse o nome de troca de base Efetuada a redefinição dos vetores R x e B x todas as etapas do processo são repetidas até que se obtenha um solução ótima ou uma solução ilimitada 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 7 of 13 Resumo Forma Matricial x Forma Tableau Seja uma solução básica do PPL representado na forma matricial de um sistema de equações 1 1 1 1 1 B R T T T B R R B B B x B R x B b z c B R c x c B b 1 1 1 1 1 ˆ 0 0 ˆ 1 0 1 0 B R B R B B B T T T B R B Base z x x RHS Base z x x RHS x B B B R B b x I R x z c B R c c B b z z z E no caso particular em que ˆ 0 R R x x temse 1 1 ˆ ˆ ˆ B B T T B B B x x B b z z c B b c x Observações a No caso de PPLs de grande porte a forma matricial é melhor pois não acumula erros ao longo das iterações b A obtenção da matriz 1 B pela método da decomposição LU e pelo uso da forma produto da inversa além de ser mais eficiente ajuda na manutenção da baixa esparsidade da matriz reduzindo o número de operações aritméticas e a necessidade de espaço para armazenamento na memória do computador 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 8 of 13 Exemplo Seja o problema da WINDOOR GLASS INC que produz janelas e portas de acordo com os seguintes dados Consumo Unitário horasunid Setores de Produção Janelas Portas Capacidade horasmês Montagem 100 4 Laminação 200 12 Corte 300 200 18 Margem de Contribuição Runid 300 500 Perguntase a o que e quanto produzir b qual será o lucro Modelo na Forma Canônica 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 Modelo na Forma Padrão 1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 3 5 0 0 0 1 0 1 0 0 4 0 2 0 1 0 12 3 2 0 0 1 18 0 0 0 0 0 x x Max z S S S x x s a S S S x x S S S 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 9 of 13 1ª iteração Adotando como partição inicial 1 1 2 2 3 1 0 4 0 0 12 0 0 18 0 0 0 3 5 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 2 0 0 1 0 0 1 3 2 B R T T B R S x x S x b x S c c B B R temse 1 2 1 1 2 3 0 ˆ 0 1 0 0 4 4 ˆ 0 1 0 12 12 0 0 1 18 18 R B x x x S x S B b S Condição de otimalidade 1 1 0 0 1 0 0 0 0 0 1 0 0 2 3 5 0 0 1 3 2 3 5 T T B R z c B R c z z Logo não é solução ótima podese aumentar o valor da variável 2x que entra na base 1 2 2 1 0 0 0 0 0 1 0 2 2 0 0 1 2 2 R B R 2 4 0 0 ˆ 0 12 2 0 18 2 0 k B B k R B x x R x x x 2 4 12 18 12 min 6 0 2 2 2 x 2 0 S sai da base 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 10 of 13 2ª iteração Com a troca de base temse 1 1 2 2 3 1 0 4 0 0 12 0 0 18 0 5 0 3 0 1 0 0 1 0 0 1 0 0 2 0 0 1 2 0 0 1 0 2 1 0 1 1 3 0 B R T T B R S x x x x b S S c c B B R Determinando a solução 1 2 1 1 2 3 0 ˆ 0 1 0 0 4 4 ˆ 0 1 2 0 12 6 0 1 1 18 6 R B x x S S x x B b S Condição de otimalidade 1 1 0 0 1 0 0 5 0 0 1 2 0 0 1 3 0 0 1 1 3 0 3 5 2 T T B R z c B R c z z Logo não é solução ótima podese aumentar o valor da variável 1x que entra na base 1 1 1 1 0 0 1 1 0 1 2 0 0 0 0 1 1 3 3 R B R 1 4 1 0 ˆ 0 6 0 0 6 3 0 k B B k R B x x R x x x 1 4 6 6 6 min 2 1 0 3 3 x 3 0 S sai da base 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 11 of 13 3ª iteração Com a troca de base temse 1 3 2 2 1 1 0 4 0 0 12 0 0 18 0 5 3 0 0 1 0 1 1 13 13 0 0 0 2 0 0 1 2 0 0 1 0 2 3 0 13 13 1 0 B R T T B R S S x x x b S x c c B B R Determinando a solução 3 2 1 1 2 1 0 ˆ 0 1 13 13 4 2 ˆ 0 1 2 0 12 6 0 13 13 18 2 R B S x S S x x B b x Condição de otimalidade 1 1 13 13 0 0 0 5 3 0 1 2 0 0 1 0 0 0 13 13 1 0 1 3 2 T T B R z c B R c z z Logo esta é a solução ótima do PPL Calculando o valor da função objetito temse 2 ˆ ˆ 0 5 3 6 36 2 T B B z c x 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 12 of 13 Resultado Variável Descrição Valor z 1x Número de janelas 2 0 2x Número de portas 6 0 1S Folga setor de montagem 2 0 2 S Folga setor de laminação 0 32 3 S Folga setor de corte 0 1 z Lucro total 36 1 Interpretação A solução ótima foi encontrada Devese produzir 2 janelas e 6 portas o que garante um lucro total de 36 Com esta solução haverá uma folga de 2 horas no setor de montagem e os demais setores são gargalos de produção Cada hora adicional de laminação aumenta o lucro total em 15 enquanto que cada hora adicional do setor de corte aumenta o lucro em 1 07 Programação Linear Método Simplex EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 13 of 13 F I M 2022 Prof Sérgio Mayerle