O problema básico de programação linear consiste no seguinte: dada uma
matriz A e vetores b e c, encontrar um vetor x tal que
Dois mil anos antes de Cristo exemplos especiais de equações lineares já tinham sido estudadas por egípcios e babilônios. Os babilônios também consideraram duas equações lineares em duas variáveis. Babilônios, gregos e chineses conheciam a idéia de eliminação de variáveis para resolver equações lineares (ou quadráticas).
O que hoje é conhecido como o método de eliminação Gaussiana foi descrito explicitamente no `Nove Livros da Aritmética' chinês que foi escrito entre 202 A.C. e 9 D.C. e descreve métodos que provavelmente foram escritos muito antes. Equações lineares e eliminação de variáveis também foram estudadas por Diophantos de Alexandria (aprox. terceiro século D.C.).
O nome eliminação Gaussiana é devido a alguns artigos de Gauss onde
eliminação é aplicada. Gauss estudou equações lineares para estimar as órbitas
de corpos celestes e observou que, se um sistema Ax = b de nequações e n incógnitas não admite solução ou admite várias soluções,
então existe um vetor y tal que yA = 0 (que é uma espécie de
afirmação `dual'). Em um de seus artigos Gauss também descreveu o que é
hoje conhecido como processo de ortogonalização de
Gram-Schmidt, que decompõe uma matriz A como A = QU, onde Q é
uma matriz ortogonal (i.e. 
e U é triangular superior.
Logo, Ax = b pode ser trocado por 
,
que é mais fácil
de ser resolvido.
Enquanto resolver vários tipos de equações foi um tópico central em matemática, pouca atenção foi tomada em encontrar uma solução `ótima' (com raras excessões). As aplicações em problemas de transporte na década de 40 (em particular, pelas forças armadas durante a segunda grande guerra mundial) foi um primeiro passo importante na criação da programação linear. Entre os pioneiros que fizeram o desenvolvimento da área estão George Dantzig em Washington e Leonid Kantorovich em Leningrado. Ambos ilustraram muito bem as fontes de aplicações da programação linear; Dantzig trabalhava para o Pentágono (inclusive durante o período da guerra entre 1941 a 1945), enquanto Kantorovich foi motivado pelo plano econômico Soviético. Outros pioneiros são Von Neumann (Game Theory), Wassily Leontief (Input-Output Model of the Economy) e Tjalling Koopmans (Theory of Optimum Allocation of Resources). Kantorovich, Koopmans e Leontief receberam o prêmio Nobel em economia; sobre isto, em Chvátal [1] encontramos o seguinte:
...On October 14, 1975, the Royal Sweden Academy of Sciences awarded the Nobel Prize in economic science to L.V. Kantorovich and T.C. Koopmans ``for their contributions to the theory of optimum allocation of resources.'' (As the reader may know, there is no Nobel Prize in mathematics. Apparently the Academy regarded the work of G.B. Dantzig, who is universally recognized as the father of linear programming, as being too mathematical.) ...
Em 1946 Dantzig era consultor para a US Air Force Comptroller no Pentágono. Foi no Pentágono que Dantzig recebeu dos seus colegas D. Hitchcock e M. Wood o desafio de tentar ver o que poderia ser feito para mecanizar o processo de planejamento. No verão de 1947 Dantzig propôs o método simplex que tornou possível a solução de problemas de otimização de vários tipos, como transporte, produção, alocação de recursos e problemas de escalonamento (scheduling). O desenvolvimento dos computadores permitiu a aplicação do método simplex a problemas de grande porte, enquanto que, por outro lado, o método revelou alguns dos problemas numéricos que podem ocorrer em cálculos feitos por um computador -- o que motivou a busca de soluções para estes problemas.
No início da década de 50 começaram a surgir várias áreas as quais chamamos hoje coletivamente de programação matemática. Essas subáreas de programação matemática cresceram rapidamente -- com programação linear desempenhando um papel fundamental nesse desenvolvimento. Entre essas subáreas estão: programação não-linear (começou por volta de 1951 com a famosa condição de Karush-Kuhn-Tucker); aplicações comerciais; fluxos em redes; métodos de grande porte; programação estocástica; e programação inteira.
Dantzig [3] descreve a origem de certos termos:
Here are some stories about how various linear programming terms arose. The military refer to their various plans or proposed schedules of training, logistical supply and deployment of combat units as a program. When I had first analyzed the Air Force planning problem and saw that it could be formulated as a system of linear inequalities, I called my first paper Programming in a Linear Structure. Note that the term `program' was used for linear programs long before it was used as the set of instructions used by a computer to solve problems. In the early days, these instructions were called codes.In the summer of 1948, Koopmans and I visited the Rand Corporation. One day we took a stroll along the Santa Monica beach. Koopmans said: ``Why not shorten `Programming in a Linear Structure' to `Linear Programming'?'' I replied: ``That's it! From now on that will be its name.'' Later that day I gave a talk at Rand, entitled `Linear Programming'; years later Tucker shortened it to Linear Program.
The term Mathematical Programming is due to Robert Dorfman of Harvard, who felt as early as 1949 that the term Linear Programming was too restrictive.
The term simplex method arose out of a discussion with T. Motzkin who felt that the approach that I was using, when viewed in the geometry of the columns, was best described as a movement from one simplex to a neighboring one. Mathematical programming is also responsible for many terms which are now standard in mathematical literature, terms like Arg Min, Arg Max, Lexico-Max, Lexico-Min. The term dual is an old mathematical term. But suprisingly the term primal is new and was proposed by my father Tobias Dantzig around 1954 after William Orchard-Hays stated the need for a word to call the original problem whose dual was such and such.
Apesar de, em termos teóricos, o algoritmo simplex (algoritmo simplex =método simplex + mecanismo que force a convergência) não ser um algoritmo eficiente, já que o número de operações executadas pelo algoritmo no pior caso é exponencial, na prática o desempenho do algoritmo é muito bom e isto foi decisivo no sucesso da programação linear.
Em 1979 L.G. Khachiyan mostrou que um método de otimização não-linear devido a N.Z. Shor, D.B. Yudin e A.S. Nemirovskii, que não era amplamente conhecido, podia ser adaptado para resolver problemas de programação linear em tempo polinomial. Este método ficou conhecido como método dos elipsóides.
Mais recentemente, em 1984, N. Karmarkar desenvolveu um novo algoritmo
polinomial para resolver problemas de programação linear. Nascia assim
os chamados métodos de pontos interiores.
Observação. O que foi brevemente tratado nesta introdução foi extraído de [3], dos prefácios de [4] e de [5], das notas históricas em [12] e de [9].