# Pesquisa Operacional e Otimização

> Transformar uma decisão num modelo com variáveis, função objetivo e restrições, e resolvê-lo — solução gráfica, simplex, programação inteira, branch-and-bound, transporte, Excel Solver e PuLP.

## 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:

1. **Variáveis de decisão** — o que você controla.
2. **Função objetivo** — o que maximizar ou minimizar.
3. **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)

1. Entender o problema.
2. Dizer em palavras quais são as respostas procuradas.
3. Definir as variáveis (com unidade!).
4. Descrever o objetivo em palavras.
5. Escrever o objetivo como equação linear.
6. Descrever cada restrição em palavras.
7. 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.

$$\max Z = 40x + 30y$$
$$\text{s.a.}\quad 2x + y \le 100,\qquad x + y \le 80,\qquad x, y \ge 0$$

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

1. **Enumeração**: listar todas as soluções. Inviável em problemas reais (a combinatória explode).
2. **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.
3. **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.
4. **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 |

```python
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á.

## Perguntas de revisão

1. **O que é pesquisa operacional?** A ciência da tomada de decisão: modelar e resolver problemas de alocação de recursos escassos.
2. **Quais são os três componentes de um modelo de otimização?** Variáveis de decisão, função objetivo e restrições.
3. **Qual a diferença entre restrição de limitação e de desempenho mínimo?** Limitação usa ≤ (recurso máximo); desempenho mínimo usa ≥.
4. **O que caracteriza um modelo de programação linear?** Variáveis contínuas e expressões lineares e aditivas.
5. **Por que o ótimo de uma PL está num vértice?** Porque, com objetivo linear, a reta de nível deixa a região factível por um vértice ou aresta.
6. **Quando existem ótimos alternativos?** Quando o objetivo é paralelo a uma restrição ativa.
7. **O simplex visita todos os vértices?** Não; vai ao vizinho que melhora o objetivo e para quando nenhum melhora.
8. **Por que a enumeração é inviável?** O número de combinações explode com o tamanho do problema.
9. **Por que o simplex sozinho não resolve problemas inteiros?** Pode devolver valores fracionários; é preciso branch-and-bound.
10. **Como funciona o branch-and-bound?** Resolve o relaxado, ramifica a variável fracionária em ≤ piso e ≥ teto e guarda o melhor inteiro.
11. **Como modelar "só em múltiplos de 7"?** $x = 7k$ com $k$ inteiro não negativo.
12. **Como modelar a ativação de uma instalação com capacidade 50?** $x \le 50y$ com $y$ binária e custo fixo no objetivo.
13. **Como converter minimização em maximização?** Maximizando o negativo do objetivo.
14. **O que é uma restrição ativa?** Uma restrição satisfeita com igualdade no ótimo — é o gargalo.
15. **Aumentar um recurso que não é gargalo melhora o resultado?** Não; só recursos de restrições ativas mudam o ótimo.
16. **Que erro comum acontece no Solver do Excel?** Esquecer a não negatividade ou inverter um sinal.
17. **Excel Solver ou PuLP?** Ambos dão o ótimo em modelos lineares; PuLP escala melhor, é versionável e mostra o log.
18. **Qual a relação entre previsão e otimização?** A previsão diz o que vai acontecer; a otimização decide o que fazer, usando a previsão como parâmetro.
19. **O que é preço sombra?** Quanto o objetivo melhora com uma unidade adicional de um recurso.
20. **Qual o ótimo do exemplo da marcenaria?** 20 mesas e 60 cadeiras, com lucro de 2600.

---
Fonte: Atlas de Dados — https://atlas.frediania.com/materia/otimizacao
