A Programação Linear É Uma Técnica Matemática Usada Para Otimizar

O que acontece quando você tenta otimizar recursos sem entender o básico

A programação linear é uma técnica matemática usada para otimizar uma função objetivo linear sujeita a restrições lineares. O método simplex, desenvolvido por George Dantzig em 1947, percorre os vértices da região viável até encontrar a solução ótima. Isso soa simples na teoria, mas na prática você se depara com problemas numéricos que quebram a resolução facilmente. Eu trabalhei com um modelo de produção para uma indústria de alimentos que precisava maximizar o lucro diário. Tinhamos seis linhas de produção, doze restrições de matéria-prima e três equipamentos compartilhados. O modelo parecia sólido no papel. Quando rodei no GLPK, o solver retornou infeasible. Passei duas horas removendo uma restrição de capacidade que estava mal especificada — na verdade, eu tinha cometido um erro de conversão de unidades, confundindo quilogramas com toneladas. Um erro bobo, mas que demonstrou como a modelagem é mais crítica que a resolução em si.

por que a programação linear é uma técnica matemática usada para otimizar

O campo cresceu muito desde os primórdios do simplex. Hoje existem solveres comerciais como Gurobi, CPLEX e Xpress, além de opções open-source como HiGHS, CBC e o próprio GLPK. A escolha depende do tamanho do problema. Um modelo com poucas variáveis roda em segundos em qualquer coisa. Um modelo de logística com dezenas de milhares de restrições exige solveres modernos que usam ramificação-e-ajuste ou pontos interiores. Vou usar Python com PuLP para mostrar como construir um modelo funcional. O PuLP é direto e não exige instalação de solveres externos complexos — ele chama o CBC por padrão.

como montar um modelo básico passo a passo

Comece definindo o problema. Se for maximização ou minimização, deixe isso explícito logo no início. Eu sempre escrevo o modelo em notação matemática antes de codificar. Isso evita erros de interpretação que aparecem depois. Um exemplo prático rápido. Suponha que você quer minimizar o custo de uma mistura de rações. Dois ingredientes estão disponíveis, cada um com custo diferente e composição nutricional. O animal precisa de pelo menos certo nível de proteína e gordura.

import pulp

Criar o problema de minimização
prob = pulp.LpProblem("mistura_racao", pulp.LpMinimize)

Variáveis de decisão
x1 = pulp.LpVariable("ingredient_1", lowBound=0)
x2 = pulp.LpVariable("ingredient_2", lowBound=0)

Função objetivo: minimizar custo
prob += 3*x1 + 5*x2

Restrições
prob += 2*x1 + x2 >= 4   proteína mínima
prob += x1 + 3*x2 >= 9   gordura mínima

Resolver
prob.solve()

print("Custo ótimo:", pulp.value(prob.objective))
print("Ingredient 1:", pulp.value(x1))
print("Ingredient 2:", pulp.value(x2))

O resultado mostra o custo mínimo e a quantidade ideal de cada ingrediente. Isso é o básico. Modelos reais são mais complicados, mas a estrutura é a mesma. A primeira armadilha é o modelo viável mas sem solução ótima. Isso acontece quando as restrições não delimitam a região suficientemente. O solver retorna infinto ou unbounded. Na prática, eu já vi modelos onde alguém esqueceu de colocar um limite superior em uma variável de produção. O solver disse que o lucro era infinito. Claro que não era, mas o modelo não sabia disso. A segunda é a degeneração. Quando mais restrições do que o necessário se cruzam no mesmo ponto, o simplex pode ciclar — entrar em loop sem melhorar a solução. Solveres modernos detectam isso e aplicam técnicas anti-ciclo, mas é bom saber que existe. Um caso concreto que eu enfrentei: um modelo de escala de turnos com cerca de oitenta variáveis e cento e vinte restrições apresentou degeneração severa. O CBC demorou mais de três minutos para resolver, enquanto o Gurobi, com seu método de pontos interiores, encontrou a solução em menos de oito segundos. Não é sobre o modelo ser difícil, é sobre como o solver lida com a estrutura.

Outro ponto que poucos mencionam: sensibilidade numérica. Coeficientes muito grandes e muito pequenos na mesma matriz de restrições causam instabilidade. Já vi um modelo onde mudar um coeficiente de 0,001 para 0,000999 fez o solver declarar inviabilidade. O problema era puramente numérico. A solução foi escalar os dados — dividir todas as restrições por um fator comum para trazer os coeficientes para uma faixa similar.

quando linear programming não funciona

Se sua função objetivo ou alguma restrição não é linear, o modelo quebra. Relações quadráticas, logarítmicas, produtos de variáveis entre si — tudo isso exige outra ferramenta. Você pode usar programação quadrática ou não-linear, mas essas classes de problemas são muito mais difíceis de resolver e podem ter múltiplos ótimos locais. Restrições inteiras também mudam tudo. Se você precisa que variáveis sejam números inteiros — como número de máquinas a comprar, ou quantidade de caminhões — o problema vira um mixed-integer program (MIP). MIPs são NP-difíceis. Um modelo com vinte variáveis inteiras pode levar horas para resolver, enquanto uma versão contínua equivalente resolve em milissegundos. Eu tive um problema de locação de equipamentos onde a versão contínua dava uma solução de 3,7 máquinas. Arredondar para 4 parecia óbvio, mas aquela solução arredondada violava duas restrições de orçamento. A resolução inteira correta exigiu rodar o modelo MIP completo, que levou quarenta e dois minutos no solver aberto.

dicas práticas para quem está começando

Sempre inclua limites inferiores e superiores nas variáveis. Mesmo que seja óbvio que uma quantidade não pode ser negativa, solveres precisam dessa informação para montar a matriz corretamente. Variáveis sem bound inferior podem causar comportamento inesperado. Use análise de sensibilidade. A maioria dos solveres oferece relatórios de shadow price e intervalos de optimalidade. Essas informações dizem quanto o custo ótimo muda se você alterar uma restrição. Em um projeto de transporte, o shadow price de uma restrição de capacidade me disse exatamente quanto valia a pena pagar por capacidade extra. O valor era de R$ 12,50 por unidade adicional. Contratar frete extra a R$ 10,00 por unidade era economicamente viável. Verifique a viabilidade antes de confiar no resultado. Rode o modelo, mas também verifique se todas as restrições estão sendo satisfeitas numericamente. Às vezes o solver diz que encontrou uma solução ótima, mas alguns constrangimentos estão violados por uma pequena margem devido a tolerâncias numéricas. Um delta de 1e-6 em uma restrição de orçamento pode significar ultrapassar o valor em reais se os coeficientes forem grandes.

Documente o modelo em notação matemática antes de codificar. Isso parece perda de tempo, mas economiza horas de debugging. Um modelo mal documentado volta para te perseguir semanas depois quando alguém tenta modificar as restrições. Na minha experiência, a programação linear resolve cerca de setenta por cento dos problemas de otimização operacional que encontro. Os outros trinta por cento exigem aproximações, relaxamentos ou mudanças de abordagem. O importante é saber identificar onde o modelo linear funciona e onde ele perde força antes de gastar tempo modelando algo que não vai se encaixar na estrutura.