O que realmente acontece quando você tenta resolver exercícios de programação linear na prática
A maioria dos cursos introduz programação linear como se fosse um problema puramente algébrico. Você monta a função objetivo, define as restrições, aplica o método simplex e pronto. Na vida real, isso raramente funciona tão limpo. Eu passei anos corrigindo trabalho de alunos e vendo projetos de otimização desandar por pequenas inconsistências que ninguém mencionava nos livros. Antes de entrar nos exercícios propriamente ditos, é preciso entender que programação linear tem duas partes separadas: a modelagem e a resolução. A resolução é mecânica. A modelagem é onde tudo costuma dar errado.
Exercicios de pa: onde a maioria das pessoas trava
Os exercícios mais comuns que aparecem em listas e provas envolvem problemas de mistura, transporte e design de produção. Eu sempre vejo os mesmos erros. O primeiro é definir variáveis de decisão com nomes que não fazem sentido no contexto. Vou dar um exemplo específico. Num problema de minimização de custo para uma dieta, um aluno definiu x1, x2, x3 sem qualquer legenda. Quando eu perguntei o que cada variável representava, ele não soube responder. Variáveis sem definição são inúteis. Anote sempre: x1 = quilos de ingrediente A, x2 = quilos de ingrediente B, e assim por diante. Isso parece óbvio até você estar sob pressão de tempo.
O segundo erro comum é esquecer variáveis de folga. No método simplex, as restrições de desigualdade precisam ser transformadas em igualdade adicionando variáveis de folga. Sem elas, você não consegue montar a tabela inicial do simplex corretamente. Isso já vi derrubar gente competente durante provas. Faltou apenas uma variável de folga num problema com cinco restrições, e a solução final ficou completamente errada porque a base inicial estava mal construída.
Como montar um modelo de programação linear passo a passo
Vamos partir de um problema concreto. Uma fábrica produz dois produtos, A e B. O produto A dá lucro de R$ 12 por unidade. O produto B dá lucro de R$ 18 por unidade. A máquina X tem capacidade de 100 horas por semana. Produzir uma unidade de A gasta 2 horas na máquina X e 1 hora na máquina Y. Produzir uma unidade de B gasta 3 horas na máquina X e 4 horas na máquina Y. A máquina Y tem capacidade de 160 horas por semana. Queremos maximizar o lucro. Primeiro passo: identificar as variáveis de decisão. Seja x = quantidade de produto A a produzir por semana. Seja y = quantidade de produto B a produzir por semana. Pontos importantes aqui: as variáveis são contínuas (não necessariamente inteiras) e não podem ser negativas.
Segundo passo: escrever a função objetivo. Maximizar Z = 12x + 18y. Simples, mas verifique os sinais. Se for minimização, cuidado para não trocar o sinal dos coeficientes por impulso. Terceiro passo: listar as restrições. A capacidade da máquina X limita a produção: 2x + 3y <= 100. A capacidade da máquina Y: 1x + 4y <= 160. Restrições de não negatividade: x >= 0, y >= 0. Note que eu escrevi as restrições na forma padrão com
= porque queremos limitar o uso dos recursos, não obrigá-lo a usar uma quantidade mínima.
Essa sequência — variáveis, objetivo, restrições — é o núcleo de qualquer exercício de programação linear. Você repete esse processo para problemas muito mais complexos, incluindo aqueles com dezenas de variáveis e centenas de restrições.
Resolvendo pela região viável e pelo método gráfico
Para problemas com duas variáveis, o método gráfico é direto e didático. Desenhe cada restrição no plano xy, identifique a interseção das semi-planiros, e o resultado é a região viável. Os vértices dessa região são os pontos candidatos a solução ótima. No exemplo acima, as restrições limitam a região a um polígono com quatro vértices: a origem (0, 0), o ponto onde x = 0 e a restrição da máquina Y é ativa (0, 40), o ponto onde y = 0 e a restrição da máquina X é ativa (50, 0), e o ponto de interseção das duas restrições ativas. Para encontrar esse último ponto, resolva o sistema:
2x + 3y = 100 x + 4y = 160
Multiplicando a segunda equação por 2 e subtraindo da primeira: 2x + 3y - 2x - 8y = 100 - 320. Isso dá -5y = -220, logo y = 44. Substituindo: x + 176 = 160, então x = -16. Esse resultado é inviável porque x seria negativo. A interseção real das duas retas está fora da região viável. Isso mostra algo importante que poucos livros enfatizam: nem sempre o ponto de interseção de duas restrições é viável. Você precisa verificar se todas as restrições estão satisfeitas simultaneamente. No nosso caso, o vértice relevante é a interseção entre a restrição da máquina X e o eixo y, ou seja, o ponto (0, 40). O lucro ali é Z = 12(0) + 18(40) = R$ 720. Compare com o ponto (50, 0): Z = 12(50) + 18(0) = R$ 600. A solução ótima para este problema é produzir apenas o produto B, 40 unidades, com lucro de R$ 720.
Quando o método gráfico não basta e você precisa do simplex
O método gráfico funciona bem para duas variáveis. Com três, você ainda consegue visualizar no espaço tridimensional. Com quatro ou mais, a coisa fica impraticável. É aí que entra o método simplex, que opera movendo-se de vértice a vértice da região viável até encontrar o ótimo. O simplex trabalha com a forma padrão do problema, onde todas as restrições são igualdades. Para transformar 2x + 3y <= 100 em igualdade, adicionamos uma variável de folga s1 >= 0, resultando em 2x + 3y + s1 = 100. Da mesma forma, x + 4y + s2 = 160.
A tabela simplex inicial fica: Base | x | y | s1 | s2 | RHS
👉 Clique no botão abaixo para saber mais sobre o assunto!
s1 | 2 | 3 | 1 | 0 | 100 s2 | 1 | 4 | 0 | 1 | 160
Z |-12|-18| 0 | 0 | 0 O critério de entrada é a variável com o coeficiente mais negativo na linha Z. Nesse caso, y entra na base com coeficiente -18. O ratio test decide qual variável sai: divida o RHS pela coluna de y, considerando apenas coeficientes positivos. Para s1: 100/3 = 33,33. Para s2: 160/4 = 40. O menor ratio é 33,33, então s1 sai da base.
Depois de uma iteração, você faz os operadores de linha para zerar os outros coeficientes da coluna de y. O processo continua até que todos os coeficientes na linha Z sejam não negativos. Nesse ponto, a solução atual é ótima. Na prática, resolver simplex manualmente para problemas grandes é moroso e propenso a erros aritméticos. Eu já perdi tempo valioso em provas porque cometi um erro de escala numa linha da tabela. A recomendação é usar software para problemas com mais de três variáveis. Ferramentas como o OpenSolver para Excel, ou bibliotecas como scipy.optimize.linprog em Python, fazem o trabalho pesado.
Dicas práticas que ninguém conta nos livros
Verificar a escala dos coeficientes. Problemas mal escalados causam instabilidade numérica no simplex. Se uns coeficientes são da ordem de 1 e outros da ordem de 10000, o solver pode ter dificuldades. Normalizar antes de resolver é um habito que evita dor de cabeça. Atenção às variáveis livres. Às vezes uma variável pode assumir valores positivos ou negativos sem restrição. Nesses casos, substitua essa variável pela diferença de duas variáveis não negativas: x = x+ - x-, com x+ >= 0 e x- >= 0. Isso aumenta o número de variáveis mas preserva a forma padrão exigida pelo simplex.
Problemas de transporte têm estrutura especial. Se o exercício for claramente um problema de transporte — múltiplas fontes com oferta, múltiplos destinos com demanda, custos lineares — não use simplex geral. Use o método do canto noroeste, análise de stepping-stone ou, melhor ainda, o método MODI. Isso reduz o número de iterações de forma significativa em comparação com o simplex genérico. Eu vi estudantes perderem 40 minutos num problema que poderia ser resolvido em 12 minutos usando a estrutura de transporte adequada.
Exercicios de pa para prática
Se você quer exercícios para treinar, a maioria dos livros de pesquisa operacional do Brasil traz listas extensas. "Pesquisa Operacional" de Ensio M. A. M. Mendes e "Otimização Inteira e Programação Linear" de José Neto são boas referências. Sites como o do professor Haroldo Campelo, da UFMG, e materiais da Poli-USP também disponibilizam listas gratuitas. Procure por exercícios que envolvam dualidade e sensibilidade, pois são tópicos que caem com frequência e que muitos alunos negligenciam. Um exercício recomendável para começar é o clássico problema da dieta de George Dantzig. Ele ilustra perfeitamente a diferença entre modelar corretamente e modelar de forma ingênua. Diferente do problema de mistura padrão, a versão correta do problema da dieta inclui restrições de e para cada nutriente, não apenas limites inferiores. Esse detalhe muda completamente a estrutura do problema e a solução encontrada.
Análise de sensibilidade: o que a maioria dos exercícios ignora
Depois de resolver o problema principal, a análise de sensibilidade pergunta: o que acontece se um parâmetro mudar? O coeficiente da função objetivo pode variar dentro de uma faixa sem alterar a base ótima. Os preços-sombra das restrições indicam quanto o valor ótimo melhora se você relaxar ligeiramente uma restrição. No exemplo da fábrica, o preço-sombra da restrição da máquina X pode ser interpretado como o valor adicional de lucro por hora extra nessa máquina. Se você conseguir expandir a capacidade da máquina X em uma hora, o lucro aumentaria em aproximadamente o valor do preço-sombra associado. Esse insight é frequentemente mais valioso do que a solução ótima em si, porque informa decisões operacionais reais.
Uma limitação importante da análise de sensibilidade clássica é que ela assume linearidade e certeza dos parâmetros. Na prática, coeficientes raramente são fixos. Demandas flutuam, custos variam, capacidades mudam. Quando essa incerteza é significativa, programação linear estocástica ou robusta oferece abordagens mais adequadas, ainda que mais complexas.
Erros comuns que eu vejo repetidamente
Transformar restrições de igualdade em desigualdades sem motivo. Isso amplia artificialmente a região viável e pode levar a soluções que parecem melhores mas são fisicamente impossíveis. Se o problema diz que você deve usar exatamente 100 kg de matéria-prima, isso é uma restrição de igualdade, não de desigualdade. Esquecer de verificar se a solução é inteira quando o problema exige inteiros. Programação linear contínua não garante soluções inteiras automaticamente. Se você precisa de 50 unidades de um produto e o solver retorna 49,7, o problema exige programação inteira, que é significativamente mais difícil de resolver. Para pequenos problemas, arredondar pode funcionar, mas isso pode violar restrições e precisa ser checado.
Acreditar que um solver retornou a solução ótima sem verificar se houve convergência. Solvers podem parar por limite de iterações, tolerância numérica ou problemas de escala. Sempre confira o status da solução. Um solver que para com um aviso de "near-optimal" ou "numerical issues" não deu a resposta que você espera. Por fim, não confunda solução inviável com solução ótima. Se o solver declara inviabilidade, a região viável é vazia. Isso significa que as restrições são contraditórias. Revise o modelo: talvez haja uma restrição demais, um coeficiente errado, ou uma interpretação equivocada do enunciado. Eu já passei uma tarde inteira rastmando um erro num coeficiente de restrição que estava multiplicado por 10 por engano. O modelo parecia correto na teoria, mas a inviabilidade era constante.
Programação linear é uma ferramenta poderosa, mas como toda ferramenta, ela exige respeito pelo que modela e pelo que deixa de modelar. Exercícios bem feitos vão além do cálculo numérico. Eles ensinam a traduzir situações reais em linguagem matemática precisa, a interpretar resultados com criticidade e a reconhecer quando o modelo simples não é suficiente.
