Lineare Programmierung

Minimieren von linearen Funktionen, die Nebenbedingungen unterliegen

Zur Linearen Programmierung (LP) zählt die Minimierung oder Maximierung einer objektiven Funktion, die Grenzen, linearen Gleichheits- und Ungleichheitsnebenbedingungen unterliegt. Dazu gehören zum Beispiel Probleme wie die Entwurfsoptimierung bei der Entwicklung, die Gewinnmaximierung bei der Herstellung, die Portfolio-Optimierung in der Finanzbranche und die Planung in der Energie- und Transportbranche.

Die lineare Optimierung stellt das mathematische Problem dar, einen Vektor \(x\) zu finden, der die folgende Funktion minimiert:

\[\min_x \left\{f^Tx\right\}\]

Unterliegt den Nebenbedingungen:

\(Ax\leq b\)
(Ungleichheitsnebenbedingung)
\(A_{eq}x=b_{eq}\)
(Gleichheitsnebenbedingung)
\(lb\leq x\leq ub\)
(Grenznebenbedingung)

Die folgenden Algorithmen werden in der Regel verwendet, um Probleme der linearen Programmierung zu lösen:

  • Innerer Punkt: Dieses Verfahren verwendet einen Algorithmus aus Primal/Dual und Predictor/Corrector und eignet sich vor allem für große Probleme, die eine definierte Struktur besitzen oder durch dünn besetzte Matrizen dargestellt werden können.
  • Active-Set: Dieses Verfahren minimiert die Zielfunktion bei jeder Iteration nur auf der Untermenge der lokal aktiven Nebenbedingungen, bis eine Lösung gefunden ist.
  • Simplex: Diese Methode verwendet ein systematisches Verfahren zum Erstellen und Testen möglicher Eckpunktlösungen für ein lineares Programm. und ist die am häufigsten verwendete Methode in der linearen Programmierung.

Weitere Informationen zu Algorithmen und linearer Programmierung finden Sie unter Optimization Toolbox.

Siehe auch: Steve zu Image Processing, Digitale Bildverarbeitung mit MATLAB (Buch), Bildverbesserung, Bildsegmentierung, Bildtransformation, Bildanalyse, geometrische Transformation und Bildregistrierung, Bild- und Videoverarbeitung, Detailextraktion, Stereosehen, optischer Fluss, Farbprofil, Bildanalyse, Bildschwellenwerte, Kantenerkennung, Bildregistrierung, Ransac, Mustererkennung