Programação Linear

Programação Linear em Resumo

Programação linear (linear programming, PL) é o problema de otimizar uma função objetivo (objective function) linear sujeita a restrições (constraints) de igualdade e/ou desigualdade lineares. A PL é uma das subclasses mais importantes de otimização convexa (convex optimization) porque:

  • O conjunto viável (feasible set) é um poliedro convexo (convex polyhedron) (uma interseção de semiespaços (half-spaces) e hiperplanos (hyperplanes)).
  • Qualquer ótimo local é um ótimo global.
  • Há uma teoria rica de dualidade (duality), que fornece tanto intuição quanto certificados práticos de otimalidade.

A PL fica na interseção entre teoria de otimização e tomada de decisão no mundo real, e aparece com frequência em sistemas de inteligência artificial (artificial intelligence, IA) que precisam alocar recursos escassos, planejar ações ou resolver problemas estruturados em larga escala. Ela também fundamenta estruturas mais complexas como Programação Inteira Mista, em que algumas decisões precisam ser inteiras.

Formulações do Problema e “Forma Padrão”

Formas primais comuns

Uma forma muito comum de PL é:

[ \min_{x \in \mathbb{R}^n} ; c^\top x \quad \text{s.t.} \quad Ax \le b ]

Opcionalmente com limites como (x \ge 0), ou igualdades e desigualdades misturadas.

Outra forma “canônica” amplamente usada é:

[ \max ; c^\top x \quad \text{s.t.} \quad Ax \le b,; x \ge 0 ]

Todas elas são equivalentes por transformações simples.

Forma padrão (igualdades + não negatividade)

Muitos livros-texto e solucionadores (solvers) reduzem PLs à forma padrão (standard form):

[ \min ; c^\top x \quad \text{s.t.} \quad Ax = b,; x \ge 0 ]

Você pode converter entre formas usando alguns truques de modelagem:

  • Desigualdade para igualdade via variáveis de folga (slack variables)
    Se (a_i^\top x \le b_i), introduza uma variável de folga (s_i \ge 0) e escreva: [ a_i^\top x + s_i = b_i ]

  • Variáveis livres (sinal não restrito)
    Se uma variável (y) pode ser negativa, represente-a como: [ y = y^+ - y^- \quad \text{with } y^+ \ge 0,; y^- \ge 0 ]

  • Restrições “(\ge)”
    Se (a_i^\top x \ge b_i), você pode multiplicar ambos os lados por (-1) para obter ((-a_i^\top x \le -b_i)) e então aplicar o truque das variáveis de folga.

Essas transformações importam na prática porque explicam como os solucionadores estruturam internamente o problema e por que as restrições de não negatividade são tão centrais para algoritmos de PL.

Geometria: Por que a PL é Convexa e por que Ótimos Vivem nos Cantos

A região viável (feasible region) de uma PL é um poliedro (polyhedron): uma interseção de semiespaços como (a_i^\top x \le b_i). Esse conjunto é convexo, então a PL é um caso especial de Otimização Convexa.

Um fato geométrico-chave:

  • Se uma PL tem uma solução ótima e o conjunto viável é não vazio e limitado na direção relevante, então existe uma solução ótima em um ponto extremo (extreme point) (um “canto” ou vértice (vertex)) do poliedro.

Essa é a intuição por trás do método do simplex (simplex method): buscar entre vértices em vez de na região contínua inteira.

Viabilidade, Limitabilidade e o que Pode Dar Errado

Uma PL pode falhar em retornar um ótimo finito “normal” por alguns motivos:

1) Inviável: nenhuma solução satisfaz as restrições

Exemplo:

  • (x \ge 1)
  • (x \le 0)

Não existe (x) que satisfaça ambas.

A inviabilidade não é apenas um estado de erro — muitas vezes é um sinal útil de modelagem (por exemplo, suas restrições de capacidade estão apertadas demais, ou restrições de demanda estão inconsistentes).

2) Ilimitada: o objetivo pode diminuir para sempre (para minimização)

Exemplo: [ \min ; -x \quad \text{s.t.} \quad x \ge 0 ] Quando (x \to \infty), o objetivo (-x \to -\infty). Não há ótimo finito.

3) Viável e limitada: tem pelo menos uma solução ótima

A maioria dos problemas práticos de planejamento busca estar nesse regime.

Certificados e diagnósticos (intuição)

Um recurso poderoso da PL é que inviabilidade e ilimitabilidade têm “certificados” que os solucionadores muitas vezes conseguem produzir, fortemente conectados à dualidade (próxima seção). Essa é uma das razões pelas quais a PL é amplamente usada em sistemas de planejamento críticos para segurança e em pipelines de pesquisa operacional (operations research).

Dualidade: o Outro Problema Escondido Dentro do Primeiro

