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


Catálogo: ~socorro


Compartilhe com seus amigos:


©aneste.org 2020
enviar mensagem

    Página principal
Universidade federal
Prefeitura municipal
santa catarina
universidade federal
terapia intensiva
Excelentíssimo senhor
minas gerais
união acórdãos
Universidade estadual
prefeitura municipal
pregão presencial
reunião ordinária
educaçÃo universidade
público federal
outras providências
ensino superior
ensino fundamental
federal rural
Palavras chave
Colégio pedro
ministério público
senhor doutor
Dispõe sobre
Serviço público
Ministério público
língua portuguesa
Relatório técnico
conselho nacional
técnico científico
Concurso público
educaçÃo física
pregão eletrônico
consentimento informado
recursos humanos
ensino médio
concurso público
Curriculum vitae
Atividade física
sujeito passivo
ciências biológicas
científico período
Sociedade brasileira
desenvolvimento rural
catarina centro
física adaptada
Conselho nacional
espírito santo
direitos humanos
Memorial descritivo
conselho municipal
campina grande