Problema de Otimização: Minimizar a Insatisfação na Fila de Merenda Escolar

Quem já foi aluno de escola pública sabe o que acontece no horário da merenda: todo santo dia ocorre uma disputa entre os alunos para ser o primeiro na fila da merenda. Os que não conseguem tentam outros meios para isso (sair mais cedo da sala, furar fila).

Para resolver esse problema, pode ser implementado um sistema de escala para almoçar. Assim, todos terão o seu momento "reservado". Essa "escala fixa" parece prática no papel, mas na vida real cria outro problema silencioso de injustiça que se repete semana após semana.

É exatamente esse problema do dia a dia que o meu projeto Otimização para Minimizar a Insatisfação no Acesso à Merenda Escolar: Um Problema de Alocação de Horários decidiu atacar — não com uma planilha de "quem faltou fazer o rodízio", mas com otimização combinatória.

A seguir, explicarei o problema, a matemática por trás da solução e os resultados da otimização.

O Problema

Numa escola com várias turmas, o intervalo tem um número fixo de horários/posições de acesso à merenda. Alguém precisa decidir: qual turma vai em qual posição, todo dia, toda semana?

Se essa decisão for arbitrária ou fixa, o resultado é previsível: as mesmas turmas acumulam os piores horários — mais tempo de espera, menos tempo de intervalo, mais insatisfação acumulada. O projeto parte da ideia de que isso é, na verdade, um problema de otimização disfarçado de rotina escolar: como distribuir turmas em horários de forma que a insatisfação total seja a menor possível, e que isso se mantenha justo ao longo do tempo?

Por que Isso é "Otimização"?

Otimizar, em termos gerais, é escolher, entre um conjunto de opções possíveis, aquela que minimiza (ou maximiza) uma medida de custo (ou benefício). O primeiro passo de qualquer problema de otimização é sempre o mesmo:

Definir as variáveis de decisão (o que pode ser escolhido);
Definir a função objetivo (o que queremos minimizar ou maximizar);
Definir as restrições (o que não pode ser violado).

Saiba mais sobre modelagem de otimização seguindo esse link.

No caso da merenda, a variável de decisão é simples de enunciar e nada trivial de resolver bem: para cada turma, qual horário ela ocupa? A função objetivo é o custo total de insatisfação gerado por essa escolha. E as restrições garantem que o problema faça sentido no mundo real: cada turma só pode almoçar uma vez, e cada horário só pode ser ocupado por uma turma.

Esse tipo de estrutura onde tem elementos de um lado, posições de outro e cada combinação tendo um custo tem nome na teoria de otimização combinatória: Problema de Atribuição (assignment problem). É o mesmo tipo de problema usado para decidir qual funcionário faz qual tarefa, qual avião pousa em qual pista, ou qual entregador atende qual rota, usado sempre que se precisa casar dois conjuntos do mesmo tamanho minimizando um custo total.

Modelando a Fila Como um Grafo

Uma forma elegante (e muito usada na prática) de enxergar o Problema de Atribuição é através de um grafo bipartido ponderado: de um lado, os vértices representam as turmas; do outro, os horários disponíveis. Cada aresta liga uma turma a um horário e carrega um peso — o custo daquela combinação específica.

Resolver o problema, nesse modelo, significa encontrar o emparelhamento perfeito de menor custo entre os dois grupos de vértices: cada turma ligada a exatamente um horário, cada horário usado por exatamente uma turma, com a soma dos pesos das arestas escolhidas sendo a menor possível.

Com n turmas e n horários, o número de formas diferentes de fazer esse emparelhamento é n! — um crescimento fatorial que torna a força bruta inviável rapidinho (com 12 turmas já são mais de 479 milhões de combinações). É aí que entra o algoritmo certo para o trabalho.

O Algoritmo Húngaro

Para resolver o Problema de Atribuição sem precisar testar todas as permutações, o projeto usa o clássico Algoritmo Húngaro, proposto por Harold Kuhn em 1955. Ele explora a estrutura do problema para encontrar a solução ótima com complexidade polinomial (O(n³)), em vez de fatorial — a diferença entre resolver o problema em milissegundos ou nunca terminar de rodar.

De forma resumida, o algoritmo trabalha em cima de uma matriz de custos, reduzindo linhas e colunas, cobrindo os zeros resultantes e ajustando a matriz sucessivamente até encontrar o emparelhamento de custo mínimo — sempre garantindo que a solução encontrada é a melhor possível, não apenas uma solução "boa o suficiente" como fariam heurísticas aproximadas.

Memória e Justiça ao Longo do Tempo

Até aqui, tudo poderia ser só um exercício acadêmico de grafos. O que torna o projeto genuinamente útil é que ele não resolve o problema uma vez — ele resolve todo dia, e cada solução carrega a memória das anteriores.

A matriz de custos usada pelo Algoritmo Húngaro é reconstruída a cada execução, considerando:

Quantas vezes aquela turma já ocupou aquela posição específica → repetir uma posição já muito usada fica cada vez mais "caro";
A posição média histórica da turma → turmas que, em média, pegaram os piores horários ganham prioridade nas próximas rodadas;
Um bônus para turmas com atividades extracurriculares → alunos saem mais cedo e se beneficiam de posições mais vantajosas.

Esse histórico fica salvo em um arquivo JSON e alimenta a otimização do dia seguinte. O resultado é um sistema dinâmico: a decisão de hoje influencia o problema de amanhã, e o algoritmo vai empurrando naturalmente o sistema para um estado de equilíbrio, em que todas as turmas circulam por todas as posições ao longo do tempo.

O que as Simulações Mostraram

O projeto testou o modelo em cenários com 12, 8 e 6 turmas, simulando várias semanas letivas consecutivas. Em todos os casos, o comportamento observado foi parecido: nos primeiros dias, o algoritmo já evita repetir posições consecutivas para a mesma turma. Depois de um número de execuções próximo ao número de posições disponíveis (por exemplo, cerca de doze dias no cenário de 12 turmas), todas as turmas já tinham passado por todas as posições pelo menos uma vez — e o sistema entra num regime cíclico e estável, onde a distribuição permanece equilibrada.

Quanto menos turmas no cenário, mais rápido esse equilíbrio é atingido, já que há menos posições para "preencher" no histórico. Isso confirma algo intuitivo: o tempo para o sistema ficar justo depende diretamente do tamanho do problema, mas o algoritmo converge de forma confiável em todos os tamanhos testados.

Implementação do Algoritmo

Na prática, o repositório traduz tudo isso em duas peças principais:

hungaro.py, com a implementação própria do Algoritmo Húngaro (incluindo uma validação por força bruta, que compara o resultado com todas as permutações possíveis em matrizes pequenas — uma boa prática para garantir que a implementação está correta);
escalonamento_merenda.py, que monta a matriz de custos dinâmica a partir do histórico, roda o algoritmo para cada dia da semana e gera um relatório em Excel com a escala, o histórico de posições e um mapa de calor de quantas vezes cada turma ocupou cada posição.

O repositório está nesse link. Lá está a implementação, os slides da apresentação e o artigo associado explicando as minúcias do trabalho desenvolvido.

Considerações Finais

O interessante desse projeto é que eu consegui transformar um problema que via na minha escola durante o ensino médio em uma solução consistente. Se fosse implementado em um sistema onde os estudantes recebessem uma notificação do seu horário de almoçar, vários problemas seriam resolvidos e, quiçá, levasse à mudanças positivas de comportamento e aprendizado.

Assista ao vídeo da minha apresentação do projeto, onde expliquei a modelagem do problema, o funcionamento do algoritmo húngaro e os resultados.