Die lineare Optimierung (auch lineare Programmierung, englisch Linear Programming, LP) ist ein mathematisches Verfahren, um eine lineare Zielfunktion unter linearen Nebenbedingungen zu maximieren oder zu minimieren. Sie ist eines der wichtigsten Werkzeuge des Operations Research und wird in Produktionsplanung, Logistik, Finanzen und vielen weiteren Bereichen eingesetzt.
Grundidee
Eine lineare Zielfunktion wie „Kosten minimieren" oder „Gewinn maximieren" hängt von mehreren Entscheidungsvariablen ab. Die Nebenbedingungen sind Gleichungen oder Ungleichungen, ebenfalls linear — etwa Kapazitäts-, Budget- oder Zeitgrenzen. Der Bereich aller zulässigen Lösungen ist ein konvexes Polyeder. Ist das Optimum beschränkt und existiert eine zulässige Lösung, dann liegt das Optimum in einer Ecke dieses Polyeders — darauf beruhen die klassischen Lösungsverfahren.
Verfahren
- Simplex-Verfahren (George Dantzig, 1947): wandert entlang der Kanten von Ecke zu Ecke, bis keine Verbesserung mehr möglich ist. In der Praxis extrem schnell, im worst case aber exponentiell.
- Ellipsoidmethode (Leonid Chatschijan, 1979): erstes nachweislich polynomielles Verfahren.
- Innere-Punkte-Verfahren (Narendra Karmarkar, 1984): nähern sich dem Optimum durch das Innere des Polyeders und sind auch theoretisch polynomial.
Lineare Optimierung ist damit in polynomieller Zeit lösbar; die Abgrenzung zur Komplexitätstheorie liefert P vs. NP.
Dualität
Jedes lineare Optimierungsproblem hat ein zugeordnetes duales Problem. Der Dualitätssatz besagt, dass die optimalen Zielfunktionswerte von primalem und dualem Problem übereinstimmen; der komplementäre Schlupf verbindet die Lösungen. Dualität wird nicht nur zur Lösungskontrolle genutzt, sondern auch für ökonomische Interpretationen wie Schattenpreise.
Ganzzahlige Variante
Müssen die Variablen ganzzahlig sein (Integer Linear Programming, ILP), wird das Problem NP-vollständig — es ist kein polynomielles Verfahren bekannt, gelöst wird mit Branch-and-Bound oder Heuristiken. Das Transportproblem ist ein klassischer Anwendungsfall der linearen Optimierung mit kontinuierlichen Variablen, die ungarische Methode löst ganzzahlige Zuordnungen auf direktem Wege. Grundbaustein ist die lineare Funktion.