linprog(method=’revised simplex’)#

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=(0, None), method='highs', callback=None, options=None, x0=None, integrality=None)

Lineare Programmierung: Minimierung einer linearen Zielfunktion unter linearen Gleichheits- und Ungleichheitsbedingungen mittels der revidierten Simplex-Methode.

Veraltet seit Version 1.9.0: method=’revised simplex’ wird in SciPy 1.11.0 entfernt. Es wird durch method=’highs’ ersetzt, da letzteres schneller und robuster ist.

Lineare Programmierung löst Probleme der folgenden Form

\[\begin{split}\min_x \ & c^T x \\ \mbox{so dass} \ & A_{ub} x \leq b_{ub},\\ & A_{eq} x = b_{eq},\\ & l \leq x \leq u ,\end{split}\]

wobei \(x\) ein Vektor von Entscheidungsvariablen ist; \(c\), \(b_{ub}\), \(b_{eq}\), \(l\) und \(u\) Vektoren sind; und \(A_{ub}\) und \(A_{eq}\) Matrizen sind.

Alternativ, das heißt

minimieren

c @ x

so dass

A_ub @ x <= b_ub
A_eq @ x == b_eq
lb <= x <= ub

Beachten Sie, dass standardmäßig lb = 0 und ub = None gilt, es sei denn, dies wird mit bounds angegeben.

Parameter:

c1-D-Array: Die Koeffizienten der linearen Zielfunktion, die minimiert werden soll.
A_ub2-D-Array, optional: Die Matrix der Ungleichheitsbedingungen. Jede Zeile von A_ub gibt die Koeffizienten einer linearen Ungleichheitsbedingung für x an.
b_ub1-D-Array, optional: Der Vektor der Ungleichheitsbedingungen. Jedes Element stellt eine Obergrenze für den entsprechenden Wert von A_ub @ x dar.
A_eq2-D-Array, optional: Die Matrix der Gleichheitsbedingungen. Jede Zeile von A_eq gibt die Koeffizienten einer linearen Gleichheitsbedingung für x an.
b_eq1-D-Array, optional: Der Vektor der Gleichheitsbedingungen. Jedes Element von A_eq @ x muss gleich dem entsprechenden Element von b_eq sein.
boundsSequenz, optional: Eine Sequenz von (min, max) -Paaren für jedes Element in x, die die minimale und maximale Wert dieser Entscheidungsvariablen definieren. Verwenden Sie None, um anzuzeigen, dass keine Grenze existiert. Standardmäßig sind die Grenzen (0, None) (alle Entscheidungsvariablen sind nicht-negativ). Wenn ein einzelnes Tupel (min, max) bereitgestellt wird, dienen min und max als Grenzen für alle Entscheidungsvariablen.
methodstr: Dies ist die methodenspezifische Dokumentation für ‚revised simplex‘. ‚highs‘, ‚highs-ds‘, ‚highs-ipm‘, ‚interior-point‘ (Standard) und ‚simplex‘ (Legacy) sind ebenfalls verfügbar.
callbackcallable, optional: Callback-Funktion, die einmal pro Iteration ausgeführt werden soll.
x01-D-Array, optional: Schätzwerte der Entscheidungsvariablen, die vom Optimierungsalgorithmus verfeinert werden. Dieses Argument wird derzeit nur von der Methode ‚revised simplex‘ verwendet und kann nur verwendet werden, wenn x0 eine zulässige Basislösung darstellt.

Rückgabe:

resOptimizeResult

Ein scipy.optimize.OptimizeResult mit den Feldern

x1-D-Array

Die Werte der Entscheidungsvariablen, die die Zielfunktion minimieren und gleichzeitig die Bedingungen erfüllen.

funfloat

Der optimale Wert der Zielfunktion c @ x.

slack1-D-Array

Die (nominal positiven) Werte der Schlupfvariablen, b_ub - A_ub @ x.

con1-D-Array

Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.

successbool

True, wenn der Algorithmus erfolgreich eine optimale Lösung findet.

statusint

Eine Ganzzahl, die den Exit-Status des Algorithmus darstellt.

0 : Optimierung erfolgreich abgeschlossen.

