Dossiê 3_PO

Prévia do material em texto

3º Etapa
19-05-2010
24-05-2010
3º Trabalho:
Valor: 5 pontos;
Tema: Simulated Annealing.
Resumo do método (07/06/10);
Implementação manual e computacional.
Proposta problema (07/06/10);
Resultados (14/06/10)
Trabalho opcional
Valor: 5 pontos extra;
Implementação manual e computacional: otimização multiobjetiva.
Exercício avaliativo realizado em sala de aula e entregue ao professor:
Resolver PPL Simplex de 2 fases:
Min. x1 + x2 + x3
	SA	2x1 + 3x2 ≤ 200
		2x1 + 3x2 ≥ 100
		x2 + 4x3 ≥ 240
		x1, x2, x3 ≥ 0
Min. x1 + x2 + x3
	SA	2x1 + 2x2 + x4 = 200
		2x1 + 2x3 – x5 = 100
		X2 + 4x3 – x6 = 240
		x1, x2, x3 ≥ 0
Min. x1 + x2 + x3				xa1 + xa2 + xa3
	SA	2x1 + 2x2 + x4
		2x1 + 2x3 – x5 + xa1
		X2 + 4x3 – x6 + xa2
		x1, x2, x3 ≥ 0
	
L1
	x1
	x2
	
 Coluna 
Pivotalx3
	
 Pivôx4
	x5
	x6
	xa1
	xa2
	
	x4
	2
	3
	0
	1
	0
	0
	0
	0
	200
	
L3
L2xa1
	2
	0
	2
	0
	-1
	0
	1
	0
	100
	
L4xa2
	0
	1
	4
	0
	0
	-1
	0
	1
	240
	
L5
	1
	1
	1
	0
	0
	0
	0
	0
	0
	
L nova
	0
	0
	0
	0
	0
	1
	1
	1
	0
	
	-2
	-1
	-6
	0
	1
	1
	0
	0
	-340
VB
L5 = L5 – L2 → -2 0 -2 0 1 0 :0 1 │-100
L5 = L5 – L3 → -2 -1 -6 0 1 1 :0 0 │-340
P1 → min {-2, -1, -6, 0, 1, 1}
P2 → min {}
L1 = L1
L2 = 
L3 = L3 - x L2
 Coluna 
PivotalL4 = L4 - x L2
 PivôL5 = L5 – x L2
	
	x1
	x2
	x3
	x4
	x5
	x6
	xa1
	xa2
	
	x4
	2
	3
	0
	1
	0
	0
	0
	0
	200
	x3
	1
	0
	1
	0
	-1/2
	0
	1/2
	0
	50
	xa2
	-4
	1
	0
	0
	2
	-1
	-2
	1
	
F. principal40
	
	0
	1
	0
	0
	0,5
	0
	-0,5
	0
	
F. artificial-50
	
	4
	-1
	0
	0
	-2
	1
	3
	0
	-40
P1 → min {-1, -2}
P2 → min {}
L1 = L1
L2 = L2 - x L3
L3 = 
L4 = L4 – x L3
L5 = L5 – x L3
	
	x1
	x2
	x3
	x4
	x5
	x6
	xa1
	xa2
	
	x4
	2
	3
	0
	1
	0
	0
	0
	0
	200
	x3
	0
	0,25
	1,25
	0
	0
	-0,25
	0
	0,25
	60
	X5
	-2
	0,5
	0
	0
	1
	-0,5
	-1
	0,5
	
F. principal20
	
	1
	0,75
	0
	0
	0
	0,25
	0
	-0,25
	
F. artificial-60
	
	0
	0
	0
	0
	0
	0
	1
	1
	0
			FO = 60
			Variável	Custo Reduzido
			 x1 = 0		 1
			 x2 = 0		0,75
			 x3 = 0		 0
			 Folga		 Preço Dual
			 x4 = 50	 0
			 x5 = 0	 0
			 x6 = 0	 0,25
31-05-2010
Otimização Combinatória
I- Caminho mínimo
Variáveis
x12
є
 = {0
,1
}x13
x24
x34
PPL
Min. Z = 5x12 + 3x13 + 2x24 + 2x34
	SA	x12 + x13 = 1
		x12 = x24
		x13 = x34
		x24 + x34 = 1
		x12, x13, x24, x34 є {0,1}, onde: 0 não faz o percurso e 1 faz o 							 percurso.
Ótimo
z* = 7
x*12 = 1 = x*24
x*13 = 1 = x*34
II- Método DIJKSTRA
F = {1}, nós fechado
A = {2,3,4}, nós abertos
C = Custo = {C(2), C(3), C(4)}
C = {5, 3, ∞}. ∞ → porque não tem caminho direto.
Escolha min {Ck}, k є A}
	
Atualizar Ci
C(i) = min {C(i), C(k), dki}
Voltar ao I.
Exemplo:
	Iteração
	F
	C(2),A
	C(3), A
	C(4),A
	0
	1
	5,1
	3,1
	∞
	1
	1,3
	5,1
	-
	9,3
	2
	1,3,2
	-
	-
	7,2
	3
	1,3,2,1
	-
	-
	-
