Determinar la ruta de un camión de reparto, planificar el fixture de un torneo deportivo o proyectar el recorrido que deben hacer los censistas, son algunos de los problemas de toma de decisiones que resuelve un equipo de investigadores docentes con las herramientas que ofrecen la matemática y la computación.
La técnica utilizada se llama programación lineal entera y permite modelar un problema real a partir del uso de variables, ecuaciones o inecuaciones y una determinada función a optimizar. Las variables representan las decisiones a tomar, las ecuaciones e inecuaciones grafican las restricciones existentes, como la disponibilidad de recursos o los tiempos de trabajo, mientras que la función a optimizar da cuenta del objetivo a mejorar, por ejemplo, minimizar la suma de las distancias recorridas en una ruta.
“Para optimizar el tiempo total del recorrido de un camión de reparto, las decisiones a tomar son, por ejemplo, a cuál cliente voy a visitar primero, quién es el segundo, etc., y las restricciones son que cada cliente se visita sólo una vez y que no hay que dejar clientes sin visitar”, explica el computador Javier Marenco, investigador del Instituto de Ciencias de la Universidad Nacional de General Sarmiento (UNGS) y director del proyecto.
Marenco indica que este tipo de modelos no siempre se puede resolver rápidamente ya que, en algunos casos, una computadora de última generación puede tardar hasta décadas para encontrar la solución óptima: “Se llaman problemas intratables porque la cantidad de combinaciones a analizar puede ser muy grande y no se conocen algoritmos eficientes para su resolución. Para el ejemplo de los camiones de reparto, todas las posibles permutaciones entre clientes son las posibilidades que hay que analizar. Si los clientes son cinco, el problema se resuelve en forma rápida, pero si son cuarenta, el número de combinaciones a analizar es astronómico”.
El trabajo de los científicos de esta disciplina, la investigación operativa, es acelerar los métodos que resuelven problemas expresados como modelos de programación lineal entera y en busca de la solución óptima, la garantía matemática.
En este caso para un recorrido de 40 clientes, el número “astronómico” de combinaciones posibles tiene 47 dígitos. “Si se usa la programación lineal entera, la computadora no necesita recorrer toda esa cantidad de combinaciones posibles”, comenta el investigador Diego Delle Donne, y explica que esta técnica permite saltear “soluciones que no son buenas para ir directamente a la solución óptima”.
Problemas a resolver
Los investigadores utilizan esta técnica para armar el fixture de la Liga Nacional de Vóley y también para determinar cuántos puntos necesita cada corredor de Turismo Carretera (TC) para clasificar a la Copa de Oro. “Si no hay distancias involucradas armar un fixture no es tan difícil. El problema de la liga de vóley es que los equipos están repartidos por todo el país y viajan en micro, salvo algunas excepciones”, explica Marenco, doctor en Computación. Los investigadores diseñan el fixture de esta liga desde 2007.
Para el caso de la categoría más convocante del automovilismo nacional, el equipo de investigación armó un modelo que analiza todas las combinaciones de resultados posibles que se pueden dar en las próximas carreras. “El resultado asegura con un 100% de certeza que si un piloto obtiene más de cierta cantidad de puntos, no hay ninguna combinación de resultados en la clasificación, en las series o en la final de las próximas carreras que lo deje fuera de los playoffs”, explica Delle Donne.
Diseñar el menú diario de comidas de sanatorios y comedores infantiles cumpliendo con estándares alimentarios, variedad y con el menor costo posible, es otro de los problemas que resuelven los investigadores de la UNGS con el uso de esta herramienta. “Los nutricionistas que trabajan en el sistema de comidas de los hospitales tardan horas en planificar el menú semanal que garantice una alimentación saludable y con un costo razonable. Así que empecé a averiguar más sobre este problema y su mecánica para poder resolverlo con la técnica de la programación lineal entera que venimos utilizando”, cuenta Sebastián Guala, ingeniero industrial egresado de la UNGS e integrante del equipo de investigación.
El resultado fue la planificación de un menú quincenal, 28 comidas entre almuerzo y cena, para pacientes sin restricciones alimenticias y personal hospitalario, que consta de entrada, plato principal con guarnición y postre. “Garantizamos que de todos los platos posibles, de todos los menús posibles que cumplen con los requerimientos nutricionales recomendados, el menú elegido sea además el que tiene el menor costo”, destaca Guala. El programa fue evaluado con datos reales facilitados por una nutricionista de una clínica privada del conurbano bonaerense que, de utilizar esta técnica, lograría reducir los costos del menú entre un 21 y 25 por ciento. En la actualidad, y luego de una adaptación, este programa se usa para planificar el menú de tres comedores infantiles ubicados en Don Torcuato y Bella Vista, Tamborcito, Madre Teresa de Calcuta y El Apego.
Planificar el recorrido de los censistas en 2010 en la provincia de Buenos Aires fue otro de los desafíos de los investigadores. “Este problema se conoce como segmentación de viviendas e involucra algunas restricciones sobre el recorrido del censista, por ejemplo, que tiene que ser continuo, que no puede visitar más de 40 viviendas ni menos de 32, etc.”, señala Delle Donne. Según los especialistas, la utilización de esta herramienta permitió una segmentación de viviendas uniforme y contribuyó a una división de trabajo pareja entre los censistas. Este trabajo fue realizado conjuntamente por investigadores de la UNGS, de la Universidad de Buenos Aires y de la Universidad de Chile.
Investigación básica y aplicada
La complejidad de los problemas de optimización combinatoria hace que sean muy difíciles de resolver computacionalmente, por eso se utiliza la matemática para pensar programas que encuentren una posible solución. Es por esto que la investigación operativa es una disciplina que se encuentra a mitad de camino entre la matemática y la computación.
En este tipo de investigaciones, los científicos logran hacer investigación básica y a la vez resolver problemas de la vida cotidiana. “Es muy interesante porque a veces se separa ciencia básica, de ciencia aplicada o incluso de la tecnología, como si se hiciera en ámbitos distintos. Nosotros tenemos la suerte de estar trabajando en un área en la que podemos hacer ciencia básica que al mismo tiempo resulta en una aplicación concreta”, destaca Marenco y agrega: “Aplicar esta técnica al deporte es una buena forma de que la gente conozca su existencia”.
Voces sobre ciencia y tecnología 