A História da Programação Linear

O desenvolvimento de técnicas algébricas para se lidar com inequações lineares é algo bastante antigo. Durante o século XVIII, o matemático e físico Jean-Baptiste Joseph Fourier desenvolveu vários métodos inovadores para se resolver sistemas de ineqüações. Um dos principais algoritmos desenvolvido por Fourier foi o Método de Eliminação de Fourier–Motzkin.

Durante a Segunda Guerra Mundial, novas tecnologias bélicas levaram à criação de grupos acadêmicos com o objetivo de resolver problemas como o uso eficiente de radares, canhões antiaéreos, escoltas navais, etc. O objetivo era sempre reduzir custos militares e buscar maximizar as baixas inimigas. Para resolver estes problemas, a Programação Linear mostrou-se extremamente útil. Os grupos acadêmicos que a utilizavam eram sempre mantidos secretos até o ano de 1947, após o término da guerra. Foi quando a Programação Linear passou a ser muito usada em empresas com o objetivo de reduzir despesas e maximizar lucros.

Também no ano de 1947, o matemático George Dantzig desenvolveu o Algoritmo Simplex, a maneira mais eficiente conhecida de se resolver modelos de Programação Linear. No mesmo ano, John von Neumann desenvolveu a teoria da dualidade e Leonid Kantorovich foi a primeira pessoa a aplicar a Programação Linear à Economia.

Em 1979, Leonid Khachiyan desenvolveu um novo algoritmo para resolver modelos de programação linear: o Algoritmo Elipsóide. O seu algoritmo foi o primeiro criado que era capaz de resolver problemas em tempo polinomial. Apesar disso, era mais lento que o já conhecido Algoritmo Simplex, tanto na teoria como na prática.

Em 1984, surge mais um método de se resolver problemas de pesquisa operacional: o Algoritmo do Ponto Interior, criado por Narendra Karmarkar. Assim como o Algoritmo Elipsóide, ele era polinomial. A diferença é que ele era bem mais rápido e conseguia competir com o Algoritmo Simplex.