·
Administração ·
Outros
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Pesquisa Operacional Método Simplex Dualidade Dualidade Todo problema de programação linear está associado a outro problema chamado dual O problema original é chamado primal Apesar de possuírem características distintas ambos os problemas levam à mesma solução ótima Se o modelo original tiver m restrições e n variáveis então seu modelo dual terá n restrições e m variáveis O modelo original Primal pode ser substituído pelo modelo Dual cuja solução pode ser mais rápida Dualidade Reparem nesses dois problemas Maximizar Z 3x1 2x2 Sujeito a 05x1 03x2 3 01x1 02x2 1 04x1 05x2 3 x1 x2 0 Solução ótima x1 462 x2 23 Z 1846 Minimizar W 3y1 1y2 3y3 Sujeito a 05y1 01y2 04y3 3 03y1 02y2 05y3 2 y1 y2 y3 0 Solução ótima y1 537 y2 0 y3 0778 W 1846 Dualidade PROBLEMA PRIMAL forma padrão modelo original maximizar 𝑍 𝒄𝟏𝑥1 𝒄𝟐𝑥2 𝒄𝒏𝑥𝑛 sa 𝒂𝟏𝟏𝑥1 𝑎12𝑥2 𝑎1𝑛𝑥𝑛 𝒃𝟏 𝒂𝟐𝟏𝑥1 𝑎22𝑥2 𝑎2𝑛𝑥𝑛 𝒃𝟐 𝒂𝒎𝟏𝑥1 𝑎𝑚2𝑥2 𝑎𝑚𝑛𝑥𝑛 𝒃𝒎 com 𝑥1 𝑥2 𝑥𝑛 0 PROBLEMA DUAL modelo dual minimizar W 𝒃𝟏𝑦1 𝒃𝟐𝑦2 𝒃𝒎𝑦𝑚 sa 𝒂𝟏𝟏𝑦1 𝒂𝟐𝟏𝑦2 𝒂𝒎𝟏𝑦𝑚 𝒄𝟏 𝑎12𝑦1 𝑎22𝑦2 𝑎𝑚2𝑦𝑚 𝒄𝟐 𝑎1𝑛𝑦1 𝑎2𝑛𝑦2 𝑎𝑚𝑛𝑦𝑚 𝒄𝒏 com 𝑦1 𝑦2 𝑦𝑚 0 Dualidade Em geral em problemas de dualidade temos Se um é problema de maximizar o outro é de minimizar Os coeficientes ci da função objetivo de um passam a ser os recursos bi do outro Os recursos técnicos bi de um passam a ser os coeficientes ci da função objetivo do outro Dos últimos dois acima percebese que As variáveis de um estão relacionadas com as restrições do outro As restrições de um estão relacionadas com as variáveis do outro Dualidade Uma das vantagens do uso da dualidade é que podemos resolver um problema PRIMAL com mais de duas variáveis usando o método gráfico no modelo DUAL PRIMAL n 3 variáveis xs m 2 restrições DUAL m 2 variáveis ys n 3 restrições Exemplo 1 Encontre o dual do problema abaixo Exemplo 2 a Escreva o Dual do PPL abaixo b Resolva os dois problemas Primal e o Dual pelo Solver do Excel c Compare a solução ótima de ambos os modelos Exemplo 3 a Escreva o Dual do PPL abaixo b Resolva os dois problemas Primal e o Dual pelo Solver do Excel c Compare a solução ótima de ambos os modelos Propriedades da relação entre Primal e Dual Se o Primal tem uma solução ótima o DUAL também terá a mesma solução ótima Se o Primal é ilimitado o DUAL será infactível sem solução Se o Primal é infactível o DUAL será infactível ou ilimitado O Dual do Dual é o Primal Primal vs Dual Em problema de PPL podese optar entre resolver o problema Primal ou o Dual A escolha deve levar em consideração o esforço computacional que por sua vez depende do número de restrições variáveis de controle de folga e artificiais Geralmente optase pelo problema Primal ou Dual que tiver menor número de restrições Primal na forma nãocanônica Até o momento trabalhamos com problemas Primal em sua forma canônica Maximizar 𝑍 𝑐1𝑥1 𝑐2𝑥2 𝑐𝑛𝑥𝑛 sa 𝑎11𝑥1 𝑎12𝑥2 𝑎1𝑛𝑥𝑛 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑎2𝑛𝑥𝑛 𝑏2 𝑎𝑚1𝑥1 𝑎𝑚2𝑥2 𝑎𝑚𝑛𝑥𝑛 𝑏𝑚 com 𝑥1 𝑥2 𝑥𝑛 0 Maximizar 𝑍 3𝑥1 5𝑥2 sa 3𝑥1 2𝑥2 18 𝑥1 4 2𝑥2 12 com 𝑥1 𝑥2 0 Maximizar 𝑍 𝑐𝑋 sa AX 𝑏 com 𝑋 0 Para outras formas do Primal é necessário algumas adaptações Tabela de conversão PrimalDual Modelo PRIMAL Modelo DUAL Minimizar Maximizar Maximizar Minimizar xi 0 restrição i será restrição i será xi 0 restrição i será restrição i será xi é livre restrição i será restrição i será Restrição i é yi 0 yi 0 Restrição i é yi 0 yi 0 Restrição i é yi é livre yi é livre Exemplo 4 Determine o dual de cada problema abaixo minimizar Z 15x1 12x2 sujeito a x1 2x2 3 2x1 4x2 5 com x1 x2 0 Solução maximizar 2y1 5y2 sa y1 2y2 15 2y1 4y2 12 Com y1 0 y2 0 Regra geral de conversão PrimalDual 1 Você pode usar a tabela de conversão PrimalDual acima ou 2 usar um regra mais geral que é a seguinte i Coloque as variáveis de folgaexcesso no primal ii Ao escrever o problema DUAL use sinal do tipo em todas nas restrições se o DUAL for problema de maximização e use sinal do tipo em todas nas restrições se o DUAL for problema de minimização ii deixe todas as variáveis duais livres Exemplo 5 Escreva o Dual do problema abaixo usando a regra geral 𝑀𝐴𝑋 𝑍 5𝑥1 12𝑥2 4𝑥3 sa 𝑥1 2𝑥2 𝑥3 10 2𝑥1 𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 Solução PRIMAL 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 sa 2𝑥1 𝑥2 𝑥3 2 𝑥1 2𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 0𝐹1 sa 2𝑥1 𝑥2 𝑥3 𝐹1 2 𝑥1 2𝑥2 3𝑥3 0𝐹1 8 𝑥1 𝑥2 𝑥3 𝐹1 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 𝑦1 𝑦2 livres 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0 𝑦1 𝑦2 livres 𝑦1 0 𝑦2 livre DUAL 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0 𝑦2 livre 2 Troque max para min As 2 restrições no primal se tornam 2 variáveis y1 y2 no dual As 4 variáveis x1x2x3 F1 no dual se tornam 4 restrições no dual Como no dual temos problema de minimização use sinais Deixe as variáveis duais y1 e y2 livres 1 Acrescentar as variáveis de folgas 1 2 Exemplo 6 Escreva o Dual do problema abaixo usando a regra geral Max Z 7x1 5x2 6x3 sa 2x1 x2 x3 2 x1 2x2 3x3 8 com x1 x2 x3 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 1𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 0𝑦1 𝑦2 0 𝑦1 𝑦2 livres Solução 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 sa 2𝑥1 𝑥2 𝑥3 2 𝑥1 2𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 0𝐹1 0𝐹2 sa 2𝑥1 𝑥2 𝑥3 𝐹1 0𝐹2 2 𝑥1 2𝑥2 3𝑥3 0𝐹1 𝐹2 8 𝑥1 𝑥2 𝑥3 𝐹1 𝐹2 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 1𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 0𝑦1 𝑦2 0 𝑦1 𝑦2 livres 𝑦1 0 𝑦2 0 𝑦1 𝑦2 livres 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 𝑦2 0 Exemplo 7 Escreva o Dual do problema abaixo Solução Veja que x1 é uma variável livre no PRIMAL então teremos um sinal de na 1ª restrição no DUAL F F F F F F F F F F Multiplicando por 1 a equação y1 y2 4y3 5 temos y1 y2 4y3 5 A mesma equação y1 y2 4y3 é e por isso usamos apenas o sinal nela Exemplo 9 Escreva o Dual do problema abaixo min 𝑍 2𝑥1 8𝑥2 sa 2𝑥1 𝑥2 7 𝑥1 2𝑥2 5 𝑥1 3𝑥2 6 𝑥1 0 𝑥2 livre Min Z 15x1 12x2 sa x1 2x2 3 2x1 4x2 5 com x1 x2 0 Max Z x1 2x2 4 sa 3x1 2x2 10 2x1 4x2 8 com x1 x2 0 Min Z 2x1 8x2 sa 2x1 x2 7 x1 2x2 5 x1 3x2 6 com x1 0 x2 livre
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Pesquisa Operacional Método Simplex Dualidade Dualidade Todo problema de programação linear está associado a outro problema chamado dual O problema original é chamado primal Apesar de possuírem características distintas ambos os problemas levam à mesma solução ótima Se o modelo original tiver m restrições e n variáveis então seu modelo dual terá n restrições e m variáveis O modelo original Primal pode ser substituído pelo modelo Dual cuja solução pode ser mais rápida Dualidade Reparem nesses dois problemas Maximizar Z 3x1 2x2 Sujeito a 05x1 03x2 3 01x1 02x2 1 04x1 05x2 3 x1 x2 0 Solução ótima x1 462 x2 23 Z 1846 Minimizar W 3y1 1y2 3y3 Sujeito a 05y1 01y2 04y3 3 03y1 02y2 05y3 2 y1 y2 y3 0 Solução ótima y1 537 y2 0 y3 0778 W 1846 Dualidade PROBLEMA PRIMAL forma padrão modelo original maximizar 𝑍 𝒄𝟏𝑥1 𝒄𝟐𝑥2 𝒄𝒏𝑥𝑛 sa 𝒂𝟏𝟏𝑥1 𝑎12𝑥2 𝑎1𝑛𝑥𝑛 𝒃𝟏 𝒂𝟐𝟏𝑥1 𝑎22𝑥2 𝑎2𝑛𝑥𝑛 𝒃𝟐 𝒂𝒎𝟏𝑥1 𝑎𝑚2𝑥2 𝑎𝑚𝑛𝑥𝑛 𝒃𝒎 com 𝑥1 𝑥2 𝑥𝑛 0 PROBLEMA DUAL modelo dual minimizar W 𝒃𝟏𝑦1 𝒃𝟐𝑦2 𝒃𝒎𝑦𝑚 sa 𝒂𝟏𝟏𝑦1 𝒂𝟐𝟏𝑦2 𝒂𝒎𝟏𝑦𝑚 𝒄𝟏 𝑎12𝑦1 𝑎22𝑦2 𝑎𝑚2𝑦𝑚 𝒄𝟐 𝑎1𝑛𝑦1 𝑎2𝑛𝑦2 𝑎𝑚𝑛𝑦𝑚 𝒄𝒏 com 𝑦1 𝑦2 𝑦𝑚 0 Dualidade Em geral em problemas de dualidade temos Se um é problema de maximizar o outro é de minimizar Os coeficientes ci da função objetivo de um passam a ser os recursos bi do outro Os recursos técnicos bi de um passam a ser os coeficientes ci da função objetivo do outro Dos últimos dois acima percebese que As variáveis de um estão relacionadas com as restrições do outro As restrições de um estão relacionadas com as variáveis do outro Dualidade Uma das vantagens do uso da dualidade é que podemos resolver um problema PRIMAL com mais de duas variáveis usando o método gráfico no modelo DUAL PRIMAL n 3 variáveis xs m 2 restrições DUAL m 2 variáveis ys n 3 restrições Exemplo 1 Encontre o dual do problema abaixo Exemplo 2 a Escreva o Dual do PPL abaixo b Resolva os dois problemas Primal e o Dual pelo Solver do Excel c Compare a solução ótima de ambos os modelos Exemplo 3 a Escreva o Dual do PPL abaixo b Resolva os dois problemas Primal e o Dual pelo Solver do Excel c Compare a solução ótima de ambos os modelos Propriedades da relação entre Primal e Dual Se o Primal tem uma solução ótima o DUAL também terá a mesma solução ótima Se o Primal é ilimitado o DUAL será infactível sem solução Se o Primal é infactível o DUAL será infactível ou ilimitado O Dual do Dual é o Primal Primal vs Dual Em problema de PPL podese optar entre resolver o problema Primal ou o Dual A escolha deve levar em consideração o esforço computacional que por sua vez depende do número de restrições variáveis de controle de folga e artificiais Geralmente optase pelo problema Primal ou Dual que tiver menor número de restrições Primal na forma nãocanônica Até o momento trabalhamos com problemas Primal em sua forma canônica Maximizar 𝑍 𝑐1𝑥1 𝑐2𝑥2 𝑐𝑛𝑥𝑛 sa 𝑎11𝑥1 𝑎12𝑥2 𝑎1𝑛𝑥𝑛 𝑏1 𝑎21𝑥1 𝑎22𝑥2 𝑎2𝑛𝑥𝑛 𝑏2 𝑎𝑚1𝑥1 𝑎𝑚2𝑥2 𝑎𝑚𝑛𝑥𝑛 𝑏𝑚 com 𝑥1 𝑥2 𝑥𝑛 0 Maximizar 𝑍 3𝑥1 5𝑥2 sa 3𝑥1 2𝑥2 18 𝑥1 4 2𝑥2 12 com 𝑥1 𝑥2 0 Maximizar 𝑍 𝑐𝑋 sa AX 𝑏 com 𝑋 0 Para outras formas do Primal é necessário algumas adaptações Tabela de conversão PrimalDual Modelo PRIMAL Modelo DUAL Minimizar Maximizar Maximizar Minimizar xi 0 restrição i será restrição i será xi 0 restrição i será restrição i será xi é livre restrição i será restrição i será Restrição i é yi 0 yi 0 Restrição i é yi 0 yi 0 Restrição i é yi é livre yi é livre Exemplo 4 Determine o dual de cada problema abaixo minimizar Z 15x1 12x2 sujeito a x1 2x2 3 2x1 4x2 5 com x1 x2 0 Solução maximizar 2y1 5y2 sa y1 2y2 15 2y1 4y2 12 Com y1 0 y2 0 Regra geral de conversão PrimalDual 1 Você pode usar a tabela de conversão PrimalDual acima ou 2 usar um regra mais geral que é a seguinte i Coloque as variáveis de folgaexcesso no primal ii Ao escrever o problema DUAL use sinal do tipo em todas nas restrições se o DUAL for problema de maximização e use sinal do tipo em todas nas restrições se o DUAL for problema de minimização ii deixe todas as variáveis duais livres Exemplo 5 Escreva o Dual do problema abaixo usando a regra geral 𝑀𝐴𝑋 𝑍 5𝑥1 12𝑥2 4𝑥3 sa 𝑥1 2𝑥2 𝑥3 10 2𝑥1 𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 Solução PRIMAL 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 sa 2𝑥1 𝑥2 𝑥3 2 𝑥1 2𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 0𝐹1 sa 2𝑥1 𝑥2 𝑥3 𝐹1 2 𝑥1 2𝑥2 3𝑥3 0𝐹1 8 𝑥1 𝑥2 𝑥3 𝐹1 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 𝑦1 𝑦2 livres 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0 𝑦1 𝑦2 livres 𝑦1 0 𝑦2 livre DUAL 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 0 𝑦2 livre 2 Troque max para min As 2 restrições no primal se tornam 2 variáveis y1 y2 no dual As 4 variáveis x1x2x3 F1 no dual se tornam 4 restrições no dual Como no dual temos problema de minimização use sinais Deixe as variáveis duais y1 e y2 livres 1 Acrescentar as variáveis de folgas 1 2 Exemplo 6 Escreva o Dual do problema abaixo usando a regra geral Max Z 7x1 5x2 6x3 sa 2x1 x2 x3 2 x1 2x2 3x3 8 com x1 x2 x3 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 1𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 0𝑦1 𝑦2 0 𝑦1 𝑦2 livres Solução 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 sa 2𝑥1 𝑥2 𝑥3 2 𝑥1 2𝑥2 3𝑥3 8 𝑥1 𝑥2 𝑥3 0 𝑀𝐴𝑋 𝑍 7𝑥1 5𝑥2 6𝑥3 0𝐹1 0𝐹2 sa 2𝑥1 𝑥2 𝑥3 𝐹1 0𝐹2 2 𝑥1 2𝑥2 3𝑥3 0𝐹1 𝐹2 8 𝑥1 𝑥2 𝑥3 𝐹1 𝐹2 0 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 1𝑦1 3𝑦2 6 𝑦1 0𝑦2 0 0𝑦1 𝑦2 0 𝑦1 𝑦2 livres 𝑦1 0 𝑦2 0 𝑦1 𝑦2 livres 𝑀𝐼𝑁 𝑊 2𝑦1 8𝑦2 sa 2𝑦1 𝑦2 7 𝑦1 2𝑦2 5 𝑦1 3𝑦2 6 𝑦1 𝑦2 0 Exemplo 7 Escreva o Dual do problema abaixo Solução Veja que x1 é uma variável livre no PRIMAL então teremos um sinal de na 1ª restrição no DUAL F F F F F F F F F F Multiplicando por 1 a equação y1 y2 4y3 5 temos y1 y2 4y3 5 A mesma equação y1 y2 4y3 é e por isso usamos apenas o sinal nela Exemplo 9 Escreva o Dual do problema abaixo min 𝑍 2𝑥1 8𝑥2 sa 2𝑥1 𝑥2 7 𝑥1 2𝑥2 5 𝑥1 3𝑥2 6 𝑥1 0 𝑥2 livre Min Z 15x1 12x2 sa x1 2x2 3 2x1 4x2 5 com x1 x2 0 Max Z x1 2x2 4 sa 3x1 2x2 10 2x1 4x2 8 com x1 x2 0 Min Z 2x1 8x2 sa 2x1 x2 7 x1 2x2 5 x1 3x2 6 com x1 0 x2 livre