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.

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

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)
Name Committee Cost Var
0 Taprice Comité de discipline 10 v000001
1 Aoba Représentant de classe 10 v000002
2 Kaguya Comité de discipline 10 v000003
3 Chino Représentant de classe 10 v000004
4 miroir Comité de discipline 10 v000005
5 Taprice Représentant de classe 30 v000006
6 Aoba Commission de la bibliothèque 30 v000007
7 Kaguya Commission de la bibliothèque 30 v000008
8 Chino Comité de discipline 30 v000009
9 miroir Représentant de classe 30 v000010

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])
Name Committee Cost Var Val
0 Taprice Comité de discipline 10 v000001 1
3 Chino Représentant de classe 10 v000004 1
4 miroir Comité de discipline 10 v000005 1
6 Aoba Commission de la bibliothèque 30 v000007 1
7 Kaguya Commission de la bibliothèque 30 v000008 1

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.

Recommended Posts

Comité du premier cycle du secondaire
Comité du premier cycle du secondaire (version Réseau X)
Modèle SIR que même les élèves du premier cycle du secondaire peuvent comprendre
Créons un dispositif de factorisation automatique / Junior High School Mathematics Vol.1
[Mathématiques au lycée + python] Problème de logistique
Script du "Livre de programmation à partir d'élèves du primaire et du premier cycle du secondaire"
Introduction à l'optimisation mathématique Python Résoudre des problèmes de mathématiques au collège avec pulp
[Python] Un lycéen a implémenté Perceptron et a essayé de classer les iris.
J'ai essayé de refactoriser le code de Python débutant (lycéen)