·
Engenharia de Produção ·
Outros
Send your question to AI and receive an answer instantly
Preview text
Dualidade e PósOtimização DUALIDADE O que ocorre com a solução ótima de um PPL caso o vetor de termos independentes se altere Por exemplo Se a demanda por um produto aumentar o custo de produção alteraria Se a disponibilidade de uma das matériasprimas aumentasse a receita aumentaria E se o limite mínimo para a concentração de um nutriente em uma receita aumentasse o que ocorreria com custo da fórmula DUALIDADE Estas indagações levam à análise do problema através da formulação de outro PPL denominado Problema Dual Por sua vez o problema original é denominado Problema Primal RELAXAÇÃO LAGRANGEANA Imagine que o problema primal tenha sido otimizado e que após isso o vetor de recursos 𝐛 sofreu uma perturbação O sistema de restrições então deixará de ser atendido ou seja 𝐀𝐱 𝐛 Neste caso o vetor perturbação será dado 𝐲 𝐛 𝐀𝐱 Seja 𝜆𝑖 o custo de perturbar o recurso 𝑖 𝑖 1 𝑚 Logo o problema de minimizar 𝑓𝐱 mais o custo das perturbações é dado por min 𝑓 𝐱 𝜆1𝑦1 𝜆2 𝑦2 𝜆𝑚 𝑦𝑚 𝐱 𝟎 Este problema é denominado Problema Lagrangeano RELAXAÇÃO LAGRANGEANA Definição1 Função Lagrangeana A função objetivo do problema langrangeano é denominada função lagrangeana dada por 𝐿 𝐱 𝛌 𝑓 𝐱 𝜆1𝑦1 𝜆2𝑦2 𝜆𝑚𝑦𝑚 para 𝐲 𝐛 𝐀𝐱 Note que a função lagrangeana pode ser reescrita da seguinte forma 𝐿 𝐱 𝛌 𝐜𝑻𝐱 𝛌𝑻𝐲 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 𝐜𝑻 𝛌𝑻𝐀𝐱 𝛌𝑻𝐛 𝐿 𝑥1 𝑥𝑛 𝛌 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 RELAXAÇÃO LAGRANGEANA Definição2 Função Dual A função dual é definida como 𝑔 𝛌 min𝑥0 𝐿 𝑥1 𝑥𝑛 𝛌 min𝑥0 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 min𝑥10 𝑐1 𝛌𝑇𝐚1 𝑥1 min𝑥20 𝑐2 𝛌𝑇𝐚2 𝑥2 min𝑥𝑛0 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 Note que a decomposição acima indicada é válida porque as variáveis são independentes entre si A função dual está associada a uma estratégia fundamental na otimização denominada de relaxação Suponha que um dado conjunto de soluções R contenha ou seja igual a outro conjunto S ou seja R S RELAXAÇÃO LAGRANGEANA Podese dizer que R é uma relaxação de S Logo a otimização de 𝑓𝐱 em R leva a uma solução tão boa quanto ou melhor do que obtenível em S min 𝑓 𝐱 𝐱 R min 𝑓 𝐱 𝐱 S para R S Como exemplo considere a minimização de uma fo em ℝ2 como ilustrado abaixo RELAXAÇÃO LAGRANGEANA Propriedade1 Dualidade Fraca 𝑔𝛌 𝑓𝐱 para todo 𝛌 ℝ𝑚 e todo 𝐱 ℝ𝑛 tal que 𝐀𝐱 𝐛 Em outras palavras a função dual fornece um limitante inferior para o valor da solução do problema primal para todo 𝐱 viável Veja 𝑔 𝛌 min𝑥0 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 min𝐀𝐱𝐛 𝑥0 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 min𝐜𝑻𝐱 𝐀𝐱 𝐛 𝐱 𝟎 𝑓 𝐱 para todo 𝐱 tal que 𝐀𝐱 𝐛 𝐱 𝟎 Ou seja podemos usar 𝑔𝛌 para subestimar o valor de 𝑓𝐱 Obviamente o ideal é encontrar 𝛌 que maximiza 𝑔𝛌 RELAXAÇÃO LAGRANGEANA Definição3 Problema Dual Lagrangeano O problema de obtenção do máximo valor para 𝑔𝛌 é denominado Problema Dual Lagrangeano o qual é definido matematicamente como max 𝑔 𝛌 s a 𝛌ϵℝ𝑚 sendo 𝛌 denominado de vetor de variáveis duais Para cada 𝛌 o Problema Dual Lagrangeano é facilmente resolvido Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 0 e logo 𝑐𝑖 𝜆𝑇𝐚𝑖𝑥𝑖 0 Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 0 e logo 𝑐𝑖 𝜆𝑇𝐚𝑖𝑥𝑖 0 PROBLEMA DUAL Para que se obtenha g𝛌 finito devese escolher 𝛌 tal que 𝐜 𝛌𝑻𝐀 𝟎 Definição4 Problema Dual Considere o seguinte problema primal min 𝑓 𝐱 𝐜𝑇𝐱 s a 𝐀𝐱 𝐛 𝐱 𝟎 O problema dual correspondente é dado por max 𝑔 𝛌 𝐛𝑇𝛌 s a 𝐀𝑻𝛌 𝐜 Propriedade2 O dual do dual é o primal PROBLEMA DUAL Para um problema primal na forma padrão Cada restrição primal de igualdade gera uma variável dual irrestrita Cada variável nãonegativa do primal define uma restrição no dual O vetor de recursos do primal 𝐛 define o vetor de custos do dual O vetor de custos do primal 𝑧 𝐜 define o vetor de recursos do dual A matriz de restrições do primal é transposta da matriz do dual Com isso temse um procedimento para construir o dual a partir de um primal na forma padrão PROBLEMA DUAL E se o primal tiver restrições do tipo min 𝑓 𝐱 𝑐1𝑥1 𝑐2𝑥2 s a 𝑎11𝑥1 𝑎12𝑥2 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑏2 𝑥1 0 𝑥2 0 Na forma padrão min 𝑓 𝐱 𝑐1𝑥1 𝑐2𝑥2 0𝑥3 s a 𝑎11𝑥1 𝑎12𝑥2 0𝑥3 𝑏1 𝑎21𝑥1 𝑎22𝑥2 1𝑥3 𝑏2 𝑥1 0 𝑥2 0 𝑥3 0 max 𝑔𝜆1 𝜆2 𝑏1𝜆1 𝑏2𝜆2 s a 𝑎11𝜆1 𝑎21𝜆2 𝑐1 𝑎12𝜆1 𝑎22𝜆2 𝑐2 𝜆2 0 PROBLEMA DUAL E se o primal tiver restrições do tipo min 𝑓 𝒙 𝑐1𝑥1 𝑐2𝑥2 s a 𝑎12𝑥1 𝑎12𝑥2 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑏2 𝑥1 0 𝑥2 0 Na forma padrão min 𝑓 𝒙 𝑐1𝑥1 𝑐2𝑥2 0𝑥3 s a 𝑎11𝑥1 𝑎12𝑥2 0𝑥3 𝑏1 𝑎21𝑥1 𝑎22𝑥2 1𝑥3 𝑏2 𝑥1 0 𝑥2 0 𝑥3 0 max 𝑔𝜆1 𝜆2 𝑏1𝜆1 𝑏2𝜆2 s a 𝑎11𝜆1 𝑎21𝜆2 𝑐1 𝑎12𝜆1 𝑎22𝜆2 𝑐2 𝜆2 0 CONSTRUÇÃO DO PAR PRIMAL x DUAL Regras para construção do par PrimalDual Primal Dual Dual Primal Minimização Maximização Vetor de recursos Gradiente do objetivo Gradiente do objetivo Vetor de recursos Restrição Variável Variável Restrição 𝐿𝑖 𝐿𝑖 RELAÇÕES PRIMAISDUAIS A propriedade 1 diz que 𝑔𝛌 𝑓𝐱 para qualquer solução 𝐱 primal viável e qualquer 𝛌 dual viável isto é 𝛌 ℝ𝒎 Mas o que acontece com um dos problemas quando o outro é inviável E quando o outro é ilimitado Sejam P e D os conjuntos de viabilidade primal e dual respectivamente P 𝐱 ℝ𝑛 𝐀𝐱 𝐛 𝐱 0 D 𝛌 ℝ𝑚 𝐀𝑇𝛌 𝐜 Na propriedade3 assumese que o primal é viável ou seja P Propriedade3 O primal terá solução ilimitada 𝑓 𝐱 se e somente se o dual for inviável D RELAÇÕES PRIMAISDUAIS É fácil ver que D é uma condição necessária para 𝑓 𝐱 pois caso contrário com D existiria 𝛌 tal que 𝑔 𝛌 𝑓 𝐱 Ou seja se o problema for dual viável 𝑔 𝛌 definirá um limite inferior impedindo que 𝑓 𝐱 decresça indefinidamente Todavia a prova de que D é condição suficiente não é trivial e por isso não será apresentada aqui neste curso Na propriedade4 assumese que o dual é viável ou seja D Propriedade4 O dual terá solução ilimitada 𝑔 𝛌 se e somente se o primal for inviável P Observe que os resultados expressos nas propriedades 3 e 4 são simétricos Além disso estas propriedades pressupõem que P ou D Mas ambos podem ser vazios simultaneamente isto é primal e dual inviáveis RELAÇÕES PRIMAISDUAIS Considere o exemplo dado por Winston 2003 e abaixo ilustrado em que tanto o primal quanto o dual são inviáveis verifique graficamente esta afirmação Primal max 𝑧 𝑥2 s a 𝑥1 1 𝑥2 1 𝑥1 0 𝑥2 0 Dual min 𝑤 𝜆1 𝜆2 s a 𝜆1 0 𝜆2 1 𝜆1 0 𝜆2 0 RELAÇÕES PRIMAISDUAIS Considerando as propriedades 3 e 4 e o exemplo anterior concluise que se um dos problemas é inviável o outro é inviável ou tem solução ilimitada Propriedade5 O primal tem solução ótima finita se e somente se o dual tem solução ótima finita Para verificar esta propriedade suponha primeiro que o primal tem solução ótima finita Ou seja 𝑃 e 𝑓 𝐱 Da propriedade3 decorre que 𝐷 pois do contrário 𝑓 𝐱 Como 𝑃 e 𝐷 primal e dual viáveis a propriedade 4 permite afirmar que 𝑔𝛌 Vêse assim que se o primal tem solução ótima finita então o dual também tem A prova da volta isto é se o dual tem solução ótima finita o primal também tem segue o mesmo raciocínio RELAÇÕES PRIMAISDUAIS Propriedade6 Sejam 𝐱 P e 𝛌 D ou seja soluções viáveis para o primal e dual respectivamente Se 𝑓𝐱 𝑔𝛌 então 𝐱 e 𝛌 são soluções ótimas para o primal e o dual respectivamente A validade da propriedade 6 decorre da propriedade 1 Note que se existisse uma solução 𝐱 melhor que 𝐱 a propriedade 1 seria violada isto é 𝑓𝐱 𝑓𝐱 𝑔𝛌 o que é absurdo À frente você verá que a recíproca da propriedade 6 também é verdadeira RELAÇÕES PRIMAISDUAIS Da condição de otimalidade na propriedade 6 temse 𝑓𝐱 𝑔𝛌 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐜𝑻𝐱 𝛌𝑻𝐀𝐱 𝐜𝑻𝛌𝑻𝐀𝐱 𝟎 Agora observe a região de viabilidade dual 𝐀𝑻𝛌 𝐜 𝐚𝟏 𝐓𝛌 𝐜𝟏 𝐚𝟐 𝐓𝛌 𝐜𝟐 𝐚𝐧𝐓𝛌 𝐜𝐧 𝐚𝟏 𝐓𝛌 𝛍𝟏 𝐜𝟏 𝐚𝟐 𝐓𝛌 𝛍𝟐 𝐜𝟐 𝐚𝐧𝐓𝛌 𝛍𝐧 𝐜𝐧 𝜇1 0 𝜇2 0 𝜇𝑛 0 RELAÇÕES PRIMAISDUAIS Note que 𝛍𝑻 𝐜𝑻 𝛌𝑻𝐀 onde 𝛍 é o vetor de folgas das restrições duais Coluna a coluna podese escrever 𝐜𝑻 𝛌𝑻𝐀 𝒄𝟏 𝛌𝑻𝐚𝟏 𝒄𝟐 𝛌𝑻𝐚𝟐 𝒄𝒏 𝛌𝑻𝐚𝐧 De volta à condição de otimalidade da propriedade 6 𝐜𝑻 𝛌𝑻𝐀 𝐱 0 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 0 𝜇1 𝑥1 𝜇2 𝑥2 𝜇𝑛 𝑥𝑛 0 Como 𝐱 𝟎 e 𝛍 𝟎 então devese ter 𝜇𝑗 𝑥𝑗 0 𝑗 1 𝑛 RELAÇÕES PRIMAISDUAIS Propriedade7 Folgas Complementares As soluções 𝐱 e 𝛌 são ótimas para os problemas primal e dual respectivamente se e somente se 𝜇𝑗 𝑥𝑗 0 𝑗 1 𝑛 Esta propriedade mostra que é possível obter a solução primal ótima a partir da solução dual ótima e viceversa bastando para isso resolver um sistema linear veremos um exemplo à frente A partir da propriedade7 também se nota que a solução ótima do PPL pode ser obtida pela resolução do sistema nãolinear 𝐀𝐱 𝐛 𝐱 𝟎 𝐀𝑇𝛌 𝛍 𝐜 𝛍 𝟎 𝜇𝑗𝑥𝑗 0 𝑗 1 𝑛 RELAÇÕES PRIMAISDUAIS Note agora que 𝛍𝑻 𝐱 𝟎 𝐜𝑇𝛌𝑇𝐀𝐱 𝟎 𝐜𝑇𝐱 𝛌𝑇𝐀𝐱 𝐜𝑇𝐱 𝛌𝑇𝐛 𝑓𝐱 𝑔𝛌 A condição necessária decorre da propriedade 9 pois se 𝛌𝑻 𝐜B 𝑇 𝐁1 for dual ótima e portanto viável então 𝐱 é ótima e Logo 𝑓 𝐱 𝐜B 𝑇 𝐱B 𝑓 𝐱 𝐜B 𝑇 𝐁1𝐛 𝑓 𝐱 𝛌𝑻𝐛 𝑓 𝐱 𝑔𝛌 Propriedade8 Dualidade Forte As soluções 𝐱 e 𝛌 são ótimas para os problemas primal e dual respectivamente se e somente se 𝑓𝐱 𝑔𝛌 Propriedade9 O vetor multiplicador simplex na base ótima 𝐜B 𝑇 𝐁1 é uma solução dual ótima Ou seja 𝛌𝑻 𝐜B 𝑇 𝐁1 RELAÇÕES PRIMAISDUAIS A validade da propriedade 9 decorre do fato de que o vetor simplex ótimo é uma solução dual viável e da igualdade entre os objetivos primal e dual 𝑔 𝛌 𝛌𝑇𝐛 𝐜𝐁 𝑇𝐁1𝐛 𝐜B 𝑇𝐱B 𝐜N 𝑇𝐱N 𝑓𝐱 A igualdade dos objetivos é válida para qualquer vetor multiplicador simplex mas apenas o vetor correspondente à base ótima é dual viável A condição de otimalidade do método simplex é atendida na base ótima Ou seja 𝑐𝑗 𝛌𝑻𝐚𝑗 0 para toda coluna nãobásica j Nas colunas básicas temse 𝑐𝑗 𝑇 𝛌𝑻𝐚𝑗 0 Logo em todas as colunas na solução ótima podese escrever 𝑐𝑗 𝛌𝑻𝐚𝑗 0 Provando assim que 𝛌𝑇 𝐜B 𝑇 𝐁1 é dual factível RELAÇÕES PRIMAISDUAIS RESUMO O problema primal tem solução ótima finita se e somente se o problema dual também tiver Se 𝑥 e 𝜆são soluções ótimas do primal e do dual respectivamente então 𝑓 𝑥 𝑔 𝜆 Se o primal dual é ilimitado o dual primal é inviável Se o primal dual é inviável então o dual primal é ilimitado ou inviável O vetor multiplicador simplex na base ótima 𝛌𝑻 𝐜B 𝑇 𝐁1 é uma solução dual ótima INTERPRETAÇÃO ECONÔMICA DO DUAL O que ocorre com o valor de 𝑓 𝐱 quando a quantidade do iésimo recurso 𝑏𝑖 varia marginalmente Lembrese que 𝑓 𝐱 𝑔 𝛌 𝑓 𝐱 𝐛𝑇𝛌 Tomandose a derivada parcial em relação a 𝑏𝑖 temse 𝑓 𝐱 𝑏𝑖 𝜆𝑖 Ou seja a iésima variável dual 𝜆𝑖 mede o impacto na fo da variação unitária do iésimo recurso INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo1 Uma manufatura produz mesas e bancos sendo capaz de vender toda sua produção no período O único recurso é a mãodeobra cuja produtividade juntamente com os lucros são dados na tabela abaixo Caso a empresa disponha de 1 horahomem adicional em qual dos recursos se espera que sua alocação gere maior lucro PRODUTO LUCRO UNITÁRIO HOMENSHORA POR UNIDADE PRODUTO MONTAGEM ACABAMENTO Mesas 20 3 4 Bancos 24 6 2 HORASHOMEM DISPO NÍVEIS 60 32 INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo1 resolução A formulação matemática deste problema de determinação do mix ótimo é mostrada abaixo max 𝑧 20𝑥1 24𝑥2 s a 3𝑥1 6𝑥2 60 4𝑥1 2𝑥2 32 𝑥1 𝑥2 0 Sua solução primal ótima é 𝐱𝑇 4800 e 𝑧 272 E a solução dual ótima é 𝛌𝑇 Τ 28 9 Τ 8 3 Se for possível aumentar em 1horahomem um dos recursos qual você escolheria INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo resolução Cada 1h adicional na montagem a receita aumenta Τ 28 9 Enquanto que para cada 1h adicional no acabamento a receita aumenta Τ 8 3 Logo é mais interessante alocar 1h adicional à montagem pois 𝜆1 𝜆2 A faixa de variação possível deste recurso para que a base atual permaneça ótima será estudada à frente As variáveis do problema dual são muitas vezes denominadas de preçossombra shadow price Pode ser interpretado como o preço justo a ser pago pela utilização de uma unidade de um dado recurso ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO O termo análise se refere ao efeito sobre a solução ótima de pequenas variações nos parâmetros do modelo E pósotimização advém do fato de que está análise é feita após o problema ser otimizado As seguintes alterações podem levar a mudança da basesolução 1 Alteração do vetor de recursos 2 Alteração do vetor de custos 3 Alteração de um coeficiente 𝑎𝑖𝑗 na matriz de restrições tecnológicas 𝐀 4 Adição de uma nova restrição ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Para analisar o impacto destas alterações é preciso avaliar se elas levam à perda da viabilidade primal eou dual 1 Alteração do vetor de recursos Como a alteração pode afetar a viabilidade primal devese garantir que esta seja preservada 𝐱𝐁 𝐁1𝐛 𝟎 𝐁1 𝐛 𝟎 𝐁1𝐛 𝐁1 𝟎 𝐱𝐁 𝐁1 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO O valor da variável dual preço sombra 𝜆𝑖 é a taxa de variação da fo em relação ao recurso 𝑖 Mas para qual variação 𝛿 da quantidade 𝑏𝑖 este preçosombra permanece válido Dependendo do tamanho desta variação pode haver modificação da base ótima Caso não haja o valor da nova fo será 𝐹 𝑏1 𝑏𝑖 𝛿 𝑏𝑚 𝑏1𝜆1 𝑏𝑖 𝛿 𝜆𝑖 𝑏𝑚𝜆𝑚 𝐹 𝑏 𝛿𝜆𝑖 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 2 No exemplo1 para qual intervalo de valores do recurso 1 a base atual permanece ótima Resolução Esta análise será feita para cada recurso mantendose o outro inalterado Seja 𝐛 𝑏1 𝛿 𝑏2 60 𝛿 32 Para a alteração manter a viabilidade primal devese atender à seguinte condição 𝐱𝐁 𝐁𝟏𝐛 𝟎 3 6 4 2 1 60 𝛿 32 𝟎 19 13 29 16 60 𝛿 32 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 2 Resolução 1 9 60 𝛿 32 3 0 1 2 9 60 𝛿 32 6 0 2 A partir das inequações 1 e 2 concluise que 36 𝛿 36 Ou seja para 24 𝑏1 96 a base atual permanece ótima ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 3 De volta ao exemplo1 se a quantidade de horas disponíveis para montagem for reduzida para 40 haverá mudança da base ótima Se não qual o novo valor da função objetivo Resolução Como 40 pertence ao intervalo de valores de 𝑏1 em que a base permanece ótima o novo valor da fo será calculado como 𝑧 𝑧 𝜆1 𝛿 272 28 9 20 20978 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos As alterações no vetor de custos não interferem na viabilidade primal mas podem levar à perda da viabilidade dual forçando uma mudança de base 21 Alteração no custo de uma variável nãobásica 𝑥𝑁𝑘 Não há alteração da solução dual pois 𝛌𝑇 𝐜𝐁𝑇𝐁1 Logo Ƹ𝑐𝑁𝑘 𝑐𝑁𝑘 𝜆𝑇𝑎𝑁𝑘 𝑐𝑁𝑘 𝛿 𝜆𝑇𝑎𝑁𝑘 Ƹ𝑐𝑁𝑘 𝛿 Se Ƹ𝑐𝑁𝑘 0 então a solução atual permanece ótima Se Ƹ𝑐𝑁𝑘 0 a solução atual deixa de ser ótima e 𝑥𝑁𝑘 entra na base método Primal Simplex Também podemos analisar assim a inclusão de uma nova variável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 4 Assuma agora que a empresa do exemplo1 desenhou um novo produto as cadeiras de balanço capaz de gerar um lucro de 22unidade e que consume em sua produção 4 horas de montagem e 3 horas de acabamento Deve a empresa considerar este produto em seu mix ótimo Resolução Seja 𝑥5 a quantidade de bancos a serem produzidos e Ƹ𝑐5 seu custo reduzido Para que valha a pena produzir este produto devese ter Ƹ𝑐5 0 Ƹ𝑐5 𝑐5 𝜆𝑇𝑎5 22 28 9 8 3 4 3 24 9 0 Logo vêse que a produção das cadeiras é interessante economicamente Portanto iterações adicionais do método primal simplex devem ser executadas para encontrar a nova base ótima Faça isso como exercício e você verificará que ela será formada pelas colunas de 𝑥2 e 𝑥5 correspondendo à solução 𝐱 0 265 0 0 365 𝑇 que vale 𝑧 282 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos 22 Alteração no custo de uma variável básica 𝑥𝐵𝑟 Há alteração da solução dual pois 𝛌𝑇 𝐜𝐁 𝑇𝐁1 Logo 𝛌𝑇 𝐜𝐵𝑇 𝛿𝐞𝑟 𝑇 𝐁1 𝐜𝐁𝑇𝐁1 𝛿𝐞𝑟 𝑇 𝐁1 𝛌𝑇 𝛿𝐞𝑟 𝑇 𝐁1 onde 𝐞𝑟 é o vetor coluna em que o a résima linha é igual a 1 e as demais 0 Portanto os custos reduzidos de todas as variáveis nãobásicas devem ser recalculados Ƹ𝑐𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 𝑐𝑗 𝛌𝑇 𝛿𝐞𝑟 𝑇 𝐁1𝐚𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 𝛿𝐞𝑟 𝑇 𝐁1𝐚𝑗 𝐲𝑗 Ƹ𝑐𝑗 𝛿𝐞𝑟 𝑇 𝐲𝑗 Ƹ𝑐𝑗 𝛿𝑦𝒓𝑗 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos 22 Alteração no custo de uma variável básica 𝑥𝐵𝑟 Se o novo custo reduzido de alguma das colunas não básicas se tornar negativo o método primal simplex deverá ser chamado para reotimizar o problema Note que os custos reduzidos das colunas básicas não se alteram qualquer seja a modificação no vetor de custos de variáveis básicas c𝐵𝑇 Ƹ𝐜𝐵 𝑇 𝐜𝐵 𝑇 𝛌 𝑇𝐁 𝐜𝐵 𝑇 𝐜𝐵 𝑇𝐁1𝐁 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 5 A base ótima do exemplo 4 permaneceria a mesma se o preço de venda dos bancos fosse reduzido para 20 reais Resolução Como há alteração de valor de uma variável básica devese recalcular 𝜆𝑇 e os custos reduzidos de todas as variáveis nãobásicas 𝛌𝑇 𝐜𝐁𝑇𝐁1 20 22 6 4 2 3 1 8 5 26 5 Ƹ𝑐1 𝑐1 𝜆𝑇𝑎1 20 8 5 26 5 3 4 8 5 0 Ƹ𝑐3 𝑐3 𝜆𝑇𝑎3 0 28 9 8 3 1 0 28 9 0 Ƹ𝑐4 𝑐4 𝜆𝑇𝑎4 0 28 9 8 3 0 1 8 3 0 Não é necessário portanto aplicar o método primal simplex para reotimizar o problema ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 3 Alteração de um elemento 𝑎𝑖𝑗 da matriz tecnológica Novamente é preciso analisar dois casos se a alteração ocorre em uma coluna básica ou não básica 31 Alteração de um elemento 𝑎𝑖𝑗 de uma coluna nãobásica A modificação de elementos de colunas não básicas não interfere na viabilidade primal pois 𝐱𝐵 𝐁1𝐛 Porém pode alterar a viabilidade dual na coluna nãobásica j Isto é o custo reduzido nesta coluna pode se tornar negativo uma vez que Ƹ𝑐𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 Neste caso se Ƹ𝑐𝑗 0 o método primal simplex deve ser usado na reotimização ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 3 Alteração de um elemento 𝑎𝑖𝑗 da matriz tecnológica 32 Alteração de um elemento 𝑎𝑖𝑗 de uma coluna básica Este é um caso mais complexo uma vez que é possível perder tanto a viabilidade primal quanto a dual Note que se B muda mudam também as variáveis primais e duais lembre que 𝐱𝐵 𝐁1𝐛 e 𝛌𝑇 𝐜𝐵𝑇𝐁1 Se apenas a viabilidade dual for perdida devese usar o método primal simplex Se for apenas a viabilidade primal devese usar o método dual simplex que será visto mais à frente Caso ambas sejam perdidas temse uma situação mais complicada devendose reconstruir a base inicial e otimizar o problema de novo ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição Quando uma nova restrição é inserida em um problema já otimizado ela pode cortar ou não o antigo vértice ótimo Caso o vértice não seja eliminado a SBV por ele representada permanece ótima no novo problema Por outro lado se o vértice for cortado a SBV antiga é primal inviável no novo PPL Ou seja a perdese a viabilidade primal Nestes casos se o método primal simplex fosse usado seria necessário introduzir variáveis artificiais para recuperar uma base viável Todavia essa não é a alternativa mais atrativa do ponto de vista computacional ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição O emprego do método dual simplex é preferível nestes casos pois é possível obter uma base dual viável de forma trivial a partir da base atual Além disso a solução dual atual é em geral uma boa solução dual inicial para o método dual simplex A seguir o método dual simplex será apresentado e posteriormente a discussão sobre inclusão de novas restrições será retomada ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição O emprego do método dual simplex é preferível nestes casos pois é possível obter uma base dual viável de forma trivial a partir da base atual Note primeiro que a inclusão da nova restrição 𝐮𝑇𝐱 faz com que o primal fique com a forma O MÉTODO DUAL SIMPLEX O método dual simplex consiste na aplicação das ideias do método simplex para resolução do problema dual Veja um exemplo introdutório Primal min 𝑓𝐱 2𝑥1 3𝑥2 2𝑥3 𝑥4 sa 𝑥1 𝑥2 2𝑥3 𝑥4 2 2𝑥1 𝑥2 𝑥3 1 𝑥1 𝑥2 𝑥3 𝑥4 0 Dual max 𝑔𝛌 2𝜆1 𝜆2 sa 𝜆1 2𝜆2 2 𝜆1 𝜆2 3 2𝜆1 𝜆2 2 𝜆1 1 O MÉTODO DUAL SIMPLEX A região viável dual é A solução dual ótima indicada na figura é 𝜆1 53 𝜆2 43 e 𝑔𝛌 143 O MÉTODO DUAL SIMPLEX Esta solução é dada pela interseção das retas que definem as restrições 2 e 3 ൝𝜆1 𝜆2 3 𝐚2𝑇𝜆 𝑐2 2𝜆1 𝜆2 2 𝐚3𝑇𝜆 𝑐3 As demais restrições duais são satisfeitas na desigualdade Dizse que as restrições 2 e 3 estão ativas enquanto 1 e 4 estão inativas Note ainda que o vetor 𝐛 pertence ao cone poliédrico formado pelos vetores colunas das restrições ativas 𝐚2 e 𝐚3 Ou seja 𝐚2𝑥2 𝐚3𝑥3 𝐛 1 2 1 1 𝑥2 𝑥3 2 1 A solução primal ótima dada pela solução deste sistema é 𝑥2 43 𝑥3 13 e 𝑓𝐱 143 O MÉTODO DUAL SIMPLEX região factível dual cone gerado por a1 e a2 a2 a3 a1 região factível dual cone gerado por a2 e a3 a2 a3 O MÉTODO DUAL SIMPLEX Analise agora o que ocorreria caso o vértice dual analisado fosse dado pela interseção das restrições duais definidas pelas colunas 𝐚1 e 𝐚2 1 1 2 1 𝑥1 𝑥2 2 1 A solução deste sistema é 𝑥1 13 e 𝑥2 53 que não é primal viável Note ainda que 𝐛 não pertence ao cone poliédrico definido pelas colunas básicas 𝐚1 e 𝐚2 Não sendo uma solução dual ótima devese procurar outro vértice na região dual de modo a aumentar o valor de 𝑔 𝛌 Perturbase então a solução 𝛌 em uma direção 𝛈 fazendo 𝛌 𝛌 𝛿𝛈 𝛿 0 O MÉTODO DUAL SIMPLEX região factível dual λ δη1 solução perturbada a1 a2 η2 λ O MÉTODO DUAL SIMPLEX Em termos da solução do sistema em 𝐚1 e 𝐚2 o que ocorre é onde 𝜂1 𝐁𝑇1𝐞1 e 𝐞1 1 0 Este vetor é chamado direção dual simplex associado à restrição que está deixando de ser ativa Ele é igual a primeira coluna de 𝐁𝑇1 multiplicada por 1 O MÉTODO DUAL SIMPLEX Caso a iésima restrição dual que deixe de ser ativa temse 𝜂𝑖 𝐁𝑇1𝐞𝑖 Note que 𝐛𝑻𝜂𝑖 𝐛𝑻𝐁𝑇1𝐞𝑖 𝑥𝐵𝑖 Quer dizer que quando se perturba a solução dual 𝛌 na direção 𝜂𝑖 a fo dual cresce à taxa 𝑥𝐵𝑖 𝑔 𝛌 𝑔 𝛌 𝜹𝜂𝒊 𝐛𝑻𝛌 𝜹𝐛𝑻𝜂𝒊 𝑔 𝛌 𝜹𝑥𝐵𝑖 No exemplo anterior temse 𝑔 𝛌 133 e 𝑥1 1 3 𝑔 𝛌 𝑔 𝛌 𝑔 𝛌 𝜹𝑥𝐵1 13 3 1 3 𝛿 O MÉTODO DUAL SIMPLEX Note que a taxa de crescimento de 𝑔𝛌 é 𝑥𝐵𝑙 Logo qual variável deve sair da base A variável 𝑥𝐵𝑙 negativa de maior módulo deve ser selecionada para produzir a maior variação na fo dual O MÉTODO DUAL SIMPLEX E qual o tamanho do passo 𝛿 0 Todas as restrições duais devem permanecer viáveis após a perturbação Veja primeiro o que ocorre nas colunas básicas onde devese ter 𝐁𝑇𝛌 𝐜𝐵 𝐁𝑇𝛌 𝐜𝐵 𝛿𝐞𝑙 𝐜𝐵 Portanto nas colunas básicas não há perda da viabilidade dual E nas colunas nãobásicas devese ter 𝐍𝑇𝛌 𝐜𝑁 𝛌𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 𝛌 𝛿𝛈𝑙𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 𝛌𝑇 𝐚𝑁𝑗 𝛿𝛈𝑙𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 Se η𝑇 𝑎𝑁𝑗 0 𝑗 1 𝑛 𝑚 então é possível aumentar 𝛿 indefinidamente sem perder a viabilidade dual Logo o dual será ilimitado e o primal inviável O MÉTODO DUAL SIMPLEX Se η𝑇 𝑎𝑁𝑗 0 para algum 𝑗 𝑗 1 𝑛 𝑚 então o limite superior para 𝛿 será Temse assim um teste para entrada na base Portanto entra na base a variável 𝑥𝑁𝑘 O ALGORITMO DUAL SIMPLEX FASEI Determine uma partição inicial dual viável 𝐴 𝐵 𝑁 FASEII iter 1 Passo 1 Cálculo da sol dual básica 𝛌𝑇 𝐜𝐵𝑇𝐁1 e dos custos rel Ƹ𝑐𝑁𝑗 𝑐𝑁𝑗 𝜆𝑇𝑎𝑁𝑗 𝑗 1 𝑛 𝑚 Passo 2 Teste de otimalidade Se 𝐱𝐁 𝐁𝟏𝐛 𝟎 então PARE A solução básica atual é ótima Passo 3 Escolha da variável 𝑥𝐵𝑙 a sair da base tal que 𝑥𝐵𝑙 min𝑥𝐵𝑖 𝑖 1 𝑚 Passo 4 Cálculo da direção dual simplex 𝛈𝒍 𝐁𝑇 1𝐞𝑙 ou resolva 𝐁𝑇𝜂𝑙 𝐞𝑙 Passo 5 Determinação do passo Se 𝛈𝑙𝑇 𝐚𝑁𝑗 0 𝑗 1 𝑛 𝑚 então PARE A solução é dual é ilimitada primal é inviável Caso contrário determine a var 𝑥𝑁𝑘 que entrará na base መ𝛿 Ƹ𝑐𝑁𝑘 𝛈𝑙𝑇 𝐚𝑁𝑘 min 𝑗1𝑛𝑚 Ƹ𝑐𝑁𝑗 𝛈𝑙𝑇 𝐚𝑁𝑗 𝛈𝑇 𝐚𝑁𝑗 0 Passo 6 Atualização da partição básica iter iter 1 Volte ao Passo 1 O ALGORITMO DUAL SIMPLEX Exemplo 5 Resolva o PPL abaixo pelo método dual simplex Resolução Inicialmente coloque o problema na forma padrão e o dualize O ALGORITMO DUAL SIMPLEX Observe agora que a solução 𝛌𝑻 00 é dual viável Como as restrições duais 𝐚1𝑇𝛌 𝑐1e 𝐚2𝑇𝛌 𝑐2 estão inativas em 𝛌𝑻 00 as colunas correspondentes no primal são nãobásicas Logo podese tomar como base inicial 𝐁 𝐚3 𝐚4 e 𝐍 𝐚1 𝐚2 Agora podese iniciar as iterações do algoritmo FASEI obtenção de uma solução dual viável inicial 𝐁 1 0 0 1 e 𝐍 2 1 1 3 FASEII iterações do algoritmo iter 1 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌 𝑇 0 0 Ƹ𝑐1 𝑐1 𝛌 𝑇𝑎1 1 0 0 2 1 𝑇 1 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 1 0 0 1 3 𝑇 1 O ALGORITMO DUAL SIMPLEX Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 𝑥3 𝑥4 4 3 0 a solução atual não é ótima Passo 3 𝑥𝐁𝑙 𝑥𝐁1 𝑥3 4 Passo 4 𝐁𝑇𝜂1 𝐞1 𝜂1 1 0 Passo 5 𝜂1𝑇𝐚1 10 21 𝑇 2 𝜂1𝑇𝐚2 10 13 𝑇 1 መ𝛿 Ƹ𝑐𝑁1 𝜂1𝑇𝐚𝑁1 min 𝑗𝑁𝐵 Ƹ𝑐𝑁𝑗 𝜂1𝑇𝐚𝑁𝑗 min 1 2 1 1 1 2 𝑥1 entra na base Passo 6 𝐁 𝐚1 𝐚4 e 𝐍 𝐚3 𝐚2 O ALGORITMO DUAL SIMPLEX Iter 2 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌𝑻 𝐜𝐁𝑻𝐁1 𝛌𝑻 1 0 2 0 1 1 1 Τ 1 2 0 Ƹ𝑐3 𝑐3 𝛌 𝑇𝑎3 0 Τ 1 2 0 0 1 𝑇 Τ 1 2 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 1 Τ 1 2 0 1 3 𝑇 Τ 1 2 Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 2 0 1 1 1 4 3 𝑥1 𝑥4 2 1 0 a solução atual não é ótima Passo 3 𝑥𝐁𝑙 𝑥𝐁2 𝑥4 1 Passo 4 𝐁𝑇𝜂2 𝐞2 𝜂2 𝐁𝑇 1𝐞2 𝜂2 1 2 1 2 0 1 0 1 1 2 1 O ALGORITMO DUAL SIMPLEX Passo 5 𝜂2𝑇𝐚3 1 0 2 1 𝑇 Τ 1 2 𝜂2𝑇𝐚2 1 0 1 3 𝑇 Τ 5 2 መ𝛿 Ƹ𝑐𝑁1 𝜂1𝑇𝐚𝑁1 min 𝑗𝑁𝐵 Τ 1 2 Τ 1 2 Τ 1 2 Τ 5 2 1 5 𝑥2 entra na base Passo 6 𝐁 𝐚1 𝐚2 e 𝐍 𝐚3 𝐚4 Iter 3 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌𝑻 𝐜𝐁𝑻𝐁1 𝛌𝑻 1 1 2 1 1 3 1 Τ 2 5 Τ 1 5 Ƹ𝑐3 𝑐3 𝛌 𝑇𝑎3 0 Τ 2 5 Τ 1 5 1 0 𝑇 Τ 2 5 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 0 Τ 2 5 Τ 1 5 0 1 𝑇 Τ 1 5 Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 2 1 1 3 1 4 3 𝑥1 𝑥2 Τ 9 5 Τ 2 5 0 PARE a solução atual é ótima O ALGORITMO DUAL SIMPLEX Como a solução é dual e primal viável na terceira iteração o método para retornando a solução ótima 𝐱 Τ 9 5 Τ 2 5 00 𝑇 e vale 𝑧 Τ 11 5 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição Voltemos agora à questão da inclusão de novas restrições sobre um PPL previamente otimizado Seja 𝐮𝑇𝐱 a nova restrição a ser inserida e seja 𝑥𝑛1 a variável de folga correspondente Temse assim o novo par primaldual min 𝑧 𝐜𝑇𝐱 sa 𝐀𝐱 𝟎𝑥𝑛1 𝐛 𝐮𝑇𝐱 𝑥𝑛1 𝐱 𝟎 𝑥𝑛1 0 max 𝑤 𝐛𝑇𝛌 𝜆𝑚1 sa 𝐀𝑻𝛌 𝐮𝜆𝑚1 𝐜 𝟎𝑇𝛌 𝜆𝑚1 0 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO A inserção de uma nova restrição no primal acompanhada de uma nova variável de folga 𝑥𝑛1 produz uma nova coluna no dual correspondente à nova variável dual 𝜆𝑚1 Não é difícil verificar que a nova solução 𝛌 0𝑇 é viável para o problema dual modificado E qual seria a base correspondente a esta nova solução Note que as restrições duais que estavam ativas antes da inserção da nova restrição isto é 𝐁𝑇𝛌 𝐜𝐁 assim permanecem E a nova restrição dual 𝜆𝑚1 0 também está ativa Logo as colunas de 𝐁 e a coluna da nova variável de folga 𝐚𝑛1 formam uma base dual viável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 6 Considere o seguinte PPL min 𝑧 5𝑥1 𝑥2 sa 7𝑥1 5𝑥2 13 3𝑥1 2𝑥2 17 𝑥1 𝑥2 0 cuja solução primal ótima é 𝐱 Τ 111 29 Τ 80 29 𝑇 Suponha que a restrição 𝑥1 3 seja inserida no problema A solução encontrada permanecerá ótima Se não permanecer reotimize o problema ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Resolução Primeiro observe que a inserção de uma nova restrição torna a solução primal inviável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO A ilustração anterior deixa claro que inserção da restrição 𝑥1 3 produz uma nova base 𝐁 que é primal inviável Todavia conforme vimos há pouco esta base 𝐁 𝐚1 𝐚2 𝐚5 é dual viável e portanto pode ser usada para iniciar o método dual simplex Primal min 𝑓 𝐱 5𝑥1 𝑥2 sa 7𝑥1 5𝑥2 13 3𝑥1 2𝑥2 17 𝑥1 3 𝑥1 𝑥2 0 Dual max 𝑔 𝛌 13𝜆1 17𝜆2 3𝜆3 sa 7𝜆1 3𝜆2 𝜆3 5 5𝜆1 2𝜆2 1 𝜆1 𝜆2 𝜆3 0 BIBLIOGRAFIA ARENALES M et al Pesquisa Operacional para Cursos de Engenharia Rio de Janeiro Elsevier 2007 GOLDBARG MC e LUNA HP Otimização Combinatória e Programação Linear Rio de Janeiro Elsevier 2005 GUÉRET C PRINS C SEVAUX M Applications of Optimization with XpressMP Dash Optimization Ltd 2007 HILLIER Frederick S LIEBERMAN Gerald J Introdução à Pesquisa Operacional São Paulo Campus 1988 TAHA HA Pesquisa Operacional 8 ed São Paulo Pearson Prentice Hall 2008 VILLELA P Notas de Aula DEMATDEPES CEFETRJ WINSTON W L Operations Research Applications and Algorithms 4 ed Duxbury Press 2003 69
Send your question to AI and receive an answer instantly
Preview text
Dualidade e PósOtimização DUALIDADE O que ocorre com a solução ótima de um PPL caso o vetor de termos independentes se altere Por exemplo Se a demanda por um produto aumentar o custo de produção alteraria Se a disponibilidade de uma das matériasprimas aumentasse a receita aumentaria E se o limite mínimo para a concentração de um nutriente em uma receita aumentasse o que ocorreria com custo da fórmula DUALIDADE Estas indagações levam à análise do problema através da formulação de outro PPL denominado Problema Dual Por sua vez o problema original é denominado Problema Primal RELAXAÇÃO LAGRANGEANA Imagine que o problema primal tenha sido otimizado e que após isso o vetor de recursos 𝐛 sofreu uma perturbação O sistema de restrições então deixará de ser atendido ou seja 𝐀𝐱 𝐛 Neste caso o vetor perturbação será dado 𝐲 𝐛 𝐀𝐱 Seja 𝜆𝑖 o custo de perturbar o recurso 𝑖 𝑖 1 𝑚 Logo o problema de minimizar 𝑓𝐱 mais o custo das perturbações é dado por min 𝑓 𝐱 𝜆1𝑦1 𝜆2 𝑦2 𝜆𝑚 𝑦𝑚 𝐱 𝟎 Este problema é denominado Problema Lagrangeano RELAXAÇÃO LAGRANGEANA Definição1 Função Lagrangeana A função objetivo do problema langrangeano é denominada função lagrangeana dada por 𝐿 𝐱 𝛌 𝑓 𝐱 𝜆1𝑦1 𝜆2𝑦2 𝜆𝑚𝑦𝑚 para 𝐲 𝐛 𝐀𝐱 Note que a função lagrangeana pode ser reescrita da seguinte forma 𝐿 𝐱 𝛌 𝐜𝑻𝐱 𝛌𝑻𝐲 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 𝐜𝑻 𝛌𝑻𝐀𝐱 𝛌𝑻𝐛 𝐿 𝑥1 𝑥𝑛 𝛌 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 RELAXAÇÃO LAGRANGEANA Definição2 Função Dual A função dual é definida como 𝑔 𝛌 min𝑥0 𝐿 𝑥1 𝑥𝑛 𝛌 min𝑥0 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 min𝑥10 𝑐1 𝛌𝑇𝐚1 𝑥1 min𝑥20 𝑐2 𝛌𝑇𝐚2 𝑥2 min𝑥𝑛0 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 𝛌𝑇𝐛 Note que a decomposição acima indicada é válida porque as variáveis são independentes entre si A função dual está associada a uma estratégia fundamental na otimização denominada de relaxação Suponha que um dado conjunto de soluções R contenha ou seja igual a outro conjunto S ou seja R S RELAXAÇÃO LAGRANGEANA Podese dizer que R é uma relaxação de S Logo a otimização de 𝑓𝐱 em R leva a uma solução tão boa quanto ou melhor do que obtenível em S min 𝑓 𝐱 𝐱 R min 𝑓 𝐱 𝐱 S para R S Como exemplo considere a minimização de uma fo em ℝ2 como ilustrado abaixo RELAXAÇÃO LAGRANGEANA Propriedade1 Dualidade Fraca 𝑔𝛌 𝑓𝐱 para todo 𝛌 ℝ𝑚 e todo 𝐱 ℝ𝑛 tal que 𝐀𝐱 𝐛 Em outras palavras a função dual fornece um limitante inferior para o valor da solução do problema primal para todo 𝐱 viável Veja 𝑔 𝛌 min𝑥0 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 min𝐀𝐱𝐛 𝑥0 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐀𝐱 min𝐜𝑻𝐱 𝐀𝐱 𝐛 𝐱 𝟎 𝑓 𝐱 para todo 𝐱 tal que 𝐀𝐱 𝐛 𝐱 𝟎 Ou seja podemos usar 𝑔𝛌 para subestimar o valor de 𝑓𝐱 Obviamente o ideal é encontrar 𝛌 que maximiza 𝑔𝛌 RELAXAÇÃO LAGRANGEANA Definição3 Problema Dual Lagrangeano O problema de obtenção do máximo valor para 𝑔𝛌 é denominado Problema Dual Lagrangeano o qual é definido matematicamente como max 𝑔 𝛌 s a 𝛌ϵℝ𝑚 sendo 𝛌 denominado de vetor de variáveis duais Para cada 𝛌 o Problema Dual Lagrangeano é facilmente resolvido Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 0 e logo 𝑐𝑖 𝜆𝑇𝐚𝑖𝑥𝑖 0 Se 𝑐𝑖 𝜆𝑇𝐚𝑖 0 𝑥𝑖 0 e logo 𝑐𝑖 𝜆𝑇𝐚𝑖𝑥𝑖 0 PROBLEMA DUAL Para que se obtenha g𝛌 finito devese escolher 𝛌 tal que 𝐜 𝛌𝑻𝐀 𝟎 Definição4 Problema Dual Considere o seguinte problema primal min 𝑓 𝐱 𝐜𝑇𝐱 s a 𝐀𝐱 𝐛 𝐱 𝟎 O problema dual correspondente é dado por max 𝑔 𝛌 𝐛𝑇𝛌 s a 𝐀𝑻𝛌 𝐜 Propriedade2 O dual do dual é o primal PROBLEMA DUAL Para um problema primal na forma padrão Cada restrição primal de igualdade gera uma variável dual irrestrita Cada variável nãonegativa do primal define uma restrição no dual O vetor de recursos do primal 𝐛 define o vetor de custos do dual O vetor de custos do primal 𝑧 𝐜 define o vetor de recursos do dual A matriz de restrições do primal é transposta da matriz do dual Com isso temse um procedimento para construir o dual a partir de um primal na forma padrão PROBLEMA DUAL E se o primal tiver restrições do tipo min 𝑓 𝐱 𝑐1𝑥1 𝑐2𝑥2 s a 𝑎11𝑥1 𝑎12𝑥2 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑏2 𝑥1 0 𝑥2 0 Na forma padrão min 𝑓 𝐱 𝑐1𝑥1 𝑐2𝑥2 0𝑥3 s a 𝑎11𝑥1 𝑎12𝑥2 0𝑥3 𝑏1 𝑎21𝑥1 𝑎22𝑥2 1𝑥3 𝑏2 𝑥1 0 𝑥2 0 𝑥3 0 max 𝑔𝜆1 𝜆2 𝑏1𝜆1 𝑏2𝜆2 s a 𝑎11𝜆1 𝑎21𝜆2 𝑐1 𝑎12𝜆1 𝑎22𝜆2 𝑐2 𝜆2 0 PROBLEMA DUAL E se o primal tiver restrições do tipo min 𝑓 𝒙 𝑐1𝑥1 𝑐2𝑥2 s a 𝑎12𝑥1 𝑎12𝑥2 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑏2 𝑥1 0 𝑥2 0 Na forma padrão min 𝑓 𝒙 𝑐1𝑥1 𝑐2𝑥2 0𝑥3 s a 𝑎11𝑥1 𝑎12𝑥2 0𝑥3 𝑏1 𝑎21𝑥1 𝑎22𝑥2 1𝑥3 𝑏2 𝑥1 0 𝑥2 0 𝑥3 0 max 𝑔𝜆1 𝜆2 𝑏1𝜆1 𝑏2𝜆2 s a 𝑎11𝜆1 𝑎21𝜆2 𝑐1 𝑎12𝜆1 𝑎22𝜆2 𝑐2 𝜆2 0 CONSTRUÇÃO DO PAR PRIMAL x DUAL Regras para construção do par PrimalDual Primal Dual Dual Primal Minimização Maximização Vetor de recursos Gradiente do objetivo Gradiente do objetivo Vetor de recursos Restrição Variável Variável Restrição 𝐿𝑖 𝐿𝑖 RELAÇÕES PRIMAISDUAIS A propriedade 1 diz que 𝑔𝛌 𝑓𝐱 para qualquer solução 𝐱 primal viável e qualquer 𝛌 dual viável isto é 𝛌 ℝ𝒎 Mas o que acontece com um dos problemas quando o outro é inviável E quando o outro é ilimitado Sejam P e D os conjuntos de viabilidade primal e dual respectivamente P 𝐱 ℝ𝑛 𝐀𝐱 𝐛 𝐱 0 D 𝛌 ℝ𝑚 𝐀𝑇𝛌 𝐜 Na propriedade3 assumese que o primal é viável ou seja P Propriedade3 O primal terá solução ilimitada 𝑓 𝐱 se e somente se o dual for inviável D RELAÇÕES PRIMAISDUAIS É fácil ver que D é uma condição necessária para 𝑓 𝐱 pois caso contrário com D existiria 𝛌 tal que 𝑔 𝛌 𝑓 𝐱 Ou seja se o problema for dual viável 𝑔 𝛌 definirá um limite inferior impedindo que 𝑓 𝐱 decresça indefinidamente Todavia a prova de que D é condição suficiente não é trivial e por isso não será apresentada aqui neste curso Na propriedade4 assumese que o dual é viável ou seja D Propriedade4 O dual terá solução ilimitada 𝑔 𝛌 se e somente se o primal for inviável P Observe que os resultados expressos nas propriedades 3 e 4 são simétricos Além disso estas propriedades pressupõem que P ou D Mas ambos podem ser vazios simultaneamente isto é primal e dual inviáveis RELAÇÕES PRIMAISDUAIS Considere o exemplo dado por Winston 2003 e abaixo ilustrado em que tanto o primal quanto o dual são inviáveis verifique graficamente esta afirmação Primal max 𝑧 𝑥2 s a 𝑥1 1 𝑥2 1 𝑥1 0 𝑥2 0 Dual min 𝑤 𝜆1 𝜆2 s a 𝜆1 0 𝜆2 1 𝜆1 0 𝜆2 0 RELAÇÕES PRIMAISDUAIS Considerando as propriedades 3 e 4 e o exemplo anterior concluise que se um dos problemas é inviável o outro é inviável ou tem solução ilimitada Propriedade5 O primal tem solução ótima finita se e somente se o dual tem solução ótima finita Para verificar esta propriedade suponha primeiro que o primal tem solução ótima finita Ou seja 𝑃 e 𝑓 𝐱 Da propriedade3 decorre que 𝐷 pois do contrário 𝑓 𝐱 Como 𝑃 e 𝐷 primal e dual viáveis a propriedade 4 permite afirmar que 𝑔𝛌 Vêse assim que se o primal tem solução ótima finita então o dual também tem A prova da volta isto é se o dual tem solução ótima finita o primal também tem segue o mesmo raciocínio RELAÇÕES PRIMAISDUAIS Propriedade6 Sejam 𝐱 P e 𝛌 D ou seja soluções viáveis para o primal e dual respectivamente Se 𝑓𝐱 𝑔𝛌 então 𝐱 e 𝛌 são soluções ótimas para o primal e o dual respectivamente A validade da propriedade 6 decorre da propriedade 1 Note que se existisse uma solução 𝐱 melhor que 𝐱 a propriedade 1 seria violada isto é 𝑓𝐱 𝑓𝐱 𝑔𝛌 o que é absurdo À frente você verá que a recíproca da propriedade 6 também é verdadeira RELAÇÕES PRIMAISDUAIS Da condição de otimalidade na propriedade 6 temse 𝑓𝐱 𝑔𝛌 𝐜𝑻𝐱 𝛌𝑻𝐛 𝐜𝑻𝐱 𝛌𝑻𝐀𝐱 𝐜𝑻𝛌𝑻𝐀𝐱 𝟎 Agora observe a região de viabilidade dual 𝐀𝑻𝛌 𝐜 𝐚𝟏 𝐓𝛌 𝐜𝟏 𝐚𝟐 𝐓𝛌 𝐜𝟐 𝐚𝐧𝐓𝛌 𝐜𝐧 𝐚𝟏 𝐓𝛌 𝛍𝟏 𝐜𝟏 𝐚𝟐 𝐓𝛌 𝛍𝟐 𝐜𝟐 𝐚𝐧𝐓𝛌 𝛍𝐧 𝐜𝐧 𝜇1 0 𝜇2 0 𝜇𝑛 0 RELAÇÕES PRIMAISDUAIS Note que 𝛍𝑻 𝐜𝑻 𝛌𝑻𝐀 onde 𝛍 é o vetor de folgas das restrições duais Coluna a coluna podese escrever 𝐜𝑻 𝛌𝑻𝐀 𝒄𝟏 𝛌𝑻𝐚𝟏 𝒄𝟐 𝛌𝑻𝐚𝟐 𝒄𝒏 𝛌𝑻𝐚𝐧 De volta à condição de otimalidade da propriedade 6 𝐜𝑻 𝛌𝑻𝐀 𝐱 0 𝑐1 𝛌𝑇𝐚1 𝑥1 𝑐2 𝛌𝑇𝐚2 𝑥2 𝑐𝑛 𝛌𝑇𝐚𝑛 𝑥𝑛 0 𝜇1 𝑥1 𝜇2 𝑥2 𝜇𝑛 𝑥𝑛 0 Como 𝐱 𝟎 e 𝛍 𝟎 então devese ter 𝜇𝑗 𝑥𝑗 0 𝑗 1 𝑛 RELAÇÕES PRIMAISDUAIS Propriedade7 Folgas Complementares As soluções 𝐱 e 𝛌 são ótimas para os problemas primal e dual respectivamente se e somente se 𝜇𝑗 𝑥𝑗 0 𝑗 1 𝑛 Esta propriedade mostra que é possível obter a solução primal ótima a partir da solução dual ótima e viceversa bastando para isso resolver um sistema linear veremos um exemplo à frente A partir da propriedade7 também se nota que a solução ótima do PPL pode ser obtida pela resolução do sistema nãolinear 𝐀𝐱 𝐛 𝐱 𝟎 𝐀𝑇𝛌 𝛍 𝐜 𝛍 𝟎 𝜇𝑗𝑥𝑗 0 𝑗 1 𝑛 RELAÇÕES PRIMAISDUAIS Note agora que 𝛍𝑻 𝐱 𝟎 𝐜𝑇𝛌𝑇𝐀𝐱 𝟎 𝐜𝑇𝐱 𝛌𝑇𝐀𝐱 𝐜𝑇𝐱 𝛌𝑇𝐛 𝑓𝐱 𝑔𝛌 A condição necessária decorre da propriedade 9 pois se 𝛌𝑻 𝐜B 𝑇 𝐁1 for dual ótima e portanto viável então 𝐱 é ótima e Logo 𝑓 𝐱 𝐜B 𝑇 𝐱B 𝑓 𝐱 𝐜B 𝑇 𝐁1𝐛 𝑓 𝐱 𝛌𝑻𝐛 𝑓 𝐱 𝑔𝛌 Propriedade8 Dualidade Forte As soluções 𝐱 e 𝛌 são ótimas para os problemas primal e dual respectivamente se e somente se 𝑓𝐱 𝑔𝛌 Propriedade9 O vetor multiplicador simplex na base ótima 𝐜B 𝑇 𝐁1 é uma solução dual ótima Ou seja 𝛌𝑻 𝐜B 𝑇 𝐁1 RELAÇÕES PRIMAISDUAIS A validade da propriedade 9 decorre do fato de que o vetor simplex ótimo é uma solução dual viável e da igualdade entre os objetivos primal e dual 𝑔 𝛌 𝛌𝑇𝐛 𝐜𝐁 𝑇𝐁1𝐛 𝐜B 𝑇𝐱B 𝐜N 𝑇𝐱N 𝑓𝐱 A igualdade dos objetivos é válida para qualquer vetor multiplicador simplex mas apenas o vetor correspondente à base ótima é dual viável A condição de otimalidade do método simplex é atendida na base ótima Ou seja 𝑐𝑗 𝛌𝑻𝐚𝑗 0 para toda coluna nãobásica j Nas colunas básicas temse 𝑐𝑗 𝑇 𝛌𝑻𝐚𝑗 0 Logo em todas as colunas na solução ótima podese escrever 𝑐𝑗 𝛌𝑻𝐚𝑗 0 Provando assim que 𝛌𝑇 𝐜B 𝑇 𝐁1 é dual factível RELAÇÕES PRIMAISDUAIS RESUMO O problema primal tem solução ótima finita se e somente se o problema dual também tiver Se 𝑥 e 𝜆são soluções ótimas do primal e do dual respectivamente então 𝑓 𝑥 𝑔 𝜆 Se o primal dual é ilimitado o dual primal é inviável Se o primal dual é inviável então o dual primal é ilimitado ou inviável O vetor multiplicador simplex na base ótima 𝛌𝑻 𝐜B 𝑇 𝐁1 é uma solução dual ótima INTERPRETAÇÃO ECONÔMICA DO DUAL O que ocorre com o valor de 𝑓 𝐱 quando a quantidade do iésimo recurso 𝑏𝑖 varia marginalmente Lembrese que 𝑓 𝐱 𝑔 𝛌 𝑓 𝐱 𝐛𝑇𝛌 Tomandose a derivada parcial em relação a 𝑏𝑖 temse 𝑓 𝐱 𝑏𝑖 𝜆𝑖 Ou seja a iésima variável dual 𝜆𝑖 mede o impacto na fo da variação unitária do iésimo recurso INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo1 Uma manufatura produz mesas e bancos sendo capaz de vender toda sua produção no período O único recurso é a mãodeobra cuja produtividade juntamente com os lucros são dados na tabela abaixo Caso a empresa disponha de 1 horahomem adicional em qual dos recursos se espera que sua alocação gere maior lucro PRODUTO LUCRO UNITÁRIO HOMENSHORA POR UNIDADE PRODUTO MONTAGEM ACABAMENTO Mesas 20 3 4 Bancos 24 6 2 HORASHOMEM DISPO NÍVEIS 60 32 INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo1 resolução A formulação matemática deste problema de determinação do mix ótimo é mostrada abaixo max 𝑧 20𝑥1 24𝑥2 s a 3𝑥1 6𝑥2 60 4𝑥1 2𝑥2 32 𝑥1 𝑥2 0 Sua solução primal ótima é 𝐱𝑇 4800 e 𝑧 272 E a solução dual ótima é 𝛌𝑇 Τ 28 9 Τ 8 3 Se for possível aumentar em 1horahomem um dos recursos qual você escolheria INTERPRETAÇÃO ECONÔMICA DO DUAL Exemplo resolução Cada 1h adicional na montagem a receita aumenta Τ 28 9 Enquanto que para cada 1h adicional no acabamento a receita aumenta Τ 8 3 Logo é mais interessante alocar 1h adicional à montagem pois 𝜆1 𝜆2 A faixa de variação possível deste recurso para que a base atual permaneça ótima será estudada à frente As variáveis do problema dual são muitas vezes denominadas de preçossombra shadow price Pode ser interpretado como o preço justo a ser pago pela utilização de uma unidade de um dado recurso ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO O termo análise se refere ao efeito sobre a solução ótima de pequenas variações nos parâmetros do modelo E pósotimização advém do fato de que está análise é feita após o problema ser otimizado As seguintes alterações podem levar a mudança da basesolução 1 Alteração do vetor de recursos 2 Alteração do vetor de custos 3 Alteração de um coeficiente 𝑎𝑖𝑗 na matriz de restrições tecnológicas 𝐀 4 Adição de uma nova restrição ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Para analisar o impacto destas alterações é preciso avaliar se elas levam à perda da viabilidade primal eou dual 1 Alteração do vetor de recursos Como a alteração pode afetar a viabilidade primal devese garantir que esta seja preservada 𝐱𝐁 𝐁1𝐛 𝟎 𝐁1 𝐛 𝟎 𝐁1𝐛 𝐁1 𝟎 𝐱𝐁 𝐁1 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO O valor da variável dual preço sombra 𝜆𝑖 é a taxa de variação da fo em relação ao recurso 𝑖 Mas para qual variação 𝛿 da quantidade 𝑏𝑖 este preçosombra permanece válido Dependendo do tamanho desta variação pode haver modificação da base ótima Caso não haja o valor da nova fo será 𝐹 𝑏1 𝑏𝑖 𝛿 𝑏𝑚 𝑏1𝜆1 𝑏𝑖 𝛿 𝜆𝑖 𝑏𝑚𝜆𝑚 𝐹 𝑏 𝛿𝜆𝑖 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 2 No exemplo1 para qual intervalo de valores do recurso 1 a base atual permanece ótima Resolução Esta análise será feita para cada recurso mantendose o outro inalterado Seja 𝐛 𝑏1 𝛿 𝑏2 60 𝛿 32 Para a alteração manter a viabilidade primal devese atender à seguinte condição 𝐱𝐁 𝐁𝟏𝐛 𝟎 3 6 4 2 1 60 𝛿 32 𝟎 19 13 29 16 60 𝛿 32 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 2 Resolução 1 9 60 𝛿 32 3 0 1 2 9 60 𝛿 32 6 0 2 A partir das inequações 1 e 2 concluise que 36 𝛿 36 Ou seja para 24 𝑏1 96 a base atual permanece ótima ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 3 De volta ao exemplo1 se a quantidade de horas disponíveis para montagem for reduzida para 40 haverá mudança da base ótima Se não qual o novo valor da função objetivo Resolução Como 40 pertence ao intervalo de valores de 𝑏1 em que a base permanece ótima o novo valor da fo será calculado como 𝑧 𝑧 𝜆1 𝛿 272 28 9 20 20978 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos As alterações no vetor de custos não interferem na viabilidade primal mas podem levar à perda da viabilidade dual forçando uma mudança de base 21 Alteração no custo de uma variável nãobásica 𝑥𝑁𝑘 Não há alteração da solução dual pois 𝛌𝑇 𝐜𝐁𝑇𝐁1 Logo Ƹ𝑐𝑁𝑘 𝑐𝑁𝑘 𝜆𝑇𝑎𝑁𝑘 𝑐𝑁𝑘 𝛿 𝜆𝑇𝑎𝑁𝑘 Ƹ𝑐𝑁𝑘 𝛿 Se Ƹ𝑐𝑁𝑘 0 então a solução atual permanece ótima Se Ƹ𝑐𝑁𝑘 0 a solução atual deixa de ser ótima e 𝑥𝑁𝑘 entra na base método Primal Simplex Também podemos analisar assim a inclusão de uma nova variável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 4 Assuma agora que a empresa do exemplo1 desenhou um novo produto as cadeiras de balanço capaz de gerar um lucro de 22unidade e que consume em sua produção 4 horas de montagem e 3 horas de acabamento Deve a empresa considerar este produto em seu mix ótimo Resolução Seja 𝑥5 a quantidade de bancos a serem produzidos e Ƹ𝑐5 seu custo reduzido Para que valha a pena produzir este produto devese ter Ƹ𝑐5 0 Ƹ𝑐5 𝑐5 𝜆𝑇𝑎5 22 28 9 8 3 4 3 24 9 0 Logo vêse que a produção das cadeiras é interessante economicamente Portanto iterações adicionais do método primal simplex devem ser executadas para encontrar a nova base ótima Faça isso como exercício e você verificará que ela será formada pelas colunas de 𝑥2 e 𝑥5 correspondendo à solução 𝐱 0 265 0 0 365 𝑇 que vale 𝑧 282 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos 22 Alteração no custo de uma variável básica 𝑥𝐵𝑟 Há alteração da solução dual pois 𝛌𝑇 𝐜𝐁 𝑇𝐁1 Logo 𝛌𝑇 𝐜𝐵𝑇 𝛿𝐞𝑟 𝑇 𝐁1 𝐜𝐁𝑇𝐁1 𝛿𝐞𝑟 𝑇 𝐁1 𝛌𝑇 𝛿𝐞𝑟 𝑇 𝐁1 onde 𝐞𝑟 é o vetor coluna em que o a résima linha é igual a 1 e as demais 0 Portanto os custos reduzidos de todas as variáveis nãobásicas devem ser recalculados Ƹ𝑐𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 𝑐𝑗 𝛌𝑇 𝛿𝐞𝑟 𝑇 𝐁1𝐚𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 𝛿𝐞𝑟 𝑇 𝐁1𝐚𝑗 𝐲𝑗 Ƹ𝑐𝑗 𝛿𝐞𝑟 𝑇 𝐲𝑗 Ƹ𝑐𝑗 𝛿𝑦𝒓𝑗 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 2 Alteração do vetor de custos 22 Alteração no custo de uma variável básica 𝑥𝐵𝑟 Se o novo custo reduzido de alguma das colunas não básicas se tornar negativo o método primal simplex deverá ser chamado para reotimizar o problema Note que os custos reduzidos das colunas básicas não se alteram qualquer seja a modificação no vetor de custos de variáveis básicas c𝐵𝑇 Ƹ𝐜𝐵 𝑇 𝐜𝐵 𝑇 𝛌 𝑇𝐁 𝐜𝐵 𝑇 𝐜𝐵 𝑇𝐁1𝐁 𝟎 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 5 A base ótima do exemplo 4 permaneceria a mesma se o preço de venda dos bancos fosse reduzido para 20 reais Resolução Como há alteração de valor de uma variável básica devese recalcular 𝜆𝑇 e os custos reduzidos de todas as variáveis nãobásicas 𝛌𝑇 𝐜𝐁𝑇𝐁1 20 22 6 4 2 3 1 8 5 26 5 Ƹ𝑐1 𝑐1 𝜆𝑇𝑎1 20 8 5 26 5 3 4 8 5 0 Ƹ𝑐3 𝑐3 𝜆𝑇𝑎3 0 28 9 8 3 1 0 28 9 0 Ƹ𝑐4 𝑐4 𝜆𝑇𝑎4 0 28 9 8 3 0 1 8 3 0 Não é necessário portanto aplicar o método primal simplex para reotimizar o problema ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 3 Alteração de um elemento 𝑎𝑖𝑗 da matriz tecnológica Novamente é preciso analisar dois casos se a alteração ocorre em uma coluna básica ou não básica 31 Alteração de um elemento 𝑎𝑖𝑗 de uma coluna nãobásica A modificação de elementos de colunas não básicas não interfere na viabilidade primal pois 𝐱𝐵 𝐁1𝐛 Porém pode alterar a viabilidade dual na coluna nãobásica j Isto é o custo reduzido nesta coluna pode se tornar negativo uma vez que Ƹ𝑐𝑗 𝑐𝑗 𝛌𝑇𝐚𝑗 Neste caso se Ƹ𝑐𝑗 0 o método primal simplex deve ser usado na reotimização ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 3 Alteração de um elemento 𝑎𝑖𝑗 da matriz tecnológica 32 Alteração de um elemento 𝑎𝑖𝑗 de uma coluna básica Este é um caso mais complexo uma vez que é possível perder tanto a viabilidade primal quanto a dual Note que se B muda mudam também as variáveis primais e duais lembre que 𝐱𝐵 𝐁1𝐛 e 𝛌𝑇 𝐜𝐵𝑇𝐁1 Se apenas a viabilidade dual for perdida devese usar o método primal simplex Se for apenas a viabilidade primal devese usar o método dual simplex que será visto mais à frente Caso ambas sejam perdidas temse uma situação mais complicada devendose reconstruir a base inicial e otimizar o problema de novo ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição Quando uma nova restrição é inserida em um problema já otimizado ela pode cortar ou não o antigo vértice ótimo Caso o vértice não seja eliminado a SBV por ele representada permanece ótima no novo problema Por outro lado se o vértice for cortado a SBV antiga é primal inviável no novo PPL Ou seja a perdese a viabilidade primal Nestes casos se o método primal simplex fosse usado seria necessário introduzir variáveis artificiais para recuperar uma base viável Todavia essa não é a alternativa mais atrativa do ponto de vista computacional ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição O emprego do método dual simplex é preferível nestes casos pois é possível obter uma base dual viável de forma trivial a partir da base atual Além disso a solução dual atual é em geral uma boa solução dual inicial para o método dual simplex A seguir o método dual simplex será apresentado e posteriormente a discussão sobre inclusão de novas restrições será retomada ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição O emprego do método dual simplex é preferível nestes casos pois é possível obter uma base dual viável de forma trivial a partir da base atual Note primeiro que a inclusão da nova restrição 𝐮𝑇𝐱 faz com que o primal fique com a forma O MÉTODO DUAL SIMPLEX O método dual simplex consiste na aplicação das ideias do método simplex para resolução do problema dual Veja um exemplo introdutório Primal min 𝑓𝐱 2𝑥1 3𝑥2 2𝑥3 𝑥4 sa 𝑥1 𝑥2 2𝑥3 𝑥4 2 2𝑥1 𝑥2 𝑥3 1 𝑥1 𝑥2 𝑥3 𝑥4 0 Dual max 𝑔𝛌 2𝜆1 𝜆2 sa 𝜆1 2𝜆2 2 𝜆1 𝜆2 3 2𝜆1 𝜆2 2 𝜆1 1 O MÉTODO DUAL SIMPLEX A região viável dual é A solução dual ótima indicada na figura é 𝜆1 53 𝜆2 43 e 𝑔𝛌 143 O MÉTODO DUAL SIMPLEX Esta solução é dada pela interseção das retas que definem as restrições 2 e 3 ൝𝜆1 𝜆2 3 𝐚2𝑇𝜆 𝑐2 2𝜆1 𝜆2 2 𝐚3𝑇𝜆 𝑐3 As demais restrições duais são satisfeitas na desigualdade Dizse que as restrições 2 e 3 estão ativas enquanto 1 e 4 estão inativas Note ainda que o vetor 𝐛 pertence ao cone poliédrico formado pelos vetores colunas das restrições ativas 𝐚2 e 𝐚3 Ou seja 𝐚2𝑥2 𝐚3𝑥3 𝐛 1 2 1 1 𝑥2 𝑥3 2 1 A solução primal ótima dada pela solução deste sistema é 𝑥2 43 𝑥3 13 e 𝑓𝐱 143 O MÉTODO DUAL SIMPLEX região factível dual cone gerado por a1 e a2 a2 a3 a1 região factível dual cone gerado por a2 e a3 a2 a3 O MÉTODO DUAL SIMPLEX Analise agora o que ocorreria caso o vértice dual analisado fosse dado pela interseção das restrições duais definidas pelas colunas 𝐚1 e 𝐚2 1 1 2 1 𝑥1 𝑥2 2 1 A solução deste sistema é 𝑥1 13 e 𝑥2 53 que não é primal viável Note ainda que 𝐛 não pertence ao cone poliédrico definido pelas colunas básicas 𝐚1 e 𝐚2 Não sendo uma solução dual ótima devese procurar outro vértice na região dual de modo a aumentar o valor de 𝑔 𝛌 Perturbase então a solução 𝛌 em uma direção 𝛈 fazendo 𝛌 𝛌 𝛿𝛈 𝛿 0 O MÉTODO DUAL SIMPLEX região factível dual λ δη1 solução perturbada a1 a2 η2 λ O MÉTODO DUAL SIMPLEX Em termos da solução do sistema em 𝐚1 e 𝐚2 o que ocorre é onde 𝜂1 𝐁𝑇1𝐞1 e 𝐞1 1 0 Este vetor é chamado direção dual simplex associado à restrição que está deixando de ser ativa Ele é igual a primeira coluna de 𝐁𝑇1 multiplicada por 1 O MÉTODO DUAL SIMPLEX Caso a iésima restrição dual que deixe de ser ativa temse 𝜂𝑖 𝐁𝑇1𝐞𝑖 Note que 𝐛𝑻𝜂𝑖 𝐛𝑻𝐁𝑇1𝐞𝑖 𝑥𝐵𝑖 Quer dizer que quando se perturba a solução dual 𝛌 na direção 𝜂𝑖 a fo dual cresce à taxa 𝑥𝐵𝑖 𝑔 𝛌 𝑔 𝛌 𝜹𝜂𝒊 𝐛𝑻𝛌 𝜹𝐛𝑻𝜂𝒊 𝑔 𝛌 𝜹𝑥𝐵𝑖 No exemplo anterior temse 𝑔 𝛌 133 e 𝑥1 1 3 𝑔 𝛌 𝑔 𝛌 𝑔 𝛌 𝜹𝑥𝐵1 13 3 1 3 𝛿 O MÉTODO DUAL SIMPLEX Note que a taxa de crescimento de 𝑔𝛌 é 𝑥𝐵𝑙 Logo qual variável deve sair da base A variável 𝑥𝐵𝑙 negativa de maior módulo deve ser selecionada para produzir a maior variação na fo dual O MÉTODO DUAL SIMPLEX E qual o tamanho do passo 𝛿 0 Todas as restrições duais devem permanecer viáveis após a perturbação Veja primeiro o que ocorre nas colunas básicas onde devese ter 𝐁𝑇𝛌 𝐜𝐵 𝐁𝑇𝛌 𝐜𝐵 𝛿𝐞𝑙 𝐜𝐵 Portanto nas colunas básicas não há perda da viabilidade dual E nas colunas nãobásicas devese ter 𝐍𝑇𝛌 𝐜𝑁 𝛌𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 𝛌 𝛿𝛈𝑙𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 𝛌𝑇 𝐚𝑁𝑗 𝛿𝛈𝑙𝑇𝐚𝑁𝑗 𝐜𝑁𝒋 Se η𝑇 𝑎𝑁𝑗 0 𝑗 1 𝑛 𝑚 então é possível aumentar 𝛿 indefinidamente sem perder a viabilidade dual Logo o dual será ilimitado e o primal inviável O MÉTODO DUAL SIMPLEX Se η𝑇 𝑎𝑁𝑗 0 para algum 𝑗 𝑗 1 𝑛 𝑚 então o limite superior para 𝛿 será Temse assim um teste para entrada na base Portanto entra na base a variável 𝑥𝑁𝑘 O ALGORITMO DUAL SIMPLEX FASEI Determine uma partição inicial dual viável 𝐴 𝐵 𝑁 FASEII iter 1 Passo 1 Cálculo da sol dual básica 𝛌𝑇 𝐜𝐵𝑇𝐁1 e dos custos rel Ƹ𝑐𝑁𝑗 𝑐𝑁𝑗 𝜆𝑇𝑎𝑁𝑗 𝑗 1 𝑛 𝑚 Passo 2 Teste de otimalidade Se 𝐱𝐁 𝐁𝟏𝐛 𝟎 então PARE A solução básica atual é ótima Passo 3 Escolha da variável 𝑥𝐵𝑙 a sair da base tal que 𝑥𝐵𝑙 min𝑥𝐵𝑖 𝑖 1 𝑚 Passo 4 Cálculo da direção dual simplex 𝛈𝒍 𝐁𝑇 1𝐞𝑙 ou resolva 𝐁𝑇𝜂𝑙 𝐞𝑙 Passo 5 Determinação do passo Se 𝛈𝑙𝑇 𝐚𝑁𝑗 0 𝑗 1 𝑛 𝑚 então PARE A solução é dual é ilimitada primal é inviável Caso contrário determine a var 𝑥𝑁𝑘 que entrará na base መ𝛿 Ƹ𝑐𝑁𝑘 𝛈𝑙𝑇 𝐚𝑁𝑘 min 𝑗1𝑛𝑚 Ƹ𝑐𝑁𝑗 𝛈𝑙𝑇 𝐚𝑁𝑗 𝛈𝑇 𝐚𝑁𝑗 0 Passo 6 Atualização da partição básica iter iter 1 Volte ao Passo 1 O ALGORITMO DUAL SIMPLEX Exemplo 5 Resolva o PPL abaixo pelo método dual simplex Resolução Inicialmente coloque o problema na forma padrão e o dualize O ALGORITMO DUAL SIMPLEX Observe agora que a solução 𝛌𝑻 00 é dual viável Como as restrições duais 𝐚1𝑇𝛌 𝑐1e 𝐚2𝑇𝛌 𝑐2 estão inativas em 𝛌𝑻 00 as colunas correspondentes no primal são nãobásicas Logo podese tomar como base inicial 𝐁 𝐚3 𝐚4 e 𝐍 𝐚1 𝐚2 Agora podese iniciar as iterações do algoritmo FASEI obtenção de uma solução dual viável inicial 𝐁 1 0 0 1 e 𝐍 2 1 1 3 FASEII iterações do algoritmo iter 1 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌 𝑇 0 0 Ƹ𝑐1 𝑐1 𝛌 𝑇𝑎1 1 0 0 2 1 𝑇 1 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 1 0 0 1 3 𝑇 1 O ALGORITMO DUAL SIMPLEX Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 𝑥3 𝑥4 4 3 0 a solução atual não é ótima Passo 3 𝑥𝐁𝑙 𝑥𝐁1 𝑥3 4 Passo 4 𝐁𝑇𝜂1 𝐞1 𝜂1 1 0 Passo 5 𝜂1𝑇𝐚1 10 21 𝑇 2 𝜂1𝑇𝐚2 10 13 𝑇 1 መ𝛿 Ƹ𝑐𝑁1 𝜂1𝑇𝐚𝑁1 min 𝑗𝑁𝐵 Ƹ𝑐𝑁𝑗 𝜂1𝑇𝐚𝑁𝑗 min 1 2 1 1 1 2 𝑥1 entra na base Passo 6 𝐁 𝐚1 𝐚4 e 𝐍 𝐚3 𝐚2 O ALGORITMO DUAL SIMPLEX Iter 2 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌𝑻 𝐜𝐁𝑻𝐁1 𝛌𝑻 1 0 2 0 1 1 1 Τ 1 2 0 Ƹ𝑐3 𝑐3 𝛌 𝑇𝑎3 0 Τ 1 2 0 0 1 𝑇 Τ 1 2 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 1 Τ 1 2 0 1 3 𝑇 Τ 1 2 Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 2 0 1 1 1 4 3 𝑥1 𝑥4 2 1 0 a solução atual não é ótima Passo 3 𝑥𝐁𝑙 𝑥𝐁2 𝑥4 1 Passo 4 𝐁𝑇𝜂2 𝐞2 𝜂2 𝐁𝑇 1𝐞2 𝜂2 1 2 1 2 0 1 0 1 1 2 1 O ALGORITMO DUAL SIMPLEX Passo 5 𝜂2𝑇𝐚3 1 0 2 1 𝑇 Τ 1 2 𝜂2𝑇𝐚2 1 0 1 3 𝑇 Τ 5 2 መ𝛿 Ƹ𝑐𝑁1 𝜂1𝑇𝐚𝑁1 min 𝑗𝑁𝐵 Τ 1 2 Τ 1 2 Τ 1 2 Τ 5 2 1 5 𝑥2 entra na base Passo 6 𝐁 𝐚1 𝐚2 e 𝐍 𝐚3 𝐚4 Iter 3 Passo 1 𝐁𝑇𝛌 𝐜𝐁 𝛌𝑻 𝐜𝐁𝑻𝐁1 𝛌𝑻 1 1 2 1 1 3 1 Τ 2 5 Τ 1 5 Ƹ𝑐3 𝑐3 𝛌 𝑇𝑎3 0 Τ 2 5 Τ 1 5 1 0 𝑇 Τ 2 5 Ƹ𝑐2 𝑐2 𝛌 𝑇𝑎2 0 Τ 2 5 Τ 1 5 0 1 𝑇 Τ 1 5 Passo 2 𝐁𝐱𝐁 𝐛 𝐱𝐁 2 1 1 3 1 4 3 𝑥1 𝑥2 Τ 9 5 Τ 2 5 0 PARE a solução atual é ótima O ALGORITMO DUAL SIMPLEX Como a solução é dual e primal viável na terceira iteração o método para retornando a solução ótima 𝐱 Τ 9 5 Τ 2 5 00 𝑇 e vale 𝑧 Τ 11 5 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO 4 Inclusão de uma nova restrição Voltemos agora à questão da inclusão de novas restrições sobre um PPL previamente otimizado Seja 𝐮𝑇𝐱 a nova restrição a ser inserida e seja 𝑥𝑛1 a variável de folga correspondente Temse assim o novo par primaldual min 𝑧 𝐜𝑇𝐱 sa 𝐀𝐱 𝟎𝑥𝑛1 𝐛 𝐮𝑇𝐱 𝑥𝑛1 𝐱 𝟎 𝑥𝑛1 0 max 𝑤 𝐛𝑇𝛌 𝜆𝑚1 sa 𝐀𝑻𝛌 𝐮𝜆𝑚1 𝐜 𝟎𝑇𝛌 𝜆𝑚1 0 ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO A inserção de uma nova restrição no primal acompanhada de uma nova variável de folga 𝑥𝑛1 produz uma nova coluna no dual correspondente à nova variável dual 𝜆𝑚1 Não é difícil verificar que a nova solução 𝛌 0𝑇 é viável para o problema dual modificado E qual seria a base correspondente a esta nova solução Note que as restrições duais que estavam ativas antes da inserção da nova restrição isto é 𝐁𝑇𝛌 𝐜𝐁 assim permanecem E a nova restrição dual 𝜆𝑚1 0 também está ativa Logo as colunas de 𝐁 e a coluna da nova variável de folga 𝐚𝑛1 formam uma base dual viável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Exemplo 6 Considere o seguinte PPL min 𝑧 5𝑥1 𝑥2 sa 7𝑥1 5𝑥2 13 3𝑥1 2𝑥2 17 𝑥1 𝑥2 0 cuja solução primal ótima é 𝐱 Τ 111 29 Τ 80 29 𝑇 Suponha que a restrição 𝑥1 3 seja inserida no problema A solução encontrada permanecerá ótima Se não permanecer reotimize o problema ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO Resolução Primeiro observe que a inserção de uma nova restrição torna a solução primal inviável ANÁLISE DE SENSIBILIDADE E PÓSOTIMIZAÇÃO A ilustração anterior deixa claro que inserção da restrição 𝑥1 3 produz uma nova base 𝐁 que é primal inviável Todavia conforme vimos há pouco esta base 𝐁 𝐚1 𝐚2 𝐚5 é dual viável e portanto pode ser usada para iniciar o método dual simplex Primal min 𝑓 𝐱 5𝑥1 𝑥2 sa 7𝑥1 5𝑥2 13 3𝑥1 2𝑥2 17 𝑥1 3 𝑥1 𝑥2 0 Dual max 𝑔 𝛌 13𝜆1 17𝜆2 3𝜆3 sa 7𝜆1 3𝜆2 𝜆3 5 5𝜆1 2𝜆2 1 𝜆1 𝜆2 𝜆3 0 BIBLIOGRAFIA ARENALES M et al Pesquisa Operacional para Cursos de Engenharia Rio de Janeiro Elsevier 2007 GOLDBARG MC e LUNA HP Otimização Combinatória e Programação Linear Rio de Janeiro Elsevier 2005 GUÉRET C PRINS C SEVAUX M Applications of Optimization with XpressMP Dash Optimization Ltd 2007 HILLIER Frederick S LIEBERMAN Gerald J Introdução à Pesquisa Operacional São Paulo Campus 1988 TAHA HA Pesquisa Operacional 8 ed São Paulo Pearson Prentice Hall 2008 VILLELA P Notas de Aula DEMATDEPES CEFETRJ WINSTON W L Operations Research Applications and Algorithms 4 ed Duxbury Press 2003 69