MODAL · UFMA · Iniciação Científica
0/0
Trilha de entrada · quatro semanas

Pesquisa Operacional e Programação Linear do zero

Um rotesimples para iniciantes em pesquisa operacional e programação linear.

4 semanas≈ 8 horas por semana
Álgebra do ensino médioúnico pré-requisito
Python + PuLPferramentas da trilha
2 4 6 2 4 6 x₁ (mesas) x₂ (armários) x₁ ≤ 4 2x₂ ≤ 12 3x₁ + 2x₂ ≤ 18 ótimo (2, 6) · z* = 36
Figura 1. O vocabulário da Semana 1 em uma imagem: as retas são as restrições, a área sombreada é a região viável, e a linha tracejada é o lucro z = 3x₁ + 5x₂ deslizando até o último ponto que ainda toca a região. Esse ponto é sempre um vértice. A figura serve para enxergar os conceitos, não para resolver nada no papel.
Antes da Semana 1 · reserve uma tarde

Preparação do ambiente

Nada aqui é difícil, mas resolver isso agora evita perder a primeira semana lutando com instalação. Se der qualquer problema, use o Google Colab e siga em frente. Instalar direito na sua máquina pode esperar.

1

Escolha onde vai programar

Caminho rápido: Google Colab, que roda no navegador sem instalar nada. Caminho definitivo: Python 3 + VS Code na sua máquina.

2

Instale as bibliotecas

PuLP resolve toda a trilha sozinho: modelos contínuos e inteiros, com o solver CBC já embutido. As outras bibliotecas são opcionais, para quando os modelos crescerem.

3

Crie o caderno de bordo

Um documento único, com data em cada entrada: o que você estudou, o que travou, que dúvida levar para a reunião. É desse caderno que sai o relatório final da IC. Não confie na memória.

4

Organize a pasta do projeto

Uma pasta por semana, com os notebooks e os PDFs que você leu. Se souber usar Git, use desde já; se não souber, aprenda o básico na Semana 4.

Teste de fumaça · se isto rodar, está tudo certo
# no terminal (ou numa célula do Colab com ! na frente)
pip install pulp pandas matplotlib     # ortools é opcional, só depois

# salve como teste.py e execute
from pulp import LpProblem, LpVariable, LpMaximize, value, LpStatus

m  = LpProblem("marcenaria", LpMaximize)
x1 = LpVariable("mesas",    lowBound=0)
x2 = LpVariable("armarios", lowBound=0)

m += 3*x1 + 5*x2                    # lucro a maximizar
m +=      x1        <= 4,  "serra"
m +=            2*x2 <= 12, "lixadeira"
m += 3*x1 + 2*x2 <= 18, "montagem"

m.solve()
print(LpStatus[m.status], value(m.objective))   # Optimal 36.0
for v in m.variables():
    print(v.name, v.varValue)                   # mesas 2.0 · armarios 6.0

Esse é exatamente o problema desenhado na Figura 1. Guarde o arquivo: ele vira a base de tudo que você escreve nas próximas quatro semanas.

O roteiro

Quatro semanas, quatro entregas

Cada semana tem uma meta única, um conjunto pequeno de conceitos, material para assistir, leitura de apoio e uma entrega para discutir na reunião de orientação. A regra é simples: os vídeos são para assistir, os textos são opcionais, ali para quando um assunto não fechar ou você quiser ir além. As tarefas são curtas de propósito: se alguma travar por mais de meia hora, pare, anote a dúvida e leve para a reunião. Ficar preso sozinho não faz parte do combinado. Marque o que terminar, que o navegador guarda seu progresso neste dispositivo.

Semana 1

Do problema em português ao modelo matemático

≈ 8 h

Meta ler um problema descrito em texto e escrevê-lo como maximizar/minimizar uma função linear sujeita a restrições lineares, com notação organizada e sem ambiguidade.

Conceitos
variável de decisão função objetivo restrição parâmetro (dado) região viável vértice solução ótima inviável ilimitado

A pergunta que resolve 90% dos travamentos: o que eu posso decidir? Aquilo que você escolhe é variável; aquilo que o problema te dá pronto é dado. Confundir os dois é o erro nº 1 de quem está começando.

Assista · obrigatório
Material de apoio · leitura opcional
Faça
Entrega da semana Um documento com os 2 modelos formulados (o clássico que você escolheu e o do seu dia a dia), cada um com dicionário de notação (conjuntos, parâmetros, variáveis), função objetivo e restrições numeradas, mais a figura da região viável de um deles.
Semana 2