Iteração 1
Atualizar (1)
C(2) = min {5,3+∞}
C(4) = min {∞,3+6}
Atualizar (2)
C(4) = min {9,5+2}
C*=7 Retroprogração 4 ← 2 ←1
Exercício
I- F = {1}
 A = {2,3,4,5}
 C = Custo = {C(2), C(3), C(4), C(5)}
 C = {5,2,4,5}
	Iteração
	F
	C(2),A
	C(3), A
	C(4),A
	0
	1
	2,1
	∞
	∞
	1
	1,3
	-
	∞
	9,3
	2
	1,3,2
	-
	6,2
	7,2
	3
	1,3,2,4
	-
	-
	7,4
	4
	1,3,2,4,5
	-
	-
	-
1- Atualização
C(2) = min{5,2+2} = 4
C(4) = min{∞,2+∞} = ∞
C(5) = min{∞,2+7} = 9
2- Atualização
C(4) = min{∞,4+2} = 6
C(5) = min{9,4+3} = 7
3- Atualização
C(5) = min{7,6+4} = 7
02-06-2010
Dualidade
Duais Assimétricas
a) Max. Ctx				b) Max. Ctx
 SA	Ax = b				 SA	Ax = b	
	X ≥ 0					X ≥ 0
Tem como o PPL			Tem como o PPL
 Min. Zd = btx			 Min. Zd = btµ
 SA	Atx ≥ C			 SA	Atµ ≥ C
					 µ ≥ 0
Obs.: µ é variável livre. O µ no simétrico deve ser ≥ 0.
Exemplo:
Encontrar o PPL dual do problema:
Max. Z = 3x1 + x2
 SA 2x1 + x2 = 18
	 x1 + 2x2 = 21
	 x1, x2 ≥ 0
Solução
Pela propriedade de duais assimétricas, temos
Min. Zd = 18µ1 + 21µ2
	 2µ1 + µ2 ≥ 3
	 µ1 + 2µ2 ≥ 1
Simplex
Max. Z = 3x1 + x2
 SA 2x1 + x2 = 400
	 x1 + 2x2 ≤ 500
	 x1, x2 ≥ 0
Forma Padrão
Min. - 3x1 - x2
SA 2x1 + x2 + xa1 = 400
 x1 + 2x2 + x3 = 500
Min. Fa = xa1 (função para desaparecer a variável artificial, se tiver mais variáveis some-os).
Quadro Simple Tableux
	VB
	x1
	x2
	x3
	xa1
	
	xa1
	2
	1
	0
	1
	400
	x3
	1
	1
	1
	0
	500
	
	-3
	-1
	0
	0
	0
	
	0
	0
	0
	1
	0
	
	-2
	-1
	0
	0
	-400
Pivoteamento inicial
L4 = L4 – L1 [-2 -1 0 0 -400] (para zerar o 1).
1a) Iteração
Variável extra base
Min {-2,-1} = -2 → x1
Variável sai da base
Min {} = → xa1
Pivoteamento
L1 = 
L2 = L2 - x L1
L3 = L3 - x L1
L4 = L4 – x L1
Quardro Simples Tableaux
	VB
	x1
	x2
	x3
	xa1
	
	X4
	1
	1/2
	0
	1/2
	200
	x3
	0
	1/2
	1
	1/2
	300
	
	0
	1/2
	0
	3/2
	600
	
	0
	0
	0
	1
	0
2a) Iteração
Iniciar a 2a fase – tirar a linha artificial
	VB
	x1
	x2
	x3
	xa1
	
	X1
	1
	1/2
	0
	1/2
	200
	x3
	0
	1/2
	1
	-1/2
	300
	
	0
	1/2
	0
	3/2
	600
Min FO primal
FO = 600
Variável	Custo Reduzido
x1 = 200		 1
 x2 = 0			1/2
Folga		 Preço Dual
 0	 3/2
X3 = 0	 0
09-06-2010
Programação Inteira (PPI)
Max. Z = 6x1 + 5x2
 SA x1 + 2x2 ≤ 10
	 3x1 + x2 ≤ 12
	 x1, x2 ≥ 0 e interior
Simplex
	
	
	
	
	
	
	
	0
	1
	3/5
	-1/5
	18/5
	
	1
	0
	-1/5
	2/5
	14/5
	
	0
	0
	9/5
	7/5
	174/5
Obs. Só as variáveis físicas podem ser fracionadas.
Gomory
P1 - Selecionar variável fracionária. Sua equação:
x1 - x3 + x4 = 
P2 - Escrever cada coeficiente fracionário como soma de um inteiro e uma fração (0,1):
x1 – (-1 + )x3 + (0 + )x4 = 2 + 
Escreva 1º membro só com os termos fracionários:
 x3 + x4 - = -x1 + x3 + 2
P3 - Exigir primeiro membro seja não negativo:
x3 + x4 - ≥ 0 ou 4x3 + 2x4 ≥ 4
Levar a desigualdade para o simplex:
	
	
	
	
	1
	1
	3/5
	0
	15/5
	
	0
	0
	-1/5
	0
	14/5
	
	0
	0
	4
	1
	4
	
	0
	0
	7/5
	0
	174/5
	
	0
	0
	0
	1
	0
	
	x1
	x2
	x3
	x4
	xa1
	
	
	1
	1
	3/5
	-1/5
	0
	18/5
	
	0
	0
	-1/5
	2/5
	0
	14/5
	
	0
	0
	4
	2
	1
	4
	
	0
	0
	9/5
	7/5
	0
	174/5
	
	0
	0
	0
	0
	1
	0
Solução ótima: z* = 33, x*1 = 3x*2, x*2 = 3, x*3 = 1, x*4 = 0.