Skip to content
Voltar aos resultados

Programação Linear — Otimizando Objetivos Lineares Sob Restrições Lineares

Proposto por
George B. Dantzig
Ano
1947
Tipo
Mathematical programming / continuous optimization

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

A programação linear (PL), pioneira por George B. Dantzig em 1947, é um método matemático para encontrar o melhor valor de uma função objetivo linear — como custo mínimo ou lucro máximo — sujeita a um conjunto de restrições de desigualdade e igualdade lineares.

É a técnica fundamental em pesquisa operacional e fundamenta o planejamento de produção, alocação de recursos, logística, problemas de dieta e inúmeros outros cenários de tomada de decisão em engenharia, economia e ciências naturais.

A intuição por trás do método

Imagine que você gerencia uma pequena fábrica que produz dois produtos. Cada produto lhe gera um certo lucro, mas sua fabricação consome matérias-primas e tempo de máquina limitados. A programação linear encontra a combinação exata de produtos que extrai o máximo de lucro de seus recursos fixos — sem violar nenhum limite físico ou contratual. A parte 'linear' significa que o lucro e o consumo de recursos escalam em uma relação de linha reta com as quantidades que você produz. As escolhas factíveis formam um polígono (em duas dimensões) ou um poliedro (em dimensões superiores), e a resposta ótima sempre se encontra em um de seus vértices.

História

O desenvolvimento sistemático da programação linear começou em 1947, quando George B. Dantzig, trabalhando para a Força Aérea dos EUA, inventou o algoritmo Simplex para automatizar o planejamento logístico militar. Dantzig publicou a teoria fundamental em sua monografia de 1963, que continua sendo a referência canônica. Trabalho independente e paralelo de Leonid Kantorovich na União Soviética (1939) abordou o planejamento de produção usando ideias matemáticas semelhantes, e Kantorovich foi agraciado com o Prêmio Nobel de Economia em 1975, em parte por essa contribuição. A questão teórica da solubilidade em tempo polinomial foi resolvida pelo método da elipsoide de Khachian (1979) e, posteriormente, pelo método de ponto interior de Karmarkar (1984), que se mostraram praticamente rápidos para problemas de larga escala. Hoje, solvers de PL comerciais e de código aberto estão embarcados em planejamento de recursos empresariais, agendamento de companhias aéreas e sistemas de energia em todo o mundo.

Quando usar

A programação linear é apropriada sempre que você precisa otimizar uma quantidade que depende linearmente de um conjunto de variáveis de decisão, e todas as restrições também são lineares. Não requer suposições de distribuição nem tamanho mínimo de amostra — é um modelo matemático determinístico, não um estimador estatístico. O método se aplica quando as variáveis de decisão são contínuas (valores fracionários são significativos); se as variáveis devem ser números inteiros ou binárias, a programação inteira é necessária em vez disso. A PL é amplamente utilizada em agendamento de produção, logística de cadeia de suprimentos, problemas de dieta e mistura, otimização de portfólio financeiro, problemas de transporte e alocação, e despacho de energia.

Limitações e considerações

  • Requisito de linearidade: se o objetivo ou qualquer restrição for não linear, o modelo de PL é mal especificado e a solução pode ser incorreta ou infactível.
  • Variáveis contínuas apenas: quando as variáveis de decisão devem assumir valores inteiros ou binários, a relaxação de PL fornece um limite inferior, mas não uma solução válida; a programação inteira deve ser usada.
  • Determinístico: PL não modela incerteza em parâmetros; programação estocástica ou otimização robusta é necessária quando os dados são incertos.
  • Degenerescência e ciclagem: em casos raros, o método Simplex pode ciclar entre bases degeneradas sem convergir, embora regras anti-ciclagem (por exemplo, regra de Bland) resolvam isso.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Ótimo global garantido: como a região factível é um poliedro convexo, qualquer ótimo local é também um ótimo global, sem risco de ficar preso em uma solução subótima.
  • Altamente escalável: solvers modernos (HiGHS, Gurobi, CPLEX) lidam com modelos com milhões de variáveis e restrições em segundos.
  • Ricas informações pós-solução: preços sombra e faixas de sensibilidade fornecem insights acionáveis sobre o valor dos recursos e a robustez da solução sem execuções adicionais.
  • Sem suposições de distribuição: PL é um modelo puramente algébrico, portanto, não requer normalidade ou qualquer propriedade estatística dos dados.

Aplicações

  • Planejamento de produção: encontrar a combinação ótima de produtos que maximiza o lucro, respeitando a capacidade da máquina e os limites de matéria-prima.
  • Logística de cadeia de suprimentos e transporte: minimizar os custos de envio em uma rede de armazéns e clientes.
  • Problemas de dieta e mistura: selecionar quantidades de ingredientes que atendam aos requisitos nutricionais com custo mínimo.
  • Otimização de portfólio financeiro: alocar capital entre ativos para maximizar o retorno esperado, sujeito a restrições de risco e regulatórias.
  • Despacho de energia e agendamento de rede elétrica: minimizar o custo de combustível, ao mesmo tempo em que satisfaz a demanda de eletricidade e os limites de capacidade dos geradores.
  • Agendamento de pessoal e força de trabalho: atribuir turnos a trabalhadores para cobrir a demanda com custo mínimo de mão de obra.

