Page 28 - UMH Sapiens 24

a profesora del Centro de Investigación
Operativa de la Universidad Miguel Her-
nández (UMH) de Elche Mercedes Lan-
Ldete define los problemas de optimiza-
ción como aquellos que se pueden describir
con variables matemáticas, en los que hay
una función muy clara que se quiere minimizar
o maximizar (la distancia total recorrida), ade-
más de unas condiciones que se tienen que
cumplir (en este caso que el viajante visite to-
das las ciudades al menos una vez y regrese
al punto de origen). En este tipo de problemas
puede haber un conjunto de soluciones finito:
por ejemplo, en el caso clásico descrito del
viajante de comercio, donde dependiendo de
las ciudades se establecerán una serie de
posibles rutas determinadas. Pero también
puede que se trate de un conjunto de solu-
ciones infinitas si, en el enunciado, el viajante
no solo debe visitar las localizaciones estable-
cidas, sino que también necesita transportar
mercancías, de manera que entra en juego la Mercedes Landete
variable del peso que puede cargar el camión
de reparto de acuerdo a su espacio.
Profesora del Centro de Investigación
Asimismo, las variables también pueden ser Operativa UMH
de otro tipo. Por ejemplo, puede tratarse del
horario, si se piensa en un escenario en el que
el vehículo debe cambiar de conductor cada
cierto número de horas al volante. Y todavía todos para resolverlo resultan más sencillos. canza, podemos decir que ya ha encontrado el
se puede complicar más si a esta circunstan- “Así que nuestro objetivo será siempre intentar conjunto de soluciones”, todo esto explicado
cia de conductores que solo pueden estar al escribirlo como un problema de optimización de una manera muy básica, matiza la experta.
volante un cierto número de horas se le añade lineal, para usar el método de resolución más
que, además, los trabajadores deban terminar cómodo”, señala la experta. Google Maps
su jornada cerca de casa. En este caso, se Un ejemplo de aplicación diaria de este tipo
trata de un problema similar al que se enfren- de problemas se encuentra en Google Maps,
tan los matemáticos que deben, a través de El algoritmo que permite calcular una distancia entre dos
algoritmos, establecer las diferentes rutas de puntos y atiende a diferentes variables de
vuelo en un aeropuerto. de reparto es acuerdo a cómo se quiere recorrer la ruta, si
de la manera más rápida o de la manera más
El algoritmo de reparto es el conjunto de ór- el conjunto de barata, sin pasar por peajes. Se trata de un
denes consecutivas que lleva a resolver el ejemplo en el que el usuario tiene que tomar
problema y pueden ser exactos o inexactos o órdenes con- decisiones que influyen en la solución. Si se
heurísticos. “Si por ejemplo estamos hablan- atiende al conjunto de soluciones posibles en
do de una solución de vuelos en la que vas secutivas que el escenario de las rutas entre ciudades, lo
a necesitar una hora para calcular todas las lógico a priori en lugar de empezar por una so-
opciones, pero solo se dispone de dos minu- lleva a resolver lución al azar, parece ser ir del punto inicial
tos, entonces basta con obtener soluciones al punto más cercano y así sucesivamente.
que sean lo suficientemente buenas”, explica el problema Según la experta, al actuar de esta forma se
Landete. Y añade: “Puede que lo óptimo sea puede alcanzar una buena solución inicial y
que todos los pilotos trabajen 6 horas y 36 a partir de ahí se sigue perfeccionando el al-
minutos y vuelvan a sus hogares. Pero para goritmo para llegar al conjunto de resultados
encontrar la solución en la que todos trabajen A su vez, los problemas de optimización se óptimos. A medida que aumenta el número de
6 horas y 36 minutos quizá se necesite mucho sirven de la teoría de grafos y de la teoría de ciudades que se deben visitar, aumentan ex-
tiempo y como los pilotos se ajustan a trabajar poliedros para representar el conjunto de solu- ponencialmente las permutaciones posibles
menos de 8 horas, en menos tiempo puedo ciones posibles. Los grafos son conjuntos de (cada ruta es una permutación). Por ejemplo,
encontrar esa solución que, no es exacta, pero objetos, llamados vértices o nodos, unidos por para 30 ciudades hay una enorme cantidad de
sí buena y rápida”, puntualiza. Esta solución aristas que permiten representar relaciones rutas posibles y de ahí deriva la importancia
recibe el nombre de heurística. binarias entre elementos de un conjunto. En de que existan técnicas de optimización.
los poliedros son los planos los que represen-
Los algoritmos de optimización combinatoria tan cada condición dada. Landete señala: “Si Variaciones del problema
resuelven este tipo de problemas a través pensamos en el poliedro como una caja de so- El problema del viajante se complica a medida
de la exploración de un gran conjunto de so- luciones y en el algoritmo como el conjunto de que se añaden condiciones. “Imagínate que
luciones posibles. Como señala Landete, la instrucciones dadas, podemos imaginar cómo voy recogiendo cualquier producto, pongamos
forma en la que surgen soluciones para estos el algoritmo se aproxima al poliedro escanean- leche, vino y huevos y que, a su vez, los voy
problemas de optimización es a través de la do los diferentes planos hasta alcanzarlo. Y en entregando a otros sitios porque tengo mi pe-
programación lineal (carece de exponentes ese trabajo es donde el algoritmo consume el queña cooperativa de granja y la ruta la tengo
y raíces cuadradas). Cuando el problema es mayor tiempo: se aproxima muy despacio al calculada para que sea la más óptima: la más
posible representarlo de esa manera, los mé- poliedro para no pasárselo. Y una vez que lo al- barata y la más rápida. Pero de pronto, me lla-

28 umhsapiens