Dualidade e Análise de Sensibilidade em PL

Prévia do material em texto

Francisco da Costa Cardoso Junior Mat.: 201201454034
Dualidade e Análise de Sensibilidade em Programação Linear
Tópicos
Introdução
Análise de sensibilidade em PL 3-Sensibilidade e dualidade
4-Relações primal e dual 
5-Modelos ilimitados e infactíveis
6-Metodo dual simplex
 7-Interpretação econômica do dual
8-Analize pós-otimização
 
Introdução
Um dos conceitos mais importantes em programação linear é o de dualidade. Qualquer problema de PL tem associado um outro problema de PL, chamado o Dual. Neste contexto, o problema original denomina-se por Primal. Um dos principais papéis da teoria da dualidade é a interpretação e implementação da análise de sensibilidade, que é uma parte muito importante de um estudo de PL.
Interpretação de modelos	de PL
função objetivo: custo, benefício
restrições  : demanda
restrições  : oferta
restrições = : oferta = demanda
não negatividade: natureza das variáveis
Lado direito das restrições
não negativo (mais natural)
Variáveis de decisão
nível de atividade
Modelo programação linear geral
max	(min)	c x	benefício (custo)
sa
F x = G x  H x 
x 
b r d
0
oferta = demanda oferta recurso r demanda recurso d
não negatividade
x  Rn	c  Rn	F  Rnmb	G  Rnmr	H  Rnmd
nível de atividade
benefício (custo)/ unidade de atividade
tecnologia
b  Rmb	r  Rmr	d  Rmd
Exemplo
	max
sa
	13x1 + 24x2 + 5x3 + 50x4
1x1+ 3x2 + 5x3 + 50x4	 89
3x3 +	5x4	 60
	benefício
demanda recurso 1
demanda recurso 2
	
	10x1+ 6x2 + 8x3 +	2x4  608
	oferta recurso 3
	
	1x2	+	1x4  28
	oferta recurso 4
	
	x1, x2, x3, x4  0
	não negatividade
cada unidade da atividade x1 consome 10 unidades do recurso 3 para produzir 1 unidade do recurso 1; cada unidade da atividade x2 consome 6 unidades do recurso 3 e 1 unidade do recurso 4 para produzir 3 unidades do recurso 1; etc.
Exemplo
Modelo da Refinaria de Petrolinea
min 20x1 + 15x2	custo
sa	0.3x1 + 0.4x2		2.0	demanda gasolina
0.4x1	+ 0.2x2		1.5	demanda gas aviação
0.2x1	+ 0.3x2		0.5	demanda lubrificantes
x1		9	oferta petróleo importado
x2		6	oferta petróleo nacional
x1, x2  0	não negatividade
cada unidade da atividade x1 requer 1 barril de petróleo importado para produzir 0.2 barril de lubrificante, 0.4 de gas de aviação e 0.3 barril de gasolina.
Análise de sensibilidade em PL
Como variações nos parâmetros afetam a solução ótima Exemplo: Modelo da Refinaria de Petrolinea
	min
	20x1
	+
	15x2
	
	sa
	0.3x1
	+
	0.4x2	
	2.0
	demanda gasolina
	
	0.4x1
	+
	0.2x2	
	1.5
	demanda gas aviação
	
	0.2x1
	+
	0.3x2	
	0.5
	demanda lubrificantes
	
	x1
	
	
	9
	oferta petróleo importado
	
	
	
	x2	
	6
	oferta petróleo nacional
