Dossiê 2_PO

Prévia do material em texto

29-03-2010
Algoritmo (Método) Simplex		
Etapa 0: Forma Padrão
	 Quadro tableaux, solução básica:
	VB
	xi
	
	
	…aij…
	bi
	
	…cj…
	
Etapa 1: Escolher ck = min {cj} caso ck ≥ 0 → ótimo.
Etapa 2: Escolher = min {}, aik > 0.
Etapa 3: Pivoteamento – solução básica e voltar para a Etapa 1.
Exemplo: simplex 1ª fase (≤)
	 Max. 2x1 + 4x2
	 SA	4x1 + 2x2 ≤ 400
			4x1 + 4x2 ≤ 900
			x1, x2 ≥ 0
Etapa 0: Min. -2x1 - 4x2
	 SA	4x1 + 2x2 + x3 = 400
			4x1 + 4x2 + x4 = 900
			x1, x2, x3, x4 ≥ 0
Coluna 
Pivotal
↑
 PivôTableaux Básico
	VB
	x1
	x2
	x3
	x4
	
→ Linha 
Pivotal
	x3
	4
	2
	1
	0
	400
	x4
	4
	4
	0
	1
	900
	
	-2
	-2
	0
	0
	
Solução Básica → F.O. = 0
			Variável	Custo Reduzido
			 x1 = 0		-2
			 x2 = 0		-4
			 Folga		 Preço Dual
			 x3 = 400	 0
			 x4 = 900	 0
Etapa 2: = min {} → = min {}
	 = 200
Etapa 3: Pivoteamento
L1 → (divide-se a linha pivotal pelo pivô)
L2 → L2 - L1 (linha 2 – (elemento a ser gerado/pivô) * linha pivotal)
L3 → L3- L2 (linha 3 – (elemento a ser gerado/pivô) * linha pivotal)
	VB
	x1
	x2
	x3
	x4
	
	x2
	2
	1
	
	0
	200
	x4
	-4
	0
	-2
	1
	100
	
	6
	0
	2
	0
	800 (F.O.)
Voltar a Etapa 1
Solução Básica → F.O. = 800
			Variável	Custo Reduzido
			 x1 = 0		6
			 x2 = 200		0
			 Folga		 Preço Dual
			 x3 = 0	 2
			 x4 = 100	 0
2ª Interação:
Etapa 1: ck = 0 → min {6, 0, 2, 0}
	 ck ≥ 0 → ótimo
05-04-2010
Revisão Simplex:	
	 Max. Z = x1 + 2x2 + 4x3 + x4
	 SA	5x1 + 5x2 + 2x3 + 6x4 ≤ 400
			x1, x2, x3, x4 ≥ 0
Apresenta o quadro
			Z = 800
			Variável	Custo Reduzido
			 x1 = 0		9
			 x2 = 0		8
 			 x3 = 0		0
			 x4 = 0		11
			 Folga		 Preço Dual
			 x5 = 0	 2
			 x6 = 100	 4
Pergunta-se:
A solução é básica? Não, deveria ter uma variável de folga e não duas (x5 e x6)
A solução é ótima? Não.
O preço dual de x2 é 9? Não, só x5 tem preço dual.
Feita a correção (tirar x6) a solução é básica.
C(5,1) = 5 vértices, onde N = 5 e M = 1, N – M = 5 – 1 = 4 → zerar 4 variáveis.
A solução seria ótima. Não há outro vértice que forneça um Z maior do que 800.
Dualidade em Programação Linear
Duais Simétricas
Dado o PPL Primal
Max. ctx
SA	Ax ≤ b
	X ≥ 0
Podemos escrever o dual
Min. btw
SA	Atw ≥ c
	w ≥ 0
	w é a variável dual
Exemplo: seja o primal
 Max. 2x1 + 4x2
	 SA	5x1 + 2x2 ≤ 100
			3x1 + 5x2 ≤ 200
			x1, x2 ≥ 0
Então o dual será:
Min. 100w1 + 200w2
	 SA	5w1 + 3w2 ≥ 2
			2w1 + 5w2 ≥ 4
			w1, w2 ≥ 0
Interpretação Econômica Variáveis Duais
Indústria produz P1 e P2 com lucros 5 e 6.
Utilização Unitária
	Recursos
	Disponível
	Gasto para fazer
	A
	14
	1
	2
	B
	9
	1
	1
	C
	56
	7
	4
Modelo:
		Max. 5x1 + 6x2
	 		 SA	x1 + 2x2 ≤ 14
				x1 + x2 ≤ 9
				7x1 + 4x2 ≤ 56
				x1, x2 ≥ 0