Dualidade é uma das ideias mais importantes em otimização, discutida de forma geral em Otimização com Restrições. Em PL, ela se torna especialmente limpa e interpretável.

Um par primal/dual padrão

Considere o primal na forma “max” com desigualdades:

Primal (P): [ \max ; c^\top x \quad \text{s.t.} \quad Ax \le b,; x \ge 0 ]

Seu dual é:

Dual (D): [ \min ; b^\top y \quad \text{s.t.} \quad A^\top y \ge c,; y \ge 0 ]

Aqui:

  • (x) são variáveis de decisão primais (por exemplo, níveis de produção, remessas).
  • (y) são variáveis duais (dual variables) (frequentemente chamadas de preços-sombra (shadow prices) ou multiplicadores de Lagrange (Lagrange multipliers)).

Dualidade fraca

Para qualquer (x) primal-viável e (y) dual-viável: [ c^\top x \le b^\top y ] Assim, o objetivo do dual sempre fornece um limite superior para o objetivo do primal (para esse pareamento na forma de maximização).

Dualidade forte (o superpoder da PL)

Sob condições brandas (por exemplo, se um dos problemas é viável e limitado), a PL satisfaz:

[ \max(P) = \min(D) ]

Isso é dualidade forte (strong duality). Significa que:

  • Você pode verificar otimalidade encontrando (x) e (y) viáveis com valores de objetivo iguais.
  • Variáveis duais frequentemente têm significado econômico direto e viabilizam análise de sensibilidade.

Intuição de preço-sombra

Se a restrição primal (a_i^\top x \le b_i) é um limite de recurso (horas de trabalho, tempo de GPU, orçamento), então a variável dual (y_i) muitas vezes pode ser interpretada como:

“Quanto o objetivo ótimo melhoraria se eu aumentasse o recurso (b_i) em uma unidade (localmente).”

Isso é extremamente útil em planejamento: diz quais restrições “valem a pena pagar para relaxar”.

Folga Complementar: Quando uma Restrição “Pega”

Folga complementar (complementary slackness) conecta soluções ótimas primais e duais.

Para o par primal/dual acima, na otimalidade:

  • Para cada restrição primal de desigualdade (i): [ y_i , (b_i - (Ax)_i) = 0 ] Ou a restrição está ativa ((Ax)_i = b_i) (recurso totalmente usado) e então (y_i) pode ser positiva, ou há folga e (y_i = 0).

  • Para cada variável primal (j) (com (x \ge 0)): [ x_j , ((A^\top y)_j - c_j) = 0 ] Ou (x_j > 0) e a restrição dual correspondente está ativa ((A^\top y)_j = c_j), ou a restrição dual está folgada e (x_j = 0).

A folga complementar é tanto uma condição teórica quanto uma ferramenta prática de depuração: se um solucionador afirma otimalidade, essas condições devem valer aproximadamente (até uma tolerância numérica).

Simplex vs Métodos de Ponto Interior: Duas Intuições Complementares

Solucionadores modernos de PL normalmente implementam variantes do simplex, métodos de ponto interior (interior-point methods), ou ambos.

Método do simplex (caminhada entre vértices) (vertex-walking)

Ideia: Mover ao longo das arestas do poliedro viável de vértice em vértice, melhorando o objetivo a cada passo.

  • Trabalha com uma base (basis): um conjunto de restrições ativas que define o vértice atual.
  • Cada pivoteamento (pivot) troca uma variável para dentro da base e outra para fora, movendo para um vértice vizinho.

Prós:

  • Muitas vezes é extremamente rápido na prática em muitas PLs estruturadas.
  • Produz uma solução básica viável (basic feasible solution) (um vértice), que frequentemente é esparsa e interpretável.
  • Oferece forte comportamento de partida a quente (warm start) (útil se você resolve PLs relacionadas repetidamente).

Contras:

  • Tempo de execução exponencial no pior caso (embora raro na prática).
  • Pode enfrentar degenerescência (degeneracy) (muitas restrições ativas), exigindo regras anti-ciclagem (anti-cycling rules).

Métodos de ponto interior (mover pelo meio)

Ideia: Adicionar um termo de barreira (barrier term) e seguir um caminho central (central path) pelo interior da região viável, convergindo ao ótimo sem “pular” entre vértices.

Prós:

  • Complexidade em tempo polinomial e excelente desempenho em muitas PLs muito grandes e esparsas.
  • Comportamento de escalabilidade frequentemente mais previsível.

Contras:

  • As soluções podem ficar “mais internas” até o final; nem sempre resultam em uma solução limpa em vértice sem pós-processamento (post-processing).
  • Partida a quente pode ser menos direta do que no simplex (varia por solucionador).

