Buscar

PO ulisses 3

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 9 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 9 páginas

Prévia do material em texto

O Problema Dual
1 – Introdução 
Todo problema de PL, a que chamaremos de primal, possui um segundo problema associado chamado dual. Ambos são completamente inter-relacionados, de modo que a solução ótima de um fornece informações completas sobre o outro.
2 – Montagem do dual
A montagem de um problema dual parte da forma canônica do primal. Se o primal é de máximo, o dual é de mínimo e vice-versa.
Considerando um modelo primal de maximização temos:
A função objetivo do dual é de minimização;
Os termos constantes das restrições do dual são os coeficientes da função objetivo do primal;
Os coeficientes da função objetivo do dual são os termos constantes das restrições do primal;
As restrições do dual são do tipo ≥ ao passo que as restrições do primal são do tipo ≤ ;
O número de incógnitas do dual é igual ao número de restrições do primal;
O número de restrições do dual é igual ao número de incógnitas do primal; e
A matriz dos coeficientes do dual é a transposta da matriz dos coeficientes do primal. 
Seja o primal:
 Max 
 
 s.a
 
 para i = 1,2,3,...,m
 
 para j = 1,2,3,....,n 
O dual será:
 Min 
 s.a
 
 para j = 1,2,3,....,n 
 
 
 para i = 1,2,3,...,m
Exemplo 1
Achar o dual do seguinte primal: 
 Max Z = 5x1 + 2x2
 s.a
 x1 ≤ 3 (y1)
 x2 ≤ 4 (y2)
 x1 + 2x2 ≤ 9 (y3)
 x1, x2 ≥ 0 
Resp:
 
 Min D = 3y1 + 4y2 + 9y3
 s.a
 y1 + y3 ≥ 5 
 y2 + 2y3 ≥ 2 
 y1, y2, y3 ≥ 0
Se a restrição k do primal é igualdade então a variável yk do dual é sem restrição de sinal. 
Se a variável xp do primal é sem restrição de sinal então a restrição p do dual é uma igualdade.
Exemplo 2
Achar o dual do seguinte primal: 
 
 Max Z = 3x1 + 2x2 - x3 + x4 + 5x5 + 4x6 
 s.a
 x1 + x2 + x3 = 10
 x4 + x5 + x6 = 15
 3x1 + 2x2 + x4 + 3x5 ≤ 20
 x2 + x3 + 2x4 + x6 ≤ 30
 x1 + x4 + 2x6 ≥ 25
 x2 + x3 + 2x5 ≥ 18
 x1, x2, x3 ≥ 0 ; x4, x5, x6 quaisquer
Passando para a forma canônica vem :
 Max Z = 3x1 + 2x2 - x3 + x4 + 5x5 + 4x6 
 s.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
O dual será:
 Min D = 10y1 + 15y2 + 20y3 + 30y4 – 25y5 – 18y6
 s.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 ; y3, y4, y5, y6 ≥ 0
Reescrevendo na forma standard temos:
Min D = 10y1 + 15y2 + 20y3 + 30y4 – 25y5 – 18y6
 s.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 ; y3, y4, y5, y6 ≥ 0
Exemplo 3 
Achar o dual do seguinte primal: 
 Min Z = x1 + 5x2 + 2x3
 s.a 
 x1 ≤ 4 (y1)
 x2 + x3 ≤ 9 (y2)
 3x1 + 2x2 – 4x3 ≥ 8 (y3)
 x1 qualquer ; x2, x3 ≥ 0
O dual será:
 Max D = -4y1 - 9y2 + 8y3 
 s.a
 -y1 + 3y3 = 1
 -y2 + 2y3 ≤ 5
 -y2 – 4y3 ≤ 2
 y1, y2, y3 ≥ 0
Interpretação econômica do Dual
Recapitulando:
Seja o primal
 Max 
 
 s.a
 
 para i = 1,2,3,...,m
 
 para j = 1,2,3,....,n 