Do papel para o computador: resolver e interpretar

≈ 8 h

Meta transformar os modelos da Semana 1 em código que resolve, ler a solução com segurança e saber dizer se ela faz sentido no problema original.

Conceitos
status da solução restrição no limite gargalo validação do modelo dados vs. modelo cenário

O algoritmo que o solver usa por dentro fica de fora desta trilha, de propósito. Aqui ele é caixa-preta: você aprende a alimentá-lo bem e a interpretar o que ele responde. Abrir a caixa é assunto de uma etapa posterior, quando já houver um problema real motivando a pergunta.

z = 0 z = 12 z = 27 z = 36 · ótimo x₁ x₂
Figura 2. O que o solver faz, em uma imagem: pula de vértice em vértice, melhorando o valor a cada passo, até nenhum vizinho melhorar. Como ele escolhe cada passo é justamente o que fica dentro da caixa-preta.
Assista · obrigatório
Material de apoio · leitura opcional
Faça
Entrega da semana Um notebook com os modelos da Semana 1 resolvidos em PuLP, cada um seguido de um parágrafo em português: qual foi a decisão recomendada, quais recursos ficaram no limite, e o que mudou na solução quando você alterou um parâmetro.
Semana 3

Decisões do tipo sim ou não: variáveis binárias

≈ 8 h

Meta modelar escolhas discretas (abrir ou não abrir, atribuir ou não atribuir) com variáveis binárias, sem trocar de ferramenta.

Conceitos
variável inteira variável binária restrição lógica big-M relaxação contínua mochila designação

Nada de ferramenta nova: no PuLP, uma decisão sim ou não é só LpVariable("abre_base", cat="Binary"), e o resto do modelo se escreve igual. O que muda é o trabalho que o solver tem por dentro, e isso você sente no relógio.

A descoberta mais importante da semana: arredondar a solução contínua não resolve. O arredondamento costuma dar resposta inviável, ou viável mas pior que a ótima. Vale ver isso acontecer com os seus próprios números.

Assista · obrigatório
Material de apoio · leitura opcional
Faça
Entrega da semana Mochila e designação implementadas com variáveis binárias, a designação já com uma restrição lógica, mais o parágrafo comparando a solução inteira com a contínua arredondada.
Semana 4

Problemas clássicos e o limite do computador

≈ 8 h

Meta reconhecer, num problema novo, a estrutura clássica que ele esconde, e sentir na prática como o tempo de resolução cresce com o tamanho da instância.

Conceitos
cobertura de conjuntos localização de instalações roteamento instância NP-difícil tempo limite gap de otimalidade

Os problemas do MODAL quase sempre caem aqui: alocar equipes a bases, escalar turnos, decidir onde abrir uma instalação, sequenciar operações num porto. Aprender os clássicos é aprender a enxergar o seu problema como uma variação de um deles.

Quando o solver não termina, ele ainda entrega algo útil: a melhor solução que achou e o gap, que diz o quanto ela ainda pode estar longe do ótimo. Saber ler isso é metade do trabalho experimental.

Assista · obrigatório
Material de apoio · leitura opcional
Faça
Entrega da semana Os dois clássicos implementados e uma tabela simples de experimentos (n, tempo, valor, e o gap quando o solver não terminar), com um parágrafo dizendo a partir de que tamanho ele começou a demorar.
Diagnóstico rápido

Oito erros que travam todo mundo no começo

Quando o modelo não sai ou o solver devolve algo estranho, passe esta lista antes de pedir ajuda. Em geral o problema está aqui.

01Dado virou variável

Se o número já está no enunciado, ele é parâmetro. Variável é só aquilo que você decide.

02Restrição não é linear

Multiplicar duas variáveis, dividir por variável ou usar max() dentro da restrição sai da programação linear.

03Domínio esquecido

Faltou x ≥ 0, ou a variável deveria ser inteira/binária e ficou contínua. Resultado: solução sem sentido físico.

04Unidades misturadas

R$/hora com R$/mês, tonelada com quilo. O modelo roda, o número mente.

05Big-M exagerado

M = 10⁹ deixa a relaxação inútil e o solver instável. Use o menor M que ainda é válido.

06Somatório sem conjunto