1 : Iterationslimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Numerische Schwierigkeiten aufgetreten.

5 : Das Problem hat keine Nebenbedingungen; Vorabprüfung aktivieren.

6 : Ungültige Schätzung angegeben.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

nitint

Die Gesamtzahl der Iterationen in allen Phasen.

Siehe auch

Die Dokumentation für die restlichen Parameter finden Sie unter scipy.optimize.linprog

Optionen:

——-
maxiterint (Standard: 5000): Die maximale Anzahl von Iterationen, die in jeder Phase durchgeführt werden.
dispbool (Standard: False): Auf True setzen, wenn Indikatoren des Optimierungsstatus bei jeder Iteration auf der Konsole ausgegeben werden sollen.
presolvebool (Standard: True): Presolve versucht, triviale Unzulässigkeiten zu identifizieren, triviale Unbeschränktheit zu erkennen und das Problem zu vereinfachen, bevor es an den Hauptlöser übergeben wird. Es wird generell empfohlen, die Standardeinstellung True beizubehalten. Setzen Sie auf False, wenn Presolve deaktiviert werden soll.
tolfloat (Standard: 1e-12): Die Toleranz, die bestimmt, wann eine Lösung in Phase 1 als „nahe genug“ an Null gilt, um als zulässige Basislösung betrachtet zu werden, oder nahe genug an positiv, um als optimale Lösung zu dienen.
autoscalebool (Standard: False): Auf True setzen, um eine automatische Äquilibrierung durchzuführen. Erwägen Sie die Verwendung dieser Option, wenn die numerischen Werte in den Bedingungen um mehrere Größenordnungen voneinander abweichen.
rrbool (Standard: True): Auf False setzen, um die automatische Entfernung redundanter Gleichungen zu deaktivieren.
maxupdateint (Standard: 10): Die maximale Anzahl von Aktualisierungen, die an der LU-Faktorisierung vorgenommen werden. Nach Erreichen dieser Anzahl von Aktualisierungen wird die Basismatrix von Grund auf neu faktorisiert.
mastbool (Standard: False): Minimieren der amortisierten Lösungszeit. Wenn aktiviert, wird die durchschnittliche Zeit zum Lösen eines linearen Systems unter Verwendung der Basisfaktorisierung gemessen. Typischerweise nimmt die durchschnittliche Lösungszeit mit jeder aufeinanderfolgenden Lösung nach der anfänglichen Faktorisierung ab, da die Faktorisierung viel mehr Zeit als die Lösungsoperation (und Aktualisierungen) in Anspruch nimmt. Schließlich wird jedoch die aktualisierte Faktorisierung so komplex, dass die durchschnittliche Lösungszeit zu steigen beginnt. Wenn dies erkannt wird, wird die Basis von Grund auf neu faktorisiert. Aktivieren Sie diese Option, um die Geschwindigkeit auf Kosten nicht deterministischen Verhaltens zu maximieren. Ignoriert, wenn maxupdate 0 ist.
pivot„mrc“ oder „bland“ (Standard: „mrc“): Pivot-Regel: Minimum Reduced Cost („mrc“) oder Bland-Regel („bland“). Wählen Sie die Bland-Regel, wenn das Iterationslimit erreicht ist und Zyklen vermutet werden.
unknown_optionsdict: Optionale Argumente, die von diesem speziellen Löser nicht verwendet werden. Wenn unknown_options nicht leer ist, wird eine Warnung ausgegeben, die alle ungenutzten Optionen auflistet.

Hinweise

Die Methode *revised simplex* verwendet die revidierte Simplex-Methode, wie in [9] beschrieben, mit der Ausnahme, dass eine Faktorisierung [11] der Basis-Matrix, anstatt ihrer Inversen, effizient aufrechterhalten und zum Lösen der linearen Systeme in jeder Iteration des Algorithmus verwendet wird.

Referenzen

[9]

Bertsimas, Dimitris, und J. Tsitsiklis. „Introduction to linear programming.“ Athena Scientific 1 (1997): 997.

[11]

Bartels, Richard H. „A stabilization of the simplex method.“ Journal in Numerische Mathematik 16.5 (1971): 414-434.