Dos siglos y medio de transporte óptimo

¿Reconoce a las personas representadas en esta figura? Normalmente no, pues esas personas… ¡no existen! Estos retratos han sido generados automáticamente por un código informático —una red neuronal—, entrenado para poder crear tantos retratos como se desee. Una de las herramientas utilizadas para entrenar esta red neuronal es el transporte óptimo. Esta teoría matemática, que se remonta a más de dos siglos, resulta muy útil en el pujante ámbito de la ciencia de datos. La física, la economía o el procesamiento de imágenes también recurren al transporte óptimo para resolver sus problemas.

Monge, un precursor -------------------------

La historia del transporte óptimo comienza con el matemático francés Gaspard Monge. Nacido en Beaune (Côte-d’Or), destacó a los 17 años al dibujar un plano detallado de su ciudad natal. En él mostró una auténtica vocación por la geometría. Fue contratado entonces como ayudante en la École royale du génie de Mézières (Ardennes), pues su origen era demasiado modesto para ser admitido allí como alumno. Pronto se convirtió en profesor de matemáticas y física. Enseñó allí durante casi veinte años y desarrolló paralelamente una actividad científica fecunda y diversa, en la que docencia, investigación y aplicaciones estaban estrechamente entrelazadas.

Las actividades científicas de Monge se nutren de aplicaciones, a menudo inspiradas en cuestiones militares. En 1781 presentó a la Académie des sciences su Mémoire sur la théorie des déblais et des remblais. La cuestión que trataba de responder era la siguiente: ¿cómo desplazar un montón de arena de una forma dada —el desmonte— para transformarlo en otro montón de arena —el terraplén— situado en otro lugar, del mismo volumen y con una forma prescrita, minimizando la suma de las distancias recorridas por los granos de arena?

Gaspard Monge, conde de Péluse (1746 — 1818), grabado de Naigeon Jeune.

Veamos un caso concreto del problema. Supongamos que N personas de una misma ciudad —representadas aquí por letras mayúsculas A, B… G— desean leer todas el mismo libro, y que N bibliotecas de la ciudad —representadas por cifras— poseen un ejemplar de ese libro cada una. Nos preguntamos cómo deben repartirse esas N personas para que cada una vaya a buscar un ejemplar a una biblioteca, sin que haya conflictos —cada biblioteca solo recibe a una de esas personas, pues solo posee un ejemplar del libro— y de modo que la suma de las distancias recorridas sea mínima. Esta cuestión se denomina problema de emparejamiento óptimo.

Para resolverlo, podemos construir una tabla con las distancias entre las personas y las bibliotecas. Las columnas corresponden a los individuos y las filas, a las bibliotecas. Resolver el problema equivale a colorear N casillas de modo que haya una única casilla coloreada por columna y una única por fila —sin conflictos—, y que la suma de las distancias de las casillas coloreadas sea mínima.

En azul, la solución del problema de emparejamiento.

En lugar de considerar las distancias entre los puntos, podríamos haber considerado el tiempo de trayecto en bicicleta, o cualquier otra función de coste entre las personas y las bibliotecas; ello habría dado lugar a una tabla distinta y, por tanto, a un resultado diferente (véase el recuadro).

Hay un caso particular en el que sabemos encontrar fácilmente una solución al problema de emparejamiento: aquel en el que todas las bibliotecas y todos los individuos se encuentran en una misma recta. El problema es entonces unidimensional. Si la función de coste del desplazamiento es la distancia, o el cuadrado de la distancia, una solución viene dada por el reordenamiento monótono: ordenamos las bibliotecas y los individuos de izquierda a derecha sobre la recta, enviamos al primer individuo a la primera biblioteca, y así sucesivamente. La solución hallada no es necesariamente única: varias soluciones distintas pueden corresponder al mínimo de la función de coste.

El problema de emparejamiento de puntos tiene una aplicación muy divertida en el procesamiento de imágenes: permite transferir los colores de una imagen a otra. Una imagen es una tabla rectangular en la que cada casilla —píxel— contiene tres valores que codifican un color (véase Mathématiques et Imagerie, número especial 77, 2021). Estos tres valores corresponden a coordenadas de rojo, verde y azul en un espacio de color tridimensional. Al emparejar mediante transporte óptimo los colores de dos imágenes, podemos transformar cada color de la primera en su color correspondiente de la segunda. Este proceso se denomina transferencia de color y resulta útil, especialmente, en la posproducción de vídeo.

####

Los caminos de la arena -----------------------

Volvamos a Monge. El problema que le interesa es más general que el de las bibliotecas. Hay que enviar un montón de arena de una forma dada a otro cuya forma también está prescrita. Seguimos teniendo que minimizar la suma de las distancias recorridas por los granos de arena, con la restricción de que los granos se distribuyen según el desmonte al partir y el terraplén al llegar. Monge no resuelve su problema, pero parte de que la solución existe y busca qué propiedades geométricas puede cumplir.

