Por: João Flávio de Freitas Almeida
Em: //www.widwor.com/2012/08/o-que-e-programacao-linear.html
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.
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.
Artigos relacionados:
- Metodologia de trabalho em pesquisa operacional
- Um exemplo de otimização em siderurgia
- Otimização de operações em planilhas Excel™
- Pesquisa operacional, muitas empresas ainda desconhecem
O que é pesquisa operacional programação linear?
Programação linear: é uma técnica que pressupõe a relação linear entre as características do problema, buscando a solução ótima para o problema estudado. Essas características do problema são representadas e relacionadas por meio de uma série de equações lineares.
O que são restrições de Pesquisa Operacional?
O problema geral de programação linear é utilizado para otimizar (maximizar ou minimizar) uma função linear de variáveis, chamada de função objetivo, sujeita a uma série de equações (ou inequações) lineares, chamadas restrições.
Qual o método mais simples de resolução de problemas de programação linear?
O algoritmo simplex é o método mais utilizado para a resolução de problemas de programação linear (PLOSKAS; SAMARAS, 2015). O Método simplex (Dantzig) para programação linear foi criado por George Dantzig em 1947.
O que é função objetivo foi em um modelo de Pesquisa Operacional?
Função objetivo. É uma função que busca maximizar ou minimizar , dependendo do objetivo do problema. Ela é essencial na definição da qualidade da solução em função das incógnitas encontradas.
Qual a importância da programação linear?
- Historicamente, ideias da programação linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações. Aqui está um exemplo de problema de programação linear.
Quais são os exercícios de programação linear?
- Investigação Operacional (Economia) Exercícios de programação linear Formulação (Problemas propostos) 1 - Um fabricante produz bicicletas e motoretas, devendo cada uma delas ser processada em duas oficinas. A oficina 1 tem um máximo de 120 hora de trabalho disponível e a oficina 2 um máximo de 180 h.
Quais são as ideias centrais da programação linear?
- Historicamente, ideias da Programação Linear inspiraram muitos dos conceitos centrais de teoria da optimização, tais como dualidade, decomposição, e a importância da convexidade e suas generalizações. Exemplo de Poliedro Convexo (Bidimensional) resultante das Restrições de um Problema de Programação Linear.
Quais são os problemas de programação inteira?
- Ao contrário da PL que pode-se encontrar a solução óptima em um tempo razoável, muitos problemas de Programação Inteira são considerados NP-difícil. Se as variáveis forem binárias, ou seja, assumirem somente os valores 0 (zero) ou 1, temos um caso especial da PI, que também pode ser classificado como NP-difícil.