Programación Lineal I: Dantzig

Después de la guerra, muchos científicos que estuvieron activos en los grupos militares de IO volvieron su atención a las posibilidades de aplicar un acercamiento similar a problemas civiles. Algunos volvieron a las universidades y concentraron sus esfuerzos en fundamentar muchas de las técnicas que habían sido precipitadamente desarrolladas, mientras otros renovaron esfuerzos para desarrollar nuevas técnicas. Muchos de los científicos se desplazaron hacia varios sectores de la economía privada, donde adaptaron los métodos desarrollados por otros a problemas particulares de las industrias.

La constitución formal de la PL alrededor de los años 50, marcó la consolidación de la IO como disciplina científica independiente. De entre todos los investigadores que contribuyeron al desarrollo de la PL, como Kantorovich, Koopmans o Kuhn entre otros, destaca la figura del matemático George Bernard Dantzig (1914-2005).

George B. Dantzig

Durante los años de la Segunda Guerra Mundial, Dantzig trabajó para el Pentágono al mando de la subdivisión de análisis de combate, en el cuartel general de Control Estadístico de la U.S. Army Air Force (Fuerza Militar Aérea de los Estados Unidos). Durante esta etapa trabajó en lo que denominaron “programming planing methods” (métodos de planificación programada). Dichos programas militares trataban de resolver, de forma eficiente, problemas de cadenas de suministros, gestión de inventarios de equipo militar, organización y despliegue de tropas, agendas de entrenamiento, etc. Una de las dificultades que encontraron fue que se necesitan cerca de 7 meses para resolver numéricamente tales programas. Tras finalizar el conflicto, Dantzig completó sus estudios doctorales en Berckley.

En 1947, tras formarse el nuevo departamento de la USAF (del inglés United States Air Force), Dantzig volvió al Pentágono, donde pasó a trabajar como asesor matemático de la Fuerza Aérea. Allí reanudó su análisis de los métodos de planificación programada (estudiados durante la contienda) en un grupo de investigación formado por otros notables investigadores, como el economista Marshall K. Wood.

En 1948, el grupo de investigación de la USAF estaba convencido de que el uso de potentes computadoras electrónicas, cuyas primeras unidades fueron fabricadas durante la guerra, podía reducir significativamente el tiempo de ejecución de los programas de la Fuerza Aérea. Puesto que no existía ninguna computadora adecuada, la U.S. Air Force se comprometió para apoyar el desarrollo del equipamiento necesario. Bajo la dirección de Wood, y con el objetivo general de desarrollar una respuesta más adecuada para los métodos de planificación programada, se estableció el proyecto SCOOP (por sus iniciales del inglés, Scientific Computing of Optimum Programs). Dantzig trabajó en este proyecto desde 1947 hasta 1952, donde formuló el problema de PL implementando una función objetivo lineal, sujeta a ecuaciones y desigualdades también lineales; además planteó el algoritmo del simplex para solucionar los problemas de PL, proporcionando a la PM el enfoque que hoy conocemos.

Posteriormente, Dantzig recogió el fruto de sus investigaciones en la PL y el simplex, en dos artículos publicados en la obra “Activity analysis of production and allocation”, dirigida por T.C. KoopmansLa obra es un “conference proceedings”, es decir, una recopilación de artículos de los ponentes de una conferencia, publicados con motivo de la celebración de la misma. Se puede encontrar una copia de la obra en la siguiente dirección: [http://cowles.econ.yale.edu/P/cm/m13/]: Maximization of a linear function subject to linear inequalities y Aplication of the simplex method to a transportation problem.

En 1963 Dantzig publicó el libro Linear programming and extesions, Princenton University Press, que pronto se convirtió en una obra de referencia en la materia.

El impacto científico y económico derivado del trabajo de Dantzig ha sido verdaderamente profundo: actualmente, todas las grandes industrias utilizan de alguna forma la PL para la toma de decisiones y la asignación de recursos; los planes económicos para el tercer mundo y países en desarrollo son guiados por técnicas de PL; en los ejércitos, la planificación de estrategias y la gestión de recursos se implementan utilizando técnicas de la PL; diversas aplicaciones, como algunas técnicas de chequeo para detectar el cáncer, programación de vuelos en líneas aéreas, desarrollo agrario, sistemas de transporte y reparto, operaciones en refinerías de petróleo, se han visto influenciadas por el trabajo de Dantzig en mayor o menor medida.

De izda. a dcha. Koopmans, Dantzig y Kantorovich

Pese a todo ello, Dantzig no pudo conseguir el Premio Nobel. En 1975, Kantorovich y Koopmans fueron distinguidos con el Premio Nobel en Economía por sus contribuciones a la teoría del reparto óptimo de recursos. Aun cuando tres participantes pueden compartir el mismo galardón, a Dantzig no le fue concedida esta distinción. Esta acción fue motivo de gran polémica entre los investigadores pertenecientes al área de la IO, que consideraban fundamentales las contribuciones de Dantzig para la teoría de la asignación de recursos.

Koopmans, que estaba profundamente disgustado porque Dantzig no fuera incluido en el premio, propuso a Kantorovich rechazar el galardón. Finalmente, decidió regalar 40,000$ al Instituto Internacional para el Análisis de Sistemas Aplicados (IIASA) de Luxemburgo, justo la cantidad que Dantzig habría recibido de compartir el premio.

No obstante, Dantzig recibió numerosas distinciones, como el premio Von Newman Theory en 1975 y la Medalla Nacional de Ciencias en 1976 (entregada por el presidente Gerald Ford, y que es considerado el más alto galardón de los Estados Unidos en el área de ciencias), entre otros.


Fuentes :
- Saul I. Gass and Arjang A. Assad. An annotated timeline of Operations Research, an informal history. Springer, 2004.
- Saul I. Gass. IFORS' Operational Research Hall of Fame: George B. Dantzig. International Transactions in Operational Research, 10:191-193, 2003.