Dantzig: pensamiento positivo y programación lineal

George Bernard Dantzig fue un profesor de computación, físico y matemático estadounidense. Su padre era un matemático ruso que trabajó con Poincaré en París y que acabó emigrando a Estados Unidos. Dantzig fue galardonado con diversos premios como, por ejemplo, el premio de Teoría John von Neumann, por su trabajo sobre programación lineal. Falleció en 2005 por diabetes, a la edad de 90 años.

Cierto día, cuando estudiaba en la Universidad de Berkeley, Dantzig llegó tarde a clase y se encontró en la pizarra dos problemas estadísticos que el profesor había puesto como ejemplos de problemas aún no resueltos, pero él pensó que eran problemas de clase. Aunque le costó más de lo que esperaba, finalmente encontró la solución ya que al ser trabajos de clase pensó que la solución debía ser asequible. Dantzig entregó los ejercicios pensando que los entregaba fuera de plazo. Pocos días después, el profesor le visitó para anunciarle que lo que había resuelto no eran ejercicios de clase sino problemas que nadie había conseguido resolver y le propuso publicar una de sus soluciones en una revista científica.

La anécdota, que fue confirmada por el protagonista, se extendió como ejemplo del poder del pensamiento positivo, ya que seguramente Dantzig no hubiera encontrado la solución si hubiese sabido que eran problemas complejos que nadie había conseguido solucionar. Se cuenta que incluso el párroco de la zona ensalzaba este hecho en sus homilías y que Dantzig se enteró de ello por casualidad a través de un amigo.

Pero la mayor contribución que este matemático hizo a la humanidad fue su algoritmo Simplex para resolver problemas de optimización en programación lineal, el cual fue elegido como uno de los diez algoritmos más importantes del siglo XX (SIAM News, Vol. 33-4). La programación lineal surgió en la Segunda Guerra Mundial con el objetivo de reducir los costos del ejército y aumentar las pérdidas del enemigo. Al parecer el algoritmo Simplex fue usado en secreto por el ejército hasta que fue publicado en 1947. A partir de esa fecha muchas empresas lo han usado y aún hoy se usa para resolver multitud de problemas reales.

La solución óptima a un sencillo ejemplo con dos fábricas y dos tiendas no es la intuitiva

Antes de explicar de forma general la utilidad del algoritmo de Dantzig, vamos a intentar explicarlo de forma sencilla usando el clásico problema del transporte: supongamos que tenemos dos fábricas en Sevilla y en Málaga del mismo producto y dos tiendas en Córdoba y Jaén, en las que se venden esos productos. Deseamos saber cuántos productos llevar de cada fábrica a cada tienda para minimizar el coste de transporte global, pero teniendo en cuenta las siguientes restricciones:

• De cada fábrica no se puede transportar más de lo que tengan almacenado: supongamos 4 unidades en Sevilla y 8 en Málaga.
• A cada tienda hay que llevar un mínimo determinado: supongamos que hay que llevar 5 unidades a Córdoba y 6 a Jaén.

Los datos que queremos descubrir son las cuatro cantidades que debemos transportar desde las fábricas a las tiendas. Estos datos los representamos con cuatro variables: Xsc (cantidad de productos a transportar de Sevilla a Córdoba), Xsj (de Sevilla a Jaén), Xmc (de Málaga a Córdoba) y Xmj (de Málaga a Jaén). Nuestro objetivo (que, de hecho, se llama “función objetivo”) es minimizar la suma de los costes de transporte desde las fábricas hasta las tiendas. Supongamos que los costes de transportar cada unidad de producto a cada tienda son, respectivamente, 1, 2, 2 y 4, tenemos que este problema de programación lineal se representa de esta forma:

• Función objetivo: Minimizar Xsc + 2 Xsj + 2 Xmc + 4 Xmj
• Restricciones: Tenemos que satisfacer estas cuatro.
• Cantidad mínima para Córdoba: Xsc + Xmc ≥ 5
• Cantidad mínima para Jaén: Xsj + Xmj ≥ 6
• Cantidad máxima desde Sevilla: Xsc + Xsj ≤ 4
• Cantidad máxima de Málaga: Xmc + Xmj ≤ 8

Las solución óptima la calcula el algoritmo Simplex y es la siguiente: Xsc=0, Xsj=4, Xmc=5 y Xmj=2. O sea, la solución óptima me dice que no debo transportar nada de Sevilla a Córdoba (a pesar de que es el precio de transporte más barato). Los 5 productos de la tienda de Córdoba vienen de la fábrica de Málaga, mientras que los 6 productos de Jaén vienen repartidos de ambas fábricas (4 de Sevilla y 2 de Málaga). El valor de la “función objetivo” con esos resultados me dice que la suma total de costes es de 26. Simplex garantiza que no hay una solución alternativa que consiga un valor menor a 26. Cualquier otra forma de transportar los productos desde las fábricas a las tiendas nos costará 26 o más.

Como ve, la solución óptima a este sencillo ejemplo con dos fábricas y dos tiendas no es la intuitiva. Imagine ahora este mismo problema si tuviéramos decenas de fábricas y de tiendas. La complejidad aumenta, pero con un ordenador la solución se obtiene de forma rápida.

Este tipo de problemas son muy comunes en todo tipo de empresas y pueden usarse para optimizar o repartir mejor todo tipo de recursos: recursos económicos (reducir costos o aumentar beneficios), recursos naturales (materias primas), recursos humanos (repartir horarios)... De igual forma puede emplearse para maximizar ventajas y minimizar inconvenientes (como contaminación). Por todo esto, la programación lineal forma parte del temario de muchas titulaciones universitarias.

En general, podemos decir que los problemas de programación lineal pretenden buscar el valor óptimo de una función objetivo lineal (su valor máximo o mínimo) de múltiples variables, de forma que dichas variables estén sujetas a una serie de restricciones expresadas mediante un sistema de inecuaciones también lineales (usando ≤ y ≥).

Finalmente, hay que comentar que se han ideado múltiples modificaciones a este algoritmo, además de otros para los casos no lineales (cuando hay multiplicaciones entre variables, potencias, raíces, funciones trigonométricas...). Por otra parte, existen multitud de programas informáticos que implementan estas técnicas de optimización, tales como Lindo, GAMS o Matlab.

José Galindo (profesor titular de la Universidad de Málaga en el área de Lenguajes y Sistemas Informáticos, y editor del blog BlogSOStenible)

Crónicas del Intangible es un espacio de divulgación sobre las ciencias de la computación, coordinado por la sociedad académica SISTEDES (Sociedad de Ingeniería de Software y de Tecnologías de Desarrollo de Software). El intangible es la parte no material de los sistemas informáticos (es decir, el software), y aquí se relatan su historia y su devenir. Los autores son profesores de las universidades españolas, coordinados por Ricardo Peña Marí (catedrático de la Universidad Complutense de Madrid) y Macario Polo Usaola (profesor titular de la Universidad de Castilla-La Mancha).