Blog‎ > ‎

O que é programação linear?

postado em 28 de nov de 2012 12:36 por João Flávio de Freitas Almeida   [ 17 de abr de 2014 08:22 atualizado‎(s)‎ ]

A programação linear, no campo da programação matemática, é uma área da pesquisa operacional com vasta aplicação em apoio à decisão. O termo “programação”, tanto linear quanto matemática, não tem a ver diretamente com programação de computadores, ou linguagem de programação. Este termo tem origem em suas aplicações, originalmente desenvolvido para resolver problemas industriais. 

Assim, o termo “programação” da programação linear está relacionado ao planejamento de recursos escassos visando atender as condições operacionais. Estas, por sua vez, são representadas por equações e funções lineares. A aplicação da programação linear em apoio à decisão ocorre na condição que se decide para atingir um objetivo. Este, por sua vez, é resultante da alocação ótima dos recursos. Por isso caracterizamos a programação linear como uma técnica de otimização. 

No problema de otimização em siderurgia, por exemplo, buscamos determinar a alocação ótima dos recursos de produção de forma a atender as limitações de capacidades de cada usina e maximizar o lucro resultante. Tanto a função de maximizar o lucro quanto as restrições de capacidade de cada planta são representados por funções lineares. Neste exemplo, o tomador de decisão pode escolher diversas combinações de alocação de seus produtos, no entanto apenas uma combinação é a mais lucrativa. Esta e a combinação ótima que maximiza o lucro, uma função linear, do problema de programação linear.

Programação linear: equações e funções são lineares
Embora originalmente o tempo “programação” de programação linear não tem a ver diretamente com programação de computadores, os problemas reais não podem ser resolvidos manualmente, dada a dimensão de problemas reais. Com a evolução da tecnologia de hardware e software, os algoritmos de programação linear são implementados em uma linguagem computacional para viabilizar a resolução de problemas reais em menor tempo. A programação linear, dessa forma, teve seu desenvolvimento junto com o desenvolvimento dos computadores, a partir da década de quarenta.
A programação linear é uma das técnicas mais usadas dentre outras grandes áreas da pesquisa operacional, como simulação, teoria de filas, programação dinâmica, teoria dos jogos. O problema de programação linear foi inventado pelo matemático Russo L. Kantorovich em 1939.  L. Kantorovich e T. Koopmans ganharam o prêmio Nobel por suas contribuições à teoria de alocação ótima de recursos. No entanto, o algoritmo mais utilizado para resolver problemas de programação linear é o simplex e suas variações (primal simplex, dual simplex, simplex revisado) formalizado por George Dantzig em 1947 enquanto trabalhava no projeto de computação científica de otimização SCOOP (Scientific Computation of Optimal Programs) na RAND (Research and Development) Corporation para a Força Aérea Americana.
 

Diversas áreas utilizam a programação linear para apoio a decisão. Dentre as áreas de aplicação estão: (i) planejamento logístico de frotas e rotas, (ii) planejamento da produção de longo, médio e curto prazo, (iii) decisão em escolha de mix de produtos em manufatura, (iv) estratégias operacionais em mineração, siderurgia, petroquímicas, agricultura, (v) decisão de localização de facilidade ou instalação de fábricas ou centros de distribuição, (vi) decisão em finanças na escolha da melhor carteira de investimentos, entre outros.
T. Koopmans, G.Dantzig e L. Kantorovich