Como funciona

Como funciona

1

O problema de decisão do mundo real é traduzido em símbolos matemáticos. Você identifica as variáveis de decisão (as quantidades que pode controlar), escreve a função objetivo (o que você quer maximizar ou minimizar) como uma combinação linear dessas variáveis e escreve cada restrição — limites de recursos, capacidades máximas, requisitos de demanda — como uma desigualdade ou igualdade linear. Uma PL bem formulada tem um objetivo claro, limites explícitos de variáveis e cada restrição estrutural expressa linearmente.

2

O modelo é levado a uma forma canônica ou padrão que um solver pode processar. Desigualdades são convertidas em igualdades pela introdução de variáveis de folga ou excedentes não negativas, e qualquer variável irrestrita é substituída pela diferença de duas variáveis não negativas. Esta etapa mecânica produz o tableau ou representação matricial sobre a qual o algoritmo atua, e não altera o problema — apenas o remodela para computação.

3

Um solver busca no poliedro factível o vértice ótimo. O método Simplex clássico pivota de vértice em vértice ao longo das arestas do poliedro, sempre melhorando (ou mantendo) o objetivo, até que nenhum vizinho que melhore exista. Métodos de ponto interior (barreira), em vez disso, viajam pelo interior da região factível ao longo de um caminho central, o que é especialmente eficiente para modelos muito grandes. Ambas as famílias garantem encontrar um ótimo global quando um existe, pois a região factível é convexa.

4

O solver retorna os valores ótimos das variáveis de decisão e o valor ótimo do objetivo, juntamente com variáveis duais (preços sombra) e faixas de sensibilidade. Preços sombra quantificam o quanto o objetivo melhoraria se uma restrição vinculante fosse relaxada em uma unidade — dizendo diretamente a um tomador de decisão onde recursos adicionais seriam mais valiosos. A análise de sensibilidade identifica o quanto um coeficiente de custo ou um valor do lado direito pode mudar antes que a base atual deixe de ser ótima.

Erros comuns

  • Aplicar PL quando restrições ou o objetivo são não lineares — a solução estará errada ou o solver rejeitará o modelo.
  • Ignorar requisitos de integridade: arredondar uma solução contínua de PL para inteiros geralmente não produz uma solução inteira factível ou ótima; use programação inteira em vez disso.
  • Modelos infactíveis ou ilimitados: se a região factível for vazia (restrições conflitantes) ou o objetivo for ilimitado (restrições de limite ausentes), o solver relatará falha — sempre verifique a estrutura do modelo antes de executar.
  • Tratar a saída de PL como uma recomendação sem análise de sensibilidade: uma solução tecnicamente ótima pode estar em uma borda muito fina onde uma pequena mudança nos dados inverte a recomendação — as faixas de sensibilidade devem sempre ser inspecionadas.

Perguntas frequentes

O que torna um problema 'linear' para fins de PL?

Tanto a função objetivo quanto cada restrição devem ser lineares — o que significa que cada termo é uma constante multiplicada por uma única variável de decisão, sem produtos de variáveis, sem expoentes e sem funções não lineares. Se mesmo uma restrição ou o objetivo envolver, digamos, x vezes y ou x ao quadrado, a PL padrão não se aplica mais e um solver de programação não linear ou quadrática é necessário.

Por que a solução ótima sempre se encontra em um vértice da região factível?

A região factível definida por restrições lineares é um poliedro (ou politopo) convexo. Uma função objetivo linear é ela própria linear, portanto, não pode ser 'puxada' para o interior de um conjunto convexo — ela sempre atinge seu valor extremo na fronteira, e especificamente em um vértice (ponto de canto). Esta é a intuição geométrica que fundamenta a estratégia de vértice a vértice do método Simplex.

Quando devo usar programação inteira em vez de PL?

Sempre que uma ou mais variáveis de decisão devem assumir valores inteiros ou binários (0/1) — por exemplo, se abrir uma instalação (sim/não), quantos caminhões despachar (números inteiros) ou quais itens incluir em uma seleção. Simplesmente resolver a PL e arredondar a solução contínua não é confiável: soluções arredondadas podem ser infactíveis ou distantes do ótimo. A programação inteira lida com a integridade corretamente, a um custo computacional maior.

O que os preços sombra me dizem?

Um preço sombra (variável dual) para uma restrição vinculante indica o quanto o valor ótimo do objetivo melhoraria se o lado direito dessa restrição fosse relaxado em uma unidade, mantendo tudo o mais constante. Por exemplo, um preço sombra de 3 em uma restrição de horas de trabalho significa que adicionar mais uma hora de trabalho melhoraria o objetivo em 3 unidades. Restrições que não são vinculantes têm um preço sombra de zero — elas não estão limitando o ótimo atual.

Métodos relacionados

Fontes

  1. Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.

    ISBN: 9780691059136
    Copiado.
  2. Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.

    Abrir referência DOI
    Copiado.