Programação Linear

Programação Linear (PL) é um ramo da programação matemática e um método amplamente utilizado na pesquisa operacional, dedicado ao desenvolvimento da teoria e dos métodos para resolver problemas de busca do extremo (máximo ou mínimo) de uma função linear, sujeito a restrições lineares.

A PL é uma das ferramentas mais poderosas e frequentemente aplicadas para resolver problemas de otimização em economia, gestão, planejamento, logística e outras áreas.

Objeto e Finalidade

A tarefa principal da programação linear é encontrar a melhor maneira (ótima) de alocar recursos limitados para atingir um determinado objetivo, quando tanto o objetivo quanto as restrições ao uso dos recursos podem ser expressos por relações lineares.

• A programação linear permite resolver problemas práticos como:
• Planejamento ótimo da produção.
• Otimização de fluxos de transporte (problema do transporte).
• Alocação ótima de investimentos.
• Corte ótimo de materiais. Problema da designação.

Formulação Matemática do Problema de PL

O problema padrão da programação linear é formulado da seguinte maneira:

É necessário encontrar os valores das variáveis de decisão que maximizam ou minimizam uma função objetivo linear. Ao mesmo tempo, as variáveis de decisão estão sujeitas a restrições na forma de um sistema de igualdades lineares e/ou desigualdades lineares. Geralmente, adiciona-se a condição de não negatividade das variáveis de decisão (seus valores devem ser maiores ou iguais a zero), o que é frequentemente ditado pelo significado físico ou econômico do problema.

Matematicamente, isso significa trabalhar com funções lineares e sistemas de equações/desigualdades lineares.

Conceitos Fundamentais da PL

• Variáveis de decisão (Variáveis controláveis): Quantidades cujos valores precisam ser determinados no processo de resolução do problema (por exemplo, os volumes de produção de diferentes produtos, a quantidade de recursos alocados para diferentes fins).
• Função objetivo: Uma função linear das variáveis de decisão, cujo valor se deseja maximizar ou minimizar. Ela expressa quantitativamente o objetivo do problema (por exemplo, o lucro total, os custos totais).
• Restrições: Um sistema de igualdades e/ou desigualdades lineares que as variáveis de decisão devem satisfazer. As restrições refletem os limites de recursos, requisitos tecnológicos, metas de planejamento e outras condições do problema.
• Região viável: O conjunto de todas as combinações de valores das variáveis de decisão que satisfazem todas as restrições do problema. Geometricamente, em um espaço multidimensional, a região viável é um poliedro convexo, que pode ser ilimitado ou vazio.
• Solução viável: Qualquer conjunto de valores das variáveis que pertença à região viável.
• Solução ótima: Uma solução viável na qual a função objetivo atinge seu valor extremo (máximo ou mínimo). Se uma solução ótima existe, ela sempre estará na fronteira da região viável, em pelo menos um dos vértices do poliedro convexo da região viável (teorema fundamental da PL).

Métodos de Resolução de Problemas de PL

Existem vários métodos principais para resolver problemas de programação linear:

• Método gráfico: Aplicado a problemas com duas variáveis de decisão. Permite visualizar a região viável e a função objetivo em um plano e encontrar a solução ótima analisando os vértices da região viável ou movendo a linha de nível da função objetivo.
• Método simplex: Um algoritmo iterativo universal desenvolvido por George Dantzig. O método se move sequencialmente de um vértice da região viável para um adjacente, melhorando o valor da função objetivo a cada passo, até que a solução ótima seja encontrada. É o método clássico e mais conhecido para resolver problemas de PL.
• Métodos de ponto interior: Uma classe alternativa de algoritmos que surgiram após o método simplex. Eles se movem em direção à solução ótima pelo interior da região viável, em vez de ao longo de suas fronteiras. Esses métodos são especialmente eficazes para resolver problemas de PL de grande dimensão.

Dualidade em Programação Linear

A cada problema de programação linear (chamado de primal) pode-se associar outro problema de PL, chamado de dual. Os problemas primal e dual estão intimamente relacionados:

A solução de um problema fornece informações sobre a solução do outro. Os valores ótimos das funções objetivo em ambos os problemas coincidem (se existirem). As variáveis do problema dual têm uma importante interpretação econômica — elas correspondem aos preços sombra (ou avaliações duais) dos recursos, mostrando o quanto o valor ótimo da função objetivo do problema primal mudaria com uma pequena alteração na restrição do recurso correspondente.

Aplicações da PL

A programação linear tem ampla aplicação em:

• Economia e negócios (planejamento de produção, logística, finanças, marketing).
• Indústria (otimização de processos tecnológicos, gerenciamento de estoques, corte de materiais).
• Transporte (otimização de rotas, horários). Agricultura (otimização de áreas de plantio, rações alimentares).
• Setor de energia (otimização do despacho de unidades geradoras).

Referências

• Dantzig G. B. Programação Linear, suas aplicações e generalizações. — Moscou: Progress, 1966.
• Yudin D. B., Golshtein E. G. Programação Linear (teoria, métodos e aplicações). — Moscou: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10ª ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11ª ed., 2021)

Ver também

• Pesquisa operacional
• Otimização
• Função objetivo
• Restrições
• Região viável
• Solução ótima