A programação linear surgiu como um dos mais importantes ramos da programação matemática com uma vasta aplicação prática. Inovações da última metade do século passado fizeram com que os algoritmos de programação linear sejam eficientes e favoráveis para a resolução de um larga variedade de problemas envolvendo questões de decisão em vários domínios. Por exemplo: no planeamento da distribuição e produção de produtos, no planeamento de curto prazo em aproveitamento hidroeléctricos, nas decisões ligadas às políticas microeconômicas e macroeconômicas de governação dos países, na utilização como subrotinas para suporte de tarefas especificas em códigos de programação não linear. Ainda, são aspectos positivos a considerar o fato da programação linear ser uma teoria de otimização significativamente completa, de existirem códigos para computadores podendo suportar problemas de muito grande dimensão.
O problema de otimizar uma função linear sujeita a restrições lineares teve as sua origem com os estudos de Fourier sobre sistemas lineares de inequações em 1826. No entanto, só em 1939 Kantorovich faz notar a importância prática destes problemas, tendo criado um algoritmo para a sua solução. Num documento cujo objetivo era expor conceitos, Kantorovich apresentou exemplos para a aplicação da programação linear, sendo a ideia fundamental de cada exemplo a obtenção da maior produção possível com base numa utilização ótima dos recursos disponíveis. Um desses exemplos envolvia a distribuição de fluxos de carga (distribuídos através de veículos de transporte), usando diferentes rotas em redes rodoviárias de forma a satisfazer os requisitos e as restrições de capacidade das rotas, minimizando o consumo de combustível. Infelizmente, durante vários anos o trabalho de Kantorovich não só foi insuficientemente conhecido na Europa de Leste, mas também foi totalmente desconhecido na Europa Ocidental. Este amplo trabalho que aborta a discussão do fluxo de tráfego ótimo na antiga URSS foi efetuado por Kantorovich e Gavurin. O conhecimento sobre este trabalho chegou só ao ocidente depois de 1950.
O problema de otimizar uma função linear sujeita a restrições lineares tem o seu auge com George Dantzig na década de 1940, consultor de matemática do US Air Force Comtroller, e com o prêmio Nobel da Economia George Stigler, que formulou o problema das dietas como um problema de mistura de componentes. Dantzig não só formula o problema de programação linear, mas também cria o Algoritmo do Simplex para a sua solução em 1947. Ainda em 1947, Koopmans mostra que a programação linear é um modelo apropriado para a análise da teoria econômica clássica. Entretanto, nos EUA, Frank L. Hitchcock apresentou o que é hoje a formulação base do problema de transporte. Independentemente, o professor Koopmans formulou o mesmo problema em ligação com o seu trabalho efetuado na “Combined Shipping Adjustement Board”. Por isso, o problema de transporte é referido, na literatura científica, quer como problema de transporte de Hitchcock, quer como problema de transporte de Hitchcock-Koopmans.
Em 1956 Alex Orden propôs a generalização do modelo de transporte em que eram permitidos pontos de transbordo de carga. Esta formulação é conhecida hoje como um problema de transbordo sem limite de capacidade. Ao mesmo tempo, o problema de fluxos máximos e o problema do fluxo do custo mínimo em rede foi formulado e investigado pela famosa equipe de Lester Ford e Delbert Fulkerson.
Entre 1950 a 1965 muita atividade foi dirigida para o desenvolvimento de algoritmos para modelos de programação linear em rede. Os algoritmos desenvolvidos podem ser classificados em duas classes, como se segue:
A especialização primal simplex começou com o trabalho de Dantzig e atingiu o apogeu com o documento de Ellis Johnson. Os fundamentos para o documento de Johnson podem ser encontrados basicamente em dois livros: um de Dantzig e outro de Charnes e Cooper.
O método primal-dual originado com o algoritmo húngaro de Harold Kuhn para o problema de atribuição é concluído com o algoritmo da condição de Delbert Fulkerson em 1961.
Muita da atividade de investigação envolveu uma eficiente implementação das técnicas básicas, a particularização dos códigos à programação linear em rede acrescentou vantagens no desempenho, comparativo, dos procedimentos para a resolução de problemas de programação linear em rede. O primeiro problema de tamanho considerável resolvido pelo Algoritmo do Simplex foi o das dietas de Stigler com nove equações e setenta e sete variáveis não negativas, gastando 120 Horas Homem nas calculadoras de secretária existentes na altura e menos de um segundo nos atuais computadores pessoais.
Em 1975, a Academia Real de Ciência atribuiu o prêmio Nobel da Ciência em Economia a Kantorovich e Koopmans pelas a suas contribuições para a teoria da alocação de recursos, considerando a contribuição de Dantzig mais no âmbito matemático, não havendo prêmio para o ramo científico da matemática, não atribuiu prêmio a Dantzig. No entanto, Dantzig permanecerá para a história da construção da programação linear como um dos arquitetos fundamentais.