Page 108 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 108
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Programación lineal (linear programming)
INtroduccIóN
La programación lineal es una pequeña parte de todo un cuerpo matemático que se ha venido
consolidando en el pasado siglo XX con el nombre optimización. En general, se trata de un conjunto
de técnicas matemáticas que intentan obtener el mayor provecho posible de sistemas económicos,
sociales, tecnológicos cuyo funcionamiento se puede describir matemáticamente de modo ade-
cuado. Además de la programación lineal, otras disciplinas de este campo son la teoría de juegos,
la programación no lineal, la cibernética y la teoría de control. Para los problemas complejos que
aborda la optimización, ha sido de vital importancia la interacción, cada vez más fácil y fluida, entre
el pensamiento matemático y el ordenador, y se piensa que los avances futuros en el tratamiento
de la complejidad de los sistemas que hay que abordar en la actualidad dependerán más de
los progresos matemáticos que de las mejoras tecnológicas de nuestros ordenadores.
El problema básico de la programación lineal es el de la maximización de una cierta expresión lineal,
que se llama función objetivo, cuyas variables están sometidas a una serie de restricciones que vie-
nen expresadas por inecuaciones lineales. En la práctica, tanto el número de variables como el de
restricciones lineales puede ser de cientos de miles, lo cual hace imprescindible encontrar algoritmos
eficaces para la solución del problema e implementables con el ordenador.
Los fundadores de la técnica son George Dantzig (1914-2005), quien publicó el algoritmo Simplex
en 1947; John von Neumann, que desarrolló la teoría de la dualidad en el mismo año, y Leonid Kan-
toróvich, un matemático ruso que utilizó técnicas similares en la economía antes de Dantzig y ganó
el Premio Nobel de Economía en 1975.
La idea sobre la que se asienta el método Simplex puede entenderse fácilmente con la siguiente
comparación: supóngase que sobre la mesa está el esqueleto, formado por las aristas, de un polie-
dro complicado convexo como el de la figura 5.1.
Figura 5.1. Esqueleto, formado por las aristas, de un poliedro complicado convexo
102
