28 febrero, 2006

La Investigación Operativa




Este artículo está en relación con el aparecido en este weblog bajo el título LA OPTIMIZACIÓN ESA GRAN DESCONOCIDA EN EL TRANSPORTE. En esta ocasión el autor pasa repaso a todo un abanico de técnicas que bajo el paraguas de la IO van desde la optimización, los algoritmos heurísticos a las redes neuronales y otras cuantas más. Es una espléndida introducción y un resumen acertado para quien quiera introducirse en estas materias, cada vez más necesarias para resolver tanto problemas empresariales como del transporte.
Por
Angel Luis Matesanz
Dirección de Cercanías de Madrid
RENFE Operadora

En este articulo se pretende hacer un repaso rápido del estado del arte de la optimización a fin de generar en el lector una idea clara, con el fin de dar a conocer sus posibilidades de aplicación a casi todos los sectores económicos y en particular al del transporte. Para finalizar, se planteará un problema ilustrativo. Las expresiones algebraicas se han reducido al mínimo, advirtiendo que no es necesaria su lectura para una correcta comprensión del articulo.
La Investigación Operativa (IO) es la aplicación del método científico a problemas relacionados con las organizaciones y sus sistemas, a fin de obtener las decisiones que mayor beneficio den a éstas.
No es de extrañar, que la resolución de este tipo de problemas haya llamado la atención de numerosos investigadores, principalmente desde la II guerra mundial.
Sin embargo el estudio de la IO se circunscribe en España a las Facultades de Matemáticas y de Informática recientemente, y de una forma superficial en las Facultades de Economía y en las Escuelas de Ingeniería. Asimismo hay que destacar especialmente que tampoco se tiene en cuenta la IO en los programas de MBA.
Esta situación provoca que estemos en el furgón de cola en esta materia y en su aplicación en las empresas. Cualquier país de Sudamérica tiene publicado en Internet más artículos de IO que España. Qué se puede esperar de un país como España, que sigue confundiendo la Estadística con las representaciones gráficas de datos y con las encuestas preelectorales.
Señalar que los problemas de optimización se encuadran dentro de la IO.

APLICACIONES PRÁCTICAS

Algunas aplicaciones prácticas de la optimización al mundo del transporte pueden ser: determinación de rutas optimas para autobuses, selección óptima del ruteo de mercancías, carga optima de cargamentos, minimización de movimientos de carga-descarga, determinación optima del trazado de línea férreas, asignación optima de gráficos de personal, asignación óptima de vehículos a gráficos de material, determinación optima de rutas incluyendo cuando hay intercambiadores modales, y un largísimo etcétera.


PROGRAMACIÓN MATEMÁTICA (PM)

La programación matemática es un área de la matemática que se ocupa, con la generación de modelos matemáticos, de representar situaciones reales en las cuales se tiene como principal preocupación la optimización de un recurso escaso.

Ejemplo: Imaginemos que una empresa vende productos en 5 ciudades A, B, C, D, y E cuyas demandas son respectivamente 10, 20, 30, 50 y 22 unidades y se surten de 3 centros productivos P, R y S con una producción diaria de 40, 42 y 50 unidades respectivamente. Teniendo en cuenta la siguiente matriz de costes de transportes, se desea determinar cuantas unidades de cada centro de producción se deben llevar a cada ciudad, para que el coste de transporte sea mínimo. Para simplificar suponer que no son posibles los transbordos.


Matriz de coste




es decir, llevar una unidad de P a A cuesta 7

SOLUCIÓN

MODELO MATEMATICO:
MINIMIZAR: { 7*XPA + 5*XPB + 3*XPC + 1*XPD + 2*XPE +
2*XRA + 4*XRB + 10*XRC + 8*XRD + 5*XRE +
9*XSA + 6*XSB + 5*XSC + 7*XSD + 8*XSE }

RESTRICCIONES:

XPA + XPB + XPC + XPD + XPE <=40 XRA + XRB + XRC +XRD + XRE <=42 XSA + XSB + XSC + XSD + XSE <=50 XPA + XRA + XSA >=10
XPB + XRB + XSB >=20
XPC + XRC + XSC >=30
XPD + XRD+ XSD >=50
XPE + XRE + XSE >=22
Siendo todas las variables mayores o iguales a cero.