Modelo dual:
		Min. 14y1 + 9y2 + 56y3
	 		SA	1y1 + 1y2 + 7y3 ≥ 5
				2y1 + 1y2 + 1y3 ≥ 6
				y1, y2, y3 ≥ 0 → Valores dos recursos
07-04-2010
Trabalho P.O.
Valor: 5 pts (opcional + 5 pts)
Tema: Resolver problema de médio porte com técnica ≠ linear:
Exemplo: roteamento, localizador e alocação.
Técnicas: programação quadrática, gradiente, gradiente projetado, conjugado, algoritmo genético, simulated annealing, probabilístico e redes neurais (RNA).
Entregar: 14/04/2010 – Resumo, problema e método.
26/04/2010 – Apostila: fundamentos, metologia, aplicação, cálculos, rotinas computacionais, resultados, conclusão e bibliografia.
03/05/2010 – Laboratório, precessamento e dúvidas.
Opcional: resolver usando 2º método e comparar o desempenho (+ 5 pts).
19-04-2010
Programa LINDO → Linear
			 Interactive
			 Discrete
			 Optimizer
Não precisa de condição de não negatividade.
Exemplo: PPL.txt
Max. 2x1
ST
2) 2x1 + 3x2 ≤ 60
3) 2x1 + 4x2 ≤ 90
		END
GO
↓
Dá a
solução
direta
não
 mostra
nenhum
tableaux
ou
 
pivotemaneto		LOOK ALL → mostra tudo
		PIV → pivoteamento → define o que entra e o que sai.
		TABLB 
		PIV → 2ª interação
		TABL
		PIV → 3ª interação
		QUIT
Abrir arquivo.bat → botão direto → editar
Lindo.exe <pplteste.txt> relat_ppl.txt
	 Arquivo de entrada Arquivo de saída
Abrir arquivo de saída em txt.
ART → função objeto
SLK (slake) → folga
L1: Máx. 2x1
L2: 2x1 + 3x2 ≤ 60
L3: 2x1 + 4x2 ≤ 90
	
	x1
	x2
	SLK2
	SLK3
	
	ART
	0
	3
	1
	0
	60
	x1
	1
	1,5
	0,5
	0
	30
	SLK
	0
	1
	-1
	1
	30
	
	x1
	x2
	x3
	x4
	
	x1
	1
	1,5
	0,5
	0
	30
	x4
	0
	1
	-1
	1
	30
	
	0
	3
	1
	1
	60
LINDO → problemas lineares
LINGO → problemas não lineares
Dual Simplex (≥)
Forma Padrão
	Min cixj
	SA Ax = b
	 x ≥ 0, b ≤ 0 (lado direito negativo)
Primal (≤)
Ø → Forma Padrão
	Min cjxj
	SA Ax = b
	 x ≥ 0, b ≥ 0 (lado direito negativo)
Min f{cj}
Min{}
PIV
Nova solução básica
P1 → Escolher variável que deixa a base
P2 → Escolher a variável que entra na base
P3 → Encontrar a solução básica fazendo o pivoteamaneto.
Exemplo:
			Min. x1 + 5x2
	 		 SA	x1 + 2x2 ≥ 400
				2x1 + x2 ≥ 900
				x1, x2 ≥ 0
Resolução:
FP → Min. x1 + 5x2
	SA	-x1 - 2x2 + x3 = -400
		-2x1 - x2 + x4 = -900
		x1, x2, x3, x4 ≥ 0
	
	x1
	x2
	x3
	x4
	
	X3
	-1
	-2
	1
	0
	-400
	x4
	-2
	-1
	0
	1
	-900
	
	0
	3
	0
	0
	0
P1 → Variável que deixa a base.
 Min. {-400,-900}
P2 → Variável que entra na base
 Máx. {}, pode ficar denominador positivo.
P3 → Solução básica:
L1 → L1 - L2 
L2 → 
 L3 → L3- L2
	
	x1
	x2
	x3
	x4
	
	X3
	0
	3/2
	1
	-1/2
	50
	X1
	0
	1/2
	0
	-1/2
	450
	
	0
	-9/2
	0
	0
	-450
Se mínimo,
trocar
 sinal.
			FO = 800
			Variável	Custo Reduzido
			 x1 = 450		 0
			 x2 = 0		-9/2
			 Folga		 Preço Dual
			 x3 = 50	 0
			 x4 = 0	 ½
Volta → P1 Min. {50, 450} → não tem negativo, acaba aqui.
			↓
		Tem variável negativa na FO (-9/2, -450)
		Aplicar o Primal.
26-04-2010
Trabalho:
Qualquer problema PNL;
Método gradiente.