Problema del agente viajero
description
Transcript of Problema del agente viajero
![Page 1: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/1.jpg)
INVESTIGACIÓN DE OPERACIONES
Tema: Problema del Agente Viajerofcq
![Page 2: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/2.jpg)
Problema del Agente Viajero
En el Problema del Agente Viajero, el objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta.
![Page 3: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/3.jpg)
Problema del Agente ViajeroAlgoritmo Base:
Definir el número de nodos, su posición y el costo por cada arista (i, j) donde i = ciudad 1 y j = ciudad 2
Elegir el nodo inicial iHacerSi el nodo más cercano no se ha visitadoVisitar nodo jActualizar lista de nodos visitadosCosto_total = costo_total + costoijNodo i = nodo jHasta haber visitado todos los nodos
![Page 4: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/4.jpg)
Problema del Agente Viajero
Modelo del agente viajero:
![Page 5: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/5.jpg)
Problema del Agente Viajero
Modelo del agente viajero:
![Page 6: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/6.jpg)
Problema del Agente ViajeroEjemplo 1:Un estudiante tiene que visitar 4 bibliotecas las cuales se representan A-B-C-D.
Y su punto de partida es la cuidad o nodo A.
¿Qué ruta debe seguir para que el costo sea mínimo?
La distancia entre los puntos es:A-B=7 B-C=10A-C=9 B-D=4A-D= 8 C-D=15
![Page 7: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/7.jpg)
Problema del Agente Viajero
Se representa mediante el grafo siguiente:
![Page 8: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/8.jpg)
Problema del Agente Viajero
Esta solución se trata de checar todos los caminos posibles.En este ejemplo nos dice que el punto de partida es de la cuidad A .Ya que tenemos todos los caminos posibles eliminamos los inversos, ya que es lo mismo y es perdida de tiempo también andar checándolos.:
![Page 9: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/9.jpg)
Problema del Agente Viajero
Ahora de los 3 caminos inversos, sustituimos por los valores que representa cada distancia de un nodo a otro. Y lo calculamos, el camino que sea menor, eses es la trayectoria que andamos buscando
![Page 10: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/10.jpg)
Problema del Agente ViajeroEjemplo 1:Un estudiante tiene que visitar 4 bibliotecas las cuales se representan A-B-C-D.
Y su punto de partida es la cuidad o nodo A.
¿Qué ruta debe seguir para que el costo sea mínimo?
La distancia entre los puntos es:A-B=7 B-C=10A-C=9 B-D=4A-D= 8 C-D=15
![Page 11: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/11.jpg)
Problema del Agente ViajeroEjemplo 2:
![Page 12: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/12.jpg)
Problema del Agente Viajero
![Page 13: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/13.jpg)
Problema del Agente Viajero
![Page 14: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/14.jpg)
Problema del Agente Viajero
![Page 15: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/15.jpg)
Problema del Agente Viajero
¡Ejercicio!Un repartidor de mercancías tiene encargos en varias ciudades, las cuales se representan A-B-C-D-E, y debe iniciar en la cuidad A¿Qué ruta debe seguir para que el costo sea mínimo?Las distancias son:A-B=7 A-E=20 B-E=11 D-E=17A-C=9B-C=10 C-D=15A-D=8 B-D=4 C-E=5
![Page 16: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/16.jpg)
Problema del Agente Viajero
Se representa mediante el grafo siguiente:
![Page 17: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/17.jpg)
Problema del Agente Viajero
Se obtienen los caminos posibles:
![Page 18: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/18.jpg)
Problema del Agente Viajero
Ahora vamos a eliminar lo inversos.Estos son los caminos que nos quedaron después de eliminar los inversos y sustituyendo los valores de las distancias dadas.
A-B-D-C-E-A=7+4+15+5+20=51A-B-D-E-C-A=7+4+17+5+9=42A-B-C-D-E-A=7+10+15+17+20=69A-B-E-D-C-A= 7+11+17+15+9=59A-D-C-B-E-A=8+15+10+11+20=64A-D-C-E-B-A=8+15+5+11+7=46A-D-E-B-C-A=8+17+11+10+9=55A-D-E-C-B-A=8+17+5+10+7=47A-D-B-C-E-A=8+4+10+5+20=47A-D-B-E-C-A=8+4+11+5+9=37A-C-D-B-E-A=9+15+4+11+20=59A-C-B-D-E-A=9+10+4+17+20=60
![Page 19: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/19.jpg)
Problema del Agente Viajero
Representación del grafo:
![Page 20: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/20.jpg)
Problema del Agente Viajero
Representación del grafo:
Como nos podemos dar cuenta el más optimo es el de 37 kilómetros de distancia.
![Page 21: Problema del agente viajero](https://reader033.fdocumento.com/reader033/viewer/2022061404/5695d19c1a28ab9b02973419/html5/thumbnails/21.jpg)
Bibliografía/Referencias
Taha, Hamdy A. Investigación de operaciones. 7a. edición. México: Pearson Educación, 2004.ISBN 970-26-0498-2
http://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html
http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigación-de-operaciones/problema-del-agente-viajero-tsp/