Qual você deve usar?

  • Se você precisa de velocidade em muitas PLs similares (reotimizando com pequenas mudanças), o simplex pode ser atraente.
  • Para PLs muito grandes e esparsas, métodos de ponto interior geralmente são uma escolha forte.
  • Na prática: use um solucionador de alta qualidade (comercial ou open-source) e deixe-o escolher, a menos que você tenha um motivo específico.

Padrões de Modelagem que Você Vai Usar de Novo e de Novo

PL é menos sobre matemática sofisticada e mais sobre transformar restrições reais e bagunçadas em expressões lineares. Alguns padrões reutilizáveis comuns:

1) Alocação de recursos (restrições de orçamento/capacidade)

Você escolhe níveis de atividade (x_j) para maximizar utilidade:

  • Objetivo: (\max \sum_j v_j x_j)
  • Restrições de recurso: (\sum_j a_{ij} x_j \le b_i)
  • Limites: (0 \le x_j \le \bar{x}_j)

Este é o template básico para alocação entre produtos, equipes, trabalhos de computação ou campanhas de anúncios.

2) Transporte e conservação de fluxo (cadeias de suprimento, redes)

Variáveis representam fluxo nas arestas:

  • (x_{ij} \ge 0): quantidade enviada do nó (i) para o nó (j)
  • Restrições de oferta: (\sum_j x_{ij} \le s_i)
  • Restrições de demanda: (\sum_i x_{ij} \ge d_j)
  • Conservação de fluxo: entrada = saída em nós intermediários

Muitos problemas de fluxo em redes são PLs com estrutura especial que podem ser resolvidas de forma extremamente eficiente.

3) Atribuição / matching (frequentemente PL + estrutura de integralidade)

Atribuição clássica:

  • (x_{ij} \in {0,1}): atribuir o trabalhador (i) ao trabalho (j)

Se você relaxar para (0 \le x_{ij} \le 1), você obtém uma PL. Curiosamente, a PL de atribuição frequentemente produz ótimos inteiros devido à unimodularidade total (total unimodularity), então a relaxação de PL pode resolver exatamente o problema discreto (um fato profundo e útil em otimização combinatória (combinatorial optimization)).

Quando a integralidade é realmente necessária e não é automaticamente implicada, você passa para Programação Inteira Mista.

4) Linearizando valores absolutos e normas \(\ell_1\)

Um padrão comum em aprendizado de máquina (machine learning) é transformar um objetivo (\ell_1) em uma PL.

Exemplo: minimizar (|x|_1) sujeito a restrições lineares (formulações no estilo busca de base (basis pursuit)): [ \min \sum_i |x_i| \quad \text{s.t.} \quad Ax = b ]

Introduza (t_i \ge 0) e imponha: [ -t_i \le x_i \le t_i ] Então minimize (\sum_i t_i). Isso vira uma PL.

5) Min/max de expressões lineares via epígrafo

Para modelar: [ \min_x \max_k (a_k^\top x + b_k) ] Introduza (t) e escreva: [ \min_{x,t} ; t \quad \text{s.t.} \quad a_k^\top x + b_k \le t ;;\forall k ] Isso é uma PL, amplamente usada em otimização robusta (robust optimization) e planejamento de pior caso.

Exemplos Práticos

Exemplo 1: Alocação de recursos para jobs de treinamento de modelos

Suponha que você tenha 3 jobs de treinamento competindo por GPU-horas e memória limitadas. Seja (x_j) a fração de uma execução de treinamento planejada que você realiza (0 a 1). Você quer maximizar o valor esperado.

  • Valores: (v = [9, 6, 4])
  • GPU-horas por execução completa: ([8, 6, 2]), total 10
  • Memória por execução completa: ([6, 4, 1]), total 7

PL: [ \max ; 9x_1 + 6x_2 + 4x_3 ] s.t. [ 8x_1 + 6x_2 + 2x_3 \le 10 ] [ 6x_1 + 4x_2 + x_3 \le 7 ] [ 0 \le x_j \le 1 ]

Isso captura um problema real de planejamento de operações de IA (AI ops): escolher quais experimentos rodar sob computação restrita.

Exemplo 2: Planejamento de transporte (cadeia de suprimentos)

Você tem fábricas (i) com ofertas (s_i), depósitos (j) com demandas (d_j), e custos de envio (c_{ij}). Seja (x_{ij}) o volume enviado.

[ \min \sum_{i,j} c_{ij} x_{ij} ] s.t. [ \sum_j x_{ij} \le s_i \quad \forall i ] [ \sum_i x_{ij} \ge d_j \quad \forall j ] [ x_{ij} \ge 0 ]

Esta é uma PL central que aparece em logística, entrega de anúncios e roteamento de dados.

Exemplo 3: Dimensionamento de equipe / escala como PL (fracionária ou agregada)

Muitos problemas de escala exigem inteiros (pessoas não são divisíveis), mas a PL ainda é útil de duas maneiras:

  1. Dimensionamento agregado (horas de trabalho contínuas)
  2. Relaxação de PL (LP relaxation) para obter limites e preços duais, depois refinado com integralidade (Programação Inteira Mista)

