Visão geral
Pesquisa operacional (PO) é a ciência da tomada de decisão: alocar recursos escassos com métodos quantitativos. Nasceu de operações militares e hoje está em produção, logística, finanças, escalas de trabalho. Não tem nada a ver com "programar computadores": programação aqui significa planejamento.
A previsão responde "o que vai acontecer?"; a otimização responde "o que fazer diante disso?". Um modelo preditivo pode fornecer os parâmetros (demanda, preços, capacidade) de um modelo de otimização.
Anatomia de um modelo
Todo modelo de otimização tem três partes:
- Variáveis de decisão — o que você controla.
- Função objetivo — o que maximizar ou minimizar.
- Restrições — as condições que a solução precisa respeitar.
Famílias
- PL (programação linear): variáveis contínuas, expressões lineares e aditivas.
- PLI (inteira): todas as variáveis inteiras.
- PLIM (inteira mista): parte inteira, parte contínua.
- Não linear (ex.: \(x_1 x_2\), \(x^2\)): fora do escopo da PL.
- Heurísticas e metaheurísticas: soluções boas em tempo razoável, sem garantia de ótimo. É o trade-off tempo × qualidade.
Receita de formulação (7 passos)
- Entender o problema.
- Dizer em palavras quais são as respostas procuradas.
- Definir as variáveis (com unidade!).
- Descrever o objetivo em palavras.
- Escrever o objetivo como equação linear.
- Descrever cada restrição em palavras.
- Escrever as restrições como equações lineares.
Definir o objetivo antes das restrições evita modelar o foco errado.
| Tipo de restrição | Forma | Palavras-chave |
|---|---|---|
| Limitação de recurso | \(\le\) | "até", "no máximo", "não pode ultrapassar" |
| Desempenho mínimo | \(\ge\) | "pelo menos", "no mínimo" |
| Conservação / balanço | \(=\) | "igual", "tudo que entra sai" |
| Domínio | \(x \ge 0\), inteiro, binário | "unidades", "ativar ou não" |
Exemplo resolvido
Uma marcenaria faz mesas (lucro 40) e cadeiras (lucro 30). Cada mesa usa 2 m² de madeira e cada cadeira 1 m²; há 100 m². Cada peça leva 1 hora e há 80 horas.
Vértices da região factível: \((0, 80) \Rightarrow 2400\); \((20, 60) \Rightarrow 2600\); \((50, 0) \Rightarrow 2000\). Ótimo: 20 mesas e 60 cadeiras, Z = 2600, com as duas restrições ativas.
Métodos de solução
- Enumeração: listar todas as soluções. Inviável em problemas reais (a combinatória explode).
- Solução gráfica (só duas variáveis): cada desigualdade vira uma reta; testa-se um ponto para achar o lado válido; desenha-se a região factível; desloca-se a reta do objetivo até o último vértice.
- Simplex: parte de um vértice e caminha para o vizinho que mais melhora \(Z\), parando quando nenhum melhora. Não visita todos os vértices.
- Branch-and-bound (para inteiros): resolve o problema relaxado; se uma variável vem fracionária (\(x = 5{,}7\)), ramifica em \(x \le 5\) e \(x \ge 6\) e guarda a melhor solução inteira.
Por que o ótimo linear está num vértice? Porque o objetivo é linear: a reta de nível sai da região factível por um vértice (ou por uma aresta inteira, quando há ótimos alternativos).
Truques de modelagem
- Ativação binária: \(x \le M\,y\), com \(y \in \{0,1\}\) e um custo fixo \(c\,y\) no objetivo (ex.: abrir um depósito de capacidade 50 → \(x \le 50y\)).
- Múltiplos: "só em lotes de 7" → \(x = 7k\), \(k\) inteiro.
- Minimizar equivale a maximizar o negativo (o solver faz isso sozinho).
- Restrição "mole": variável de folga com penalidade no objetivo.
- Tempo: índice \(t\) nas variáveis e balanço de estoque \(E_t = E_{t-1} + P_t - D_t\).
- Transporte: origens com oferta, destinos com demanda, custo por rota; minimizar o custo total.
- Transbordo: pontos intermediários onde o que entra é igual ao que sai.
Ferramentas
| Ferramenta | Quando usar | Limite |
|---|---|---|
| Solução gráfica | 2 variáveis, para entender a geometria | não escala |
| Excel Solver (LP Simplex) | modelos pequenos, comunicar com quem usa planilha | difícil de escalar, sem log, erros de sinal |
| PuLP + CBC (Python) | dezenas a milhares de variáveis, versionável | só linear |
| Pyomo, OR-Tools, Gurobi, CPLEX | modelos grandes ou não lineares | curva de aprendizado / licença |
import pulp
m = pulp.LpProblem("marcenaria", pulp.LpMaximize)
x = pulp.LpVariable("mesas", lowBound=0, cat="Integer")
y = pulp.LpVariable("cadeiras", lowBound=0, cat="Integer")
m += 40*x + 30*y # objetivo
m += 2*x + y <= 100, "madeira"
m += x + y <= 80, "horas"
m.solve()
print(pulp.LpStatus[m.status], x.value(), y.value(), pulp.value(m.objective))
Como avaliar a solução
- Confira o status (ótimo, inviável, ilimitado) e cada restrição no ponto encontrado.
- Identifique as restrições ativas (gargalos): aumentar um recurso que não é gargalo não muda nada.
- Faça análise de cenários trocando parâmetros e resolvendo de novo.
- Leituras complementares: dualidade, preço sombra (quanto o objetivo melhora com uma unidade a mais de recurso), folga e custo reduzido.
- Soluções diferentes com o mesmo valor podem ser ótimos alternativos.
- O solver garante o ótimo do modelo — se o modelo estiver errado (unidade, sinal, restrição esquecida), o ótimo também estará.