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.

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 del mismo producto en Sevilla y Málaga, y dos tiendas donde se venden esos productos en Córdoba y Jaén. Deseamos saber cuántos productos llevar de cada fábrica a cada tienda para minimizar el coste de transporte global (o la distancia a transportar), 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 a Córdoba y 6 a Jaén.

Los datos que queremos descubrir son las cuatro cantidades que debemos transportar desde cada fábrica a cada tienda. 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), 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 (o distancias) desde las fábricas hasta las tiendas. Para ello necesitamos saber los costes de transportar cada unidad desde cada fábrica a cada tienda. Si suponemos que esos costes por producto son, por ejemplo, 1, 2, 2 y 4, respectivamente, 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 de Sevilla: Xsc + Xmj ≤ 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 entre la fábrica de Sevilla y la tienda de Córdoba (a pesar de que ese es el precio de transporte más barato). Los 5 productos de la tienda de Córdoba vienen de Málaga, mientras que los 6 productos de Jaén vienen 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. El algoritmo 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, 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.

Tal vez pueda interesarte:

• Redes inteligentes (Smart Grids) para sistemas de generación de energía eléctrica más sostenibles.
• El tipo de letra que gasta menos tinta al imprimir.
• Darwin, ¿el mejor científico de la Historia?
• ¿Es ecológico comprar aparatos más eficientes y tirar los viejos? (coches, electrodomésticos…).
• Asertividad para Resolver Conflictos: Los Tres Pasos de la Técnica Sandwich.
• La Llave Maestra de la Inteligencia Emocional: ¿Cómo hacer que la vida sea fácil?
• El Poder del Pensamiento: ¿Funciona la Ley de la Atracción?

NOTA: Este artículo fue publicado en Crónicas del Intangible, un espacio de divulgación sobre las ciencias de la computación y el software (blogs de EL PAIS, 27-5-2016).