Comité du premier cycle du secondaire

Qu'est-ce que c'est

Sur la base des souhaits des étudiants, nous résoudrons le "problème d'affectation des membres de la classe" par l'optimisation des combinaisons. Ceci est la version Python de Une histoire sur l'optimisation du comité de lycée au moindre coût.

politique

--Créez un pandas.DataFrame avec un enregistrement des souhaits du comité étudiant.

• Le coût du premier choix est de 10 et le coût du deuxième choix est de 30. --Créez un modèle d'optimisation mathématique (minimisation des coûts) à l'aide de DataFrame. -Solvez Modèle d'optimisation mathématique avec un solveur pour obtenir l'affectation.

Modèle d'optimisation mathématique

--Variable: créé comme une colonne de DataFrame (1 ligne, 1 variable). --Fonction objective: minimiser le coût total souhaité --Restrictions --Jusqu'à un membre peut être étudiant

• Les membres rencontrent le nombre fixe

contribution

Créez un DataFrame.

import pandas as pd
from pulp import lpDot, lpSum
from ortoolpy import model_min, addbinvars, addvals

lst = [['Taprice', 'Comité de discipline', 10], ['Aoba', 'Représentant de classe', 10], ['Kaguya', 'Comité de discipline', 10],
       ['Chino', 'Représentant de classe', 10], ['miroir', 'Comité de discipline', 10],
       ['Taprice', 'Représentant de classe', 30], ['Aoba', 'Commission de la bibliothèque', 30], ['Kaguya', 'Commission de la bibliothèque', 30],
       ['Chino', 'Comité de discipline', 30], ['miroir', 'Représentant de classe', 30]]
need = {"Représentant de classe": 1, "Commission de la bibliothèque": 2, "Comité de discipline": 2}
df = pd.DataFrame(lst, columns=['Name', 'Committee', 'Cost'])
addbinvars(df)

print(df)

La colonne Var est variable (1: attribuer, 0: ne pas attribuer)

Modélisation et résolution

m = model_min()
m += lpDot(df.Cost, df.Var)  #Somme des coûts souhaités
for _, gr in df.groupby('Name'):
    m += lpSum(gr.Var) <= 1  #Jusqu'à un membre peut être étudiant
for k, gr in df.groupby('Committee'):
    m += lpSum(gr.Var) == need[k]  #Les membres du comité rencontrent un nombre fixe
m.solve()
addvals(df)

résultat

print(df[df.Val > 0])

Supplément

Dans l'article original, c'est le problème du flux de coût minimum. Dans ce cas, vous pouvez utiliser min_cost_flow de Network X.

Toutefois, si vous souhaitez modifier le modèle, un modèle optimisé mathématiquement comme cet article sera plus facile à gérer. Le temps de calcul pour l'optimisation mathématique est également assez rapide.