Lineare Programmierung (LP)

Die lineare Programmierung ist die Problemklasse max c^T x s.t. Ax ≤ b, x ≥ 0 in kanonischer Form, wobei c ∈ R^n der Kostenvektor, A ∈ R^(m×n) die Restriktionsmatrix, b ∈ R^m die rechte Seite und x ∈ R^n die kontinuierlichen reellen Entscheidungsvariablen sind. Der zulässige Bereich X = {x : Ax ≤ b, x ≥ 0} ist ein konvexes Polytop, und eine lineare Zielfunktion nimmt ihr Optimum stets in einem Eckpunkt (Basislösung) an. Begründet wurde die Disziplin von George B. Dantzigs Simplex-Algorithmus 1947, motiviert durch Planungsprobleme der US-Luftwaffe (daher der Begriff 'Programmierung', der dem informatischen Sprachgebrauch vorausgeht). Die Dualitätstheorie (von Neumann 1947) ordnet jedem primalen LP ein duales LP zu; der starke Dualitätssatz besagt, dass bei beidseitiger Zulässigkeit und Beschränktheit die optimalen Zielwerte übereinstimmen; Schattenpreise werden aus den dualen Variablen abgelesen. Komplexität: Klee und Minty (1972) zeigten die exponentielle Worst-Case-Laufzeit des Simplex-Verfahrens; Khachiyan (1979) lieferte mit der Ellipsoidmethode den ersten polynomiellen LP-Algorithmus (theoretisch); Karmarkar (1984) führte ein polynomielles und praktisch leistungsfähiges Innere-Punkte-Verfahren ein. Moderne Löser kombinieren revidiertes Simplex- und Innere-Punkte-Verfahren mit Presolve, sparsamer LU-Faktorisierung und Crash-Start und lösen Millionen-Variablen-Probleme in Sekunden. Anwendungen umfassen Produktionsplanung, Mischungsprobleme, Transportprobleme, Cashflow-Planung und das Diätproblem.