Dualidade



Baixar 43.51 Kb.
Encontro26.06.2019
Tamanho43.51 Kb.

25/06/19

Dualidade em Otimização Linear

Socorro Rangel

A cada problema de programação linear:



(P)

Podemos associar um outro problema, chamado problema dual, na forma:



. (D)

O problema original é chamado de problema primal.

Existem várias relações entre estes dois problemas. Podemos observar que:

i) O sentido de otimização no par Primal/Dual é contrário. Neste exemplo, o sentido no problema (P) é max, enquanto que o sentido de otimização no problema (D) é min;

ii) A matriz de restrições do problema Dual é a transposta da matriz de restrições do problema Primal. Portanto, o número de variáveis do problema dual é igual ao número de restrições do problema primal e vice-versa;

iii) O termos do lado direito nas inequações do Primal (vetor ) são os coeficientes da função objetivo do problema Dual. E os coeficientes da função objetivo do problema Primal (vetor ) formam os termos do lado direito das restrições do problema Dual;

iv) As restrições do Primal são do tipo “” e as do Dual são “”;

v) Sinal das variáveis do problema Primal e Dual é: “”;

Exemplo: Considere o problema:

(1)

Como construir o problema Dual?

i) sentido de otimização: min

ii) número de variáveis: 2 e número de restrições : 3

iii) coeficientes da função objetivo: 80 e 30

iv) sinal das restrições : “

v) sinal das variáveis : “

O problema Dual é então:



(2)

Qual a relação entre os problemas (1) e (2)? Como interpretar o problema Dual (2)?

Vamos supor que o problema primal esteja associado ao problema do planejamento da produção de três tipos de molhos a partir de dois ingredientes : Ketchup e Mostarda1. Estes dois ingredientes são misturados na proporção 5:2, 4:3 e 1:5 para gerarem os molhos 1, 2 e 3. O objetivo é maximizar os lucros associados com a venda dos três tipos de molhos.

E o problema Dual?

Vamos supor que um concorrente esteja interessado em comprar as matérias primas Ketchup e mostarda. Qual seria o preço justo a ser cobrado? Isto é: qual é o custo interno destes ingredientes?

Sejam as variáveis duais o preço a ser cobrado por cada um dos ingredientes respectivamente. A primeira restrição do problema Dual indica que a receita proveniente da venda de 5 unidades de ketchup e 2 unidades de mostarda ( de acordo com a fórmula para produzir o molho 1) tem que ser maior ou igual ao lucro obtido com a venda do molho 1. De forma similar podemos interpretar as demais restrições do problema dual. Ou seja, as restrições do problema dual indicam que a receita obtida com venda da matéria prima, em quantidades correspondentes as proporções necessárias para a produção de uma unidade do molho 1 (), deve ser maior ou igual ao lucro obtido com a produção de .

É claro que a idéia é cobrar o menor preço possível para que o concorrente continue interessado na compra da matéria prima. Portanto queremos min o preço total a ser cobrado com a venda da materia prima disponível: 80 unidades de ketchup e 30 de mostarda.

Será que as soluções destes dois problemas também estão relacionadas?

Exercício: Resolver os problemas (1) e (2) pelo método simplex revisado e comparar as soluções obtidas.

Construção do Problema Dual

Considere o problema:



qual é o seu dual?

Antes de discutirmos o caso geral, vamos escrever o dual de um caso particular:

vamos substituir as retrições de igualdade “” por 2 restrições de desigualdade “” e “”:



transformando as restrições do tipo “” em “” , temos:



(3)

agora nos temos condições de escrever o dual do problema (3):

i) sentido de otimização: min

ii) número de variáveis: 4 e número de restrições : 3

iii) coeficientes da função objetivo: 6, -6, 4, -4

iv) sinal das restrições : “

v) sinal das variáveis : “

O problema Dual é então:



(4)

Se fizermos:e , o problema (4) pode ser reescrito como:

Ou seja, de uma maneira geral temos o seguinte par primal/dual:

(P) (D)
Propriedades

Vamos ver a seguir que o conceito de dualidade é relativo. Qualquer um dos problemas em um par primal/dual pode ser considerado primal e vice-versa.

Lema 1 - O dual do problema dual é igual ao problema primal.

Prova: Considere o par primal/dual:



(P) (D)

Vamos construir o dual do problema (D). Até agora so conhecemos a forma dual de problemas escretos no formto do problema (P) acima. Portanto vamos transformar o problema (D) para aquele formato. Basta multiplicar a função objetivo e as restrições por (-1), par ober:



(D’)

o dual do problema (D’) é:



(P’)

fazendo e multiplicando a função objetivo e as restrições por (-1), o problema (P’) pode ser reescrito como



que é o problema (P).

Exemplo:

Escrevendo o problema no formato (P) temos:



(P’)

o dual de (P’) é:



(5)

se fizermos uma mudança de variáveis: , o problema (5) se torna:



de uma maneira geral. podemos então dizer que o dual de um problema no formato:



é: .

Conhecidas estas formas de dualidade, e usando o Lema 1, podemos montar o seguinte diagrama:



Regras de Correspondências entre os Problemas Primal e Dual




max




min




Restrição







Variável
















=



livre




Variável







Restrição








?(completar)







livre



?(completar)





Relações entre os problemas Pimal/Dual

Vamos apresentar agora algumas propriedades que explicitam as relações entre o par de problemas Primal/Dual.



Teorema Fraco da Dualidade - Considere o par Primal/Dual:

(P) (D)

Se são soluções factíveis para os problemas Primal/Dual respectivamente, então:



.

Prova: Vamos reescrever o par Primal/dual

Exemplo: Considere as seguintes soluções factíveis para os problemas (1) e (2) abaixo:

(1) (2)

a) , Z= 90 e , D = 154.35

e temos .Esta informação nos diz que o valor ótimo destes problemas esta dentro do intervalo: [90,154.35].

b) , Z= 150 e , D = 150


Corolário I - Considere o par Primal/Dual:

(P) (D)

Se são soluções factíveis para os problemas Primal/Dual respectivamente, e .

então são as soluções ótimas para os respectivos problemas.
Mas os dois problemas sempre terão soluções ótimas?

1) O que acontece com a solução do problema dual se o problema primal é ilimitado?

O dual é infactível.

Ex.


2) Os dois problemas podem ser infactíveis?

(1) (2)

sim.


Teorema Fundamental Da Dualidade - Considere um par Primal/Dual de problemas de programação Linear. Então uma e apenas uma das seguintes situações ocorrerá:

1) Se o problema primal possui solução ótima, , então o problema dual possui solução otima e além disso: Z= c.

2) Se um dos problemas é ilimitado, então o outro é infactível.

3) Os dois problemas são infactíveis.

O resultado deste teorema pode ser resumido no seguinte diagrama:





Dual

Primal





factível

infactível




factível








infactível



pode ocorrer





Teorama das Folgas Complementares - Considere o par Primal/Dual:

(P) (D)

Seja são soluções factíveis para os problemas Primal/Dual respectivamente. Então são soluções ótimas se e somente se :



e

1 Puccini






©aneste.org 2017
enviar mensagem

    Página principal