·
Administração ·
Outros
Send your question to AI and receive an answer instantly
Preview text
Pesquisa Operacional Problema Dual Dualidade 1 PO PESQUISA OPERACIONAL EM ADMINISTRAÇÃO Continuação Profa Léa Benatti 27 Problema Dual Dualidade P O pg 83 Puccini pg 132 Modelo original PRIMAL Modelo DUAL Conhecida a solução PRIMAL em consequência é conhecida a solução DUAL e viceversa Sendo o Modelo de Programação Linear PRIMAL Função objetivo de maximização Restrições do tipo Variáveis não negativas Ao modelo primal acima descrito podese associar o modelo dual construído da seguinte maneira a VARIÁVEL DE DECISÃO DO DUAL cada restrição do primal corresponde uma variável Yi do dual b OBJETIVO a função objetivo será de minimização Cada uma de suas parcelas será o produto da variável Yi pelo termo da direita da restrição correspondente c RESTRIÇÕES cada variável de decisão primal gera uma restrição no dual TERMO DA ESQUERDA cada termo é o produto da variável dual Yi pelo coeficiente respectivo da variável de decisão primal SINAL sinal do tipo TERMO DA DIREITA é o coeficiente da variável primal na função objetivo d As variáveis Yi são todas não negativas Yi 0 2 Exemplo 1 P O pg 84 PRIMAL Maximizar Z 2X1 3X2 1X3 Sujeito a 3X1 4X2 2X3 10 Y1 2X1 6X2 X3 20 Y2 X1 X2 X3 30 Y3 X1 X2 X3 0 DUAL Minimizar D 10Y1 20Y2 30Y3 termos da direita das restrições do primal Sujeito a 3Y1 2Y2 Y3 2 coeficiente de X1 da F Obj Primal 4Y1 6Y2 Y3 3 coeficiente de X2 da F Obj Primal 2Y1 Y2 Y3 1 coeficiente de X3 da F Obj Primal Y1 Y2 Y3 0 Sendo o Modelo de Programação Linear PRIMAL Função objetivo de minimização Restrições do tipo Variáveis não negativas Primal dual do Exemplo 1 dado anteriormente O modelo Dual terá então Função objetivo de maximização Restrições do tipo Variáveis não negativas Exemplo 2 O dual do Exemplo 1 será agora o Primal P O pg 84 PRIMAL Minimizar Z 10X1 20X2 30X3 Sujeito a 3X1 2X2 X3 2 Y1 4X1 6X2 X3 3 Y2 2X1 X2 X3 1 Y3 X1 X2 X3 0 DUAL Maximizar D 2Y1 3Y2 Y3 termos da direita das restrições Sujeito a 3Y1 4Y2 2Y3 10 coef X1 da F Obj Primal 2Y1 6Y2 Y3 20 coef X2 da F Obj Primal Y1 Y2 Y3 30 coef X3 da F Obj Primal Y1 Y2 Y3 0 Primal do Exemplo 1 Variáveis Primal Xi Variáveis Dual Yi Variáveis Primal Xi Variáveis Dual Yi 3 Logo o dual obtido a partir de um dual retorna ao modelo primal A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal PROPRIEDADES P O Pg 85 a Se uma restrição primal é do tipo a variável dual correspondente será sem restrição de sinal variável livre variável qualquer b Se uma variável primal for sem restrição de sinal variável livre var qualquer a restrição do dual correspondente será do tipo Propriedades Exemplo 3 P O pg 85 PRIMAL DUAL PRIMAL Maximizar Z 2X1 3X2 X3 sinal var livre Sujeito a X1 X2 10 Y1 var Livre sinal 2X1 4X2 X3 20 Y2 X1 X2 X3 0 DUAL Minimizar D 10Y1 20Y2 Max Min Sujeito a Y1 2Y2 2 Y1 4Y2 3 Y2 1 Y1 0 Y2 livre PREPARAÇÃO DO PRIMAL PRIMAL F Obj Maximizar Z F Obj Minimizar Z Restrições tipo Restrições tipo Variável 0 Xi Variável 0 Xi DUAL F Obj Minimizar D F Obj Maximizar D Restrições tipo Restrições tipo Variável 0 Yi Variável 0 Yi 4 Dependendo da situação em que se encontra o modelo primal devese trabalhá lo antes da busca do seu correspondente dual Caso haja necessidade de preparar o primal F Objetivo MAX x 1 MIN Restrições x 1 Permanece inalterado EXEMPLOS DE FORMULAÇÃO DO DUAL Puccini Pg 136 1 Seja o problema Primal abaixo Puccini Pg 136 PRIMAL Maximizar Z 5X1 2X2 Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 Ou melhor Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 O seu dual será DUAL Minimizar D 3Y1 4Y2 9Y3 termos da direita das restrições do primal Sujeito a Y1 Y3 5 coef X1 da F Obj Primal Y2 2Y3 2 coef X2 da F Obj Primal Y1 Y2 Y3 0 Primal Max restrições tipos Primal Min restrições tipos Variáveis Primal Xi Variáveis Dual Yi Espaços vazios podem ser substituídos por coeficiente zero multiplicando a variável primal Xi Assim neste caso X1 0X2 3 Y1 0X1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 Propriedades Na busca do dual a Variável qualquer no primal Restrição tipo no dual Var livre sem restrição de sinal b Restrição tipo no primal Var qualquer no dual ou livre ou sem restrição de sinal 5 Ou Sujeito a Y1 0 Y3 5 0 Y2 2Y3 2 Y1 Y2 Y3 0 Onde matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal 2 Seja o seguinte problema Primal Puccini Pg 137 Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 Y1 X4 X5 X6 15 Y2 3X1 2X2 X4 3X5 20 Y3 X2 X3 2X4 X6 30 Y4 X1 X2 X3 0 X4 X5 X6 quaisquer Temse o dual Minimizar D 10Y1 15Y2 20Y3 30Y4 Sujeito a Y1 3Y3 3 Y1 2Y3 Y4 2 Y1 Y4 1 Y2 Y3 2Y4 1 Y2 3Y3 5 Y2 Y4 4 Y1 Y2 quaisquer ou livres ou sem restrição de sinais Y3 Y4 0 3 Seja o seguinte problema Primal Puccini Pg 138 Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 X4 X5 X6 15 3X1 2X2 X4 3X5 20 X2 X3 2X4 X6 30 X1 X4 2X6 25 x 1 X2 X3 2X5 18 x 1 X1 X2 X3 0 X4 X5 X6 quaisquer Variável livre Restrição tipo Restrição tipo Variável livre I 6 Preparar o Primal Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 Y1 X4 X5 X6 15 Y2 3X1 2X2 X4 3X5 20 Y3 X2 X3 2X4 X6 30 Y4 X1 X4 2X6 25 Y5 X2 X3 2X5 18 Y6 X1 X2 X3 0 X4 X5 X6 quaisquer Temse o seguinte dual Minimizar D 10Y1 15Y2 20Y3 30Y4 25Y5 18Y6 Sujeito a Y1 3Y3 Y5 3 Y1 2Y3 Y4 Y6 2 Y1 Y4 Y6 1 Y2 Y3 2Y4 Y5 1 Y2 3Y3 2Y6 5 Y2 Y4 2Y5 4 Y1 Y2 quaisquer ou livres ou sem restrição de sinais Y3 Y4 Y5 Y6 0 Matriz de coeficientes Dual Matriz de coeficientes PrimalT II IT A menos das linhas I correspondentes às restrições do tipo duas últimas restrições Para estas duas linhas a transposta se faz com sinal trocado devido à multiplicação por 1 das restrições do primal 4 Seja o Primal Puccini Pg 140 Minimizar Z X1 5X2 2X3 Sujeito a X1 4 Max X2 X3 9 Min 3X1 2X2 4X3 8 X1 qualquer X2 X3 0 Preparar o Primal há duas maneiras II 7 a Transformar Função objetivo em Maximizar e transformar restrições do tipo para PRIMAL Maximizar Z X1 5X2 2X3 Sujeito a X1 4 Y1 X2 X3 9 Y2 3X1 2X2 4X3 8 Y3 X1 qualquer X2 X3 0 Temse o dual Minimizar D 4Y1 9Y2 8Y3 x 1 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 Que é equivalente a Maximizar D 4Y1 9Y2 8Y3 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 b Manter função objetivo como Minimizar e transformar restrições do tipo para PRIMAL Minimizar Z X1 5X2 2X3 Sujeito a X1 4 Y1 X2 X3 9 Y2 3X1 2X2 4X3 8 Y3 X1 qualquer X2 X3 0 Temse o dual Maximizar D 4Y1 9Y2 8Y3 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 Resultado I coincide com o II ok Termos da direita negativos X 1 I Restrições tornamse Logo usar Fç objetivo de Max II 8 5 Determinar o modelo Dual do seguinte problema Primal Maximizar Z 13X1 12X2 7X4 5X5 14X6 Sujeito a X1 X2 X6 10 X4 X5 4X6 15 3X1 5X2 X4 3X5 0 X2 X3 2X4 X6 30 X1 X4 2X6 25 X2 X3 2X5 18 x 1 X1 X2 X3 X5 0 X4 X6 quaisquer Preparar o Primal Maximizar Z 13X1 12X2 0X3 7X4 5X5 14X6 Sujeito a X1 X2 X6 10 Y1 X4 X5 4X6 15 Y2 3X1 5X2 X4 3X5 0 Y3 X2 X3 2X4 X6 30 Y4 X1 X4 2X6 25 Y5 X2 X3 2X5 18 Y6 X1 X2 X3 X5 0 X4 X6 quaisquer Temse o seguinte dual Minimizar D 10Y1 15Y2 0Y3 30Y4 25Y5 18Y6 ou Minimizar D 10Y1 15Y2 30Y4 25Y5 18Y6 Sujeito a Y1 3Y3 Y5 13 Y1 5Y3 Y4 Y6 12 Y4 Y6 0 Y2 Y3 2Y4 Y5 7 x 1 Y2 Y3 2Y4 Y5 7 Y2 3Y3 2Y6 5 Y1 4Y2 Y4 2Y5 14 Y2 Y4 quaisquer ou livres ou sem restrição de sinais Y1 Y3 Y5 Y6 0 Condição não negativa Matriz de coeficientes Dual Matriz de coeficientes PrimalT I II Fç Obj MAX sinais Fç Obj MIN sinais 9 6 Determinar o modelo Dual do seguinte problema Primal Minimizar Z 10X1 15X2 9X3 11X5 Sujeito a X1 2X2 X5 12 X2 X4 2X5 16 5X2 2X4 3X5 10 x 1 4X1 X2 X3 2X4 20 3X1 X4 X5 26 X2 X3 2X5 18 X1 X3 X4 X5 0 X2 qualquer Preparar o Primal Minimizar Z 10X1 15X2 9X3 0X4 11X5 Sujeito a X1 2X2 X5 12 Y1 X2 X4 2X5 16 Y2 5X2 2X4 3X5 10 Y3 4X1 X2 X3 2X4 20 Y4 3X1 X4 X5 26 Y5 X2 X3 2X5 18 Y6 X1 X3 X4 X5 0 X2 qualquer Temse o seguinte dual Maximizar D 12Y1 16Y2 10Y3 20Y4 26Y5 18Y6 Sujeito a Y1 4Y4 3Y5 10 2Y1 Y2 5Y3 Y4 Y6 15 x1 2Y1 Y2 5Y3 Y4 Y6 15 Y4 Y6 9 Y2 2Y3 2Y4 Y5 0 Y1 2Y2 3Y3 Y5 2Y6 11 Y2 Y5 quaisquer ou livres ou sem restrição de sinais Y1 Y3 Y4 Y6 0 Condição não negativa Fç Obj MAX sinais Fç Obj MIN sinais 10 ANALOGIA ENTRE AS SOLUÇÕES PRIMAL E DUAL 1 A cada solução viável básica primal não ótima corresponde uma solução básica inviável dual 2 A solução ótima primal corresponde à solução ótima dual com Z D 3 O coeficiente da variável de decisão na função objetivo primal é o valor da variável de folga correspondente na solução dual com sinal trocado 4 O coeficiente da variável de folga da função objetivo primal é o valor da variável de decisão correspondente na solução dual com sinal trocado 5 Como o primal é dual do próprio dual vale o raciocínio no sentido dual primal Exemplo 1 Dualidade com tabelas de Simplex Puccini Pg 154 Seja o problema primal Maximizar Z 5X1 2X2 Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 condição não negativa O modelo dual é dado por Minimizar D 3Y1 4Y2 9Y3 Sujeito a Y1 Y3 5 Y2 2Y3 2 Y1 Y2 Y3 0 condição não negativa Coef de Xi valor de di linha C Z Coef de Si valor de Yi linha C Z Coef de Yi valor de Si linha b D Coef de di valor de Xi linha b D Duas variáveis de decisão primal X1 X2 duas restrições do dual 11 Acrescentando variável de folga Si primal di dual Primal Maximizar Z 5X1 2X2 0S1 0S2 0S3 Sujeito a X1 S1 3 X2 S2 4 X1 2X2 S3 9 X1 X2 0 condições não negativa S1 S2 S3 0 condições não negativa Dual Minimizar D 3Y1 4Y2 9Y3 0d1 0d2 Maximizar D 3Y1 4Y2 9Y3 0d1 0d2 Sujeito a Y1 Y3 d1 5 Y2 2Y3 d2 2 Y1 Y2 Y3 0 condição não negativa d1 d2 0 condições não negativa 1a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 0 S1 1 0 1 0 0 3 31 3 0 S2 0 1 0 1 0 4 40 ind 0 S3 1 2 0 0 1 9 91 9 Z 0 0 0 0 0 0 CZ 5 2 0 0 0 Solução básica possível Variáveis básicas S1 3 Variáveis não básicas X1 X2 0 S2 4 Z 0 S3 9 Sinais do tipo somar variável de folga Sinais do tipo usar variável de folga Não usar var artificial Método Simplex Sai LP entra 12 1a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 0 d1 1 0 1 1 0 5 0 d2 0 1 2 0 1 2 D 0 0 0 0 0 0 bD 3 4 9 0 0 Solução inviável pois d1 e d2 0 Logo Variáveis básicas d1 5 d2 2 d1 d2 0 inviável Variáveis não básicas Y1 Y2 Y3 0 D 0 Correspondências PRIMAL DUAL Coef de X1 5 Valor de d1 5 Coef de X2 2 Valor de d2 2 Coef de S1 0 Valor de Y1 0 Coef de S2 0 Valor de Y2 0 Coef de S3 0 Valor de Y3 0 Valor de X1 0 Coef de d1 0 Valor de X2 0 Coef de d2 0 Valor de S1 3 Coef de Y1 3 Valor de S2 4 Coef de Y2 4 Valor de S3 9 Coef de Y3 9 Valor de Z 0 Valor de D 0 Variáveis básicas d1 5 d2 2 Variáveis não básicas Y1 Y2 Y3 0 A solução dual não é ótima pois as variáveis d1 e d2 são inviáveis valor 0 Na Fç Obj C Z Solução 13 Obs Resumo Primal Dual Dual Primal E ainda Valor Z Valor D Próxima solução viável básica do primal Var entra X1 maior coef na linha C Z Var sai S1 menor bj aij linha principal Pivô 1 2a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 5 X1 1 0 1 0 0 3 30 ind 0 S2 0 1 0 1 0 4 41 4 0 S3 0 2 1 0 1 6 62 3 Z 5 0 5 0 0 15 CZ 0 2 5 0 0 Solução básica possível Variáveis básicas X1 3 Variáveis não básicas X2 S1 0 S2 4 Z 15 S3 6 Coef de Xi valor de di linha C Z Coef de Si valor de Yi linha C Z Coef de Yi valor de Si linha b D Coef de di valor de Xi linha b D Sai LP entra 14 Correspondências PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 2 Valor de d2 2 Coef de S1 5 Valor de Y1 5 Coef de S2 0 Valor de Y2 0 Coef de S3 0 Valor de Y3 0 Valor de X1 3 Coef de d1 3 Valor de X2 0 Coef de d2 0 Valor de S1 0 Coef de Y1 0 Valor de S2 4 Coef de Y2 4 Valor de S3 6 Coef de Y3 6 Valor de Z 15 Valor de D 15 2a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 3 Y1 1 0 5 0 d2 0 1 2 D 15 bD 0 4 6 3 0 Solução inviável dual Solução básica Variáveis básicas Y1 5 d2 2 0 inviável Variáveis não básicas Y2 Y3 d1 0 D 15 Na Fç Obj C Z Solução Var que entra tem coef na linha b D igual à zero ok 15 3a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 5 X1 1 0 1 0 0 3 0 S2 0 0 12 1 12 1 2 X2 0 1 12 0 ½ 3 Z 5 2 4 0 1 21 CZ 0 0 4 0 1 Linha C Z Coef zero solução ótima Solução básica possível Variáveis básicas X1 3 Variáveis não básicas S1 S3 0 S2 1 Z 21 X2 3 Correspondências PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 0 Valor de d2 0 Coef de S1 4 Valor de Y1 4 Coef de S2 0 Valor de Y2 0 Coef de S3 1 Valor de Y3 1 Valor de X1 3 Coef de d1 3 Valor de X2 3 Coef de d2 3 Valor de S1 0 Coef de Y1 0 Valor de S2 1 Coef de Y2 1 Valor de S3 0 Coef de Y3 0 Valor de Z 21 Valor de D 21 Variáveis básicas Y1 4 Y3 1 Variáveis não básicas d1 d2 Y2 0 A solução dual é ótima pois as variáveis Y1 e Y3 são viáveis valor 0 Na Fç Obj C Z Solução 16 3a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 3 Y1 1 0 4 9 Y3 0 1 1 D 21 bD 0 1 0 3 3 Solução viável dual solução ótima primal Solução básica Variáveis básicas Y1 4 Solução viável Y1 e Y3 0 Y3 1 Variáveis não básicas Y2 d1 d2 0 D 21 Ao se aplicar o método Simplex ao problema primal visando a sua otimização estáse indiretamente procurando a compatibilidade do problema dual Isto é facilmente identificado pois o método simplex procura tornar zero todos os coeficientes das variáveis Xi e Si i 1 2 da linha C Z do quadro das soluções Quando este objetivo for alcançado o primal estará otimizado e o dual compatibilizado Dado um problema de programação linear podese escolher entre solucionar o modelo primal ou o dual correspondente A escolha leva em consideração o esforço computacional que depende do número de restrições variáveis artificiais etc Exemplo 2 Dualidade com tabelas de Simplex PO Pg 86 Seja o problema primal Maximizar Z X1 2X2 3X3 Sujeito a X1 X2 X3 10 Y1 2X1 X2 4X3 12 Y2 X1 3X2 X3 9 Y3 X1 X2 X3 0 condição não negativa Determinar a solução do Dual usando a analogia entre os modelos ok ok Deixar para os alunos resolverem 17 Exemplo 3 Dualidade com tabelas de Simplex P O Medeiros da Silva pg 46 Seja o problema primal Maximizar Z 3X 5Y Sujeito a 2X 4Y 10 6X Y 20 X Y 30 X 0 Y 0 condição de não negatividade Problema Equivalente Forma Genérica do problema Maximizar Z 3X 5Y 0S1 0S2 0S3 Sujeito a 2X 4Y 1S1 0S2 0S3 10 6X Y 0S1 1S2 0S3 20 X Y 0S1 0S2 1S3 30 X Y 0 S1 S2 S3 0 cond não negatividade Depois da resolução de duas tabelas do Simplex temse a 3ª Tabela como indicada abaixo 3a Tabela Variáveis de decisão título da tabela Ci 3 5 0 0 0 L objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij 5 X2 0 1 311 111 0 091 3 X1 1 0 122 211 0 318 0 S3 0 0 722 311 1 2773 Z 3 5 123 009 0 1409 CZ 0 0 123 009 0 Linha CZ valores menores ou iguais a zero Solução Ótima do Primal Logo Variáveis básicas X1 3511 318 Z 15511 1409 X2 1011 091 S3 30511 2773 Variáveis não básicas S1 S2 0 a Obter solução do DUAL com base na tabela acima do Primal b Quais são as variáveis básicas e não básicas do DUAL c É caso de solução ótima do DUAL Por que 18 a Correspondências entre Primal e Dual PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 0 Valor de d2 0 Coef de S1 123 Valor de Y1 123 Coef de S2 009 Valor de Y2 009 Coef de S3 0 Valor de Y3 0 Valor de X1 318 Coef de d1 318 Valor de X2 091 Coef de d2 091 Valor de S1 0 Coef de Y1 0 Valor de S2 0 Coef de Y2 0 Valor de S3 2773 Coef de Y3 2773 Valor de Z 1409 Valor de D 1409 b Quais são as variáveis básicas e não básicas do DUAL Variáveis básicas Y1 123 Y2 009 Variáveis não básicas d1 d2 Y3 0 c É caso de solução ótima do DUAL Por que Sim é caso de solução ótima do dual pois as variáveis básicas do dual Y1 e Y3 são viáveis valores 0 Y1 123 e Y2 009 Bibliografia usada na elaboração do material do curso BIBLIOGRAFIA PRINCIPAL BP Normas ABNT 1 Pesquisa Operacional na Tomada de Decisões Modelagem em Excel Para Cursos de Administração Economia e Ciências Contábeis Gerson Lachtermacher Editora Campus Rio de Janeiro 2002 BIBLIOGRAFIA COMPLEMENTAR BC Normas ABNT 1 Administração da Produção e Operações Daniel Augusto Moreira 3a Edição Livraria Pioneira Editora São Paulo 1998 2 Pesquisa Operacional Ermes Medeiros da Silva Elio Medeiros da Silva Valter Gonçalves Afrânio Carlos Murilo 3a Edição Editora Atlas S A São Paulo 1998 3 Introdução à Programação Linear Abelardo de Lima Puccini Livros Técnicos e Científicos Editora S A Rio de Janeiro 1981 última reimpressão 4 Introdução à Pesquisa Operacional Hillier Lieberman Editora Campus Ltda Editora da Universidade de São Paulo São Paulo 1998 5 Pesquisa Operacional Harvey M Wagner PrenticeHall do Brasil Rio de Janeiro 1986 6 Introdução à Pesquisa Operacional Métodos e Modelos para Análise de Decisões Eduardo Leopoldino de Andrade 3a ed Editora LTC Rio de Janeiro 2002 Na Fç Obj C Z Solução 19 Resumo Dualidade Primal Fç Objetivo de Maximização Restrição com sinais exceto restrições de e das condições não negativas Fç Objetivo de Minimização Restrição com sinais exceto restrições de e das condições não negativas Em caso contrário preparar o Primal Propriedades Primal Dual Variável livre Restrição tipo Restrição tipo Variável livre qualquer sem restrição de sinal Matriz de coeficientes do Dual é a transposta da matriz de coeficientes do primal
Send your question to AI and receive an answer instantly
Preview text
Pesquisa Operacional Problema Dual Dualidade 1 PO PESQUISA OPERACIONAL EM ADMINISTRAÇÃO Continuação Profa Léa Benatti 27 Problema Dual Dualidade P O pg 83 Puccini pg 132 Modelo original PRIMAL Modelo DUAL Conhecida a solução PRIMAL em consequência é conhecida a solução DUAL e viceversa Sendo o Modelo de Programação Linear PRIMAL Função objetivo de maximização Restrições do tipo Variáveis não negativas Ao modelo primal acima descrito podese associar o modelo dual construído da seguinte maneira a VARIÁVEL DE DECISÃO DO DUAL cada restrição do primal corresponde uma variável Yi do dual b OBJETIVO a função objetivo será de minimização Cada uma de suas parcelas será o produto da variável Yi pelo termo da direita da restrição correspondente c RESTRIÇÕES cada variável de decisão primal gera uma restrição no dual TERMO DA ESQUERDA cada termo é o produto da variável dual Yi pelo coeficiente respectivo da variável de decisão primal SINAL sinal do tipo TERMO DA DIREITA é o coeficiente da variável primal na função objetivo d As variáveis Yi são todas não negativas Yi 0 2 Exemplo 1 P O pg 84 PRIMAL Maximizar Z 2X1 3X2 1X3 Sujeito a 3X1 4X2 2X3 10 Y1 2X1 6X2 X3 20 Y2 X1 X2 X3 30 Y3 X1 X2 X3 0 DUAL Minimizar D 10Y1 20Y2 30Y3 termos da direita das restrições do primal Sujeito a 3Y1 2Y2 Y3 2 coeficiente de X1 da F Obj Primal 4Y1 6Y2 Y3 3 coeficiente de X2 da F Obj Primal 2Y1 Y2 Y3 1 coeficiente de X3 da F Obj Primal Y1 Y2 Y3 0 Sendo o Modelo de Programação Linear PRIMAL Função objetivo de minimização Restrições do tipo Variáveis não negativas Primal dual do Exemplo 1 dado anteriormente O modelo Dual terá então Função objetivo de maximização Restrições do tipo Variáveis não negativas Exemplo 2 O dual do Exemplo 1 será agora o Primal P O pg 84 PRIMAL Minimizar Z 10X1 20X2 30X3 Sujeito a 3X1 2X2 X3 2 Y1 4X1 6X2 X3 3 Y2 2X1 X2 X3 1 Y3 X1 X2 X3 0 DUAL Maximizar D 2Y1 3Y2 Y3 termos da direita das restrições Sujeito a 3Y1 4Y2 2Y3 10 coef X1 da F Obj Primal 2Y1 6Y2 Y3 20 coef X2 da F Obj Primal Y1 Y2 Y3 30 coef X3 da F Obj Primal Y1 Y2 Y3 0 Primal do Exemplo 1 Variáveis Primal Xi Variáveis Dual Yi Variáveis Primal Xi Variáveis Dual Yi 3 Logo o dual obtido a partir de um dual retorna ao modelo primal A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal PROPRIEDADES P O Pg 85 a Se uma restrição primal é do tipo a variável dual correspondente será sem restrição de sinal variável livre variável qualquer b Se uma variável primal for sem restrição de sinal variável livre var qualquer a restrição do dual correspondente será do tipo Propriedades Exemplo 3 P O pg 85 PRIMAL DUAL PRIMAL Maximizar Z 2X1 3X2 X3 sinal var livre Sujeito a X1 X2 10 Y1 var Livre sinal 2X1 4X2 X3 20 Y2 X1 X2 X3 0 DUAL Minimizar D 10Y1 20Y2 Max Min Sujeito a Y1 2Y2 2 Y1 4Y2 3 Y2 1 Y1 0 Y2 livre PREPARAÇÃO DO PRIMAL PRIMAL F Obj Maximizar Z F Obj Minimizar Z Restrições tipo Restrições tipo Variável 0 Xi Variável 0 Xi DUAL F Obj Minimizar D F Obj Maximizar D Restrições tipo Restrições tipo Variável 0 Yi Variável 0 Yi 4 Dependendo da situação em que se encontra o modelo primal devese trabalhá lo antes da busca do seu correspondente dual Caso haja necessidade de preparar o primal F Objetivo MAX x 1 MIN Restrições x 1 Permanece inalterado EXEMPLOS DE FORMULAÇÃO DO DUAL Puccini Pg 136 1 Seja o problema Primal abaixo Puccini Pg 136 PRIMAL Maximizar Z 5X1 2X2 Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 Ou melhor Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 O seu dual será DUAL Minimizar D 3Y1 4Y2 9Y3 termos da direita das restrições do primal Sujeito a Y1 Y3 5 coef X1 da F Obj Primal Y2 2Y3 2 coef X2 da F Obj Primal Y1 Y2 Y3 0 Primal Max restrições tipos Primal Min restrições tipos Variáveis Primal Xi Variáveis Dual Yi Espaços vazios podem ser substituídos por coeficiente zero multiplicando a variável primal Xi Assim neste caso X1 0X2 3 Y1 0X1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 Propriedades Na busca do dual a Variável qualquer no primal Restrição tipo no dual Var livre sem restrição de sinal b Restrição tipo no primal Var qualquer no dual ou livre ou sem restrição de sinal 5 Ou Sujeito a Y1 0 Y3 5 0 Y2 2Y3 2 Y1 Y2 Y3 0 Onde matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal 2 Seja o seguinte problema Primal Puccini Pg 137 Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 Y1 X4 X5 X6 15 Y2 3X1 2X2 X4 3X5 20 Y3 X2 X3 2X4 X6 30 Y4 X1 X2 X3 0 X4 X5 X6 quaisquer Temse o dual Minimizar D 10Y1 15Y2 20Y3 30Y4 Sujeito a Y1 3Y3 3 Y1 2Y3 Y4 2 Y1 Y4 1 Y2 Y3 2Y4 1 Y2 3Y3 5 Y2 Y4 4 Y1 Y2 quaisquer ou livres ou sem restrição de sinais Y3 Y4 0 3 Seja o seguinte problema Primal Puccini Pg 138 Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 X4 X5 X6 15 3X1 2X2 X4 3X5 20 X2 X3 2X4 X6 30 X1 X4 2X6 25 x 1 X2 X3 2X5 18 x 1 X1 X2 X3 0 X4 X5 X6 quaisquer Variável livre Restrição tipo Restrição tipo Variável livre I 6 Preparar o Primal Maximizar Z 3X1 2X2 X3 X4 5X5 4X6 Sujeito a X1 X2 X3 10 Y1 X4 X5 X6 15 Y2 3X1 2X2 X4 3X5 20 Y3 X2 X3 2X4 X6 30 Y4 X1 X4 2X6 25 Y5 X2 X3 2X5 18 Y6 X1 X2 X3 0 X4 X5 X6 quaisquer Temse o seguinte dual Minimizar D 10Y1 15Y2 20Y3 30Y4 25Y5 18Y6 Sujeito a Y1 3Y3 Y5 3 Y1 2Y3 Y4 Y6 2 Y1 Y4 Y6 1 Y2 Y3 2Y4 Y5 1 Y2 3Y3 2Y6 5 Y2 Y4 2Y5 4 Y1 Y2 quaisquer ou livres ou sem restrição de sinais Y3 Y4 Y5 Y6 0 Matriz de coeficientes Dual Matriz de coeficientes PrimalT II IT A menos das linhas I correspondentes às restrições do tipo duas últimas restrições Para estas duas linhas a transposta se faz com sinal trocado devido à multiplicação por 1 das restrições do primal 4 Seja o Primal Puccini Pg 140 Minimizar Z X1 5X2 2X3 Sujeito a X1 4 Max X2 X3 9 Min 3X1 2X2 4X3 8 X1 qualquer X2 X3 0 Preparar o Primal há duas maneiras II 7 a Transformar Função objetivo em Maximizar e transformar restrições do tipo para PRIMAL Maximizar Z X1 5X2 2X3 Sujeito a X1 4 Y1 X2 X3 9 Y2 3X1 2X2 4X3 8 Y3 X1 qualquer X2 X3 0 Temse o dual Minimizar D 4Y1 9Y2 8Y3 x 1 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 Que é equivalente a Maximizar D 4Y1 9Y2 8Y3 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 b Manter função objetivo como Minimizar e transformar restrições do tipo para PRIMAL Minimizar Z X1 5X2 2X3 Sujeito a X1 4 Y1 X2 X3 9 Y2 3X1 2X2 4X3 8 Y3 X1 qualquer X2 X3 0 Temse o dual Maximizar D 4Y1 9Y2 8Y3 Sujeito a Y1 3Y3 1 Y2 2Y3 5 Y2 4Y3 2 Y1 Y2 Y3 0 Resultado I coincide com o II ok Termos da direita negativos X 1 I Restrições tornamse Logo usar Fç objetivo de Max II 8 5 Determinar o modelo Dual do seguinte problema Primal Maximizar Z 13X1 12X2 7X4 5X5 14X6 Sujeito a X1 X2 X6 10 X4 X5 4X6 15 3X1 5X2 X4 3X5 0 X2 X3 2X4 X6 30 X1 X4 2X6 25 X2 X3 2X5 18 x 1 X1 X2 X3 X5 0 X4 X6 quaisquer Preparar o Primal Maximizar Z 13X1 12X2 0X3 7X4 5X5 14X6 Sujeito a X1 X2 X6 10 Y1 X4 X5 4X6 15 Y2 3X1 5X2 X4 3X5 0 Y3 X2 X3 2X4 X6 30 Y4 X1 X4 2X6 25 Y5 X2 X3 2X5 18 Y6 X1 X2 X3 X5 0 X4 X6 quaisquer Temse o seguinte dual Minimizar D 10Y1 15Y2 0Y3 30Y4 25Y5 18Y6 ou Minimizar D 10Y1 15Y2 30Y4 25Y5 18Y6 Sujeito a Y1 3Y3 Y5 13 Y1 5Y3 Y4 Y6 12 Y4 Y6 0 Y2 Y3 2Y4 Y5 7 x 1 Y2 Y3 2Y4 Y5 7 Y2 3Y3 2Y6 5 Y1 4Y2 Y4 2Y5 14 Y2 Y4 quaisquer ou livres ou sem restrição de sinais Y1 Y3 Y5 Y6 0 Condição não negativa Matriz de coeficientes Dual Matriz de coeficientes PrimalT I II Fç Obj MAX sinais Fç Obj MIN sinais 9 6 Determinar o modelo Dual do seguinte problema Primal Minimizar Z 10X1 15X2 9X3 11X5 Sujeito a X1 2X2 X5 12 X2 X4 2X5 16 5X2 2X4 3X5 10 x 1 4X1 X2 X3 2X4 20 3X1 X4 X5 26 X2 X3 2X5 18 X1 X3 X4 X5 0 X2 qualquer Preparar o Primal Minimizar Z 10X1 15X2 9X3 0X4 11X5 Sujeito a X1 2X2 X5 12 Y1 X2 X4 2X5 16 Y2 5X2 2X4 3X5 10 Y3 4X1 X2 X3 2X4 20 Y4 3X1 X4 X5 26 Y5 X2 X3 2X5 18 Y6 X1 X3 X4 X5 0 X2 qualquer Temse o seguinte dual Maximizar D 12Y1 16Y2 10Y3 20Y4 26Y5 18Y6 Sujeito a Y1 4Y4 3Y5 10 2Y1 Y2 5Y3 Y4 Y6 15 x1 2Y1 Y2 5Y3 Y4 Y6 15 Y4 Y6 9 Y2 2Y3 2Y4 Y5 0 Y1 2Y2 3Y3 Y5 2Y6 11 Y2 Y5 quaisquer ou livres ou sem restrição de sinais Y1 Y3 Y4 Y6 0 Condição não negativa Fç Obj MAX sinais Fç Obj MIN sinais 10 ANALOGIA ENTRE AS SOLUÇÕES PRIMAL E DUAL 1 A cada solução viável básica primal não ótima corresponde uma solução básica inviável dual 2 A solução ótima primal corresponde à solução ótima dual com Z D 3 O coeficiente da variável de decisão na função objetivo primal é o valor da variável de folga correspondente na solução dual com sinal trocado 4 O coeficiente da variável de folga da função objetivo primal é o valor da variável de decisão correspondente na solução dual com sinal trocado 5 Como o primal é dual do próprio dual vale o raciocínio no sentido dual primal Exemplo 1 Dualidade com tabelas de Simplex Puccini Pg 154 Seja o problema primal Maximizar Z 5X1 2X2 Sujeito a X1 3 Y1 X2 4 Y2 X1 2X2 9 Y3 X1 X2 0 condição não negativa O modelo dual é dado por Minimizar D 3Y1 4Y2 9Y3 Sujeito a Y1 Y3 5 Y2 2Y3 2 Y1 Y2 Y3 0 condição não negativa Coef de Xi valor de di linha C Z Coef de Si valor de Yi linha C Z Coef de Yi valor de Si linha b D Coef de di valor de Xi linha b D Duas variáveis de decisão primal X1 X2 duas restrições do dual 11 Acrescentando variável de folga Si primal di dual Primal Maximizar Z 5X1 2X2 0S1 0S2 0S3 Sujeito a X1 S1 3 X2 S2 4 X1 2X2 S3 9 X1 X2 0 condições não negativa S1 S2 S3 0 condições não negativa Dual Minimizar D 3Y1 4Y2 9Y3 0d1 0d2 Maximizar D 3Y1 4Y2 9Y3 0d1 0d2 Sujeito a Y1 Y3 d1 5 Y2 2Y3 d2 2 Y1 Y2 Y3 0 condição não negativa d1 d2 0 condições não negativa 1a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 0 S1 1 0 1 0 0 3 31 3 0 S2 0 1 0 1 0 4 40 ind 0 S3 1 2 0 0 1 9 91 9 Z 0 0 0 0 0 0 CZ 5 2 0 0 0 Solução básica possível Variáveis básicas S1 3 Variáveis não básicas X1 X2 0 S2 4 Z 0 S3 9 Sinais do tipo somar variável de folga Sinais do tipo usar variável de folga Não usar var artificial Método Simplex Sai LP entra 12 1a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 0 d1 1 0 1 1 0 5 0 d2 0 1 2 0 1 2 D 0 0 0 0 0 0 bD 3 4 9 0 0 Solução inviável pois d1 e d2 0 Logo Variáveis básicas d1 5 d2 2 d1 d2 0 inviável Variáveis não básicas Y1 Y2 Y3 0 D 0 Correspondências PRIMAL DUAL Coef de X1 5 Valor de d1 5 Coef de X2 2 Valor de d2 2 Coef de S1 0 Valor de Y1 0 Coef de S2 0 Valor de Y2 0 Coef de S3 0 Valor de Y3 0 Valor de X1 0 Coef de d1 0 Valor de X2 0 Coef de d2 0 Valor de S1 3 Coef de Y1 3 Valor de S2 4 Coef de Y2 4 Valor de S3 9 Coef de Y3 9 Valor de Z 0 Valor de D 0 Variáveis básicas d1 5 d2 2 Variáveis não básicas Y1 Y2 Y3 0 A solução dual não é ótima pois as variáveis d1 e d2 são inviáveis valor 0 Na Fç Obj C Z Solução 13 Obs Resumo Primal Dual Dual Primal E ainda Valor Z Valor D Próxima solução viável básica do primal Var entra X1 maior coef na linha C Z Var sai S1 menor bj aij linha principal Pivô 1 2a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 5 X1 1 0 1 0 0 3 30 ind 0 S2 0 1 0 1 0 4 41 4 0 S3 0 2 1 0 1 6 62 3 Z 5 0 5 0 0 15 CZ 0 2 5 0 0 Solução básica possível Variáveis básicas X1 3 Variáveis não básicas X2 S1 0 S2 4 Z 15 S3 6 Coef de Xi valor de di linha C Z Coef de Si valor de Yi linha C Z Coef de Yi valor de Si linha b D Coef de di valor de Xi linha b D Sai LP entra 14 Correspondências PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 2 Valor de d2 2 Coef de S1 5 Valor de Y1 5 Coef de S2 0 Valor de Y2 0 Coef de S3 0 Valor de Y3 0 Valor de X1 3 Coef de d1 3 Valor de X2 0 Coef de d2 0 Valor de S1 0 Coef de Y1 0 Valor de S2 4 Coef de Y2 4 Valor de S3 6 Coef de Y3 6 Valor de Z 15 Valor de D 15 2a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 3 Y1 1 0 5 0 d2 0 1 2 D 15 bD 0 4 6 3 0 Solução inviável dual Solução básica Variáveis básicas Y1 5 d2 2 0 inviável Variáveis não básicas Y2 Y3 d1 0 D 15 Na Fç Obj C Z Solução Var que entra tem coef na linha b D igual à zero ok 15 3a Tabela Primal Variáveis de decisão título da tabela Ci 5 2 0 0 0 Linha objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij bjaij 5 X1 1 0 1 0 0 3 0 S2 0 0 12 1 12 1 2 X2 0 1 12 0 ½ 3 Z 5 2 4 0 1 21 CZ 0 0 4 0 1 Linha C Z Coef zero solução ótima Solução básica possível Variáveis básicas X1 3 Variáveis não básicas S1 S3 0 S2 1 Z 21 X2 3 Correspondências PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 0 Valor de d2 0 Coef de S1 4 Valor de Y1 4 Coef de S2 0 Valor de Y2 0 Coef de S3 1 Valor de Y3 1 Valor de X1 3 Coef de d1 3 Valor de X2 3 Coef de d2 3 Valor de S1 0 Coef de Y1 0 Valor de S2 1 Coef de Y2 1 Valor de S3 0 Coef de Y3 0 Valor de Z 21 Valor de D 21 Variáveis básicas Y1 4 Y3 1 Variáveis não básicas d1 d2 Y2 0 A solução dual é ótima pois as variáveis Y1 e Y3 são viáveis valor 0 Na Fç Obj C Z Solução 16 3a Tabela Dual Variáveis de decisão título da tabela 3 4 9 0 0 Linha objetivo bi V na Solução Y1 Y2 Y3 d1 d2 cj cjaij 3 Y1 1 0 4 9 Y3 0 1 1 D 21 bD 0 1 0 3 3 Solução viável dual solução ótima primal Solução básica Variáveis básicas Y1 4 Solução viável Y1 e Y3 0 Y3 1 Variáveis não básicas Y2 d1 d2 0 D 21 Ao se aplicar o método Simplex ao problema primal visando a sua otimização estáse indiretamente procurando a compatibilidade do problema dual Isto é facilmente identificado pois o método simplex procura tornar zero todos os coeficientes das variáveis Xi e Si i 1 2 da linha C Z do quadro das soluções Quando este objetivo for alcançado o primal estará otimizado e o dual compatibilizado Dado um problema de programação linear podese escolher entre solucionar o modelo primal ou o dual correspondente A escolha leva em consideração o esforço computacional que depende do número de restrições variáveis artificiais etc Exemplo 2 Dualidade com tabelas de Simplex PO Pg 86 Seja o problema primal Maximizar Z X1 2X2 3X3 Sujeito a X1 X2 X3 10 Y1 2X1 X2 4X3 12 Y2 X1 3X2 X3 9 Y3 X1 X2 X3 0 condição não negativa Determinar a solução do Dual usando a analogia entre os modelos ok ok Deixar para os alunos resolverem 17 Exemplo 3 Dualidade com tabelas de Simplex P O Medeiros da Silva pg 46 Seja o problema primal Maximizar Z 3X 5Y Sujeito a 2X 4Y 10 6X Y 20 X Y 30 X 0 Y 0 condição de não negatividade Problema Equivalente Forma Genérica do problema Maximizar Z 3X 5Y 0S1 0S2 0S3 Sujeito a 2X 4Y 1S1 0S2 0S3 10 6X Y 0S1 1S2 0S3 20 X Y 0S1 0S2 1S3 30 X Y 0 S1 S2 S3 0 cond não negatividade Depois da resolução de duas tabelas do Simplex temse a 3ª Tabela como indicada abaixo 3a Tabela Variáveis de decisão título da tabela Ci 3 5 0 0 0 L objetivo Ci V na Solução X1 X2 S1 S2 S3 bj bjaij 5 X2 0 1 311 111 0 091 3 X1 1 0 122 211 0 318 0 S3 0 0 722 311 1 2773 Z 3 5 123 009 0 1409 CZ 0 0 123 009 0 Linha CZ valores menores ou iguais a zero Solução Ótima do Primal Logo Variáveis básicas X1 3511 318 Z 15511 1409 X2 1011 091 S3 30511 2773 Variáveis não básicas S1 S2 0 a Obter solução do DUAL com base na tabela acima do Primal b Quais são as variáveis básicas e não básicas do DUAL c É caso de solução ótima do DUAL Por que 18 a Correspondências entre Primal e Dual PRIMAL DUAL Coef de X1 0 Valor de d1 0 Coef de X2 0 Valor de d2 0 Coef de S1 123 Valor de Y1 123 Coef de S2 009 Valor de Y2 009 Coef de S3 0 Valor de Y3 0 Valor de X1 318 Coef de d1 318 Valor de X2 091 Coef de d2 091 Valor de S1 0 Coef de Y1 0 Valor de S2 0 Coef de Y2 0 Valor de S3 2773 Coef de Y3 2773 Valor de Z 1409 Valor de D 1409 b Quais são as variáveis básicas e não básicas do DUAL Variáveis básicas Y1 123 Y2 009 Variáveis não básicas d1 d2 Y3 0 c É caso de solução ótima do DUAL Por que Sim é caso de solução ótima do dual pois as variáveis básicas do dual Y1 e Y3 são viáveis valores 0 Y1 123 e Y2 009 Bibliografia usada na elaboração do material do curso BIBLIOGRAFIA PRINCIPAL BP Normas ABNT 1 Pesquisa Operacional na Tomada de Decisões Modelagem em Excel Para Cursos de Administração Economia e Ciências Contábeis Gerson Lachtermacher Editora Campus Rio de Janeiro 2002 BIBLIOGRAFIA COMPLEMENTAR BC Normas ABNT 1 Administração da Produção e Operações Daniel Augusto Moreira 3a Edição Livraria Pioneira Editora São Paulo 1998 2 Pesquisa Operacional Ermes Medeiros da Silva Elio Medeiros da Silva Valter Gonçalves Afrânio Carlos Murilo 3a Edição Editora Atlas S A São Paulo 1998 3 Introdução à Programação Linear Abelardo de Lima Puccini Livros Técnicos e Científicos Editora S A Rio de Janeiro 1981 última reimpressão 4 Introdução à Pesquisa Operacional Hillier Lieberman Editora Campus Ltda Editora da Universidade de São Paulo São Paulo 1998 5 Pesquisa Operacional Harvey M Wagner PrenticeHall do Brasil Rio de Janeiro 1986 6 Introdução à Pesquisa Operacional Métodos e Modelos para Análise de Decisões Eduardo Leopoldino de Andrade 3a ed Editora LTC Rio de Janeiro 2002 Na Fç Obj C Z Solução 19 Resumo Dualidade Primal Fç Objetivo de Maximização Restrição com sinais exceto restrições de e das condições não negativas Fç Objetivo de Minimização Restrição com sinais exceto restrições de e das condições não negativas Em caso contrário preparar o Primal Propriedades Primal Dual Variável livre Restrição tipo Restrição tipo Variável livre qualquer sem restrição de sinal Matriz de coeficientes do Dual é a transposta da matriz de coeficientes do primal