Skip to content
Voltar aos resultados

Programação Linear Determinística — PL Clássica com Parâmetros Certos

Proposto por
George B. Dantzig
Ano
1947
Tipo
Deterministic mathematical optimization
Família
Simulation / 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 Determinística (DLP) é a forma clássica de programação linear na qual todos os coeficientes da função objetivo, coeficientes das restrições e valores do lado direito são conhecidos com certeza.

Ela encontra a alocação ótima de recursos para maximizar ou minimizar um objetivo linear sujeito a restrições lineares, fornecendo uma solução exata e reproduzível sob dados fixos e certos.

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

Imagine alocar um orçamento fixo entre projetos, cada um com custos e retornos conhecidos, sujeito a limites de recursos que você conhece precisamente. A PL Determinística codifica isso como um sistema de desigualdades lineares e encontra a solução de ponto de canto que extrai o maior valor dessas restrições. Como cada parâmetro é certo — sem distribuições de probabilidade, sem ambiguidade — o resolvedor retorna um único plano ótimo exato, em vez de uma distribuição de resultados. Essa clareza torna a DLP o modelo de primeira escolha natural quando os dados são bem medidos e a incerteza não é uma preocupação primária.

História

A programação linear foi formalizada por George B. Dantzig em 1947 com o desenvolvimento do algoritmo Simplex enquanto trabalhava para a Força Aérea dos EUA. A monografia de Dantzig de 1963 tornou-se a referência canônica. O qualificador 'determinístico' surgiu à medida que variantes de PL estocástica foram introduzidas (Dantzig e Beale, décadas de 1950-1960) para distinguir o modelo original de parâmetros certos de suas extensões probabilísticas.

Quando usar

Use a Programação Linear Determinística quando o problema de decisão puder ser modelado com um objetivo linear e restrições lineares, e quando todos os parâmetros forem conhecidos com certeza suficiente para justificar tratá-los como constantes fixas. Cenários ideais incluem planejamento de produção, transporte e logística, problemas de dieta e mistura, e fluxo de rede sob condições estáveis. NÃO use DLP quando os parâmetros são genuinamente incertos e o risco importa — prefira PL Estocástica ou PL Robusta. Evite DLP quando o objetivo ou as restrições são não lineares, quando as variáveis devem ser inteiras (use MIP), ou quando múltiplos objetivos conflitantes devem ser equilibrados simultaneamente sem agregá-los em uma soma ponderada (use PL multi-objetivo ou programação por metas).

Limitações e considerações

  • Exige que todas as relações sejam estritamente lineares — curvas de custo não lineares ou retornos decrescentes não podem ser capturados sem aproximação.
  • Todos os parâmetros devem ser conhecidos e fixos; o modelo não oferece um mecanismo nativo para lidar com incerteza ou erro de estimativa de parâmetros.
  • A solução ótima pode não ser única (degenerada), tornando a escolha da base de relatório ambígua sem critérios adicionais.
  • Requisitos inteiros ou combinatórios (por exemplo, decisões sim/não) exigem extensão para programação inteira mista, que é computacionalmente mais difícil.
  • Problemas de grande escala com matrizes de restrições densas podem consumir muita memória, mesmo para resolvedores modernos.

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

  • Solução ótima global garantida para qualquer instância de PL viável e limitada devido à convexidade.
  • Altamente escalável — resolvedores modernos lidam com milhões de variáveis e restrições em segundos.
  • Variáveis duais e análise de sensibilidade fornecem rica interpretação econômica de preços sombra e intervalos de variação.
  • Formulação transparente e auditável: cada suposição é explícita na matriz de restrições.
  • Ecossistema de software maduro (CPLEX, Gurobi, HiGHS, GLPK) com implementações confiáveis e bem testadas.
  • Sinal claro de viabilidade passa/falha: a inviabilidade revela imediatamente a má especificação do modelo.

Aplicações

  • Programação de produção e manufatura com capacidades de recursos fixas e demanda conhecida.
  • Transporte e logística: encontrando rotas de envio de custo mínimo em uma rede.
  • Problemas de dieta e mistura: formulando misturas nutricionais ou químicas de menor custo que satisfaçam as restrições de composição.
  • Otimização de portfólio financeiro sob retornos lineares e restrições orçamentárias.
  • Planejamento de sistemas de energia: despacho ótimo de unidades de geração de energia com custos e capacidades conhecidos.
  • Projeto de rede de cadeia de suprimentos quando a demanda e os prazos de entrega são tratados como constantes conhecidas.

Como funciona

Como funciona

1

Defina as variáveis de decisão x (por exemplo, quantidades de produção, valores de fluxo), a função objetivo c^T x para minimizar ou maximizar, e o conjunto de restrições Ax <= b com x >= 0. Todos os coeficientes em c, A e b são tratados como constantes exatas e conhecidas — é isso que torna o modelo determinístico. Escreva a PL na forma padrão: min c^T x sujeito a Ax = b, x >= 0.

