Dualidade em problemas de programação linear
Dualidade em problemas de programação linear!
Para cada problema de programação linear, existe um problema único correspondente envolvendo os mesmos dados e também descreve o problema original. O problema original é chamado primal program e o problema único correspondente é chamado de programa Dual. Os dois programas estão intimamente relacionados e a solução ótima de dual fornece informações completas sobre a solução ótima de primal e vice-versa.
Diferentes aspectos úteis desta propriedade são:
(a) Se o primal tiver um grande número de restrições e um pequeno número de variáveis, o cálculo pode ser consideravelmente reduzido convertendo-se o problema em Dual e depois solucionando-o.
(b) A dualidade na programação linear tem certas conseqüências de natureza econômica. Isso pode ajudar os gerentes a responder a perguntas sobre cursos alternativos de ação e seus valores relativos.
(c) O cálculo do dual verifica a precisão da solução primal.
(d) A dualidade na programação linear mostra que cada programa linear é equivalente a um jogo de soma zero com duas pessoas. Isso indica que existem relações bastante próximas entre a programação linear e a teoria dos jogos.
1. Formando Dual quando Primal está em Forma Canônica:
Dos dois programas acima, os seguintes pontos são claros:
(i) O problema de maximização no primitivo torna-se o problema de minimização no dual e vice-versa.
(ii) O problema de maximização possui () restrições.
(iii) Se o primal contiver n variáveis e m restrições, o dual conterá m variáveis e n restrições.
(iv) As constantes b 1 b 2, b 3 ……… b m nas restrições do primal aparecem na função objetiva do dual.
(v) As constantes c 1, c 2, c 3 c n na função objetivo do primal aparecem nas restrições do dual.
(vi) As variáveis em ambos os problemas são não-negativas.
As relações de restrição do primal e do dual são representadas abaixo.
Exemplo 1:
Construa o dual para o problema primordial
Solução:
Em primeiro lugar, a restrição ≥ é convertida em ≤ restrição multiplicando ambos os lados por -1.
Exemplo 2:
Construa o dual para o problema primordial
Solução:
Se Y 1, Y 2, V 3 e V 4 forem as variáveis duplas correspondentes, então o problema dual é dado por
Como o problema dual tem menor número de restrições do que o primitivo (2 em vez de 4), requer menos trabalho e esforço para resolvê-lo. Isso decorre do fato de que a dificuldade computacional no problema de programação linear está associada principalmente ao número de restrições, e não ao número de variáveis.
Exemplo 3:
Construa o dual do problema
Solução:
Como o problema dado é de minimização, todas as restrições devem ser do tipo. Multiplicando a terceira restrição por - 1 em ambos os lados, obtemos.
-8x 1 + 2x 2 + 2x 3 ≥ -10
O dual do problema dado será
onde y 1, y 2, y 3, y 4 e y 5 são as variáveis duais associadas à primeira, segunda terceira, quarta e quinta restrições, respectivamente.
