23 Schüler von Stufe A, 24 von Stufe B und 30 von Stufe C müssen in drei Klassen eingeteilt werden. Die Klassen müssen fast exakt gleich groß sein. Verschiedene Ebenen können in eine einzelne Klasse gemischt werden, es ist jedoch besser, wenn es vermieden werden kann. In jedem Fall sollten 0 Schüler einer Klasse oder mehr als 6 Schüler sein.
Können Sie mir helfen, dieses kombinatorische Optimierungsproblem zu lösen? Im Folgenden finden Sie eine Beispieleingabe und -ausgabe. Bonuspunkte, wenn Sie mir zeigen können, wie Sie das allgemeine Problem lösen können!
Eingabe:
%Vor%Beispielausgabe (nicht sehr gut!)
%Vor%Bearbeiten : Hier ist mein sehr hackischer, völlig undokumentierter Semi-Brute-Force-Code. Es ist hässlich, aber es funktioniert! Ich würde gerne lernen, wie ich eine elegantere Lösung schreiben könnte.
Die grundlegende Schwierigkeit besteht darin, dass Sie ein Problem mit mehreren Zielen haben. Sie haben drei Dinge, an denen Sie interessiert sind, dass Sie entweder Ziele oder "weiche Einschränkungen" in Betracht ziehen können:
Beachten Sie, dass ich dafür ein Optimierungsmodell in AMPL geschrieben habe. Da Sie Python verwenden, gibt es ähnliche Optimierungsmodellierungssprachen für Python wie PuLP und pyomo, die Sie verwenden könnten. Das Modell sollte nicht zu schwer zu übersetzen sein.
Hier ist ein Integer-Programmiermodell und eine Datendatei, die das Ziel Nummer 1 betont, während das Problem (integer) linear bleibt. Mit diesem Ziel findet das Optimierungsproblem dieselbe Lösung, die Sie in Ihrem Beispiel angegeben haben. Hoffentlich können Sie darauf aufbauen und weitere Einschränkungen und / oder objektive Begriffe hinzufügen und bessere Lösungen erhalten.
Ziel ist es, die größte Klassengröße zu minimieren. Die Variable von Interesse ist y [i, j]. y [i, j] für i in LEVEL, j in CLASS ist die Anzahl der Schüler von Level i, die der Klasse j zugeordnet sind. Es geht davon aus, dass Sie für die Mindestanzahl von Schülern aus jedem Level in jeder Klasse eine Eingabe gemacht haben, wenn sie diesem Level zugewiesen sind.
Die Zielfunktion ist möglicherweise nicht das, was Sie wollen, aber es ist eine Möglichkeit, die Klassengröße auszugleichen, die linear ist. Ich verspreche auch nicht, dass dies der effizienteste Weg zur Lösung des Problems ist. Möglicherweise gibt es einen besseren benutzerdefinierten Algorithmus für das Problem, aber ich musste nur die Einschränkungen und das Ziel ausdrücken und keinen Algorithmus schreiben. Es ist wahrscheinlich gut genug für Sie.
Mit dem Solver Gurobi auf neos-server.org (Sie könnten lpsolve oder einen anderen Open-Source-Optimierungslöser verwenden), habe ich die Lösung
%Vor%Modell:
%Vor%Datendatei für Ihr Beispiel:
%Vor%