Was ist lineare Programmierung?

Bei der linearen Programmierung, die auch als lineare Optimierung bezeichnet wird, geht es um die Minimierung oder Maximierung einer linearen Zielfunktion, die Randbedingungen wie Grenzen, linearer Gleichheit und linearer Ungleichheit unterliegt. Beispielprobleme sind die Vermischung in der Verfahrenstechnik, die Produktionsplanung in der Fertigung, der Cashflow-Abgleich im Finanzwesen sowie die Planung im Bereich Energie und Transportwesen.

Die lineare Programmierung befasst sich mit dem mathematischen Problem, einen Vektor \(x\) zur Minimierung der folgenden Funktion zu finden:

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

Unter den Randbedingungen:

\[\begin{eqnarray}Ax \leq b & \quad & \text{(Randbedingung der Ungleichheit)} \\A_{eq}x = b_{eq} & \quad & \text{(Randbedingung der Gleichheit)} \\lb \leq x \leq ub & \quad & \text{(Randbedingung der Grenze)}\end{eqnarray}\]

Lineare Programmierung mit MATLAB

Mit MATLAB^® können Sie die folgenden häufig verwendeten Algorithmen zum Lösen linearer Programmierungsprobleme implementieren:

• Innere Punkte: Mit primal-dualem Predictor-Corrector-Algorithmus; besonders hilfreich bei großen linearen Programmen mit Struktur oder die mithilfe von dünnbesetzten Matrizen definierbar sind.
• Simplex: Mit systematischem Verfahren zur Generierung und Testung vielversprechender Scheitelpunktlösungen eines linearen Programms. Der Simplex-Algorithmus und der verwandte Dual-Simplex-Algorithmus sind die bei der linearen Optimierung am häufigsten verwendeten Algorithmen.

Der linprog-Solver in der Optimization Toolbox™ implementiert diese linearen Optimierungstechniken.

Sonderfälle bei der linearen Programmierung

Algorithmen für einige Sonderfälle linearer Optimierungsprobleme mit Randbedingungen in Netzstruktur sind in der Regel schneller als die Universalalgorithmen Innere Punkte oder Simplex. Zu den Sonderfällen gehören:

• Maximaler Netzwerkfluss: mit den Augmentierender-Pfad- und Push-Relabel-Algorithmen.
• Kürzester Pfad: mit den Dijkstra-, Bellman-Ford- und Suchalgorithmen.
• Lineare Zuweisung: mit einem Algorithmus zum zweiseitigen Abgleich.

Weitere Informationen zu Algorithmen und zur linearen Optimierung finden Sie unter Optimization Toolbox.