Uma PL simples de dimensionamento:

  • (x_t): número de horas de trabalho atribuídas ao intervalo de tempo (t)
  • Demanda (d_t): horas de trabalho necessárias

[ \min \sum_t c_t x_t \quad \text{s.t.} \quad x_t \ge d_t,; x_t \ge 0 ]

Para modelar estruturas de turno (por exemplo, turnos de 4 horas cobrindo vários intervalos), você define variáveis por turno e usa uma matriz de cobertura — ainda linear.

PL em Fluxos de Trabalho de IA e Aprendizado de Máquina

Mesmo que o treinamento de modelos profundos geralmente seja uma otimização não convexa (nonconvex optimization) sem restrições, a PL aparece em IA/aprendizado de máquina de várias formas:

  • Relaxações de PL para inferência discreta
    Inferência de máximo a posteriori (MAP inference) e minimização de energia (energy minimization) em alguns modelos gráficos (graphical models) podem ser aproximadas via relaxações de PL, produzindo limites e às vezes soluções exatas.

  • Otimização robusta e de pior caso
    Quando conjuntos de incerteza são poliédricos, restrições robustas frequentemente permanecem lineares usando truques de epígrafo. Muitos problemas de planejamento robusto se reduzem a PLs.

  • Análise adversarial sob modelos lineares
    Para classificadores lineares (linear classifiers) ou aproximações localmente lineares (locally linear approximations), encontrar perturbações de pior caso sob limites (\ell_\infty) pode virar uma PL.

  • Otimização de operações em torno de sistemas de aprendizado de máquina
    Alocação de recursos para treino/inferência, escalonamento de data centers, limitação de taxa (rate limiting) e planejamento de suprimentos em torno de produtos guiados por aprendizado de máquina frequentemente são problemas de PL/Programação Inteira Mista.

Assim, a PL é uma “ponte” prática entre modelos preditivos e sistemas de tomada de decisão.

Resolvendo PLs na Prática

Solucionadores e ferramentas de modelagem

Solucionadores populares de PL incluem:

  • Comerciais: Gurobi, CPLEX, Mosek
  • Open-source: HiGHS, GLPK, CBC (frequentemente via camadas de modelagem)

Camadas de modelagem comuns:

  • CVXPY (Python) para modelagem de otimização convexa
  • PuLP, Pyomo (mais orientadas à pesquisa operacional)
  • OR-Tools (Google; forte para ecossistemas de roteamento/escala)

Exemplo com CVXPY (alocação de recursos)

import cvxpy as cp
import numpy as np

v = np.array([9.0, 6.0, 4.0])
gpu = np.array([8.0, 6.0, 2.0])
mem = np.array([6.0, 4.0, 1.0])

x = cp.Variable(3)

constraints = [
    gpu @ x <= 10,
    mem @ x <= 7,
    x >= 0,
    x <= 1
]

objective = cp.Maximize(v @ x)
prob = cp.Problem(objective, constraints)
prob.solve(solver=cp.HIGHS)

print("status:", prob.status)
print("optimal value:", prob.value)
print("x:", x.value)
print("shadow prices (dual values):", [c.dual_value for c in constraints[:2]])

A última linha mostra valores duais para as duas restrições de capacidade — interpretáveis como preços-sombra de GPU-horas e memória.

Dicas práticas

  • Escale suas unidades para evitar coeficientes cobrindo muitas ordens de magnitude (estabilidade numérica).
  • Adicione limites explícitos quando fizer sentido (mesmo limites superiores grandes) para ajudar solucionadores.
  • Use valores duais para fazer análise de sensibilidade (sensitivity analysis): qual restrição está limitando?
  • Se você resolve repetidamente PLs similares (por exemplo, planejamento de horizonte rolante (rolling horizon planning)), considere solucionadores/algoritmos que suportem bem partidas a quente (frequentemente baseados em simplex).

Principais Conclusões

  • Programação linear otimiza um objetivo linear sobre um poliedro convexo, tornando-a uma ferramenta central em Otimização Convexa.
  • PLs têm noções claras de viabilidade e limitabilidade; dualidade fornece certificados e interpretações poderosas.
  • Dualidade e folga complementar transformam restrições em “preços” interpretáveis e explicam quais restrições importam no ótimo.
  • Simplex explora vértices de forma eficiente na prática; métodos de ponto interior atravessam o interior com fortes garantias polinomiais e excelente desempenho em grande escala.
  • PL é um motor de modelagem para alocação de recursos, escalonamento (frequentemente via relaxações) e planejamento de cadeias de suprimento, e frequentemente dá suporte a sistemas de IA como a camada de tomada de decisão em torno de modelos preditivos.