Investigacion De Operaciones En Accion

Investigación de Operaciones en Acción:

Aplicación del TSP en Problemas de Manufactura y Logística 1. Introducción

La ciencia de la toma de decisiones, mejor conocida como Investigación de Operaciones (IO), 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, la IO fue alcanzando un alto grado de interés entre investigadores y profesionistas en los campos de ingeniería, matemáticas aplicadas y administración, quienes motivados por los diversos y complejos problemas de toma de decisiones que surgían en varias áreas del qué hacer 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) y optimización entera mixta (en variables continuas y discretas), por mencionar algunas.

Aplicaciones de IO se encuentran en prácticamente todos los niveles y en todo tipo de industrias. Es evidente que las corporaciones aspiran a tomar decisiones que les reditúen en beneficios económicos, y normalmente, estas decisiones se encuentran restringidas de forma muy compleja. Estos atributos son únicos de modelos de IO. En las últimas décadas el impacto de IO en la industria ha sido impresionante, convirtiéndose en ganancias (o ahorros) con frecuencia multimillonaria en los diversos ramos industriales.

El presente pretende introducirnos con problemas y metodologías de I.O. (clásicas y recientes) y cómo estas se usan para resolver problemas reales que surgen en los diversos campos de la ciencia: ingeniería química, ingeniería civil, ingeniería eléctrica, administración, economía, ciencias computacionales, estadística y matemáticas aplicadas entre otras. Así mismo se pretende ilustrar la importancia de saber evaluar las ventajas y desventajas que surgen entre la obtención de soluciones de alta calidad contra los recursos empleados para obtenerla (tiempo de cómputo, requerimientos de memoria). Tratamos un problema clásico de IO como lo es el Problema del Agente Viajero (TSP, por sus siglas en inglés: Traveling Salesperson Problem) y su aplicación para resolver el problema de programación de tareas que se presenta en la manufactura, y el del ruteo de vehículos en el ramo de la logística.

2. Qué es el TSP

El TSP [1], 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 tour. 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 ocho ciudades

El problema en sí es fácil de formular. Sin embargo, al igual que muchos otros que se presentan en el campo de optimización, es sumamente difícil de resolver (por resolver, nos referimos a encontrar la solución óptima al problema y probar desde luego que ésta es efectivamente la mejor solución posible). El establecer cuándo un problema es “fácil” o “difícil” (la cual es una de las áreas más importantes en los campos de optimización y computación) está íntimamente ligado al tiempo de solución del problema. Sin entrar en detalles técnicos, decimos que un problema es “fácil” de resolver cuando es posible encontrar un algoritmo (método de solución) cuyo tiempo de ejecución en una computadora crece de forma “razonable” o moderada (o polinomial) con el tamaño del problema.

Por el contrario, si no existe tal algoritmo decimos que el problema es “difícil” de resolver. Esto no

implica que el problema no pueda resolverse, sino que cada algoritmo existente para la solución del problema tiene un tiempo de ejecución que crece explosivamente (o exponencialmente) con el tamaño del problema. La consecuencia directa de un algoritmo que tiene una función de tiempo exponencial es que a medida que aumenta el tamaño del problema, el tiempo requerido para la solución aumenta de forma exponencial, lo cual limita bastante el tamaño de problemas que pueden resolverse en las computadoras modernas. Técnicamente hablando, determinar si un problema es fácil o difícil se denomina establecer la complejidad computacional del problema, y esto es todo un arte, especialmente para demostrar que un problema es de los difíciles.

Veamos un ejemplo. Supongamos que tenemos una instancia del TSP con n ciudades. Una forma (poco inteligente) de resolverlo es por enumeración exhaustiva. Es decir, formamos todas las posibles combinaciones de tours (en este caso (n-1)!, donde n! = n(n-1)(n-2)…(2)(1) ) y calculamos la distancia total para cada tour, eligiendo aquel que tenga la mínima distancia total. En este caso el problema ha quedado totalmente resuelto porque estamos exhibiendo todos los tours posibles. El tiempo de ejecución de este algoritmo es a grosso modo f(n)=(n)! Esta forma, como puede verse, deja de ser viable una vez que consideramos conjuntos de ciudades mayores. En el caso n=5, por ejemplo, tenemos que calcular 4!=24 tours lo cual puede hacerse en fracción de segundos en cualquier computadora. Al considerar un conjunto con n=50 ciudades, el número posible de tours es 49!, el cual es un número tan gigantesco que no alcanzaría a resolverse en varios meses ni en las computadoras más potentes de hoy en día. Hay que notar que la función factorial f(n)=n! es una función que crece exponencialmente a medida que crece el valor de n. Claro, esto no prueba que el TSP es difícil, ya que muy bien pudiera existir otro algoritmo que lo resolviera cuyo tiempo de ejecución fuera polinomial.

En este caso, sin embargo, ya se ha demostrado que tal algoritmo polinomial no existe y que el TSP pertenece a esa clase de problemas difíciles. La Figura 2) ilustra las diferencias de crecimiento de diferentes funciones de tiempo (columnas). Las cifras que se muestran son tiempo de procesamiento en computadora que procesa 1 millón de operaciones de punto flotante por segundo. Nótese el crecimiento explosivo de las funciones exponenciales (últimas dos columnas).

...