x1, x2  0
Exemplo
x2
min
*  2
*  3.5x
x
1
2
10
oferta importado
c(2, 3.5) = 92.5
8	demanda gas aviação
0.4x1 + 0.2x2		1.5
6
x1  9
0.3x1 + 0.4x2 	2.0
4	x*
x2	 6
demanda gasolina
2
oferta nacional
0.2x1 + 0.3x2		0.5
demanda lubrificantes
2	4	6	8	10	x1
Variação de demanda: Exemplo
x2
10
demanda gas aviação
8
oferta importado
x1  9
6
0.3x1 + 0.4x2 	2.0
demanda gasolina	4	x*
2
0.2x1 + 0.3x2		0.5
demanda lubrificantes
x2	 6
oferta nacional
x*
2	4	6	8	10	x1
9
Variação de demanda
valor ótimo
lado
direito	10
Variação de oferta: Exemplo
x2
10
8
6
0.3x1 + 0.4x2 	2.0
demanda gasolina	4
0.2x1 + 0.3x2		0.52
demanda lubrificantes
demanda gas aviação
0.4x1 + 0.2x2		1.5
x*	x*
oferta importado
x1  9
oferta nacional
2	4	6	8	10	x1
11
Variação de oferta: Exemplo
valor ótimo
lado
direito	
Em geral: Variação de oferta (  )
valor ótimomax
min
lado direito
Em geral: Variação de demanda (  )
valor ótimomin
max
lado direito
Variação função objetivo: Exemplo (custo)
x2
10
demanda gas aviação
8
0.4x1 + 0.2x2		1.5
6	x*
oferta importado
x1  9
0.3x1 + 0.4x2 	2.0
demanda gasolina	4	x*
0.2x1 + 0.3x2		0.5 2
demanda lubrificantes
x2	 6
oferta nacional
2	4	6	8
10	x1
Variação no coeficiente c1: Exemplo
valor ótimo
c1
Em geral: Variação coeficiente
valor ótimomin
max
coef. função objetivo
Sensibilidade e dualidade
Modelo primal: modela a aplicação de interesse
Modelo dual	: modelo auxiliar que caracteriza sensibilidade
dos resultados do modelo primal com relação a variação nos parâmetros do modelo
Variáveis duais
uma (vi) para cada restrição (i) do primal
taxa de variação do valor ótimo primal/unidade lado direito
aumentando valor de um dos parâmetros (bi)
Tipo Restrição
Oferta (  ) Demanda (  )vi  0
vi  0
vi  0
vi  0
i é 
i é 
Aumenta lado direito
Relaxa Aperta
Diminui lado direito
Aperta Relaxa
Variável dual	vi
Primal
min
max
Relaxa restrições
valor ótimo melhora ou permanece o mesmo
maior ( max )
menor ( min )
Aperta restrições
valor ótimo piora ou permanece o mesmo
menor ( max )
maior ( min )
	i é =
irrestrita irrestrita
i-ésima restrição
19
Exemplo
min	20x1 + 15x2
	sa
	0.3x1
	+
	0.4x2	
	2.0
	v1
	 0
	demanda gasolina
	
	0.4x1
	+
	0.2x2	
	1.5
	v2
	 0
	demanda gas aviação
	
	0.2x1
	+
	0.3x2	
	0.5
	v3
	 0
	demanda lubrificantes
	
	x1
	
	
	9
	v4
	 0
	oferta petróleo importado
	
	
	
	x2	
	6
	v5
	 0
	oferta petróleo nacional
x1, x2  0
v1	(1000$/1000 barris): custo implícito para produzir 1000 barris adicionais
de gasolina quando a demanda é de2000 barris (preço marginal da gasolina)
v4	(1000$/1000 barris): valor de 1000 barris adicionais de petróleo importado
quando o nível oferta é 9000 barris	20
Formulação modelo dual
 aij vi  c j i
vi  0
sa
max	 bivi
i
 c j x j j
 aij x j  bi
j
x j  0
min
sa
Primal	Dua
31
Exemplo
Primalmin
20x1
+
15x2
sa
0.3x1
+
0.4x2	
2.0
demanda gasolina
0.4x1
+
0.2x2	
1.5
demanda gas aviação
0.2x1
+
0.3x2	
0.5
demanda lubrificantes
x1

9
oferta petróleo importado
x2	
6
oferta petróleo nacional
x1, x2
 0
max		2 v1	+ 15v2 + 0.5v3 + 9v4 + 6v5 sa		0.3v1	+ 0.4v2 + 0.2v3 + 1v4  20 0.4v1	+ 0.2v2 + 0.3v3 + 1v5  15
v1, v2, v3  0; v4, v5  0
Dual
Características do modelo dual
Variáveis duais: fornecem preços implícitos de uma unidade marginal do recurso modelado por cada restrição quando o limite do lado direito é atingido
Valor marginal implícito (minimização) ou preço (maximização) de uma unidade de atividade (variável primal) j devido à variável dual vi é iaijvi, onde aij é o coeficiente da atividade j no lado esquerdo da i-ésima restrição
A cada atividade xj corresponde a restrição dual
i aijvi  cj	minimização
i aijvi  cj	maximização
Relações entre modelo primal e dual
Se primal possui solução ótima então	 c x *	=  b v *j	j j	i	i i
Folga complementar primal
ou a solução primal ativa a i-ésima restrição primal, ou vi = 0
Folga complementar dual
ou solução ótima primal é xj = 0, ou vi ativa j-ésima restrição dualx

	a ij x j
	j
bi

 v i		0


	j	ic
 
v
i

a ij 

j		0
primal é maximizar
primal é minimizar
j cjxj	 i bivi
j cjxj	 i bivi
Dualidade fraca: para qualquer valor factível de	xje	vi:
 c j x j   bivi  c j x j

    vi aij x j

  vi aij x j    bi vi
