Problemas de Rota e Distância

Prévia do material em texto

1) (Caminho mínimo) Considere que os números indicados em cada aresta significam o número de quilômetros necessários para um automóvel percorrer a estrada entre duas cidades indicadas pelos nós extremos das arestas observadas. Monte o modelo que determine a rota que um automóvel deve seguir para sair de Chapecó e chegar a Porto Alegre, percorrendo a menor quantidade de quilômetros possível. Resposta 2450
2) (CAMINHO MÍNIMO) Um fornecedor de alimentos localizado em Osasco entrega salgados e doces diariamente para uma padaria localizada na região da Vila For mosa, em São Paulo. Para isso, o motorista pode percorrer mais de um caminho, passando por diferentes bairros em São Paulo. A Figura apresenta os possíveis caminhos que o veículo pode percorrer, do nó de oferta (Osasco) para o nó de demanda (Vila For mosa), além das distâncias em quilômetros entre os nós ou bairros. Formule o problema do caminho mais curto estudado. (resposta: MinZ = 24)
3) [Problema de Caixeiro viajante] Um caixeiro viajante tem que percorrer um conjunto de cidades de tal modo que percorra todas as cidades sem passar duas vezes pela mesma cidade. Pretende-se minimizar a distância percorrida. Apresenta-se de seguida o mapa. Complete a tabela e calcule o caminho com a menor distância (R:32)
	
	A
	B
	C
	D
	E
	A
	-
	7
	6
	10
	7
	B
	7
	-
	7
	10
	10
	C
	6
	7
	-
	5
	9
	D
	10
	10
	5
	-
	6
	E
	7
	10
	9
	6
	
4) [Problema de Caixeiro viajante] Um transportador tem que percorrer um conjunto de cidades de Santa Catarina de tal modo que realize todas sem passar duas vezes pela mesma Cidade. Pretende-se minimizar a distância percorrida. Segue a tabela com a distância entre as origens e os destinos (R: 1428)
	0
	Chapeco
	Concordia
	Cacador
	Lages
	Joinville
	Bal.Camboriu
	Brusque
	Florianopolis
	Tubarao
	Criciuma
	Chapeco
	0
	80
	207
	310
	490
	514
	496
	531
	511
	490
	Concordia
	80
	0
	154
	231
	437
	435
	416
	451
	431
	417
	Cacador
	207
	154
	0
	170
	298
	325
	306
	353
	366
	359
	Lages
	310
	231
	170
	0
	288
	251
	213
	255
	202
	192
	Joinville
	490
	437
	298
	288
	0
	94
	115
	180
	297
	347
	Bal.Camboriu
	514
	435
	325
	251
	94
	0
	41
	85
	202
	252
	Brusque
	496
	416
	306
	213
	115
	41
	0
	96
	214
	243
	Florianopolis
	531
	451
	353
	255
	180
	85
	96
	0
	139
	189
	Tubarao
	511
	431
	366
	202
	297
	202
	214
	139
	0
	50
	Criciuma
	490
	417
	359
	192
	347
	252
	243
	189
	50
	0
image3.emf
image1.png
image2.png