Les étudiants seront affectés à plusieurs laboratoires en classe. Je souhaite trouver une méthode d'affectation avec le moins de plaintes possible par une méthode systématique. Par conséquent, nous utiliserons la méthode de programmation entière.
Je pensais qu'il serait facile d'utiliser le solveur de l'addin Excel, mais quand je l'ai essayé, j'ai reçu un message disant "Il y a trop de cellules variables." Il semble que le nombre de variables soit jusqu'à 200, donc il ne peut pas être utilisé pour ce problème (100 étudiants, 10 laboratoires).
J'ai pensé à utiliser CPLEX ou un solveur indépendant, mais comme le fichier d'entrée doit de toute façon être créé automatiquement par le programme, cette fois, je vais déplacer le solveur depuis le programme Python.
Plus précisément, utilisez le package PuLP.
Les étudiants ont répondu à l'ordre souhaité de chaque laboratoire (1 est le plus élevé).
import pulp
data = (
("Nom", "Laboratoire Yuino", "Laboratoire Ari Nestgawa", "Shishi Seiken"),
("Rei Ichido", 1, 2, 3),
("Froid", 1, 2, 3),
("Kiyoshi Dese", 1, 3, 2),
("Hitoshi Oma", 3, 1, 2),
("Taille étoile", 3, 1, 2)
)
La cession est décidée en deux étapes comme suit.
Considérons l'étudiant ayant le rang le plus bas parmi les étudiants en termes d'ordre de préférence du laboratoire assigné. Par souci d'équité, la priorité la plus élevée est donnée à l'ordre de préférence pour ces pires laboratoires d'affectation des étudiants autant que possible.
Par conséquent, même si 99 étudiants sur 100 sont classés 1er dans l'ordre souhaité, si le 1er restant est le 10e laboratoire, les 100 étudiants seront affectés au 9e laboratoire. La priorité est donnée à ceux qui le sont.
Nous voulons conserver les meilleurs et les pires classements que nous ayons trouvés dans la première étape, et nous assurer que tout le monde est aussi haut que possible dans le laboratoire souhaité. Cependant, il vaut mieux que les étudiants A et B soient affectés aux 2ème et 3ème laboratoires que d'être affectés aux 1er et 4ème laboratoires dans l'ordre de préférence. En d'autres termes, l'amélioration du classement inférieur a la priorité sur l'amélioration du classement supérieur.
constant $ m $: Nombre d'étudiants, $ n $: Nombre de laboratoires, $ a_ {i, j} $: Étudiant $ i (0 \ leq i \ leq m-1) $ laboratoire $ j (0 \ leq j \ leq n-1) Ordre souhaité pour $ ($ 1 \ leq a_ {i, j} \ leq n $), $ size_ {min} $: Limite inférieure du nombre de personnes affectées au laboratoire, $ size_ {max} $: Laboratoire Nombre maximum de personnes affectées à
variable 0-1 La variable $ x_ {i, j} $$ (1 \ leq i \ leq m, 1 \ leq j \ leq n) $ indique que l'étudiant $ i $ a été affecté au laboratoire $ j $ .. S'il vaut 1, attribuez-le. La variable $ pire $$ (1 \ leq j \ leq n) $ représente l'ordre souhaité du laboratoire assigné dans le pire des cas.
Fonction objectif: $ pire $ → minimiser Contrainte $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ L'élève $ i $ sera toujours affecté quelque part $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ Le nombre de personnes affectées au laboratoire $ j $ est $ size_ {min} $ ou plus, $ size_ {max} $ ou moins $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq pire $ étudiant $ i L'ordre souhaité du $ laboratoire attribué est $ pire $ ou plus
Soit $ bound $ l'ordre souhaité du pire des cas obtenu en résolvant le problème 1, c'est-à-dire la valeur de $ pire $ dans la solution optimale.
Fonction objectif: $ \ sum_i a_ {i, 1} ^ \ alpha x_ {i, 1} + a_ {i, 2} ^ \ alpha x_ {i, 2} + ... + a_ {i, n} ^ \ alpha x_ {i, n} $ → minimiser
$ \ Alpha $ est un nombre réel supérieur ou égal à 1. Si $ \ alpha = 1 $, l'amélioration de la 2ème place à la 1ère place et l'amélioration de la 3ème place à la 2ème place sont considérées comme ayant la même importance. Si $ \ alpha> 1 $, la priorité est donnée à une amélioration inférieure. Par exemple, si $ \ alpha = 2 $, l'amélioration de la 2ème place à la 1ère place diminue la valeur de la fonction objectif de 2 $ ^ 2 --1 ^ 2 = 3 $, mais l'amélioration de la 3ème place à la 2ème place est de 3 $ ^ 2- 2 ^ 2 = 5 $ de moins.
Contrainte $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ L'élève $ i $ sera toujours affecté quelque part $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ Le nombre de personnes affectées au laboratoire $ j $ est $ size_ {min} $ ou plus, $ size_ {max} $ ou moins $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq lié $ Student $ i L'ordre souhaité du $ laboratoire attribué est $ lié $ ou plus
Le même nombre de personnes sera affecté au laboratoire. S'il y a un reste, réduisez la différence du nombre de personnes affectées à 1 ou moins. Ce qui suit est une continuation de ce qui précède.
NUM_MEMBERS = len(data)-1 #Nombre d'étudiants
NUM_GROUPS = len(data[0])-1 #Nombre de groupes
MIN_GROUP_SIZE = NUM_MEMBERS//NUM_GROUPS #Nombre minimum de personnes dans un groupe
#Nombre maximum de personnes dans un groupe(Valeur maximum-valeur minimum<= 1)
if NUM_MEMBERS % NUM_GROUPS == 0:
MAX_GROUP_SIZE = MIN_GROUP_SIZE
else:
MAX_GROUP_SIZE = MIN_GROUP_SIZE + 1
#question 1
problem1 = pulp.LpProblem('FindWorstCase', pulp.LpMinimize)
# 0-1 variable x[i,j]Déclarer i:étudiant, j:groupe
x = {}
for i in range(0, NUM_MEMBERS):
for j in range(0, NUM_GROUPS):
x[i, j] = pulp.LpVariable("x({:},{:})".format(i, j), 0, 1, 'Binary')
#Déclarez la variable entière la plus mauvaise. La valeur est 1 ou plus et le nombre de groupes ou moins.
worst = pulp.LpVariable('worst', 1, NUM_GROUPS, 'Integer')
#Contrainte A:Chaque étudiant est affecté à exactement un groupe
for i in range(0, NUM_MEMBERS):
problem1 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Contrainte B:Le nombre de personnes dans chaque groupe est supérieur au minimum et inférieur au maximum
for j in range(0, NUM_GROUPS):
problem1 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) >= MIN_GROUP_SIZE
problem1 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) <= MAX_GROUP_SIZE
#Contrainte C:Les laboratoires auxquels chaque étudiant est affecté sont les mêmes ou plus jeunes que les pires dans l'ordre de préférence.
for i in range(0, NUM_MEMBERS):
problem1 += sum(data[i+1][j+1] * x[i, j]
for j in range(0, NUM_GROUPS)) <= worst
#Fonction objectif: le pire, c'est-à-dire le pire des cas dans l'ordre souhaité
problem1 += worst
#Résoudre le problème
problem1.solve()
print("Worst:", worst.value())
#Problème 2
bound = worst.value() #Le pire des cas que vous ayez demandé est la borne dans l'ordre souhaité.
problem2 = pulp.LpProblem('AsssignAll', pulp.LpMinimize)
#Contrainte A:Chaque étudiant est affecté à exactement un groupe
for i in range(0, NUM_MEMBERS):
problem2 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Contrainte B:Le nombre de personnes dans chaque groupe est supérieur au minimum et inférieur au maximum
for j in range(0, NUM_GROUPS):
problem2 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) >= MIN_GROUP_SIZE
problem2 += sum(x[i, j] for i in range(0, NUM_MEMBERS)) <= MAX_GROUP_SIZE
#Contraintes:Les laboratoires auxquels chaque étudiant est affecté sont identiques ou supérieurs à la limite dans l'ordre de préférence.
for i in range(0, NUM_MEMBERS):
problem2 += sum(data[i+1][j+1] * x[i, j]
for j in range(0, NUM_GROUPS)) <= bound
#Fonction objective
WEIGHT_EXPONENT = 1.2 #Α pour la pondération
problem2 += sum((data[i+1][j+1] ** WEIGHT_EXPONENT) * x[i, j]
for i in range(0, NUM_MEMBERS) for j in range(0, NUM_GROUPS))
#Résoudre le problème
problem2.solve()
print("Nom", "Laboratoire", "Classement")
for i in range(0, NUM_MEMBERS):
for j in range(0, NUM_GROUPS):
if x[i, j].value() > 0:
print(data[i+1][0], data[0][j+1], data[i+1][j+1])
Résultat d'exécution
Worst: 2.0
Nom du classement du laboratoire
Laboratoire Rei Ichido Yuino 1
Allez au laboratoire Yuino.1
Kiyoshi Dese Shishiseiken 2
Laboratoire Hitoshi Oma Ari Nestgawa 1
Monoboshi Dai Ari Nestgawa Lab 1
Recommended Posts