Fórmula
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

Antes de otimizar, verifique se a região viável não é vazia (o conjunto de restrições tem pelo menos uma solução) e se o objetivo é limitado. Se a região viável for vazia, o problema é inviável; se o objetivo for ilimitado, o modelo está mal especificado. Essas verificações são realizadas automaticamente pelos resolvedores, mas devem ser interpretadas pelo analista para identificar erros de formulação.

3

Resolva a PL usando o algoritmo Simplex (pivotando ao longo das arestas do poliedro convexo em direção ao vértice ótimo) ou um método de ponto interior (seguindo um caminho através do interior da região viável). Ambas as abordagens exploram a convexidade do conjunto viável e a linearidade do objetivo, garantindo que qualquer ótimo local seja global. Resolvedores modernos (CPLEX, Gurobi, HiGHS) lidam com milhões de variáveis e restrições de forma eficiente.

4

O resolvedor retorna o vetor de decisão ótimo x* e o valor objetivo ótimo c^T x*. Como a região viável é um poliedro convexo e o objetivo é linear, o ótimo é sempre atingido em um vértice (solução básica viável). Registre x* e verifique se ele satisfaz todas as restrições, então traduza-o de volta para termos gerenciais (por exemplo, unidades a produzir, rotas a usar).

Fórmula
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

Após obter x*, conduza a análise de sensibilidade (pós-otimalidade) para determinar o quanto cada coeficiente em c ou b pode mudar antes que a base atual — e, portanto, a solução ótima — mude. Os preços sombra (variáveis duais) quantificam o valor marginal de relaxar cada restrição. Embora o modelo seja determinístico, a análise de sensibilidade revela a robustez da solução a erros de estimativa de parâmetros sem abandonar a estrutura determinística.

Erros comuns

  • Tratar parâmetros incertos como estimativas de ponto fixo sem análise de sensibilidade subsequente pode produzir soluções que são ótimas no papel, mas frágeis na prática.
  • Esquecer de incluir restrições de não negatividade ou limites lógicos pode gerar soluções matematicamente ótimas, mas operacionalmente inviáveis (por exemplo, quantidades de produção negativas).
  • Interpretar erroneamente os preços sombra como valores marginais garantidos fora do intervalo de validade identificado na análise de variação.
  • Usar DLP quando o problema real tem estrutura inteira (por exemplo, número de caminhões) e arredondar soluções de PL — isso pode violar restrições ou perder ótimos verdadeiros.
  • Super-agregar objetivos em uma única soma ponderada sem validar se os pesos refletem com precisão as preferências das partes interessadas, ocultando importantes trade-offs.

Perguntas frequentes

O que torna a PL 'determinística' em oposição a 'estocástica'?

Na PL determinística, cada coeficiente na função objetivo, matriz de restrições e vetor do lado direito é uma constante conhecida. A PL estocástica, por outro lado, trata alguns ou todos esses como variáveis aleatórias com distribuições de probabilidade, buscando soluções que tenham bom desempenho na expectativa ou com alta probabilidade em diferentes cenários.

O algoritmo simplex é sempre eficiente?

Na prática, sim — o método Simplex resolve virtualmente todas as PLs do mundo real extremamente rápido. Teoricamente, ele pode levar tempo exponencial no pior caso (exemplos de Klee–Minty), mas os métodos de ponto interior (por exemplo, o algoritmo de Karmarkar) são executados em tempo polinomial e são competitivos para instâncias muito grandes.

Posso usar DLP se algumas das minhas variáveis de decisão devem ser números inteiros?

Não. Se as variáveis devem ser inteiras (por exemplo, número de máquinas a comprar), o modelo se torna um programa inteiro misto ou puro. Resolver o relaxamento da PL e arredondar pode violar restrições ou perder o verdadeiro ótimo inteiro; use um resolvedor MIP dedicado.

Como os preços sombra ajudam após a resolução?

O preço sombra (variável dual) de uma restrição informa o quanto o valor objetivo melhoraria se o lado direito dessa restrição fosse relaxado em uma unidade, dentro do intervalo de variação válido. Isso orienta as decisões sobre onde investir para expandir a capacidade de forma mais econômica.

Quando devo fazer um upgrade de DLP para PL Robusta ou Estocástica?

Faça o upgrade quando a incerteza dos parâmetros não for trivial e o custo de uma solução inviável ou ruim sob os valores de parâmetros realizados for significativo. Se um desvio de 10 a 20% em um coeficiente chave mudaria qual solução é preferida ou causaria violação de restrição, a suposição de certeza da PL determinística é muito forte.

Métodos relacionados

Fontes

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

    ISBN: 9780691059136
    Copiado.
  2. Linear programming. Wikipedia.

    Abrir referência da publicação
    Copiado.