Slide Programação Linear Método Simplex

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 15  PPL na forma canônica e na forma padrão  Transformações de equivalência  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 15 PPL na Forma Canônica e na Forma Padrão Diz-se 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,..., (1.a) (1.b) (1.c) (1.d) (1.e) 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                     Diz-se 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 21 1 22 2 2 2 1 1 2 2 ... . : ... ... ... 0 1,..., (2.a) (2.b) (2.c) (2.d) (2.e) 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                     O primeiro passo para se resolver um PPL, de acordo com o algoritmo Simplex, é escrevendo o problema na forma padrão. 07 Programação Linear – Método Simplex EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 4 of 15 Transformações de equivalência Qualquer que seja a estrutura do PPL, sempre é possível transformá-lo na forma padrão apresentada. Para tanto, utilizam-se as seguintes relações de equivalência:  Relação entre equações e inequações 1 1 1 1 0 0 (3.a) (3.b) 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                                  Tratamento de limites de variáveis 0 0 0 0 0 (3.c) (3.d) (3.e) e 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                                                     Relação entre maximização e minimização 1 1 ( ) ( ) (3.f) n n j j j j j j Max z c x Min z c x          07 Programação Linear – Método Simplex EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 5 of 15 Método Simplex Matricial Seja o PPL na forma padrão: . : 0 (4.a) (4.b) (4.c) T Max z c x s a Ax b x    onde , ,0 n c x  R , m b  R e A é uma matriz m n  de posto m. Obtenção de uma solução No sistema de equações lineares (4.b), 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, tem-se:   (5) B B R R x c x c A B R x c                onde , m B B c x  R , , n m R R c x  R  , B é uma matriz m m  não-singular, e R é uma matriz ( ) m n m   . Com isto o PPL poderá ser re-escrito na forma: . : 0 0 (6.a) (6.b) e (6.c) 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       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 (6.b):   1 1 1 1 (7.a) (7.b) (7.c) B R B R B R B x b R x B B x B b R x x B b B R x           : 07 Programação Linear – Método Simplex EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 6 of 15 No caso particular em que se arbitra ˆ 0 R x  , tem-se uma solução básica, e o valor das componentes do vetor B x poderá ser obtido através de: 1 ˆ (8) xB B  b  Os vetores ˆB x e ˆR x são denominados de vetor de variáveis básicas e vetor de variáveis não-básicas, respectivamente. Considere que a solução assim obtida satisfaz as condições de não-negatividade, apresentadas em (6.c), isto é, que ˆ  0 xB . Neste caso, diz-se 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 (6.a), que no caso particular de uma solução básica resume-se a: ˆ ˆ (9) T B B z  c x Até agora, mostrou-se como o valor das variáveis B x pode ser obtido a partir do arbítrio das variáveis R x . Variando-se o valor destas, obtém-se diferentes soluções para B x . Substituindo (7.c) na expressão (6.a), obtém-se:         1 1 1 1 1 1 1 ˆ ˆ ˆ (10.a) (10.b) (10.c) (10.d) (10.e) 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                       Com esta expressão, pode-se 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 7 of 15 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 (11.a) ou (11.b) T T R B R T T B R R c c B R x c B R c x       Dado que na solução básica corrente xR  0 , e que a condição de não-negatividade deve ser mantida, para satisfazer a condição (11.b) é necessário aumentar as componentes de R x associadas a componentes negativas do vetor 1 (12) T T B R z c B R c     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, diz-se 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 (13) k j j j z z z      é 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ão-básica xRk que será aumentada, deve-se 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 (7.c), satisfaça a condição: 1 1 0 (14) B R x B b B R x      07 Programação Linear – Método Simplex EPS7005 – Pesquisa Operacional © 2022 Prof. Sérgio F. Mayerle Page 8 of 15 Considerando que apenas uma componente do vetor de variáveis não-básicas é incrementado por vêz, esta expressão resume-se a: 1 ˆ 0 ˆ 0 (15.a) (15.b) k k B B k R B B k R x x B R x x x R x        ou ainda, considerando as várias linhas desta condição: ˆ 0 1,..., (16) i i k B B ik R x x R x i m      onde ik R é a i-ésima componente de 1 k k R B  R  . Considerando que a variável não-básica será aumentada (positiva), é necessário verificar a condição (16) somente para 0 Rik  . Com isto o incremento da variável não-básica será limitado em:   ˆ min min | 0 (17) iB s i ik i i ik x R R                Não existindo 0 Rik  , não haverá limites para o incremento da variável não-básica. Neste caso, diz-se 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ão-básica, uma nova solução poderá ser obtida fazendo-se: (18) Rk s x  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ão-básicas R x , e a variável não-bá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 re-definiçã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 9 of 15 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 z z z c B R c c B b         E, no caso particular em que ˆ 0 R R x  x  , tem-se: 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 PPL’s 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 10 of 15 Exercício Seja o seguinte PPL:   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 11 of 15 1ª iteração Adotando a 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                                                                                    tem-se: 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; pode-se 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 12 of 15 2ª iteração Com a troca de base, tem-se:     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; pode-se 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                                    2 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 13 of 15 3ª iteração Com a troca de base, tem-se:     1 3 2 2 1 1 0 4 0 0 12 0 0 18 0 5 3 0 0 1 0 1 1 1/3 1/3 0 0 0 2 0 0 1/ 2 0 0 1 0 2 3 0 1/3 1/3 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 1/3 1/3 4 2 ˆ 0 1/ 2 0 12 6 0 1/3 1/3 18 2 R B S x S S x x B b x                                                              Condição de otimalidade       1 1 1/3 1/3 0 0 0 5 3 0 1/ 2 0 0 1 0 0 0 1/3 1/3 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, tem-se:   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 14 of 15 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 3/2 3 S Folga setor de corte 0 1 z Lucro total 36 1 Interpretação A solução ótima foi encontrada. Deve-se 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 1.5, 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 15 of 15 F I M (© 2022 Prof. Sérgio Mayerle)