Todo índice precisa dizer onde vive: ∀ i ∈ I. Índice solto no papel vira bug no código.

07Modelo sem dicionário

Sem listar conjuntos, parâmetros e variáveis antes das equações, nem você entende o que escreveu daqui a duas semanas.

08Status ignorado

Sempre confira LpStatus: Optimal, Infeasible e Unbounded exigem reações completamente diferentes.

Português ↔ Inglês

Glossário para sobreviver à literatura

Cedo ou tarde você vai ler em inglês, não tem jeito: é onde está a maior parte da produção da área. Estes termos cobrem quase todo o vocabulário de um artigo introdutório.

PortuguêsInglêsO que é, em uma frase
variável de decisãodecision variableO que você escolhe: quanto produzir, quem vai onde, abrir ou não.
função objetivoobjective functionA conta que você quer maximizar ou minimizar.
restriçãoconstraintO limite da realidade: capacidade, demanda, orçamento, tempo.
região viávelfeasible regionTodas as decisões que respeitam simultaneamente as restrições.
solução ótimaoptimal solutionA melhor entre as viáveis; em PL, sempre num vértice.
inviávelinfeasibleNenhuma decisão satisfaz tudo: suas restrições se contradizem.
ilimitadounboundedDá para melhorar para sempre, e quase sempre falta uma restrição.
relaxação linearLP relaxationO modelo inteiro com as variáveis deixadas contínuas; dá um limitante rápido.
limitanteboundUm valor que o ótimo certamente não ultrapassa (ou não fica abaixo).
gap de otimalidadeoptimality gapA distância entre a melhor solução achada e o melhor limitante conhecido.
programação inteira mistaMILPModelo com variáveis contínuas e inteiras ao mesmo tempo.
ramificação e limitaçãobranch-and-boundComo o solver quebra o problema em subproblemas e poda os ruins.
plano de cortecutting planeRestrição extra que corta soluções fracionárias sem perder as inteiras.
instânciainstanceUm conjunto concreto de dados para o modelo; o modelo é a forma, a instância é o recheio.
resolvedorsolverO programa que resolve: CBC, HiGHS, Gurobi, CPLEX.
metaheurísticametaheuristicMétodo que busca boas soluções rápido, sem provar que são ótimas.
Biblioteca

Tudo reunido, para consultar depois

Os mesmos links das semanas, organizados por tipo, mais o que sobra para quando a trilha acabar.

Videoaulas em português

O que a trilha pede que você assista, reunido num lugar só.

Notas de aula e apostilas

Leitura de apoio, sempre opcional. Material universitário aberto, em português.

Ferramentas

O que instalar, o que usar no navegador.

  • Python
    PuLPResolve tudo o que a trilha pede, contínuo e inteiro, com o CBC incluído.
  • Python
    Python-MIP · OR-ToolsAlternativas para depois: modelos grandes, controle fino do solver e roteamento.
  • Web
    PHPSimplex · GeoGebraVisualizar a região viável e conferir soluções sem escrever código.
  • Web
    Google ColabAmbiente pronto, sem instalação, com tudo que a trilha precisa.
  • Licença
    Gurobi: licença acadêmica gratuitaPeça com o e-mail institucional quando os modelos ficarem grandes.

Artigos, instâncias e comunidade

Onde a pesquisa brasileira da área acontece.

E depois?

Quando a quarta semana acabar

O passo imediato é um só, e é combinado na reunião: escolher com o orientador um artigo para estudar a fundo. É esse artigo que define para onde a sua IC caminha. As outras portas abrem depois, conforme o problema escolhido pedir.

Metaheurísticas

Quando a instância cresce e o solver exato não fecha: GRASP, VNS, busca tabu, BRKGA e, para múltiplos objetivos, NSGA-II. As notas da UFOP são o começo natural.

Decomposição

Modelos grandes se quebram: relaxação lagrangiana, geração de colunas e decomposição de Benders. Passa antes por dualidade e preços-sombra, que ficam para depois desta trilha.

Solvers profissionais

Gurobi e CPLEX com licença acadêmica, callbacks, cortes definidos pelo usuário e ajuste fino de parâmetros. É o que separa um protótipo de um experimento publicável.

Escrita científica

LaTeX, tabelas de resultados que se defendem sozinhas, revisão de literatura e submissão ao SBPO. Comece cedo: escrever é parte de pesquisar, não o passo final.