Pesquisa Operacional - Programacao Linear Metodo M Grande e Duas Fases

Pesquisa Operacional Oficina 5 Programação Linear Prof Victor Diogho Heuer de Carvalho Campus do Sertão Universidade Federal de Alagoas Conteúdo da Oficina 4 Programação Linear o Casos de Dificuldade o Método do Grande Número ou M Grande o Método das Duas Fases o Problemas de Minimização Casos de Dificuldade Retomemos o modelo matemático introduzido na nossa oficina anterior E se agora esse modelo passasse a ser Notese que a única alteração feita foi em contudo isso demanda uma nova estratégia dentro do Simplex Tabular para a resolução do problema Casos de Dificuldade O novo modelo com uma igualdade em uma de suas restrições não está mais na forma canônica Essa igualdade irá gerar o que chamamos de variável artificial que denotaremos por a para a complementação do modelo na forma padrão Já sabemos dado o problema resolvido anteriormente que passa a ser passa a ser E agora com como deveremos proceder É aqui que entra a variável artificial a Casos de Dificuldade Essa variável artificial a deve ser refletida também na função objetivo 0 0 Notese que na função objetivo o a para este caso entrará com sinal negativo Este mesmo processo para aplicação da resolução no simplex tabular também é valido para casos onde uma das restrições tem maior ou igual o que nos dá um complemento em relação ao acréscimo da variável de excesso S Casos de Dificuldade Se a restrição fosse teríamos então de considerar 3 𝑥12𝑥218𝑎𝑆 3 𝑥12𝑥2𝑎𝑆18 Também neste caso a função objetivo seria impactada com um a como demonstrado anteriormente Devemos pensar nessa a como uma espécie de penalização Método do Grande Número M Grande Uma das estratégias para resolver este tipo de problema é chamada de Método do Grande Número ou do M Grande Ela consiste em associar como coeficiente às variáveis artificias um um numério tão grande quanto o necessário que denominamos por M de modo que o valor máximo de Z só será alcançado se a variável artificial adicionada ao modelo na forma padrão seja a 0 O Simplex Tabular será operado portanto considerando esse grande número O valor de M jamais será descoberto permanecendo como M até que tenhamos atingido a otimalidade Método do Grande Número Seja o modelo inicial Notese que ele está fora da forma canônica devido à restrição com o A forma padrão portanto é 0 0 Método do Grande Número Na sequencia precisamos realizar uma transformação algébrica na Função Objetivo considerando A esse a podemos multiplicar o M de ambos os lados Inclusive podemos também considerar que chamaremos de I Método do Grande Número Podemos considerar também 0 0 0 0 0 0 que chamaremos de II Subtraíndo I de II 𝑍 3𝑥15𝑥2 M 𝒂0 𝑍 3𝑥15𝑥2 M 𝒂0 3 𝑴 𝑥12 𝑴 𝑥2 𝑴𝒂18 𝑴 𝑍 3𝑥13 𝑴 𝑥15 𝑥22 𝑴 𝑥218 𝑴 Método do Grande Número 𝑍 𝑥133 𝑴𝑥252 𝑴18 𝑴 Podemos reorganizar em 𝑍𝑥1 33 𝑴 𝑥252 𝑴 18 𝑴 Estudando os coeficientes podemos pensar da seguinte forma Entre e quem aumenta em uma taxa maior Se considerarmos que temos um valor multiplicado por um número muito grande M o coeficiente multiplicado por M será decisivo dado que a parte independente é desprezível frente à esse número Logo Método do Grande Número Com a análise feita no slide anterior basta que criemos agora nossa Tabela 0 e já temos que a coluna de x1 será a coluna pivô Z x1 x2 S1 S2 a b Z 1 3 3M 5 2M 0 0 0 18M S1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 a 0 3 2 0 0 1 18 A partir daqui basta operar o Simplex Tabular com a diferença que temos de considerar nas nossas operações a existência de M Simplex com o Grande Número Pivotando e Obtendo a Tabela Auxiliar A coluna pivô já foi determinada Para a linha pivô 4 1 4 menor valor entre os resultados 12 0 18 3 6 O número pivô será 1 Z x1 x2 S1 S2 a b Z 1 3 3M 5 2M 0 0 0 18M S1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 a 0 3 2 0 0 1 18 Tabela 0 Z x1 x2 S1 S2 a b S1 0 1 0 1 0 0 4 Pivô 1 1 1 1 1 1 1 x1 0 1 0 1 0 0 4 Tabela Auxiliar Divide Simplex com o Grande Número Z x1 x2 S1 S2 a b Z 1 3 3M 5 2M 0 0 0 18M S1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 a 0 3 2 0 0 1 18 Tabela 0 Tabela 1 Z x1 x2 S1 S2 a b Z x1 0 1 0 1 0 0 4 S2 a Linha de Z 1 33M x 0 1 33M 33M x 1 0 52M 33M x 0 52M 0 33M x 1 33M 0 33M x 0 0 0 33M x 0 0 18M 33M x 4 6M12 Simplex com o Grande Número Z x1 x2 S1 S2 a b Z 1 3 3M 5 2M 0 0 0 18M S1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 a 0 3 2 0 0 1 18 Tabela 0 Tabela 1 Z x1 x2 S1 S2 a b Z 1 0 5M2 33M 0 0 6M12 x1 0 1 0 1 0 0 4 S2 a Linha de Z 1 33M x 0 1 33M 33M x 1 0 52M 33M x 0 52M 0 33M x 1 33M 0 33M x 0 0 0 33M x 0 0 18M 33M x 4 6M12 Simplex com o Grande Número Tabela 1 Z x1 x2 S1 S2 a b Z 1 0 5M2 33M 0 0 6M12 x1 0 1 0 1 0 0 4 S2 0 0 2 0 1 0 12 a 0 0 2 3 0 1 6 O mesmo processo se repetirá para as demais linhas de variáveis básicas conforme as regras referentes aos sinais dos valores As Tabelas 1 e 2 com os resultados estão ao lado Tabela 2 Z x1 x2 S1 S2 a b Z 1 0 0 92 0 M 52 27 x1 0 1 0 1 0 0 4 S2 0 0 0 3 1 1 6 x2 0 0 1 32 0 12 3 Simplex com o Grande Número Tabela 3 final Z x1 x2 S1 S2 a b Z 1 0 0 0 32 M 1 36 x1 0 1 0 0 13 13 2 S1 0 0 0 1 13 13 2 x2 0 0 1 0 12 0 6 Solução Z 36 x1 2 x2 6 S1 2 S2 0 S3 0 Problemas de Minimização Quando temos um problema de minimização conforme a generalização abaixo Podemos reescrevêlo como um problema de maximização conforme já vimos na oficina anterior Sendo que as duas formulações levam às mesmas soluções Problemas de Minimização Seja o seguinte modelo Transformandoo para a forma padrão Por que a1 e a2 neste caso não entraram na FO negativas Devemos lembrar que as variáveis artificiais podem ser sinalizadas como penalizações ao modelo Logo o que penaliza um modelo de minimização não é uma subtração e sim uma soma a lógica se inverte Problemas de Minimização Método das Duas Fases Tendo em vista o modelo em sua forma padrão podemos separálo em duas fases 1ª Fase considera na FO apenas as variáveis artificiais 2ª Fase sem as variáveis artificiais na FO Problemas de Minimização Método das Duas Fases Para começarmos a operar a 1ª fase devemos realizar as transformações necessárias na FO de forma semelhante à que fizemos anteriormente com o método do Grande Número Devemos sempre considerar todas as restrições que geraram variáveis artificiais para aplicar essas transformações Também devemos considerar que Min Z é o mesmo que Max Z Realizando as operações 𝑍0 𝑥10 𝑥20𝑆10 𝑆2𝑎1𝑎20 05 𝑥10 5 𝑥20𝑆10𝑆2𝑎10𝑎261 06 𝑥104 𝑥20 𝑆1𝑆20𝑎1𝑎261 𝑍0 𝑥10 𝑥20𝑆10 𝑆2𝑎1𝑎20 05 𝑥105𝑥20 𝑆10𝑆2𝑎10 𝑎26 06𝑥1 0 4 𝑥20 𝑆1𝑆20𝑎1 𝑎26 𝑍11 𝑥10 9 𝑥20𝑆1𝑆20𝑎10𝑎212 Problemas de Minimização Método das Duas Fases Para construir a Tabela 0 da 1ª Fase consideraremos Z x1 x2 S1 S2 a1 a2 b Z 1 11 09 0 1 0 0 12 S1 0 03 01 1 0 0 0 27 a1 0 05 05 0 0 1 0 6 a2 0 06 04 0 1 0 1 6 A base é iniciada com as variáveis de folga excesso e artificiais No caso da primeira restrição ela adicionou S1 a segunda restrição adicionou somente a1 ao modelo a terceira restrição adicionou S2 e a2 mas prevalece a2 Problemas de Minimização Método das Duas Fases O processo de resolução é o mesmo que vimos anteriormente em outras palavras iremos rodar o algoritmo normal do Simplex O pivotamento indica que a variável x1 é quem entra na base então ela define a coluna pivô Na sequencia temos o pivotamento das linhas para descobrir qual variável sai da base 27 03 9 menor valor determinando a linha pivô 6 05 12 6 06 10 Na intersecção entre coluna e linha pivôs o número pivô será 03 Z x1 x2 S1 S2 a1 a2 b Z 1 11 09 0 1 0 0 12 S1 0 03 01 1 0 0 0 27 a1 0 05 05 0 0 1 0 6 a2 0 06 04 0 1 0 1 6 Tabela 0 1ª Fase Problemas de Minimização Método das Duas Fases Neste problema em específico iremos obter a partir da Tabela 0 mais 3 tabelas A 1ª fase se encerra portanto na Tabela 3 onde obteremos a otimalidade conforme a função objetivo contendo as soluções dessa fase O algoritmo a ser executado tabela após tabela até a Tabela 3 é o mesmo que aprendemos na oficina passada A Tabela 3 encontrase ao lado Z x1 x2 S1 S2 a1 a2 b Z 1 0 0 0 0 1 0 0 S1 0 1 0 0 5 4 5 6 a1 0 0 0 1 1 06 1 03 a2 0 0 1 0 5 6 5 6 Tabela 3 Final 1ª Fase Percebese que esta tabela final da 1ª Fase atende ao teste de otimalidade as variáveis originais do problema são positivas e neste caso são 0 Problemas de Minimização Método das Duas Fases Podemos agora portanto partir para a 2ª Fase Eliminamse as variáveis artificiais Substituise a Função Objetivo da 1ª Fase pela que foi definida para a 2ª Fase Z x1 x2 S1 S2 a1 a2 b Z 1 0 0 0 0 1 0 0 x1 0 1 0 0 5 4 5 6 S1 0 0 0 1 1 06 1 03 x2 0 0 1 0 5 6 5 6 Tabela 3 Final 1ª Fase Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Tabela 0 2ª Fase Problemas de Minimização Método das Duas Fases E agora Já temos valores na FO que são positivos Mas eles precisam ser zerados para x1 e x2 Como são as variáveis originais Podemos operálas exatamente com as linhas da Tabela 0 da 2ª Fase que dizem respeito à elas Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Tabela 0 2ª Fase Problemas de Minimização Método das Duas Fases Para não precisarmos fazer uma nova operação algébrica Podemos considerar uma Tabela Auxiliar para obter a atualização da linha de Z e somente dela Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Tabela 0 2ª Fase Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 04 x1 0 1 0 0 5 6 05 x2 0 0 1 0 5 6 Tabela Auxiliar Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 x1 0 04 0 0 2 24 x2 0 0 05 0 25 3 Z atualizada 1 0 0 0 05 54 Soma Problemas de Minimização Método das Duas Fases Da Tabela Auxiliar com Z atualizado podemos obter nossa Tabela 1 da 2ª Fase substituindo apenas o valor anterior de Z na Tabela 0 da 2ª fase exatamente pelo Z atualizado Daí em diante basta rodar mais uma vez o algoritmo do Simplex Tabular como normalmente fazemos Z x1 x2 S1 S2 b Z 1 04 05 0 0 0 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Tabela 0 2ª Fase Z x1 x2 S1 S2 b Z 1 0 0 0 05 54 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Tabela 1 2ª Fase Atualizado Problemas de Minimização Método das Duas Fases Este problema em específico precisou de apenas mais uma iteração do Simplex para obter a Tabela 2 e final da 2ª Fase Na Tabela 2 vemos que o teste de otimalidade é satisfeito com todos os valores positivos e as variáveis originais sendo 0 na linha de Z Solução Z 525 ou Z 525 x1 75 x2 45 S1 0 S2 03 Tabela 1 2ª Fase Z x1 x2 S1 S2 b Z 1 0 0 05 0 525 x1 0 1 0 5 0 75 S2 0 0 0 1 1 03 x2 0 0 1 5 0 45 Tabela 2 Final 2ª Fase Z x1 x2 S1 S2 b Z 1 0 0 0 05 54 x1 0 1 0 0 5 6 S1 0 0 0 1 1 03 x2 0 0 1 0 5 6 Exercícios Usem os 2 problemas apresentados o primeiro de Maximização usando o Método do Grande Número e o segundo de Minimização usando o Método das Duas Fases e resolvam as demais tabelas que não foram apresentadas Também haverá uma lista de exercícios sobre o Método do Grande Número das Duas Fases e Problemas de Minimização Fiquem atentos nos nossos canais de comunicação Referências HILLIER F S LIEBERMAN GJ Introdução à Pesquisa Operacional 9ª Ed AMGH Editora 2013 MOREIRA Daniel Augusto Pesquisa Operacional curso introdutório 2 ed São Paulo Cengage Learning 2010 PUCCINI Abelardo de Lima PIZZOLATO Nélio Domingues Programação Linear Rio de Janeiro São Paulo LTC 1987 Autoria e Uso da Apresentação Esta apresentação foi desenvolvida pelo Prof Victor Diogho Heuer de Carvalho para uso na disciplina de Pesquisa Operacional e é propriedade do Group of Engineering in Decision Making and Artificial Intelligence GEDAI Todo uso deste material deverá fazer referência também ao seu autor e ao referido grupo Campus do Sertão Delmiro Gouveia