Aula32PCVExemploGusek

Prévia do material em texto

Aula 32
Módulo 4.3 –PCV: Exemplo numérico e GUSEK by A.A.
Pesquisa Operacional II
1
Caixeiro Viajante
3
2
1
4
Percorrer todas as cidades;
1
Passar por todas 1 única vez;
2
Minimizar a distância total.
3
i
j
xij
Variáveis de Decisão
Xij = 1 se o caixeiro vai do nó i para o nó j.
xi j
Origem
(Cidade i)
Destino
(Cidade j)
Caixeiro Viajante
3
Min 
S.a.:
MODELO COMPLETO GERAL
custo para realizar percorrer a rota i-j
# nós sub-grafo
Eliminação 
sub-rotas
Caixeiro Viajante
4
1
2
3
4
5
2
1
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
Caixeiro Viajante
Distância entre a cidade 1 e a cidade 3
d13
10
Localização Facilidades
4
(x4,y4)
(x10,y10)
(y4-y10)
(x4-x10)
d4,10
d24,10 = (y4 – y10)2 + (x4 – x10)2
X
Y
d2I,J = (yI – yJ)2 + (xI – xJ)2
dI,J =  (yI – yJ)2 + (xI – xJ)2
Caixeiro Viajante
	C	X	Y
	1	2	2
	2	6	2
	3	8	7
	4	11	5
	5	13	7
Coordenadas
Distâncias
	C\C	1	2	3	4	5
	1	0,00	4,00	7,81	9,49	12,08
	2	4,00	0,00	5,39	5,83	8,60
	3	7,81	5,39	0,00	3,61	5,00
	4	9,49	5,83	3,61	0,00	2,83
	5	12,08	8,60	5,00	2,83	0,00
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
Modelo no GUSEK
Ciclos de tamanho 3: com 3 arcos
Restrições que eliminam a existência de sub-rotas !!
Caixeiro Viajante
5
10
Modelo no GUSEK
Modelo no GUSEK
1
2
3
4
5
2
1
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
Caixeiro Viajante
1
2
3
4
5
2
1
3
4
5
6
7
8
9
10
11
12
13
14
1
2
3
4
5
6
7
8
d1,4 + d4,5 + d5,3 + d3,2 + d2,1 =
9,49 + 2,83 + 5 + 5,39 + 4 = 
26,71
Caixeiro Viajante
Caixeiro Viajante
Aula 32
Módulo 4.3 –PCV: Exemplo numérico e GUSEK by A.A.
Pesquisa Operacional II
15
m
i
x
m
j
i
j
ij
,
,
1
 
,
 
1
,
1
L
=
=
å
¹
=
m
j
x
m
j
i
i
ij
,
,
1
 
,
 
1
,
1
L
=
=
å
¹
=
å
å
=
=
m
i
m
j
ij
ij
x
c
1
1
m
j
i
x
ij
,
,
1
,
,
0
1
L
=
=
 
 
 
ou
 
2
,
,
2
 
,
1
,
-
=
-
£
å
Î
S
j
i
ij
m
S
S
x
L
m
i
x
m
j
i
j
ij
,
,
1
 
,
 
1
,
1
L
=
=
å
¹
=
m
j
x
m
j
i
i
ij
,
,
1
 
,
 
1
,
1
L
=
=
å
¹
=
2
,
,
2
 
,
1
,
-
=
-
£
å
Î
S
j
i
ij
m
S
S
x
L