j	i	j
	i	j
i	j		i
			
   c j x j    vi aij x j      vi aij x j   bivi  
 j	i	j		 i	j	i	
			
   c j x j    aij vi x j      aij x j vi   bivi  
 j	i	j
	
	 i	j	i	
	
   c j   vi aij x j     aij x j  bi vi
j 	i		i  j	
*
*
j cjxj	= i bivi
Dualidade forte: se o ou primal ou o dual possui uma solução ótima,
então ambos possuem solução ótima e
vB  (c1st , c2nd ,Lcmth )
c j  c j
 aij vi  0
i
(supondo minimização)
Se simplex revisado pára com uma solução ótima, então v = cB–1 é solução ótima para o modelo dual correspondente
- Se v satisfaz condições de otimalidade, então é solução factível do dual
se	c j
 c j
 aij vi  0
i
 variáveis j (forma padrão)
então
 aij vi
i
 c j
(supondo minimização)
- Valor da função objetivo do modelo dual para v que satisfaz condição de otimalidade do modelo primal é idêntico ao valor da função objetivo do modelo primal
1 –	c j
 aij vi  0		 aij vi  c j
i	i
akj
1
 1
k  i e i k  i e i
é do é do
tipo 
tipo	
(para as variáveis de folga/excesso)
	caso0

contrário
se 
então
 (1vi )  0
 vi  0
se 
então
 (1vi )  0
 vi  0
2	–	 bivi 
i
(c1st ,c2nd ,L,cmth )B1b
(x1st , x2nd ,L,xmth )
 B1b
(componentes não nulas são básicas)
 c j	* jx

j
c1st
x1st 
c2nd
x2nd
 L
cmth
xmth 
(c1st
, c2nd
,L, c
mth
)B1b
 c x*   b v
( dualidade
fraca ) 
 c x*   b v*
j	j	i i
j	i
j	j	i i
j	i
Folga complementar ótimo primal e dual
0   c x* 	 b v* 
j	j	i	i
j	i
33
	*	 *	
*	 *
   c j   vi aij x j
   aij x j  bi vi
j i
	i 	j	
	*		*
	*	 *
	 c j
 vi aij x j  0	e
  aij x j
bi vi	 0
	i	
	
Modelos ilimitados e infactíveis
 c j x j j
  bivi
i
(dualidade
fraca)
min
modelo primal ilimitado  modelo dual infactível modelo dual ilimitado	 modelo primal infactível
Metodos dual simplex 
 Neste artigo estudamos o problema de otimização linear canalizado (restrições e variáveis canalizadas, chamado formato geral) e desenvolvemos métodos do tipo dual simplex explorando o problema dual, o qual é linear por partes, num certo sentido não-linear. Várias alternativas de busca unidimensional foram examinadas. Experimentos computacionais revelam que a busca unidimensional exata na direção dual simplex apresenta melhor desempenho.
