O que é programação linear
Programação linear é uma técnica de otimização que encontra o melhor valor, máximo ou mínimo, de uma função objetivo respeitando um conjunto de restrições lineares. Na indústria, ela responde perguntas como: quanto produzir de cada produto para ter o maior lucro com as horas de máquina e de mão de obra disponíveis?
O método Simplex, criado por George Dantzig em 1947, é o algoritmo que resolve esses problemas percorrendo os vértices da região viável até achar o ótimo, sem testar todas as combinações.
Mapa visual da programação linear
O mapa traz os elementos do modelo, a região viável com os quatro vértices, a solução ótima e o passo a passo do Simplex.
Elementos do modelo
| Elemento | Significado | No exemplo |
|---|---|---|
| Variáveis de decisão | O que se quer determinar | x = quantidade do produto A; y = quantidade do produto B |
| Função objetivo | O que se quer maximizar ou minimizar | Z = 40x + 30y (margem total) |
| Restrições | Limites dos recursos | 2x + y ≤ 100 e x + 2y ≤ 80 |
| Não negatividade | Não existe produção negativa | x ≥ 0 e y ≥ 0 |
| Região viável | Pontos que atendem a todas as restrições | Polígono com vértices (0,0), (50,0), (40,20) e (0,40) |
Exemplo: mix de produção de dois produtos
Cada unidade do produto A dá margem de 40 e cada unidade de B, de 30. A primeira restrição pode representar horas de máquina (A usa 2 horas, B usa 1, há 100 disponíveis); a segunda, horas de montagem (A usa 1, B usa 2, há 80 disponíveis).
Maximizar Z = 40x + 30y | 2x + y ≤ 100 | x + 2y ≤ 80 | x, y ≥ 0
Método gráfico: testar os vértices
Com duas variáveis, dá para desenhar as restrições e enxergar a região viável. A solução ótima está sempre em um vértice:
| Vértice (x, y) | Z = 40x + 30y | Observação |
|---|---|---|
| (0, 0) | 0 | Origem |
| (50, 0) | 2.000 | Só o produto A |
| (0, 40) | 1.200 | Só o produto B |
| (40, 20) | 2.200 | Interseção das duas restrições: ótimo |
A solução ótima é produzir 40 unidades de A e 20 de B, com Z = 2.200. Nesse ponto as duas restrições estão no limite: 2 × 40 + 20 = 100 e 40 + 2 × 20 = 80.
Como o Simplex chega ao mesmo resultado
- Formule o problema: função objetivo e restrições.
- Converta para a forma padrão: some variáveis de folga (2x + y + s1 = 100; x + 2y + s2 = 80).
- Monte a tabela inicial, partindo da origem (x = 0, y = 0).
- Itere: escolha a variável que mais melhora Z para entrar na base e a que limita primeiro para sair.
- Verifique a otimalidade: quando nenhuma variável melhora Z, a solução é ótima.
- Interprete: x = 40, y = 20, folgas zero e Z = 2.200.
Na prática, ninguém faz as tabelas à mão em problemas reais: o Solver do Excel, com o método LP Simplex, resolve centenas de variáveis em segundos.
Preço sombra: quanto vale mais uma hora
A análise de sensibilidade mostra quanto Z melhora se uma restrição for afrouxada. No exemplo, uma hora a mais de máquina aumenta Z em cerca de 16,67, e uma hora a mais de montagem, em cerca de 6,67. Esses valores, os preços sombra, dizem onde investir: vale mais ampliar a máquina do que a montagem, desde que o custo da hora extra seja menor que o ganho.
A mesma lógica aparece na teoria das restrições: o recurso com maior preço sombra é o gargalo econômico.
Aplicações
- Planejamento da produção: mix ótimo de produtos, como no exemplo, e apoio ao PCP.
- Problemas de corte: menor perda ao cortar chapas, bobinas e barras.
- Logística: transporte e alocação de cargas com menor custo.
- Mistura: ração, ligas metálicas e combustíveis com menor custo atendendo à especificação.
- Escalas de trabalho e alocação de recursos.
Erros comuns
- Modelagem incorreta da função objetivo, misturando receita com margem.
- Restrições esquecidas, que geram soluções impossíveis na fábrica.
- Sinal trocado (≤ no lugar de ≥).
- Ignorar que as variáveis precisam ser inteiras quando se trata de peças; nesse caso, use programação inteira.
- Usar o resultado sem conferir se faz sentido para quem opera.
Perguntas frequentes
O que é programação linear?
É uma técnica de otimização que maximiza ou minimiza uma função linear sujeita a restrições lineares, como recursos limitados.
O que é o método Simplex?
É o algoritmo criado por George Dantzig que percorre os vértices da região viável até encontrar a solução ótima.
Qual a solução do exemplo?
Produzir 40 unidades de A e 20 de B, com Z = 2.200, no vértice onde as duas restrições se cruzam.
Como resolver programação linear no Excel?
Use o suplemento Solver, defina a célula objetivo, as células variáveis e as restrições, e escolha o método LP Simplex.
O que é preço sombra?
É quanto a função objetivo melhora com uma unidade a mais de um recurso limitado.
Fontes
- DANTZIG, G. B. Linear Programming and Extensions. Princeton: Princeton University Press, 1963.
- HILLIER, F. S.; LIEBERMAN, G. J. Introdução à Pesquisa Operacional. Porto Alegre: AMGH.
- TAHA, H. A. Pesquisa Operacional. São Paulo: Pearson.
Quer decidir com números?
Baixe o e-book gratuito sobre indicadores de desempenho para a gestão da produção.
Baixar e-book
Sobre o autor
Especialista em Lean Manufacturing e Gestão Comportamental
Mais de 20 anos de indústria automotiva e metalmecânica (GM e Dana), especialista em Lean Manufacturing desde 2006. Instrutor e mentor do SENAI no programa Brasil Mais Produtivo, com consultorias, treinamentos e auditorias em mais de 50 empresas, unindo qualidade, produtividade e desenvolvimento de pessoas.