Simulacion

INTRODUCCIÓN

La simulación es un método por el cual se puede probar o experimentar o ver qué sucede en determinado proceso, escenario u objeto sin el riesgo que haya consecuencias reales. Luego permite comparar diferentes soluciones ante un problema, probarlas y ver cuál es la mejor, posteriormente, se podría aplicar esa solución que funcionó adecuadamente en la simulación, en el mundo real y esperar que las consecuencias que el modelo de simulación mostró, sean las mismas en el mundo real. Es por ese motivo que cuando se planea una simulación, ésta debe ser lo más realista posible o acercarse lo suficiente a lo que sucede en la realidad.

DEFINICIÓN DEL SISTEMA

El problema del viajero es un ejemplo que muestra y analiza la problemática que subyace tras algunos tipos de problemas matemáticos que a priori parecen tener una solución relativamente sencilla, y que en la práctica presentan un gran problema. Es uno de los problemas más famosos en el campo de la optimización combinatoria conceptual. Se conoce la forma de resolverlo pero solo en teoría, en la práctica la solución no es aplicable debido al tiempo que computacionalmente se precisa para obtener su resultado. Así, como este, existen unos problemas cuya solución determinística es muy costosa porque requiere una gigantesca cantidad de cálculos que aun hechos por veloces computadoras tardarían mucho tiempo en resolver.

MARCO TEORICO

El problema del viajero, es un problema de optimización, y de los más interesantes de este conjunto de problemas. Este problema se refiere a la tarea de encontrar una ruta con el menor costo posible dado un conjunto de ciudades, sin visitar una ciudad en más de una ocasión.

La primera noticia que se tiene del problema del viajero data del año 1831 en Alemania. Un libro fue publicado y titulado “El agente viajero”, en donde se hacia la pregunta: ¿Cómo debe ser un viajero y que debe hacer para optimizar su viaje?

El estudio del problema del viajero ha interesado a investigadores de diversos campos, como matemáticas, investigación de operaciones, biología, por nombrar algunos. Esto debido a que muchas aplicaciones pueden ser modeladas a través de este problema o como una variable de este. Este ejercicio presenta todos los aspectos de los problemas de optimización por lo que sirve como base para nuevas propuestas algorítmicas.

OBJETIVO GENERAL

Analizar y simular uno de los problemas más conocido en el campo de la optimización combinatoria conceptual, de tal forma que gracias al estudio realizado se pueda obtener una solución lo más real posible.

OBJETIVOS ESPECIFICOS

 Recolectar la información necesaria acerca del problema del viajero investigando el concepto y todas las variables que intervienen en el sistema.

 Analizar toda la información abarcada para tomar la decisión de cuál es la mejor forma de afrontar el problema.

 Desarrollar la simulación procurando dejar el mínimo rango de acciones al azar para asi tener una simulación confiable y lo más real posible.

DEFINICIÓN DEL SISTEMA A SIMULAR

Dado un conjunto finito de ciudades, donde hay costo para ir de una ciudad a otra, hallar la secuencia de visita de todas esas ciudades, de tal manera que solo se visite una sola vez cada ciudad, al menor costo posible. Para comprender mejor el problema, se tiene en cuenta la siguiente matriz la cual indica el costo de ir de una ciudad a otra.

Ciudad A B C D E F G H I J

A 0 6 34 65 11 13 20 19 61 41

B 6 0 21 8 51 6 30 23 24 34

C 34 21 0 41 21 9 27 41 10 22

D 65 8 41 0 18 63 63 19 56 6

E 11 51 21 18 0 12 46 61 20 17

F 13 6 9 63 12 0 53 53 61 53

G 20 30 27 63 46 53 0 41 19 31

H 19 23 41 19 61 53 41 0 7 61

I 61 24 10 56 20 61 19 7 0 20

J 41 34 22 6 17 53 31 61 20 0

Esta matriz permite tener en cuenta el costo que se tiene para viajar de una ciudad a otra.

Este problema del viajero es asimétrico ya que trata de un grafo en el que el costo de viajar del punto A al punto B no es necesariamente el mismo que de viajar del punto B al punto A.

VARIABLES DEL SISTEMA

Los modelos que se toma en la simulación van a servir de guía y para averiguar qué pasaría en el problema si se dieran n unas rutas aleatorias que sirvan de hipótesis para el comienzo de la simulación:

Se tomaron las siguientes rutas aleatorias:

E – A – D – C – J – G – B – I – F – H

Ruta desglosada Valor

E-A $ 11

A-D $ 65

D-C $ 41

C-J $ 22

J-G $ 31

G-B $ 30

B-I $ 24

I-F $ 61

F-H $ 53

Total $ 338

A – B – F – C – I – H – D – E – J – G

Ruta desglosada Valor

A-B $ 6

B-F $ 6

F-C $ 9

...