O dual será:
 Min 
 s.a
 
 para j = 1,2,3,....,n 
 
 
 para i = 1,2,3,...,m
Onde bi ( quantidade do recurso i para as n atividades ( bi ≥ 0);
 xj ( nível de produção da atividade j. Os xj são as incógnitas
 (variáveis) do problema;
 cj ( lucro unitário do produto j;
 aij ( quantidade do recurso i consumida na produção de uma
 unidade do produto j.
Conclui-se então que yi será o valor unitário do recurso i.
Apesar da variável yi representar o valor unitário do recurso i, nada nos garante que este valor coincida com o seu valor de mercado, é um valor implícito do recurso i que só é válido para o problema em questão.
O valor ótimo de yi representa a taxa na qual o Z ótimo aumenta ou diminui de valor se a quantidade disponível do recurso i aumentar ou diminuir dentro de certos limites.
Esse limite é determinado pelo intervalo de bi dentro do qual a base da solução ótima não se altera. 
O valor ótimo de yi recebe várias denominações tais como : valor implícito; preço de sombra; incremental value; intrinsic value; shadow price; internal price; efficiency price; etc.
Exemplo
 Seja o primal 
 Min Z = 10x1 + 11x2 
 s.a
 10x1 + 20x2 ≥ 50
 50x1 + 10x2 ≥ 100
 x1; x2 ≥ 0
Cujo dual é:
 Max D = 50y1 + 100y2
 s.a
 10y1 + 50y2 ≤ 10
 20y1 + 10y2 ≤ 11
 y1; y2 ≥ 0
A resolução fica a cargo dos alunos.
Resolvendo temos
Z = 35 , x1 = 5/3 , x2 = 5/3
D = 35 , y1 = 1/2 , y2 = 1/10
Se eu mudar a primeira restrição do primal para 51 vem:
Z’ = 71/2 , x1 = 149/90 , x2 = 155/90
Z’ – Z = 71/2 – 35 = 1/2 = y1
Voltando ao problema original, se eu mudar a segunda restrição para 101:
Z’ = 3159/90 , x1 = 152/90 , x2 = 149/90
Z’ – Z = 3159/90 – 35 = 1/10 = y2 
 
Teorema da Folga Complementar:
Obtida pelo método simplex a solução ótima do primal, então: 
O valor ótimo da variável yi do dual é igual ao coeficiente na linha do Z ótima, da variável de folga xn+i do primal; e 
O valor ótimo da variável de folga ym+j do dual é igual ao coeficiente na linha do Z ótima, da variável xj do primal .
Colocando-se a variável de folga xn+i na restrição i do primal temos
 
 
e ym+j+ na restrição j do dual
 
 
	
	
	ym+1 ym+2 --------- ym+n 
	 y1 y2 --------- ym 
	
	
	Z
	 x1 x2 --------- xn
	xn+1 xn+2 --------- xn+m 
	b
	base
	1
	 c1 c2 --------- cn 
	 0 0 --------- 0
	0
	xn+1
	0
	 a11 a12 --------- a1n
	 1 0 --------- 0
	b1
	 xn+2
	0
	 a21 a22 --------- a2n
	 0 1 --------- 0
	b2
	----
	--
	---------------------------
	--------------------------
	---
	xn+m
	0
	 am1 am2 --------- amn
	 0 0 --------- 1
	bm
 
 Corolário do teorema da folga complementar
O corolário do teorema da folga complementar pode ser expresso do seguinte modo:
 Na solução ótima temos: 
yi = 0 quando xn+i > 0 ou seja, se na solução ótima do primal a variável de folga xn+i for básica, então a variável yi do dual é não básica. Economicamente significa nem que todo recurso i está sendo consumido pelas n atividades, havendo portanto, sobra daquele recurso, e seu valor implícito é 0;
yi > 0 quando xn+i = 0 ou seja, se na solução ótima do primal a variável de folga xn+i for não básica, então a variável yi do dual é básica. Economicamente significa que todo recurso i está sendo consumidopelas n atividades, não havendo portanto, sobra daquele recurso, e seu valor implícito é > 0; 
xj = 0 quando ym+j > 0 ou seja, se na solução ótima do primal a variável xj for não básica, então a variável de folga do dual ym+j é básica. Economicamente significa que esta atividade não será realizada xj = 0 ; e
xj > 0 quando ym+j = 0 ou seja, se na solução ótima do primal a variável xj for básica, então a variável de folga do dual ym+j é não básica. Economicamente significa que esta atividade será realizada xj > 0.
 
 Aproveitando o primeiro exemplo de dual: 
 Max Z = 5x1 + 2x2
 s.a
 x1 ≤ 3
 x2 ≤ 4 
 x1 + 2x2 ≤ 9
 x1, x2 ≥ 0 
 
 Min D = 3y1 + 4y2 + 9y3
 s.a
 y1 + y3 ≥ 5 
 y2 + 2y3 ≥ 2 
 y1, y2, y3 ≥ 0
Cuja solução ótima do primal é:
 y4 y5 y1 y2 y3
	
	Z
	x1
	x2
	x3
	x4
	x5
	b
	base
	1
	0
	0
	4
	0
	1
	21
	x1
	0
	1
	0
	1
	0
	0
	3
	x4
	0
	0
	0
	1/2
	1
	-1/2
	1
	x2
	0
	0
	1
	- 1/2
	0
	1/2
	3
 
Temos :
Primal
Z = 21, x1 = 3 básica, x2 = 3 básica, x3 = 0 não básica, x4 = 1 básica, x5 = 0 não básica
Dual
D = 21, y1 = 4 básica, y2 = 0 não básica, y3 = 1 básica, y4 = 0 não básica, y5 = 0 não básica.
Verifica-se que o valor intrínseco do recurso 1 é 4, do recurso 2 e 0 e do recurso 3 é 1. Portanto está sobrando recurso 2 pois x4 = 1 e o seu valor intrínseco é 0.
Como exercício os alunos deverão diminuir o recurso 1 de uma unidade e verificar a alteração do Z, em seguida no problema original, aumentar o recurso 3 de uma unidade e verificar a alteração de Z.
Exercício
Foi apresentado um problema de PL, a um administrador, composto de: 
Função objetivo com três variáveis;
Restrições compostas de quatro inequações, sendo a primeira referente à hora de máquinas, a segunda referente à matéria prima no 1, a terceira à matéria prima no 2 e a quarta à mão de obra; e
As variáveis da função objetivo ≥ 0.
Ao resolver o problema, o administrador chegou ao seguinte quadro para a solução ótima:
	
	Z
	x1
	x2
	x3
	x4
	x5
	x6
	x7
	b
	base
	1
	0
	0
	0
	2
	3
	1/3
	0
	235
	x2
	0
	0
	1
	0
	1
	3
	1
	0
	80
	x7
	0
	0
	0
	0
	2/3
	1/2
	2
	1
	2
	x1
	0
	1
	0
	0
	-2
	-5
	3/4
	0
	28
	x3
	0
	0
	0
	1
	3
	-1
	1/4
	0
	35
 
Pede-se:
As variáveis da função objetivo do Dual;
As variáveis de folga do Dual;
As variáveis básicas do Dual e seus valores;
As variáveis não básicas do Dual e seus valores;
O valor ótimo de D;
Caso a empresa precisasse reduzir custos, qual dos recursos deveria ser reduzido e em quantas unidades, de modo a não alterar o lucro máximo? 
_1172386734.unknown
_1172386838.unknown
_1173852565.unknown
_1174114047.unknown
_1174114229.unknown
_1173852428.unknown
_1172386760.unknown
_1172385918.unknown
_1172386465.unknown
_1172384969.unknown

Materiais recentes

Perguntas Recentes