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 9  Transformações lineares no PPL  Método Simplex Tableau  Exemplos 06 Programação Linear – Forma Tableau EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 3 of 9 Transformações Lineares do PPL Seja a matriz T , definida a partir dos dados de 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 como: 0 1 T B B M c        cuja inversa é dada por: 1 1 1 0 1 T B B M c B           Então, aplicando sobre a matriz T a transformação M 1  T obtém-se: 1 1 1 0 0 1 0 1 T T T B R B B R b B M T c c c B                   E, realizando o produto entre as matrizes: 1 1 1 1 1 0 1 0 T T T B R B I B R B b M T c B R c c B b                1 1 ˆ 0 ˆ 1 0 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: ˆB x , ˆz , z  e 1 B R  . Observe-se 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 4 of 9 Método Simplex Tableau Problema de Programação Linear Seja o PPL em sua forma padrão estendida (somente equações): 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 1 2 2 . : ... ... ... ˆ ... 0 1,..., n n n n m m mn n m n n j Max z s a a x a x a x b a x a x a x b a x a x a x b z c x c x c x z x j n                      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 11 12 1 1 2 21 22 2 2 1 2 1 2 0 0 0 ˆ 1 n B n B n B m m m mn m n Base z x x x RHS x a a a b x a a a b x 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 5 of 9 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, tem-se 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, tem-se uma solução básica viável (vértice). 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 n m B n m B m m m m n m m n Base z x x x x x x RHS x a a a b x a a a b x a a a b z c c c z                          06 Programação Linear – Forma Tableau EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 6 of 9 Troca de Base (vértice) A troca de base dá-se através das seguintes operações:  escolha uma variável não básica kx para entrar na base, associada a um jc  0 ; caso não exista, pare!... a solução corrente é ótima;  determine a variável que sai da base na linha com menor valor da razão / i i ik R  b a , entre todas as linhas com 0 ik a  ; caso não exista, pare!... a solução é ilimitada; Operações de Linha para Troca de Base  em cada linha i  r calcule ik i rk a a   e faça: 1,..., ij ij i rj i i i r a a a j n b b b          Para a linha de z calcule k z rk c a   e faça: 1,..., ˆ ˆ j j z rj z r c c a j n z z b          Para a linha r faça: 1,..., rj rj rk r r rk a a j n a b b a     06 Programação Linear – Forma Tableau EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 7 of 9 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, tem-se: 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 8 of 9 BASE Z XA XB S1 S2 S3 RHS Razão S1 0 1/2 0 1 -1/2 0 10 20 ◄ XB 0 1/2 1 0 1/2 0 60 120 S3 0 3/2 0 0 -1/2 1 70 46,7 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 9 of 9 F I M (© 2022 Prof. Sérgio Mayerle)