Resolviendo el anterior programa lineal tenemos que el coste mínimo es de 490 unidades, con la siguiente solución: (no existe otra mejor)

XPD=40 (llevar 40 unidades de P a D)
XRA =10 XRB =10 XRE =22 (10 de R a A, 10 de R a B y 22 de R a E)
XSB =22 XSC =30 XSD=10 (22 de S a B, 30 de S a C y 10 de S a D)



La PM dispone de métodos genéricos para resolver cualquier problema de optimización. Sin embargo cuando los problemas son muy grandes, el empleo de los referidos métodos pueden resultar ineficientes incluso con el ordenador más potente. Por este motivo han surgido una gran variedad de algoritmos con mejor eficiencia algorítmica. (Algoritmo del transporte, Kruskal, Prim, Dijkstra, Bellman-Ford, Floyd, Ramificación y Poda, etc. Como curiosidad, si no existiera el algoritmo de Dijkstra o el del Bellman-Ford la navegación por Internet sería muchísimo más lenta, ya que usan para el encaminamiento dinámico de los paquetes.


PROGRAMACIÓN HEURÍSTICA (PH)

Muchos problemas de optimización no pueden ser abordados por métodos exactos, debido a su alto grado combinatorio o por la dificultad de encontrar un modelo basado en programación matemática capaz de representar exactamente una situación real. Para situaciones de esta naturaleza surgieron métodos que pese a no encontrar la mejor solución, si encuentran una aceptable a un coste computacional bajo. Es decir, no garantizan que la solución encontrada sea la óptima (EXACTA), aunque si muy próxima a ésta en el caso que no la encuentre. Estos métodos no fueron bien vistos en los círculos matemáticos en un primer momento, sin embargo, poco a poco se han ido imponiendo como herramienta útil para resolver muchos problemas prácticos.

Se puede y debe usar PH en los siguientes casos:
1. Cuando no existe un método exacto o éste requiere mucho tiempo de computación.
2. Cuando no se necesita solución óptima.
3. Cuando los datos de partida son poco fiables.
4. Cuando se requiera una respuesta rápida aún a costa de precisión.
5. Como paso intermedio de otro algoritmo exacto.

En la década de los 80 surgieron una nueva familia de algoritmos llamados meta-heurísticos, que tienen la capacidad de ser aplicables a problemas de diversa naturaleza. Es decir, una misma plantilla algorítmica puede ser utilizada para resolver problemas de distinta naturaleza.
A continuación se enumeran algunos de ellos, advirtiendo que pese a ser muy pintorescos, son métodos totalmente consolidados y su implementación a casos prácticos pueden ser efectuados por personas con conocimientos medios de programación de ordenadores:

Recocido Simulado: Consiste en simular la técnica metalúrgica del recocido usando la mecánica estadística. Al igual que en proceso metalúrgico, el enfriamiento controlado permite generar un estado de mínima energía, siendo en nuestro caso, el óptimo del problema. Destacar que son algoritmos muy sencillos de adaptar a cualquier problema.
Búsqueda Tabú: Se basa en utilizar una memoria a corto y a largo plazo, para ir buscando la solución.
Algoritmos Genéticos: Consiste en aplicar las reglas de la evolución Darviniana a un grupo de soluciones iniciales para obtener la solución final, perfectamente “adaptada” al mundo que hemos creado. Los operadores empleados son: selección natural de progenitores, cruzamiento de cromosomas, selección natural de supervivencia y mutación.
Redes Neuronales: Son simulaciones matemáticas de los fenómenos de transferencia entre las neuronas de un cerebro de un ser vivo.
Colonias de Hormigas: Consiste en simular el comportamiento de las hormigas para encontrar el camino mas corto a la comida.
Inteligencia Artificial: conocidos también como métodos de búsqueda exhaustiva, generan de manera constructiva caminos hacia la solución óptima. Tienen la habilidad de desdoblarse entre los exacto y lo heurístico. Son los conocidos algoritmos de la ramificación y poda, los A* y los AO*, entre otros muchos.
¿CÓMO SE DEBE RESOLVER UN PROBLEMA?


En este apartado pretendo dar unas normas generales de cómo entiendo que se pueden resolver los problemas de optimización:
1. Comprender bien el problema a resolver sin olvidar ningún detalle.
2. Obtener la función objetivo o multiobjetivo del problema, junto con las ecuaciones de las restricciones, si es que tienen.
3. Resolver el programa matemático planteado en el punto 2 mediante técnicas generales de PM o especificas para ese problema si es que existen. Si esto no fuera posible, hay que recurrir a métodos no exactos:
a. Utilizando un SOLVER comercial capaz de resolver con métodos heurísticos las ecuaciones del punto 2.
b. O bien, implementando alguna técnica meta heurística, debiéndose elegir aquel que en la practica mejor funcione.


UN EJEMPLO

Para ilustrar este articulo con un ejemplo me ha parecido adecuado estudiar y resolver el siguiente problema de optimización:
“Imaginemos que tenemos que realizar 50 tareas para lo cual tenemos 15 maquinas. Además sabemos cual es el coste que nos genera usar una determinada maquina para una determinada tarea. El problema se trata de asignar cada una de las tareas a una sola maquina, teniendo además en cuenta que a ninguna maquina se la puede asignar más de m tareas, y en el caso de que a una máquina se le asigne alguna tarea no pueden ser menos de n tareas.”

Solución: las ecuaciones algebraicas a resolver son las siguientes
Minimizar

Sujeto a
j=1 .. 15 cada tarea a sólo una empresa
j=1 .. 15 m tareas como máximo a cada empresa

j=1..15 a cada empresa se le asigna un mínimo de n tareas o ninguna

1 si asignamos la tarea i a la empresa j, =0 en otro caso
Yij = 1 si a la empresa j le asignamos al menos n tareas, =0 si no le asignamos
ninguna
............................

Es decir, tenemos 45 restricciones y 765 variables binarias. Los métodos de resolución de la PM no son apropiados para resolver este tamaño de problema.
Por otra parte la ramificación y poda (RP) es capaz de resolverlo de forma EXACTA. Sin embargo pese a que este esquema algorítmico puede resolver problemas mucho más grandes, quizá podamos tener ineficiencias en función de los parámetros m y n.
Por este motivo, no podemos quedarnos solo con la RP, viéndonos obligados a
recurrir a algún algoritmo metaheurístico para este fin: en este caso he elegido el Recocido Simulado, por su facilidad de implementación.
Advertir que no recurro a ningún programa comercial de tipo Solver porque no dispongo de ninguno, a excepción del que se incluye en MS Excel, que pese a ser excelente, no es capaz de admitir tamaños de problemas como el tratado.
A continuación se expresan los resultados para diferentes valores de m y n, indicando el tiempo empleado en encontrar la solución exacta, así como el tiempo empleado en alcanzar discrepancias de ésta.
Nota: los datos de los costes con los que se hace correr al programa están diseñados para someter a los algoritmos a condiciones extremas de dificultad.
En las tablas expuestas a continuación, se figuran el tiempo de resolución de cada algoritmo en función de m y n.

Para finalizar, decir que en función de los parámetros m y n puede ser mejor uno u otro algoritmo. Asimismo, entiendo que habría que probar algún esquema genético al entender que quizá puede ser más eficiente para este problema concreto.
Tabla de soluciones

3 comentarios:

Anónimo dijo...

Sorprendente y creativo. Me sorprende la cantidad de variaciones de aplicación que se abren en el campo de la matemática y la estadística para el mundo de la empresa.

FTF dijo...

Nuestra enhorabuena al autor por su labor didáctica, de síntesis y por abrir nuevos horizontes de conocimiento práctico al complejo mundo del transporte. Esperamos nuevas colaboraciones en este sentido. Gracias.

Anónimo dijo...

Buenos dias,mi nombre es Paola, he estado leyendo y buscando sobre la secuenciación de tareas con recocido simulado para un trabajo de la Universidad y la verdad no entiendo como puedo aplicar el algoritmo. Estuve leyendo las fórmulas que aparecen en esta entrada pero no se me ocurre cual pueda ser la solución inicial, cómo se trabaja la matriz, cómo garantizo que se cumplan las restricciones? En todos lados encuentro lo mismo, hablan de la matriz y del algoritmo, pero omiten el paso de la matriz al algoritmo. Le agradezco de antemano cualquier información que me pueda brindar, mi correo es paitorv@gmail.com. Muchas Gracias!