Numa escola, antes da definição das turmas, cada aluno preenche um formulário informando com quais colegas tem afinidade, resultando na tabela abaixo (onde 1 indica afinidade).
Matriz de afinidades (é simétrica, se um aluno tem afinidade com outro, o inverso também é verdadeiro):
| Aluno 1 | Aluno 2 | Aluno 3 | Aluno 4 | Aluno 5 | Aluno 6 | Aluno 7 | Aluno 8 | Aluno 9 | Aluno 10 | Aluno 11 | Aluno 12 | Aluno 13 | Aluno 14 | Aluno 15 | |
| Aluno 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | |
| Aluno 2 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | |
| Aluno 3 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| Aluno 4 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |
| Aluno 5 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | |
| Aluno 6 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| Aluno 7 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | |
| Aluno 8 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | |
| Aluno 9 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | |
| Aluno 10 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
| Aluno 11 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | |
| Aluno 12 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | |
| Aluno 13 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| Aluno 14 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | |
| Aluno 15 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 |
A escola deve dividir os 15 alunos em 3 turmas de 5 alunos cada.
Dois alunos com afinidade gostam de estar na mesma turma, e dois alunos sem afinidade são indiferentes.
O score de afinidade total é calculado assim: para cada turma, cada par de alunos com afinidade acrescenta 1 ao score.
Desafio proposto em https://ideiasesquecidas.com/2023/05/20/desafio-maximizar-afinidades/. Seguem algumas resoluções.
Solução 1) Algoritmo aleatório
É possível resolver utilizando algoritmo aleatório puro. Fiz uma versão em VBA, e guardei no Github (https://github.com/asgunzi/max_afinidades).
Basicamente o algoritmo vai testar soluções aleatórias que atendam às restrições, e ir salvando a melhor. Funciona bem, para o caso.
É necessário ativar macros para rodar.
Solução 2) Programação linear inteira
Outra alternativa é modelando via programação linear inteira. Para tal, é necessário utilizar variáveis auxiliares binárias. A ideia seria criar uma variável indicador, que indique se dois alunos estão na mesma turma.
Fiz a resolução em Pyomo (pacote do Python) e resolução no CBC (é um solver free). Formulação no Github https://github.com/asgunzi/max_afinidades,
É bem mais complexo, porém é muito mais poderoso. Essa formulação vai garantir o ótimo global.
Um trecho do código para dar uma ideia.
# Objective function
def somaFO(model):
return sum(model.indicador[aluno1,aluno2, turma]*int(afinidades[aluno1][aluno2]) for aluno1 in alunos for aluno2 in alunosaux for turma in turmas) – 1000*sum(model.indicador[aluno1,aluno2, turma] for aluno1 in alunos for aluno2 in alunosaux for turma in turmas)
model.objective = Objective(rule = somaFO, sense=maximize)
# Constraint: Capacidade turmas
def capacidadeturmas_rule(model, turma):
return sum(model.aloc[aluno,turma] for aluno in alunos) == 5
model.capacidade= Constraint(turmas, rule=capacidadeturmas_rule)
# Constraint: alocar todo mundo
def alocar_rule(model, aluno):
return sum(model.aloc[aluno,turma] for turma in turmas) <= 1
model.alocartodos= Constraint(alunos, rule=alocar_rule)
# Constraint: indicador de dois alunos na mesma turma
def indicador_rule(model, aluno1, aluno2, turma):
return model.aloc[aluno1,turma] + model.aloc[aluno2,turma] – 1 <= model.indicador[aluno1,aluno2,turma]
model.indicadorafim= Constraint(alunos, alunosaux, turmas, rule=indicador_rule)
A resposta ótima é 22, e uma das soluções possíveis é a seguinte:
| Alocação | Turma 1 | Turma 2 | Turma 3 |
| Aluno 1 | 1 | ||
| Aluno 2 | 1 | ||
| Aluno 3 | 1 | ||
| Aluno 4 | 1 | ||
| Aluno 5 | 1 | ||
| Aluno 6 | 1 | ||
| Aluno 7 | 1 | ||
| Aluno 8 | 1 | ||
| Aluno 9 | 1 | ||
| Aluno 10 | 1 | ||
| Aluno 11 | 1 | ||
| Aluno 12 | 1 | ||
| Aluno 13 | 1 | ||
| Aluno 14 | 1 | ||
| Aluno 15 | 1 |
Este é um problema um pouquinho mais difícil de formular.
Algumas pessoas enviaram resposta utilizando o solver, numa função não linear que necessita da opção Evolutionary do mesmo. Também é possível chegar à resposta assim, porém, o cuidado é que utilizando o solver assim não garante o ótimo global.
Veja também. https://ideiasesquecidas.com/laboratorio-de-matematica/
Forgotten Lore 