Teoremas da Dualidade em Pesquisa Operacional

Prévia do material em texto

Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
EPD072: Pesquisa Operacional I
- Aula 01 -
Dualidade
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG.
Departamento de Engenharia de Produc¸a˜o EE UFMG
carlos@dep.ufmg.br
1 de junho de 2011
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 1
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
1 Definic¸a˜o - Forma Padra˜o
2 Teoremas
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
3 Teorema da Folga complementar
Restric¸o˜es Justas e Restric¸o˜es folgadas
Teorema da Folga Complementar
4 Interpretac¸a˜o Econoˆmica do Dual
Um exemplo
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 2
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Definic¸a˜o: Primal - Dual
PRIMAL - forma pada˜o
Se denominarmos como PRIMAL o Programa Linear (P):
max z = cx
s. a` Ax ≤ b
x ≥ 0
(P)
DUAL
Enta˜o o DUAL de (P) e´ o Programa Linear (D) escrito sob a
forma:
min w = bT y
s. a` AT y ≥ cT
y ≥ 0
(D)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 3
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Teorema 1
O Dual do Dual e´ o Primal
Generalizac¸a˜o
PRIMAL (DUAL) DUAL (PRIMAL)
maximizar minimizar
i e´sima restric¸a˜o ≥ i e´sima varia´vel ≤ 0
i e´sima restric¸a˜o ≤ i e´sima varia´vel ≥ 0
i e´sima restric¸a˜o = i e´sima varia´vel ∈ IR
j e´sima varia´vel ≥ 0 j e´sima restric¸a˜o ≥
j e´sima varia´vel ≤ 0 j e´sima restric¸a˜o ≤
j e´sima varia´vel ∈ IR j e´sima restric¸a˜o =
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 4
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Exemplo 1 - Forma padra˜o
max z = 4 x1 +5 x2 (0)
sujeito a`s 2 x1 + x2 ≤ 8 (1)
retric¸o˜es x1 +2 x2 ≤ 7 (2)
0 x1 + x2 ≤ 3 (3)
x1 ≥ 0 x2 ≥ 0
Exemplo 2 - Forma qualquer
min z = 5 x1 −2 x2 (0)
sujeito a`s x1 ≤ 3 (1)
retric¸o˜es x2 ≤ 4 (2)
x1 +2 x2 ≥ 9 (3)
x1 ∈ IR (4) x2 ≥ −3 (5)
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 5
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Definic¸a˜o: Primal - Dual
PRIMAL
maximizar z =
n∑
j=1
cjxj
sujeito a
n∑
j=1
aijxj ≤ bi ∀ i = 1, . . . ,m
xj ≥ 0 ∀j = 1, . . . , n
DUAL
maximizar w =
m∑
i=1
biyi
sujeito a
m∑
i=1
aijyi ≥ cj ∀ j = 1, . . . , n
yi ≥ 0 ∀i = 1, . . . ,m
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 6
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Teorema 2 - Dualidade Fraca
Teorema 2 - Dualidade Fraca
Se (P) e (D) sa˜o um par PRIMAL-DUAL, para qualquer soluc¸a˜o
via´vel x¯ de (P) e qualquer soluc¸a˜o via`vel y¯ de (D), tem-se
cx¯ ≤ bT y¯
Demonstrac¸a˜o
1 multiplicar as restric¸o˜es do primal por y e soma-las
2 multiplicar as restric¸o˜es do dual por x e soma-las
3 comparar os resultados
Colora´rio 2.1 - Primal Ilimitado
Se o primal (P) e´ ilimitado, enta˜o o Dual (D) de (P) na˜o possui
soluc¸a˜o via´vel.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 7
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Teorema 3 - Dualidade Forte
Teorema 3 - Dualidade Forte
Se (P) e (D) sa˜o via´veis e x∗ e y∗ sa˜o soluc¸o˜es o´timas,
respectivamente, enta˜o:
cx∗ = bT y∗
Demonstrac¸a˜o
Por construc¸a˜o.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 8
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Teorema 1 - Generalizac¸a˜o do Dual
Teorema 2 - Dualidade Fraca
Teorema 3 - Dualidade Forte
Teorema 4 - Teorema da Dualidade
Teorema da Dualidade
Considere o par de programas lineares duais (P) e (D)
1 Se um e outro admitem soluc¸o˜es via´veis, ambos teˆm ao
menos uma soluc¸a˜o o´tima e o valor de suas func¸o˜es objetivos
sa˜o iguais;
2 Se um dos programas admite um conjunto de soluc¸o˜es via´veis
nas quais a func¸a˜o objetivo e´ ilimitada (superiormente para
(P) e inferiormente para (D)), logo o outro na˜o tem soluc¸a˜o
via´vel;
3 Se (P) (resp. (D)) tem uma soluc¸a˜o via´vel, mas (D) (resp.
(P)) na˜o, enta˜o (P) (resp. (D)) admite um conjunto de
soluc¸o˜es via´veis nas quais a func¸a˜o objetivo e´ ilimitada
superiormente (resp. inferiormente);
4 Pode acontecer que nem (P) e nem (D) tenham soluc¸o˜es
via´veis
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 9
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Restric¸o˜es Justas e Restric¸o˜es folgadas
Teorema da Folga Complementar
Restric¸o˜es Justas e Restric¸o˜es folgadas
Seja x¯ uma soluc¸a˜o via´vel de (P). Uma restric¸a˜o i qualquer e´
denominada:
Folgada
folgada se Ai x¯ < bi : isto implica que a varia´vel de folga xn+i
associada a esta restric¸a˜o e´ positiva, ou seja, xn+i > 0 e portanto
ela esta´ na base na soluc¸a˜o x¯ ;
Justa
justa se Ai x¯ = bi : isto implica que a varia´vel folga xn+i associada
a esta restric¸a˜o e´ nula, ou seja, xn+i = 0. Note aqui que xn+i = 0
na˜o implica que xn+i esteja fora da base na soluc¸a˜o x¯ , ela pode ser
uma varia´vel ba´sica degenerada.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 10
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Restric¸o˜es Justas e Restric¸o˜es folgadas
Teorema da Folga Complementar
Teorema da Folga Complementar
Teorema da Folga Complementar
Duas soluc¸o˜es x∗ e y∗ sa˜o soluc¸o˜es o´timas dos problemas duais
(P) e (D), respectivamente, se e somente se:
(y∗Aj − cj)x∗ = 0, ∀ j = 1, . . . , n
As condic¸o˜es necessa´rias e suficientes para que duas soluc¸o˜es via´veis do par de
programas lineares primal-duais (P) e (D) sejam um par de soluc¸o˜es o´timas sa˜o:
se uma restric¸a˜o de um dos programas lineares e´ folgada, a varia´vel dual
correspondente do dual e´ nula;
se uma varia´vel de um dos programas lineares e´ positiva, a restric¸a˜o
correspondente do dual e´ justa.
Importante: pode ocorrer que uma restric¸a˜o de um dos programas seja justa e a
varia´vel dual correspondente do dual seja nula.
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 11
Definic¸a˜o - Forma Padra˜o
Teoremas
Teorema da Folga complementar
Interpretac¸a˜o Econoˆmica do Dual
Um exemplo
Um exemplo
Uma determinada empresa esta´ interessada em maximizar o lucro mensal proveniente
de quatrode seus produtos, designados por I, II, III e IV. Para fabricar esses quatro
produtos, ela utiliza dois tipos de ma´quinas (M1 e M2) e dois tipos de ma˜o-de-obra
(MO1 e MO2) que teˆm as disponibilidades conforme os dados das tabelas abaixo.
Ma´qs. tempo dispon´ıvel
(horas-ma´quinas/meˆs)
M1 80
M2 20
Ma˜o-de- tempo dispon´ıvel
obra (homens-hora/meˆs)
MO1 120
MO2 160
As necessidades de produc¸a˜o e o lucro de uma unidade de cada produto sa˜o:
Ma´q Produtos
I II III IV
M1 5 4 8 9
M2 2 6 - 8
Ma˜o-de- Produtos
obra I II III IV
MO1 2 4 2 8
MO2 7 3 - 7
Prod. Lucro
I 10,00
II 8,00
III 9,00
IV 7,00
Quanto a emprese deve produzir de cada produto?
Prof. Carlos Roberto Venaˆncio de Carvalho, DEP EE UFMG. (DEP EE UFMG)EPD072: Pesquisa Operacional I - Aula 01 - Dualidade 12
	Definição - Forma Padrão
	Teoremas
	Teorema 1 - Generalização do Dual
	Teorema 2 - Dualidade Fraca
	Teorema 3 - Dualidade Forte
	Teorema 4 - Teorema da Dualidade
	Teorema da Folga complementar
	Restrições Justas e Restrições folgadas
	Teorema da Folga Complementar
	Interpretação Econômica do Dual
	Um exemplo