Den Solver suchen lassen
Eine Schreinerin kann Tische und Stühle bauen, aber Holz und Stunden gehen zur Neige. Welche Mischung bringt am meisten? Man könnte einen ganzen Nachmittag lang Pläne ausprobieren. Oder man schreibt die Grenzen auf und lässt einen Solver den besten Plan finden oder beweisen, dass es keinen gibt.
Am Ende dieser Lektion
Notiz
Ich kann ein Optimierungsmodell ausführen und seinen Status, seinen Plan und seine Schattenpreise ablesen.
Schlüsselwörter
- Modell: die Grenzen und das Ziel, aufgeschrieben.
- Solver: ein Programm, das die beste Antwort auf ein Modell findet.
- Schlupf: was von einer Grenze übrig bleibt.
- Schattenpreis: was eine Einheit mehr von einer Grenze wert ist.
- Ganzzahl: eine Zahl ohne Bruchteil.
Zum Start: Was du schon weißt
Notiz
Antworte im Kopf. 1. Was ist eine Variable? 2. Was heißt es, etwas zu maximieren? 3. Kann man 2,5 Stühle bauen? Die dritte Antwort brauchst du gleich.
Bevor du anfängst
Notiz
Drücke oben in der Leiste dieser Lektion auf Lab starten. Dieses Lab ist eine ganze Ubuntu-Maschine für dich allein, sie braucht daher etwas länger zum Starten als ein Container und installiert ihre Solver beim ersten Mal. Jede Schaltfläche Ausführen tippt ihren Befehl in das Terminal der Maschine, einen nach dem anderen, in derselben Sitzung. Wenn eine meldet, dass die Maschine noch startet, warte ein paar Sekunden und drücke sie erneut. Um zuzusehen oder eigene Befehle zu tippen, drücke in der Leiste auf Terminal öffnen.
Ein Modell ist ein Ziel und einige Grenzen
Deine Dateien liegen im Ordner optimisation. Der erste Befehl wechselt dorthin. lp.py ist ein mit PuLP geschriebenes Modell: Tische und Stühle, ein Gewinn, der maximiert werden soll, und Grenzen für Holz, Stunden und Lagerplatz. opt führt eine Python-Datei aus, bei der die Solver bereitstehen. Die erste Zeile sagt Optimal: Der Solver ist fertig geworden, und die Antwort ist verlässlich. Der Plan lautet 20 Tische und 60 Stühle, ein Gewinn von 2800.
cd optimisationHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
opt lp.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Prüfe dich
Tipp
Welche Grenze hat Schlupf, und wie hoch ist ihr Schattenpreis? Antwort: Beim Lagerplatz bleiben 60 übrig, eine Einheit mehr ist also nichts wert. Holz und Stunden sind aufgebraucht, und ihre Schattenpreise sind 20 und 10: Eine Einheit Holz mehr bringt 20 mehr Gewinn.
Ein häufiger Fehler
Warnung
Viele glauben, jede aufgebrauchte Grenze bremse den Gewinn gleich stark. Das stimmt nicht. Lies den Schattenpreis: Eine aufgebrauchte Grenze mit einem Preis von 20 lohnt sich, mehr davon zu beschaffen, und eine Grenze mit Schlupf ist nicht mehr wert, auch wenn sie groß ist.
Ganze Zahlen brauchen einen anderen Solver
integer.py wählt Projekte, und ein Projekt wird ganz oder gar nicht gemacht. Das Modell wird zweimal gelöst. Mit erlaubten Bruchteilen ist der Wert 45,17, und der Plan macht 0,67 eines Projekts. Rundet man diesen Plan auf ganze Projekte, kostet er 22 bei einem Budget von 19, ist also kein Plan. Verlangt man nur ganze Projekte, ist der Wert 42, mit drei Projekten: bridge, garden und theatre.
opt integer.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Prüfe dich
Tipp
Warum ist die Antwort mit Bruchteilen mehr wert als die ganzzahlige? Antwort: Sie hat weniger Regeln. Teile eines Projekts zu erlauben kann nur helfen, daher ist sie eine obere Schranke für die ganzzahlige Antwort.
Ein Constraint-Solver erstellt einen Dienstplan
shifts.py verwendet OR-Tools CP-SAT. Drei Pflegekräfte teilen sich vier Tage lang drei Schichten am Tag, und jede hat Wünsche, bestimmte Schichten nicht zu arbeiten. Niemand arbeitet eine Nachtschicht und danach die Frühschicht des nächsten Tages. Der Solver sagt OPTIMAL und dass ein Wunsch verletzt werden muss, weil zwei Pflegekräfte am ersten Tag nicht dieselben Schichten meiden können. Für jeden Tag wird ein Dienstplan ausgegeben.
opt shifts.pyHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Abschlusscheck
Tipp
Antworte, ohne zurückzublättern. 1. Was macht ein Solver? 2. Was sagt dir der Status Optimal? 3. Was ist ein Schattenpreis? 4. Warum kann man einen gebrochenen Plan nicht einfach runden? Antworten: Er findet die beste Antwort auf ein Modell; dass der Solver fertig ist und die Antwort die beste ist; was eine Einheit mehr von einer Grenze wert ist; der gerundete Plan kann eine Grenze verletzen. Öffne jetzt die README.md in deinem Home-Ordner mit cat ~/README.md: Du schreibst zwei Modelle.
Für Lehrkräfte
Tipp
Diese Lektion ist ein kleines Beispiel für eine Lektion, die in einem Lab bearbeitet wird: Die Schritte und die Schaltflächen „Ausführen“ sind die Lektion, und das Lab ist die eigene Kopie jeder lernenden Person. Sie läuft in einem VM-Lab: Alle Lernenden haben eine eigene Ubuntu-Maschine mit installiertem PuLP, CBC und OR-Tools, und „Ausführen“ tippt in deren Terminal und zeigt, was ausgegeben wurde. Kernpunkte: 1. Ein Modell ist ein Ziel und einige Grenzen, und ein Solver findet die beste Antwort. 2. Den Status lesen, bevor man die Zahlen liest. 3. Schlupf und Schattenpreis sagen, welche Grenzen zählen. 4. Ganze Zahlen brauchen einen ganzzahligen Solver, und Runden kann eine Grenze verletzen. Häufiger Fehler: jede aufgebrauchte Grenze verantwortlich machen, ohne ihren Preis zu lesen. Material: das Lab und ein Browser. Tipp: Lass die Klasse vor dem zweiten Befehl 0,67 eines Projekts selbst runden. Das Lab selbst hat eine Prüfung, die zwei Modelle auf verborgenen Instanzen bewertet. Das Modul Operations Research löst seine Aufgaben mit SciPy; dieses Lab ist der Ort, an dem eine Klasse PuLP und OR-Tools kennenlernt. Kopiere die Lektion in dein eigenes Modul und ändere sie, oder baue im Lektionseditor über das Menü Lab eine neue von Grund auf.