1. Introdução
O clássico problema de otimização linear (formato padrão):
em que A é uma matriz mn, foi formalizado por George B. Dantzig em 1947 que, em seguida, desenvolveu também o método primal simplex para resolvê-lo. Desde então, um número grande de pesquisadores têm contribuído para o campo da otimização linear de diferentes maneiras, seja incluindo desenvolvimentos teóricos e computacionais, seja encontrando novas aplicações práticas.
Logo após a publicação do método primal simplex de Dantzig (1951), sua versão dual surgiu com Lemke (1954), que consiste numa especialização do método primal simplex para o problema dual:
Segundo Maros (2003), o método dual simplex tem atraído considerável interesse, devido à importante aplicação nos métodos de otimização linear inteiro misto, os quais resolvem uma seqüência de problemas de otimização linear, com característica de que uma solução básica dual factível de boa qualidade é sempre disponível para o problema seguinte da seqüência. Segundo Bixby (2001), testes computacionais mostram que o desempenho do método dual simplex pode ser superior ao método primal simplex.
É importante observar que a evolução das implementações computacionais dos resolvedores lineares teve um papel fundamental no progresso da Otimização Linear. Um exemplo disto é o pacote CPLEX, que vem sendo melhorado desde sua primeira versão lançada em 1988. Bixby (2001) relatou que a implementação do método dual simplex, na primeira versão do pacote CPLEX 1.0 rodado numa estação de trabalho UltraSparc de 300 MHz, resolvia um problema de 16223 restrições e 28568 variáveis, com 88340 elementos não nulos em 1217.4 segundos e, o mesmo método na última versão CPLEX 7.1 na mesma máquina, resolvia o mesmo problema em 22.6 segundos. Ou seja, um mesmo método pode se tornar 50 vezes mais rápido dependendo de sua implementação. Vale observar que esta relação de desempenho também foi obtida por Karmarkar (1984), que afirmou que o método de pontos interiores era 50 vezes mais rápido do que o método simplex. Obviamente, estruturas de dados adequadas são fundamentais para um bom desempenho de uma implementação computacional. A despeito disto, um mesmo método pode permitir um número grande de variantes, com desempenhos bastante diversos, como por exemplo, a regra de Dantizg normalizada (conhecida na literatura de língua inglesa por 'steepest edge rule'. Veja Forrest & Goldfarb, 1992).
O objetivo principal deste trabalho consiste em desenvolver métodos tipo dual simplex para um formato geral de problemas de otimização linear (assim chamado em Vanderbei, 1997, o qual chamamos problemas canalizados) explorando o problema dual linear por partes (em certo sentido, não-linear), com buscas unidimensionais, exatas e inexatas. Em Vanderbei (1997), um método dual simplex para esta classe de problemas foi apresentado, baseado em tableau-simplex, em que se explorasse a natureza linear por partes do problema dual. Em trabalhos futuros examinaremos o efeito da regra de Dantizg normalizada e certas estruturas de dados, para problemas esparsos de médio e grande porte.
A maioria dos problemas práticos de otimização linear incluem diversos tipos de restrições (limitantes inferiores e/ou superiores, igualdades, variáveis livres, etc.). Para resolver esses problemas, necessita-se de uma versão do algoritmo dual simplex que possa tratar todos os tipos de restrições eficientemente (Maros, 2003). Este trabalho, apresenta o algoritmo dual simplex especializado em resolver problemas canalizados, baseado na característica da função dual simplex, que é linear por partes. A principal característica deste método é que em uma iteração ele pode fazer um progresso equivalente a muitas iterações do dual simplex padrão.
O artigo está organizado da seguinte forma: Na seção 2 relatamos sobre a eficiência e a complexidade computacional do método simplex, na seção 3 é descrito o algoritmo dual simplex linear por partes (Arenales, 1984), e na seção 4 descrevemos algumas modificações para busca unidimensional utilizada no algoritmo. A seção 5 apresenta os primeiros experimentos computacionais. Finalmente na seção 6, temos as conclusões.
Interpretação econômica do dual
 Considerando o exemplo 1, os valores de y´s (y1 = 0.25, y2 = 0.5, y3 = 0) ou os coeficientes de u´s (0.25u1, 0.5u2 ,0u3) indicam o Valor de Oportunidade dos Recursos, ou seja, a capacidade da unidade de cada recurso gerar lucro. Assim, por exemplo, se o recurso 1 (R1 = 160) aumentar de uma unidade (R1 = 161), o lucro Z aumentará de 0.25, resultando em Z = 100.25. A interpretação do valor de y3 = 0 (ou 0u3) é que este recurso é não escasso (abundante) no sistema, e portanto, o aumento deste recurso não irá aumentar o lucro. Os valores de y´s são geralmente tratados como Shadow Prices (Preços Sombra) ou Dual Prices.
Na Função Objetivo Dual, cada parcela mede então o Valor de Oportunidade dos Recursos envolvidos na produção (estoque X valor de oportunidade unitário do recurso). A Função-Objetivo Dual mede, portanto, a capacidade do estoque de recursos gerar lucro.
Analise pós-otimizaçãNa análise de pós-optimização é abordado o impacto na solução óptima de alterações discretas nos parâmetros do modelo : alterações dos coeficientes da FO, dos termos independentes e dos coeficientes da matriz, introdução de novas variáveis e de novas restrições.
Uma alteração dos coeficientes da FO pode alterar a solução óptima já obtida, sem contudo pôr em causa a sua admissibilidade. A SBA óptima do problema é dada por, X B b1 B ∗ − = o que permite concluir que uma alteração dos coeficientes da FO nunca afectará a admissibilidade (primal) da solução óptima já obtida.
Por outro lado, o critério da optimalidade continua a ser satisfeito para , se ∗ XB z c 0, (j 1, 2, , n) j − j ≥ = L podendo haver violação daquele critério, e consequentemente, da nova solução óptima. Portanto, apenas há alteração nalguns, ou em todos, os elementos da linha (zj − cj ), conforme a alteração se verifica num coeficiente duma VNB ou VB, respectivamente. Assim, seja δ a alteração no coeficiente ck, mantendo-se os restantes parâmetros do modelo inalterados : ∆C = [ 0 ... 0 δ 0 ... 0 ].
Observação
Este material refere-se às notas de aula do curso Engenharia de produção da Universidade Estácio. Não substitui o livro texto, as referências recomendadas e nem as aulas expositivas. 
35
Prof Robson