Operaciones En Acción (Heurística)

Tabla de Contenido

Introducción Página 3

Objetivos Página 4

Operaciones en Acción (Heurística) Página 4

Conclusiones Página 5

Bibliografía Página 5

Introducción

La ciencia de la toma de decisiones, mejor conocida como Investigación de Operaciones (lO), nació hace ya más de cincuenta años cuando George Dantzig inventó el método Simplex para resolver problemas de optimización lineal, es decir, problemas cuyas variables de decisión son continuas y relacionadas de manera lineal. Aun cuando en sus orígenes, esta naciente área de la ciencia fue motivada por aplicaciones de carácter militar, a 10 fue alcanzando un alto grado de interés entre y profesionistas en los campos de investigadores matemáticas aplicadas y administración, ingeniería, quienes motivados por los diversos y complejos problemas de toma de decisiones que surgían en varias áreas del quehacer científico e industrial, comenzaron a estudiar y desarrollar metodologías de solución para problemas de diferentes características.

Fue así como nacieron posteriormente las ramas de optimización no lineal (relación no lineal entre las variables de decisión), optimización discreta (variables enteras) optimización entera mixta (en variables continuas discretas), por mencionar algunas.

TSP, por sus siglas en inglés; Traveling Salesperson Problem), el cual es un problema clásico de optimización combinatoria, una de las subdisciplinas de la investigación de operaciones (IO). Señalamos cómo las aplicaciones de IO se encuentran en prácticamente todos los niveles y en todo tipo de industrias, y cómo una utilización adecuada de las técnicas de IO dándole soporte al complejo proceso de toma de decisiones que enfrentan las empresas, puede tener un impacto económico significativo.

Como una de las características del TSP es el de pertenecer a una clase de problemas muy difíciles de resolver, es decir, hallar la solución óptima, en la práctica es muy común el utilizar algoritmos de aproximación (heurísticas) para obtener soluciones factibles de alta calidad (relativamente cercanas al óptimo) en tiempos de ejecución relativamente pequeños.

Objetivos

El objetivo es encontrar la solución para problemas de TSP mediante el uso de algoritmos para encontrar la mejor solución y poder probar que esa es la solución más factible.

Operaciones en Acción (Heurística)

El TSP, uno de los problemas clásicos de optimización, se formula de la siguiente manera.

Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida. Un recorrido con estas características, es llamado dentro de este contexto un lour.

El problema consiste en encontrar el tour para el cual la distancia total recorrida sea mínima. Se asume que se conoce, para cada par de ciudades, la distancia entre ellas. La Figura 1 ilustra un tour en una instancia de

...