linprog(method=’highs-ds’)#

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: Minimieren einer linearen Zielfunktion unter linearen Gleichheits- und Ungleichheitsnebenbedingungen mit dem HiGHS-Dual-Simplex-Solver.

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 ‘highs-ds’. ‘highs’, ‘highs-ipm’, ‘interior-point’ (Standard), ‘revised simplex’ und ‘simplex’ (Legacy) sind ebenfalls verfügbar.

Rückgabe:

resOptimizeResult

Ein scipy.optimize.OptimizeResult mit den Feldern

x1D-Array

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

funfloat

Der optimale Wert der Zielfunktion c @ x.

slack1D-Array

Die (nominal positiven) Werte des Schlupfes, b_ub - A_ub @ x.

con1D-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 : Iterations- oder Zeitlimit erreicht.

2 : Problem scheint unzulässig zu sein.

3 : Problem scheint unbeschränkt zu sein.

4 : Der HiGHS-Solver hatte ein Problem.

messagestr

Eine Zeichenkette, die den Beendigungsstatus des Algorithmus beschreibt.

nitint

Die Gesamtzahl der durchgeführten Iterationen. Dies schließt Iterationen in allen Phasen ein.

crossover_nitint

Dies ist immer 0 für die HiGHS-Simplex-Methode. Für die HiGHS-Interior-Point-Methode ist dies die Anzahl der während der Crossover-Routine durchgeführten Primal-/Dual-Pushes.

ineqlinOptimizeResult

Lösungs- und Sensitivitätsinformationen für die Ungleichheitsbeschränkungen, b_ub. Ein Wörterbuch, das die Felder enthält

residualnp.ndnarray: Die (nominal positiven) Werte der Schlupfvariablen, b_ub - A_ub @ x. Diese Größe wird auch häufig als „Schlupf“ bezeichnet.
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die rechte Seite der Ungleichheitsbeschränkungen, b_ub.

eqlinOptimizeResult

Lösungs- und Sensitivitätsinformationen für die Gleichheitsbeschränkungen, b_eq. Ein Wörterbuch, das die Felder enthält

residualnp.ndarray: Die (nominal nullen) Residuen der Gleichheitsbedingungen, b_eq - A_eq @ x.
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die rechte Seite der Gleichheitsbeschränkungen, b_eq.

lower, upperOptimizeResult

Lösungs- und Sensitivitätsinformationen für die unteren und oberen Schranken für Entscheidungsvariablen, bounds.

residualnp.ndarray: Die (nominal positiven) Werte der Größe x - lb (unten) oder ub - x (oben).
marginalsnp.ndarray: Die Sensitivität (partielle Ableitung) der Zielfunktion in Bezug auf die unteren und oberen bounds.

Siehe auch

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

Optionen:

——-

maxiterint

Die maximale Anzahl von Iterationen, die in einer beliebigen Phase durchgeführt werden sollen. Standard ist der größtmögliche Wert für einen int auf der Plattform.

dispbool (Standard: False)

Auf True setzen, wenn Optimierungsstatusanzeigen während der Optimierung 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.

time_limitfloat

Die maximal zugelassene Zeit in Sekunden zur Lösung des Problems; Standard ist der größtmögliche Wert für ein double auf der Plattform.

dual_feasibility_tolerancedouble (Standard: 1e-07)

Dual-Fehlertoleranz für ‘highs-ds’.

primal_feasibility_tolerancedouble (Standard: 1e-07)

Primal-Fehlertoleranz für ‘highs-ds’.

simplex_dual_edge_weight_strategystr (Standard: None)

Strategie für die Gewichte der dualen Kanten im Simplex. Die Standardeinstellung None wählt automatisch eine der folgenden Optionen aus.

'dantzig' verwendet Dantzig's ursprüngliche Strategie, die den negativsten reduzierten Kostenkoeffizienten wählt.

'devex' verwendet die in [15] beschriebene Strategie.

steepest verwendet die exakte steepest-edge-Strategie, wie in [16] beschrieben.

'steepest-devex' beginnt mit der exakten steepest-edge-Strategie, bis die Berechnung zu kostspielig oder ungenau wird, und schaltet dann auf die devex-Methode um.

Derzeit wählt None immer 'steepest-devex' aus, dies kann sich jedoch ändern, wenn neue Optionen verfügbar werden.

unknown_optionsdict

Optionale Argumente, die von diesem speziellen Solver nicht verwendet werden. Wenn unknown_options nicht leer ist, wird eine Warnung ausgegeben, die alle ungenutzten Optionen auflistet.

Hinweise

Die Methode ‘highs-ds’ ist ein Wrapper für die C++-Hochleistungs-Dual-Revised-Simplex-Implementierung (HSOL) [13], [14]. Die Methode ‘highs-ipm’ ist ein Wrapper für eine C++-Implementierung einer **i**nternen **P**unkt**m**ethode [13]; sie verfügt über eine Crossover-Routine und ist daher genauso genau wie ein Simplex-Solver. Die Methode ‘highs’ wählt automatisch zwischen den beiden. Für neuen Code, der linprog verwendet, empfehlen wir, explizit einen dieser drei Methodenwerte anstelle von ‘interior-point’ (Standard), ‘revised simplex’ und ‘simplex’ (Legacy) zu wählen.

Die Ergebnis-Felder ineqlin, eqlin, lower und upper enthalten alle marginals, oder partielle Ableitungen der Zielfunktion in Bezug auf die rechte Seite jeder Beschränkung. Diese partiellen Ableitungen werden auch als „Lagrange-Multiplikatoren“, „Dualwerte“ und „Schattenpreise“ bezeichnet. Die Vorzeichenkonvention von marginals ist entgegengesetzt zu der von Lagrange-Multiplikatoren, die von vielen nichtlinearen Lösern erzeugt werden.

Referenzen

[13] (1,2)

Huangfu, Q., Galabova, I., Feldmeier, M., und Hall, J. A. J. „HiGHS - high performance software for linear optimization.“ https://highs.dev/

[14]

Huangfu, Q. und Hall, J. A. J. „Parallelizing the dual revised simplex method.“ Mathematical Programming Computation, 10 (1), 119-142, 2018. DOI: 10.1007/s12532-017-0130-5

[15]

Harris, Paula MJ. “Pivot selection methods of the Devex LP code.” Mathematical programming 5.1 (1973): 1-28.

[16]

Goldfarb, Donald, and John Ker Reid. “A practicable steepest-edge simplex algorithm.” Mathematical Programming 12.1 (1977): 361-371.