Lineare Programmierung

Die Minimierung oder Maximierung einer linearen Zielfunktion unter Berücksichtigung von Schranken, linearen Gleichheits- und Ungleichheitsbedingungen wird als lineare Programmierung (LP) bezeichnet. Dazu gehören zum Beispiel Probleme wie das Mischen in der Prozessindustrie, die Produktionsplanung in der Fertigung, der Cashflow-Abgleich im Finanzwesen und die Planung im Energie- und Transportwesen.

Unter linearer Programmierung versteht man das mathematische Problem, einen Vektor x zu finden, der diese Funktion minimiert:

\[\min_{x} \left\{f^{\mathsf{T}}x\right\}\]

Unter Berücksichtigung der Nebenbedingungen:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(Ungleichheitsnebenbedingung)} \\A_{eq}x = b_{eq} & \quad & \text{(Gleichheitsnebenbedingung)} \\lb \leq x \leq ub & \quad & \text{(Grenznebenbedingung)}\end{eqnarray}\]

Mit MATLAB^® sind Sie in der Lage, die folgenden, häufig verwendeten Algorithmen zum Lösen linearer Optimierungsprobleme zu implementieren:

• 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.
• Simplex: Diese Methode verwendet ein systematisches Verfahren zum Erstellen und Testen möglicher Eckpunktlösungen für ein lineares Programm. Der Simplex-Algorithmus und der verwandte Dual-Simplex-Algorithmus sind die am häufigsten verwendeten Algorithmen für die lineare Programmierung.

Algorithmen für einige Sonderfälle von linearen Programmen, bei denen die Nebenbedingungen eine Netzwerkstruktur haben, sind üblicherweise schneller als die allgemeinen Innerer-Punkt- und Simplex-Algorithmen. Zu den Sonderfällen gehören:

• Maximaler Netzdurchsatz: Verwendet Augmenting-Path- und Push-Relabel-Algorithmen.
• Kürzester Pfad: Verwendet Dijkstra-, Bellman-Ford- und Suchalgorithmen.
• Lineare Zuweisung: Verwendet einen zweiseitigen Abstimmungsalgorithmus.

Weitere Informationen zu Algorithmen und linearer Programmierung finden Sie in den Erläuterungen zur Optimization Toolbox™.