lineare Programmierung, Klasse von Optimierungsproblemen, bei denen eine lineare Zielfunktion c^T · x unter linearen Ungleichungs-Nebenbedingungen optimiert wird, d. h., auf einer Menge der Form

\begin{eqnarray}M:=\{x\in {{\mathbb{R}}}^{n}|A\cdot x\le b\}\end{eqnarray}

mit A ∈ ℝ^m×n, b ∈ ℝ^m. Die Ungleichung ist dabei komponentenweise zu verstehen.

Das Problem gehört zur Klasse der konvexen Optimierungsaufgaben. Es gibt eine Reihe von Formulierungen für lineare Optimierungsprobleme, die in dem Sinne äquivalent sind, daß man ein Problem ohne Effizienzverlust von einer gegebenen in jede beliebige andere dieser Formulierungen umformen kann. Dazu gehören beispielsweise

\begin{eqnarray}\begin{array}{c}\begin{array}{l}\min {c}^{T}\cdot x\,\text{unter}\,A\cdot x\le b;\\ \min {c}^{T}\cdot x\,\text{unter}\,A\cdot x\ge b,x\ge 0;\\ \min {c}^{T}\cdot x\,\text{unter}\,A\cdot x=b,x\ge 0,\end{array}\end{array}\end{eqnarray}

und viele mehr.

Schließlich ist das Auffinden eines Extremalpunktes eines derartigen Problems über den Dualitätssatz der linearen Programmierung ebenfalls äquivalent zum Berechnen eines zulässigen Punktes einer Menge {x ∈ ℝⁿ| A · x ≤ b}. Je nachdem, welche Lösungsverfahren betrachtet werden, startet man mit verschiedenen dieser Problemformulierungen. Zu den wichtigsten Lösungsverfahren gehören das Simplexverfahren, die Ellipsoidmethoden, sowie die Innere-Punkte Methoden.

Der 1947 von Dantzig entwickelte Simplexalgorithmus galt viele Jahre als der wesentliche Algorithmus für lineare Optimierungsprobleme. Seine exponentielle Laufzeit im worst-case Verhalten war lange Zeit Grund für die Vermutung, die lineare Optimierung gehöre nicht zur Klasse P der in Polynomzeit lösbaren Probleme (im Modell der Turingmaschine).

Das 1979 von Khachiyan vorgestellte Ellipsoidverfahren widerlegte diese Vermutung: Die lineare Programmierung ist (im Modell der Turingmaschine) ein in Polynomzeit lösbares Problem. Dieses Ergebnis führte zur Suche nach nicht nur theoretisch, sondern auch praktisch effizienten Verfahren.

Seit ihrer Einführung durch Karmarkar 1984 haben die innere-Punkte Methoden zunehmend an Bedeutung gewonnen und stellen heute eine wesentliche Klasse von Lösungsmethoden für konvexe Optimierungsprobleme dar.

Eine zentrale, noch ungelöste Frage bzgl. der Lösung linearer Programme ist die nach der Existenz polynomialer Algorithmen in algebraischen Rechenmodellen. Dabei zählt man nur die Anzahl der arithmetischen Operationen und Vergleiche der Form „x ≥ 0“ eines Verfahrens in Abhängigkeit von der algebraischen Größe eines speziellen Problems. Diese ist als Anzahl der das Problem bestimmenden reellen Zahlen definiert (hier also n · m + n + m für c ∈ ℝⁿ, b ∈ ℝ^m und A ∈ ℝ^m×n). Positive Teilergebnisse in diese Richtung liegen vor (z. B. von Tardos (1986) und Vavasis-Ye (1996)), die allgemeine Frage ist derzeit (Ende 2000) unbeantwortet. Ebenfalls offen ist die Frage nach der Parallelisierbarkeit linearer Programmierungsverfahren: Das zugehörige Entscheidungsproblem ist P-vollständig.

In neuerer Zeit werden lineare Optimierungsprobleme zunehmend auch unter Aspekten ihrer Konditionierung analysiert. Dabei geht man davon aus, daß die Eingabedaten nur mit einer gewissen, bekannten Genauigkeit gegeben sind. Von Lösungsalgorithmen erwartet man nun nur in dem Fall ein Ergebnis, wenn das gegebene Problem bzgl. der Genauigkeit gut genug konditioniert war.

[1] Schrijver, A.: Theory of linear and integer programming. John Wiley and Sons, 1986.