Nacido en 1912 en Leningrado (entonces San Petersburgo) recibe, junto a Koopmans, el premio Nobel de Economía en 1975. Graduado en matemáticas en esa misma ciudad, pronto compatibiliza su trabajo como profesor con sus investigaciones en Análisis Funcional y Matemáticas aplicadas.
En 1938 comienza sus trabajos sobre economía, planteándose el problema de optimizar la distribución de distintas materias primas entre varios centros de producción, bajo ciertas restricciones. Se trataba de maximizar una función lineal, dentro de un poliedro convexo. El método general de resolución, consistente en comparar el valor que toma la función en cada uno de los vértices no resultaba conveniente, debido al gran número de ellos que se obtienen incluso en problemas muy sencillos.
En 1939 la Universidad de Leningrado publica sus trabajos bajo el título "Métodos matemáticos de planificación y organización de la producción", que contiene las ideas básicas de la teoría y los algoritmos de Programación Lineal. Desgraciadamente este trabajo no llegó a ser conocido en occidente hasta bastantes años después y de hecho no fue traducido al inglés hasta 1959. Casi de forma simultánea, el matemático holandés Koopmans, se plantea un problema similar y obtiene resultados parecidos. Por ello el "problema del transporte" es conocido hoy como "problema de Koopmans-Kantorovich".
Nacido en Seattle (Washington) en 1911, recibió el Nobel de Economía en 1982. Atraído por distintos temas económicos, son conocidos sus estudios sobre la teoría de los precios "Readings in Price Theory". En 1946 publica su trabajo de programación lineal, denominado "El coste de la subsistencia", en el que desarrolla el llamado "problema de la dieta" y encuentra una solución aproximada al mismo.
Nacido en 1910 en Graveland (Holanda) recibió junto a Kantorovich el premio Nobel de Economía en1975. En 1942, de forma paralela, pero independiente, ambos formulan el llamado problema del transporte consistente en planificar el transporte de cierto producto entre varios centros de producción y varios centros de consumo.
Se le considera una de las figuras claves de la economía moderna, ya que sus trabajos fueron de gran trascendencia en los desarrollos posteriores de la teoría de la asignación de recursos escasos y en el desarrollo de métodos estadísticos aplicados a la economía.
Durante la segunda guerra mundial Koopmans trabajó como estadístico para la British Merchant Shipping Mission en Washington. Durante esos años se plantea investigar acerca del análisis económico de las rutas de transporte.
El problema de la determinación del plan de embarques que minimice el coste total, conociendo de antemano las disponibilidades y las demandas de cada puerto se conoce como el "problema del transporte". Hoy en día es un problema sencillo de Programación Lineal, pero en 1942 Koopmans no podía saber que el suyo era un caso particular de un problema más general.
George Dantzig
Nacido en Oregón en 1914, hijo de inmigrantes de origen ruso, estudia matemáticas en la Universidad de Maryland. Poco después de doctorarse por la Universidad de Berkeley, en 1947, formula el enunciado estándar de un problema general de Programación Lineal y desarrolla el método del simplex. De hecho, estos estudios son una consecuencia de su trabajo como experto en métodos de planificación para las Fuerzas Aéras estadounidenses, que resolvía utilizando calculadoras de mesa.
El nombre de "programación" proviene, en realidad, del término militar "programa", que se refiere a la organización de la planificación o los protocolos de instrucción, suministro de materiales o despliegue de tropas.
Una de las primeras aplicaciones de sus estudios fue la resolución del llamado "puente aéreo de Berlín". A mediados de 1948, en plena guerra fría, la URSS bloqueó las comunicaciones terrestres con Berlín. Utilizando la Programación Lineal, se diseñó un plan de abastecimiento aéreo que en pocos meses consiguió igualar a los anteriores suministros realizados por carretera y ferrocarril.
La aplicación del método del simplex ha estado siempre ligada al desarrollo de los ordenadores. En 1951 el ordenador SEAC (Standards Eastern Automatic Computer) resolvía problemas con 48 restricciones y 72 variables, si bien con cierta lentitud (William Orchard-Hays, refiriéndose a esa época, comentaba: "Una vez empezada una iteración, nos íbamos a comer y volvíamos antes de que acabara")
En 1963 el IBM 7090 resolvía problemas con 1024 restricciones y 10 años más tarde otro IBM, el modelo 360, era ya capaz de utilizar 32000 restricciones.
La contribución de Dantzig ha sido reconocida con numerosos premios, entre los que destaca el premio Von Neumann de la Sociedad Americana de Investigación Operativa del año 1975.
Janos Von Neumann
Los fundamentos matemáticos de la Programación Lineal se deben a al matemático Janos Von Neumann, nacido en Budapest en 1903 y discípulo de Hilbert en Gotinga durante los años 1926 y 27. En su libro Theory of Games and Economic Behavior sistematiza, junto con Oskar Morgenstern, la teoría de juegos en la que venía trabajando desde 1928, en particular, los denominados juegos de dos personas de suma cero, en los que la ganancia de un jugador es una pérdida para el otro, estableciendo la solución denominada "mini-max". Estos juegos pueden resolverse como problemas de programación lineal.
En la página http://www.egwald.com/operationsresearch/gametheory.php3 puede verse un ejemplo de esta resolución.
Narendra Karmarkar
En 1984 Narendra Karmarkar, un matemático
hindú de 28 años establecido en Estados Unidos publicó
el artículo "A New Polynomial-Time Algorithm for Linear Programming",
que marcó un hito en la Programación Lineal. A partir del
trabajo de Karmarkar se reactivó la investigación en esta
rama matemática, en especial en métodos de barrera y de
punto interior. Este nuevo método se utiliza actualmente para la
resolución de problemas con un gran número de variables.
Recientemente un problema con 800.000 variables fue resuelto por este
algoritmo. Su resolución necesitó 10 horas de trabajo de
ordenador. Parece ser que utilizando el método del simplex su tiempo
de resolución hubiera sido de varias semanas.
