Slide - Programação Linear Forma Tableau - 2022-1

06 Programação Linear Forma Tableau 2022 Prof Sérgio F Mayerle 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 2 of 11 Transformações de equivalência Forma canônica e forma padrão de um PPL Método Simplex na Forma Tableau Exemplos 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 3 of 11 Transformações de equivalência Qualquer que seja a estrutura do PPL sempre é possível transformálo numa forma padrão Para tanto utilizamse as seguintes relações de equivalência Relação entre maximização e minimização 1 1 1 n n j j j j j j Min z c x Max z c x Relação entre equações e inequações 1 1 1 1 0 0 n n ij j i i j ij j i j i n n ij j i i j ij j i j i a x S b a x b S a x S b a x b S 2a 2b Tratamento de limites de variáveis 0 0 0 0 0 0 3a 3b 3c j j j j j j j j j j j j j j j j j x x x x x x x x x x x x x x x x x x e 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 4 of 11 Forma Canônica e Forma Padrão de um PPL Dizse que o PPL está na forma canônica se todas as restrições são do tipo e as variáveis satisfazem a condição jx 0 1 j n como segue 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 0 1 n n n n n n m m mn n m j Max z c x c x c x s a a x a x a x b a x a x a x b a x a x a x b x j n 4a 4b 4c 4d 4e Dizse que o PPL está em sua forma padrão se todas as restrições são do tipo e se as variáveis satisfazem a condição jx 0 1 j n como segue 1 1 2 2 11 1 12 2 1 1 1 21 1 22 2 2 2 2 1 1 2 2 0 1 0 1 n n n n n n m m mn n m m j i Max z c x c x c x s a a x a x a x S b a x a x a x S b a x a x a x S b x j n S i m 5a 5b 5c 5d 5e 5f Para resolver um PPL usando o algoritmo Simplex é necessário escrever o problema na forma padrão 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 5 of 11 Método Simplex na Forma Tableau Problema de Programação Linear Seja o PPL em sua forma padrão estendida somente equações 11 1 12 2 1 1 1 21 1 22 2 2 2 2 1 1 2 2 1 1 2 2 ˆ 0 1 0 1 n n n n m m mn n m m n n j i Max z s a a x a x a x S b a x a x a x S b a x a x a x S b z c x c x c x z x j n S i m onde ˆz é uma constante na equação da função objetivo Forma tableu do PPL A forma tableau é uma representação do sistema de equações associado ao PPL apresentado numa forma tabular como segue 1 2 1 2 1 11 12 1 1 2 21 22 2 2 1 2 1 2 0 1 0 0 0 0 1 0 0 0 0 1 ˆ 1 0 0 0 n m n n m m m mn m n Base z x x x S S S RHS S a a a b S a a a b S a a a b z c c c z Nesta tabela cada coluna corresponde a uma variável do problema e cada linha corresponde a uma equação A coluna RHS right hand side mantém as constantes que ficam no lado direito de cada equação 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 6 of 11 Quando da construção de uma solução inicial algumas variáveis se associam a um vetor coluna unitário Estas variáveis passam a ocupar uma posição na base correspondente ao 1 deste vetor unitário Garantindo que a variável z permaneça sempre associada à última linha a obtenção das colunas unitárias pode ser forçada através de operações de linha sobre o sistema de equações lineares representado de modo que se tenha uma variável em cada posição da base Desta forma fazendo todas as variáveis que não se encontram na base iguais a zero temse que as variáveis da base se igualam aos valores da coluna RHS e se estes valores de RHS para as variáveis básicas são todos não negativos temse uma solução básica viável vértice Como resultado destas transformações lineares obtémse 1 2 1 2 1 11 12 1 1 2 21 22 2 2 1 2 1 2 ˆ 0 1 0 0 ˆ 0 0 1 0 ˆ 0 0 0 1 ˆ 1 0 0 0 R R R B B B n m m B B n m B B n m B B m m m m n m m n Base z x x x x x x RHS x a a a x x a a a x x a a a x z c c c z 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 7 of 11 Troca de Base vértice A troca de base vértice dáse através da escolha das variáveis que serão permutadas como segue escolha uma variável não básica R kx para entrar na base associada a um kc 0 caso não exista pare a solução corrente é ótima determine a variável básica que deve sair da base associada à linha com menor valor da razão ˆ B r r rk x a entre todas as linhas com 0 ark caso não exista pare a solução é ilimitada Operações para atualização do tableau O novo tableau é determinado através de operações de linha válidas em sistemas de equações lineares de modo a garantir que as novas variáveis básicas estejam associadas a vetores unitários como segue em cada linha i r calcule 1 ˆ ˆ ˆ ik ij ij rj rk B B B ik i i r rk a a a a j n a a x x x a Para a linha de z calcule 1 ˆ ˆ ˆ k j j rj rk B k r rk c c c a j n a c z z x a Para a linha r faça 1 ˆ ˆ rj rj rk B B r r rk a a j n a x x a 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 8 of 11 Transformações Lineares sobre o tableau Seja a matriz T de coeficientes do tableau definida por uma partição do PPL como segue 0 1 0 T T B R B R b T c c Seja a matriz M definida a partir desta partição como 0 1 T B B M c Sendo B uma matriz não singular a inversa da matriz M será dada por 1 1 1 0 1 T B B M c B Então aplicando sobre a matriz T a transformação linear M 1 T obtémse o novo tableau após a realização da troca de base 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 ˆ 0 ˆ 1 0 T T T B R B T T T B R B B B R b B M T c c c B I B R B b M T c B R c c B b I B R x M T z z Esta transformação linear explicita em M 1 T todos os resultados intermediários do método Simplex a saber 1 ˆB x B b 1 ˆ T B z c B b 1 T T B R z c B R c e 1 B R Observese que em 1 B R estão todas as colunas 1 k k R R a B a associadas às variáveis não básicas 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 9 of 11 Exemplo Seja o PPL abaixo com solução inicial básica viável 180 300 1 1 70 1 2 120 2 1 130 0 A B A B A B A B A B Max z x x s a x x x x x x x x Montando o problema na forma padrão estendida temse 1 2 3 1 2 3 1 1 1 70 1 2 1 120 2 1 1 130 180 300 0 0 A B A B A B A B A B Max z s a x x S x x S x x S z x x x x S S S Construindo o tableau BASE Z XA XB S1 S2 S3 RHS Razão S1 0 1 1 1 0 0 70 70 S2 0 1 2 0 1 0 120 60 S3 0 2 1 0 0 1 130 130 Z 1 180 300 0 0 0 0 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 10 of 11 BASE Z XA XB S1 S2 S3 RHS Razão S1 0 12 0 1 12 0 10 20 XB 0 12 1 0 12 0 60 120 S3 0 32 0 0 12 1 70 467 Z 1 30 0 0 150 0 18000 BASE Z XA XB S1 S2 S3 RHS XA 0 1 0 2 1 0 20 XB 0 0 1 1 1 0 50 S3 0 0 0 3 1 1 40 Z 1 0 0 60 120 0 18600 Resultado Variável Valor z A x 20 0 B x 50 0 1S 0 60 2 S 0 120 3 S 40 0 z 18600 1 06 Programação Linear Forma Tableau EPS7005 Pesquisa Operacional 2022 Prof Sérgio F Mayerle Page 11 of 11 F I M 2022 Prof Sérgio Mayerle