Considere O Seguinte Problema De Programação Linear

Como resolver um problema de programação linear na prática

A maioria dos problemas de programação linear que eu vejo são mal formulados antes mesmo de chegar ao solver. O modelo em si é simples — maximizar ou minimizar uma função linear sujeita a restrições lineares — mas a parte chata é transformar a realidade em um sistema que o scipy ou o pulp consome sem reclamar. Vamos partir de um exemplo concreto que apareceu no meu último projeto. Uma empresa de logística precisa decidir quantos caminhões de cada tipo alocar para três rotas diferentes, respeitando capacidade de carga, disponibilidade de motoristas e um orçamento fixo. As variáveis são contáveis e não-negativas, as restrições são lineares, o objetivo é linear. Problema clássico de PL, certeiro. O formato matricial padrão é:

Maximizar z = c^Tx sujeito a Ax b e x 0 Na hora da implementação, eu sempre monto a matriz de coeficientes A, o vetor b das restrições e o vetor c da função objetivo. O scipy.optimize.linprog assume minimização por padrão, então se seu objetivo for maximização, basta multiplicar c por -1 e depois negar o resultado final. Isso já causou dor de cabeça pra muita gente, inclusive pra mim numa ocasião em que esqueci e o solver retornou o valor mínimo em vez do máximo.

Implementação com Python

Eu recomendo usar o pulp para problemas que precisam ser lidos e depurados com mais calma, porque ele deixa o modelo quase legível como matemática escrita. Já o linprog é mais rápido e mais leve, ideal para integrar em pipelines onde você não quer dependências pesadas. Com pulp, a estrutura fica assim: import pulp
prob = pulp.LpProblem("logistica", pulp.LpMaximize)
x = pulp.LpVariable.dicts("caminhao", range(3), lowBound=0, cat='Integer')
prob += 500*x['0'] + 300*x['1'] + 400*x['2']
prob += 2*x['0'] + x['1'] + 3*x['2'] <= 100
prob += x['0'] + x['1'] + x['2']

= 15

Quando eu rodei esse modelo, o solver retornou solução inteira automaticamente porque declarei as variáveis como Integer. Se eu tivesse esquecido esse detalhe, o pulp poderia retornar valores fracionários que não fazem sentido no mundo real — dois quintos de caminhão não sai pela estrada. Com o linprog, o código é mais baixo nível: from scipy.optimize import linprog
c = [-500, -300, -400]
A = [[2, 1, 3], [1, 1, 1]]
b = [100, 15]
res = linprog(c, A_ub=A, b_ub=b, bounds=[(0, None)]*3)
print(-res.fun, res.x)

Perceba que passei bounds como uma lista de tuplas, cada uma definindo limite inferior e superior para uma variável. Se você não passar bounds, o linprog assume por padrão que todas as variáveis estão entre 0 e infinito, o que geralmente é o comportamento certo, mas é bom saber que pode sobrescrever.

Problemas que eu encontrei no campo

Num projeto de mix de produção, eu me deparei com uma situação em que o solver retornava "infeasible" sem motivo aparente. As restrições pareciam razoáveis e o fato é que, ao isolar cada restrição individualmente, todas eram viáveis. O problema era que a interseção de todas elas era vazia quando consideramos a precisão numérica do solver. Eu resolvi relaxando levemente as restrições de igualdade, transformando-as em desigualdades com uma tolerância de 1e-6, e aí o problema ficou viável. Em PL, isso é comum: restrições de igualdade são muito mais restritivas do que parecem no papel. Outro caso foi com escala. Eu tinha variáveis na casa dos milhares e coeficientes na casa dos milionésimos. O simplex do linprog praticamente travou até eu normalizar as variáveis dividindo-as por 1000. Questão de unidades, nada demais, mas se você não prestar atenção nisso, pode perder horas achando que o modelo tá errado quando na verdade é só o solver que tá sofrendo com números mal escalados.

Pegadinhas comuns

Primeiro: o linprog só resolve problemas contínuos de PL. Se precisar de variáveis inteiras, use o pulp com o solver CBC ou o highspy. Segundo: não confie cegamente no status retornado pelo solver. Ele pode marcar "optimal" e ainda assim a solução tiver residuais grandes nas restrições. Sempre verifique se Ax b é satisfeito com a tolerância que faz sentido pro seu domínio. Terceiro: problemas de grande porte, digamos mais de dez mil variáveis, podem demorar minutos ou horas dependendo da esparsidade da matriz A. Nesse cenário, considere usar o ecos ou o clarabel em vez do simplex padrão do scipy. Se o seu problema tem relações não-lineares, como custos que variam quadraticamente com o volume ou restrições de produtividade com retornos decrescentes, a programação linear vai te entregar uma solução que não reflete a realidade. Nesses casos, parte pra programação não-linear ou inteira mista, mas saiba que o custo computacional sobe bastante. Um problema de PL de cinco mil variáveis resolve em segundos; o mesmo problema vira PLI (programação linear inteira) e pode levar dias. No fim das contas, a lição prática é: formule bem antes de chamar o solver, verifique escalas, teste com dados menores primeiro e nunca aceite o resultado do solver sem checar a viabilidade numérica das restrições. Já vi gente mandar solução inviável pros stakeholders achando que optimal era sinônimo de correto. Não é.