Estudia el problema en dos dimensiones y después en tres. Muestra, en particular, que los caminos no se cruzan: si hay que enviar dos granos de arena desde los puntos A y B hasta los puntos a y b, los caminos que minimizan la suma de los desplazamientos no pueden cruzarse (véase el recuadro).

El problema de Monge es, en realidad, particular y difícil. Podemos construir ejemplos sencillos en los que no tiene una solución única, sino varias, y otros en los que sencillamente no hay solución. Un siglo después —a finales del 19^.º siglo—, la cuestión seguía sin resolverse y la Académie des sciences la propuso con ocasión del premio Bordin.

Hubo que esperar al 20^.º siglo para que se resolviera por fin la cuestión de la existencia de soluciones al problema del transporte óptimo. Varios matemáticos propusieron importantes avances desde los años 1930 y durante la Segunda Guerra Mundial, especialmente para responder a cuestiones de asignación de recursos y optimización de la producción en economía. Todas estas ideas surgieron paralela e independientemente entre varios científicos, tanto «en Occidente» como «en Oriente».

Kantorovitch entra en escena --------------------------------

Las contribuciones más importantes sobre el tema fueron realizadas por el matemático ruso Leonid Vitalievich Kantorovitch (1912-1986). Desarrolló las herramientas de la programación lineal, una de las aportaciones más significativas a la teoría económica del 20^.º siglo. Recibió el Premio Nobel de Economía en 1975, junto con Tjalling Charles Koopmans (1910-1985), por estos trabajos.

El problema estudiado por Kantorovitch es ligeramente distinto del de Monge. Volvamos a nuestros individuos y bibliotecas. En el problema de Monge hay tantas personas como bibliotecas y buscamos emparejarlas. En la versión de Kantorovitch, cada biblioteca puede poseer varios ejemplares del libro y cada persona se sustituye por un hogar compuesto por varios individuos que viven en el mismo lugar y desean leer la obra tan codiciada.

El número total de individuos que desean leer el libro en todos los hogares es igual al número total de ejemplares en todas las bibliotecas. Seguimos buscando cómo repartir a los individuos entre las distintas bibliotecas, de modo que no haya conflictos y todos queden atendidos, minimizando la suma de los desplazamientos. Pero esta vez varios individuos de un mismo hogar pueden repartirse entre bibliotecas distintas —y, a la inversa, una misma biblioteca puede recibir individuos procedentes de hogares diferentes—.

Para resolver el problema de Kantorovitch, volvemos a crear una matriz de distancias entre los hogares —A, B, C y D— y las bibliotecas —a, b y c—. Denotamos mediante *c_a*_A la distancia entre el hogar A y la biblioteca a, y así sucesivamente. A continuación creamos otra tabla del mismo tamaño, que indica cómo se reparten los distintos hogares entre las bibliotecas. El valor *p_a*_A, por ejemplo, designa cuántos individuos del hogar A irán a la biblioteca a.

Los valores de esta tabla deben satisfacer restricciones: el número de individuos de los distintos hogares que van a la biblioteca a debe ser exactamente igual al número de ejemplares del libro en dicha biblioteca —es decir, 3—. Del mismo modo, el número de individuos que acuden a las bibliotecas desde el hogar A debe ser exactamente igual al número de individuos de ese hogar —es decir, 2—. Todas estas restricciones se traducen en siete ecuaciones, que fijan las sumas de los valores de la tabla en cada fila y en cada columna.

A continuación buscamos rellenar la tabla de modo que la suma de los productos de los *p_i*_,*_j por los costes c_i*_,*_j sea mínima, con la restricción de que las cantidades p* sean positivas y satisfagan las siete ecuaciones, es decir:

El problema obtenido es un caso particular de una clase de problemas más generales, denominados de programación lineal. Un algoritmo muy conocido para resolverlos es el del símplex, debido a George Dantzig en 1947 (véase la Recherche opérationnelle, número especial 75, 2020).

Solución del problema de transporte óptimo de Kantorovitch.

Una herramienta clave -----------------

Hubo que esperar a los años 1990 y, en particular, a los trabajos del matemático francés Yann Brenier para que se explicitaran las condiciones en las que las soluciones del problema de Kantorovitch proporcionan soluciones al problema de Monge. Desde entonces, la escuela francoitaliana del transporte óptimo se ha desarrollado considerablemente y ha cosechado numerosos éxitos, tanto en matemáticas teóricas como aplicadas. El transporte óptimo se ha convertido asimismo en una herramienta clave en numerosos campos de aplicación, como la economía, la informática gráfica o la física. Por ejemplo, guarda estrechos vínculos con la mecánica de fluidos. En el ámbito de la imagen interviene en la modificación del contraste o del color, en la comparación o creación de interpolaciones entre formas, en la manipulación de imágenes de texturas… En aprendizaje automático, se ha vuelto una herramienta imprescindible para comparar datos, y se utiliza especialmente para entrenar determinadas redes neuronales. ¡Hoy el transporte óptimo hace maravillas!