Die Schüler werden mehreren Labors in der Klasse zugewiesen. Ich möchte eine Zuordnungsmethode mit möglichst wenigen Beschwerden durch eine systematische Methode finden. Daher werden wir die ganzzahlige Programmiermethode verwenden.
Ich dachte, es wäre einfach, den Solver des Excel-Add-Ins zu verwenden, aber als ich es ausprobierte, erhielt ich die Meldung "Es gibt zu viele variable Zellen." Es scheint, dass die Anzahl der Variablen bis zu 200 beträgt, daher kann sie nicht für dieses Problem verwendet werden (100 Studenten, 10 Labors). Ich habe überlegt, CPLEX oder einen unabhängigen Solver zu verwenden, aber da ich die Eingabedatei ohnehin automatisch vom Programm erstellen muss, werde ich den Solver dieses Mal aus dem Python-Programm heraus verschieben. Verwenden Sie insbesondere das PuLP-Paket. Die Schüler haben die gewünschte Reihenfolge jedes Labors beantwortet (1 ist die höchste).
import pulp
data = (
("Name", "Yuino Lab", "Ari Nestgawa Lab", "Shishi Seiken"),
("Rei Ichido", 1, 2, 3),
("Erkältung", 1, 2, 3),
("Kiyoshi Dese", 1, 3, 2),
("Hitoshi Oma", 3, 1, 2),
("Sterngröße", 3, 1, 2)
)
Die Zuordnung erfolgt in zwei Schritten wie folgt.
Betrachten Sie den Schüler mit dem niedrigsten Rang unter den Schülern in Bezug auf die Präferenzreihenfolge des zugewiesenen Labors. Aus Gründen der Fairness hat die Reihenfolge der Präferenz für solche Laboratorien mit der schlechtesten Studentenzuordnung so weit wie möglich höchste Priorität.
Selbst wenn 99 von 100 Schülern in der gewünschten Reihenfolge auf dem 1. Platz liegen und der verbleibende auf dem 10. Platz liegt, werden alle 100 dem 9. Platz zugewiesen. Vorrang haben diejenigen, die es sind.
Wir wollen die besten und schlechtesten Platzierungen behalten, die wir in der ersten Phase gefunden haben, und sicherstellen, dass alle im gewünschten Labor so hoch wie möglich sind. Es ist jedoch besser, wenn die Schüler A und B dem 2. und 3. Labor zugeordnet werden, als dem 1. und 4. Labor in der Reihenfolge ihrer Präferenz. Mit anderen Worten, die Verbesserung des unteren Ranges hat Vorrang vor der Verbesserung des oberen Ranges.
Konstante $ m $: Anzahl der Schüler, $ n $: Anzahl der Labors, $ a_ {i, j} $: Schüler $ i (0 \ leq i \ leq m-1) $ labor $ j (0 \ leq j \ leq n-1) Gewünschte Reihenfolge für $ ($ 1 \ leq a_ {i, j} \ leq n $), $ size_ {min} $: Untergrenze der Anzahl der dem Labor zugewiesenen Personen, $ size_ {max} $: Labor Maximale Anzahl der zugewiesenen Personen
Variable 0-1 Variable $ x_ {i, j} $$ (1 \ leq i \ leq m, 1 \ leq j \ leq n) $ gibt an, dass der Schüler $ i $ dem Labor $ j $ zugewiesen wurde .. Wenn es 1 ist, weisen Sie es zu. Die Variable $ schlechteste $$ (1 \ leq j \ leq n) $ repräsentiert im schlimmsten Fall die gewünschte Reihenfolge des zugewiesenen Labors.
Zielfunktion: $ schlechteste $ → minimieren Zwang $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ Student $ i $ wird immer irgendwo zugewiesen $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ Die Anzahl der dem Labor zugewiesenen Personen $ j $ beträgt $ size_ {min} $ oder mehr, $ size_ {max} $ oder weniger $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq schlechtester $ Student $ i Die gewünschte Reihenfolge des $ zugewiesenen Labors ist $ schlecht $ oder höher
Sei $ bound $ die gewünschte Reihenfolge des schlechtesten Falls, der durch Lösen von Problem 1 erhalten wird, dh der Wert von $ schlechtesten $ in der optimalen Lösung.
Zielfunktion: $ \ sum_i a_ {i, 1} ^ \ alpha x_ {i, 1} + a_ {i, 2} ^ \ alpha x_ {i, 2} + ... + a_ {i, n} ^ \ alpha x_ {i, n} $ → minimieren
$ \ Alpha $ ist eine reelle Zahl größer oder gleich 1. Wenn $ \ alpha = 1 $ ist, werden die Verbesserung vom 2. auf den 1. Platz und die Verbesserung vom 3. auf den 2. Platz als gleich wichtig angesehen. Wenn $ \ alpha> 1 $ ist, wird der geringeren Verbesserung Priorität eingeräumt. Wenn beispielsweise $ \ alpha = 2 $ ist, senkt die Verbesserung vom 2. auf den 1. Platz den Wert der Zielfunktion um $ 2 ^ 2 - 1 ^ 2 = 3 $, aber die Verbesserung vom 3. auf den 2. Platz beträgt $ 3 ^ 2- 2 ^ 2 = 5 $ niedriger.
Zwang $ x_ {i, 1} + x_ {i, 2} + ... + x_ {i, n} = 1 $ Student $ i $ wird immer irgendwo zugewiesen $ x_ {1, j} + x_ {2, j} + ... + x_ {m, j} \ geq size_ {min} $, $ x_ {1, j} + x_ {2, j} + .. . + x_ {m, j} \ leq size_ {max} $ Die Anzahl der dem Labor zugewiesenen Personen $ j $ beträgt $ size_ {min} $ oder mehr, $ size_ {max} $ oder weniger $ a_ {i, 1} x_ {i, 1} + a_ {i, 2} x_ {i, 2} + ... + a_ {i, n} x_ {i, n} \ leq gebunden $ Student $ i Die gewünschte Reihenfolge des $ zugewiesenen Labors ist $ gebunden $ oder höher
Die gleiche Anzahl von Personen wird dem Labor zugewiesen. Wenn es einen Rest gibt, reduzieren Sie den Unterschied in der Anzahl der Personen, die 1 oder weniger zugewiesen sind. Das Folgende ist eine Fortsetzung des Obigen.
NUM_MEMBERS = len(data)-1 #Anzahl der Schüler
NUM_GROUPS = len(data[0])-1 #Anzahl der Gruppen
MIN_GROUP_SIZE = NUM_MEMBERS//NUM_GROUPS #Mindestanzahl von Personen in einer Gruppe
#Maximale Anzahl von Personen in einer Gruppe(Maximalwert-Mindestwert<= 1)
if NUM_MEMBERS % NUM_GROUPS == 0:
MAX_GROUP_SIZE = MIN_GROUP_SIZE
else:
MAX_GROUP_SIZE = MIN_GROUP_SIZE + 1
#Frage 1
problem1 = pulp.LpProblem('FindWorstCase', pulp.LpMinimize)
# 0-1 Variable x[i,j]Erkläre ich:Schüler, j:Gruppe
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')
#Deklarieren Sie die Ganzzahlvariable als schlechteste. Der Wert ist 1 oder mehr und die Anzahl der Gruppen oder weniger.
worst = pulp.LpVariable('worst', 1, NUM_GROUPS, 'Integer')
#Einschränkung A.:Jeder Schüler ist genau einer Gruppe zugeordnet
for i in range(0, NUM_MEMBERS):
problem1 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Einschränkung B.:Die Anzahl der Personen in jeder Gruppe liegt über dem Minimum und unter dem 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
#Einschränkung C.:Die Labors, denen jeder Schüler zugeordnet ist, sind in der Reihenfolge ihrer Präferenz gleich oder jünger als die schlechtesten.
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
#Zielfunktion: schlimmster, dh schlimmster Fall in der gewünschten Reihenfolge
problem1 += worst
#Das Problem lösen
problem1.solve()
print("Worst:", worst.value())
#Problem 2
bound = worst.value() #Der schlimmste Fall, nach dem Sie gefragt haben, ist die Bindung in der gewünschten Reihenfolge.
problem2 = pulp.LpProblem('AsssignAll', pulp.LpMinimize)
#Einschränkung A.:Jeder Schüler ist genau einer Gruppe zugeordnet
for i in range(0, NUM_MEMBERS):
problem2 += sum(x[i, j] for j in range(0, NUM_GROUPS)) == 1
#Einschränkung B.:Die Anzahl der Personen in jeder Gruppe liegt über dem Minimum und unter dem 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
#Einschränkungen:Die Labors, denen jeder Schüler zugeordnet ist, sind in der Reihenfolge ihrer Präferenz gleich oder höher als gebunden.
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
#Zielfunktion
WEIGHT_EXPONENT = 1.2 #Α zur Gewichtung
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))
#Das Problem lösen
problem2.solve()
print("Name", "Labor", "Rangfolge")
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])
Ausführungsergebnis
Worst: 2.0
Nennen Sie das Laborranking
Rei Ichido Yuino Lab 1
Gehen Sie zum Yuino Lab. 1
Kiyoshi Dese Shishiseiken 2
Hitoshi Oma Ari Nestgawa Labor 1
Monoboshi Dai Ari Nestgawa Labor 1
Recommended Posts