Ein Programm löst das lineare Programm
Die Funktion linprog aus der Bibliothek SciPy löst ein lineares Programm in Sekundenbruchteilen, auch mit hundert Variablen. Sie müssen nur Ziel und Grenzen als Listen aufschreiben.
In dieser Lektion rechnen Sie die Bäckerei mit linprog nach. Sie lernen, was die Ausgabe bedeutet und wie das Programm sagt, dass es keine Lösung gibt.
Am Ende dieser Lektion
Notiz
Ich kann ein lineares Programm mit linprog lösen und das Ergebnis lesen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| SciPy | eine Python-Bibliothek für wissenschaftliche Rechnungen | |
| linprog | die SciPy-Funktion für lineare Programme | |
| Koeffizient | die Zahl, mit der eine Variable malgenommen wird | 50 vor x |
| Status | eine Zahl, die sagt, wie die Rechnung endete | |
| Unzulässig | kein Plan hält alle Grenzen ein |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
linprog minimiert immer, ein Maximum braucht ein Minus
Die Funktion linprog sucht den kleinsten Wert der Zielfunktion. Wollen Sie einen Gewinn möglichst groß machen, geben Sie ihr das Negative: minus 50 und minus 30.
Der kleinste Wert von minus Gewinn gehört zum größten Gewinn. Das Ergebnis müssen Sie am Ende wieder mit minus malnehmen.
Der Minus-Trick in reinem Python
# Ein Maximum ist das Minimum des Negativen.
gewinne = [50, 30]
negativ = []
for g in gewinne:
negativ.append(-g)
plan = [2, 2]
wert = plan[0] * negativ[0] + plan[1] * negativ[1]
print("Zielwert fürs Minimieren:", wert)
print("Gewinn in Euro:", -wert)
# Ändern Sie plan in [3, 0] und starten Sie erneut.
# Welches Vorzeichen hat der Zielwert fürs Minimieren?
Beispiel: wie das Modell zu Listen wird
| Teil des Modells | Name bei linprog | Wert für die Bäckerei |
|---|---|---|
| Zielfunktion, negativ | c | [-50, -30] |
| Verbrauch je Nebenbedingung | A_ub | [[1, 1], [2, 1]] |
| Vorräte | b_ub | [4, 6] |
| Untergrenzen der Variablen | bounds | je (0, None): ab null, nach oben offen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Der Aufruf von linprog für die Bäckerei
from scipy.optimize import linprog
c = [-50, -30] # minus der Gewinne, denn linprog minimiert
A_ub = [[1, 1], [2, 1]] # eine Zeile je Nebenbedingung
b_ub = [4, 6] # die Vorräte rechts vom <=
bounds = [(0, None), (0, None)] # x >= 0 und y >= 0
ergebnis = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds)
print(ergebnis.status) # 0 heißt: gelöst
print(ergebnis.x) # der beste Plan
print(-ergebnis.fun) # der Gewinn, wieder positivDie Bäckerei mit linprog lösen
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-50, -30], A_ub=[[1, 1], [2, 1]], b_ub=[4, 6]); print(r.x, -r.fun)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Der Status sagt, ob es eine Lösung gibt
Nicht jedes Modell hat eine beste Lösung. Das Ergebnis trägt deshalb einen Status. Die Null heißt: gelöst.
Die Zwei heißt unzulässig: Kein Plan hält alle Grenzen ein, etwa x plus y höchstens 1 und zugleich mindestens 3. Die Drei heißt unbeschränkt: Der Wert wird ohne Ende besser, weil eine Grenze fehlt.
Ein Modell ohne zulässigen Plan
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([1, 1], A_ub=[[1, 1], [-1, -1]], b_ub=[1, -3]); print(r.status)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ein Modell ohne Obergrenze
docker exec jupyter python3 -c "from scipy.optimize import linprog; r = linprog([-1]); print(r.status)"Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die wichtigsten Statuswerte
| Status | Bedeutung | Was Sie tun |
|---|---|---|
| 0 | Gelöst | Plan und Zielwert lesen |
| 2 | Unzulässig | Grenzen prüfen: widersprechen sie sich? |
| 3 | Unbeschränkt | Eine Grenze fehlt, etwa ein Vorrat |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein häufiger Fehler
Warnung
Viele lesen r.fun als den Gewinn. Wer minus 50 und minus 30 übergeben hat, bekommt aber minus 160. Der Gewinn ist -r.fun. Lesen Sie Zielwert und Plan erst, wenn der Status 0 ist.
Im Inneren sucht linprog Ecken ab
Das Programm erfindet keine neue Mathematik. Es sucht, wie Sie in der letzten Lektion, den besten Eckpunkt, aber klug: Es springt von Ecke zu Ecke und geht nur zu besseren.
Zur Kontrolle zählen Sie in der Aufgabe alle Ecken selbst auf. Das Ergebnis sollte zu dem passen, was linprog findet.