¶ Lineare Programmierung
Lineare Programmierung (LP) oder lineare Optimierung bezeichnet Methoden zur Optimierung (minierung oder maximierung) einer linearen Zielfunktion oder Kostenfunktion, welche einer Reihe linearer Nebenbedingungen unterliegt. Damit handelt es sich bei linearer Programmierung also nicht um einen einzigen Algorithmus sondern unterschiedliche Methoden zur Lösung einer klasse von Optimierungsproblems.
Formal wird ein LP-Problem meist wie folgt mathematisch beschrieben. Es sei die Matrix und die Vektoren , gegeben. Ziel ist es ein Vektor zu finden, so dass
unter den Nebenbedingungen
Zu bemerken ist, dass im Gegensatz zu Integer-Programmierung hier der Vektor nicht auf die natürlichen Zahlen beschränkt ist.
Das Problem von linearer Programmierung ist in Polynomieller Zeit lösbar. Durch gewisse Algorithmen wie die Ellipsoid-Methode oder Inner-Punkt-Verfahren wie Karmarkar's Algorithmus kann eine, im worst-case, polynomielle Laufzeit garantiert werden.[1] Jedoch werden in der Praxis meist Methoden wie die Simplex-Methode verwendet. Diese hat im worst-case zwar eine exponentielle Laufzeit, ist jedoch in der Praxis meist effizienter. [1:1]
¶ Geschichte
Im Jahr 1939 entwickelte der sowjetische Mathematiker Leonid Kantorowitsch die Grundlage für lineare Programmierung. In seiner Publikation
"Mathematische Methoden für die Organisation und Planung der Produktion" bemerkte er, dass viele wirtschaftliche Produktionsprobleme, bzw. Planungsprobleme, durch lineare Gleichungen beschrieben werden können.[2] Weiter argumentierte er für numerische Ansätze zum Lösen dieser Probleme. Seine Arbeit fand jedoch nur wenig Anklang und wurde anfangs ignoriert. [2:1]
Jedoch wurde er 1975 mit dem Nobelpreis für seine Arbeit an linearer Programmierung Ausgezeichnet.[3]
In Folge des zweiten Weltkriegs und den damit einhergehenden logistischen Fragestellungen, begann die Suche nach einer praktischen Lösung für LPs.[2:2] Im Jahr 1947 entwickelte George Dantzig die sogenannte Simplex-Methode, zur Lösung linearer Programme. Diese ist bis heute eine weit verbreitete Methode zur Lösung von LP-Problemen.[4] Der Mathematiker John von Neumann war einer der ersten, die die Wichtigkeit der Simplex-Methode erkannten.[3:1] Er entwickelte das Konzept von Dualität und verband lineare Optimierung mit der Spieltheorie.[2:3]
Seit der Simplex-Methode wurden eine Reihe unterschiedlicher Methoden zum Lösung von LPs vorgestellt.[2:4] Die meisten Algorithmen fallen hierbei in eine von zwei Kategorien. Die Basisaustauschverfahren und Innere-Punkt-Verfahren. Jedoch gibt es auch Algorithmen, die sich keiner der beiden Kategorien zurordenen lassen.
¶ Mathematische Formulierung
¶ Formale Beschreibung
Es seien die Matrix und die Vektoren und gegeben. Wir bezeichnen als zulässige, wenn für gilt:
bzw. das folgende System von Ungleichungen erfüllt.
Ziel ist es nun einen Vektor zu finden, welcher zulässig ist, und den Term
maximiert. Diese Formulierung wird als Ungleichungsform bezeichnet. [1:2] Manchmal wird auch die Standardform verwendet, bei der die Ungleichungen durch Gleichungen ersetzt werden.
¶ Intuition
Dazu wird zunächst die Nebenbedingungen betrachtet. Eine einzige Zeile kann wie folgt verstanden werden. Im allgemeinen beschreibt eine Gleichung der Form
eine Hyperebene im n-Dimensionalen Raum [3:2] (in ist dies z.B. eine Gerade). Die Ungleichung
Beschreibt somit alle Vektoren, welche "unterhalb" einer solchen Hyperebene liegen. Genauer zerteilt jede Ungleichung den n-Dimensionalen Raum in zwei Hälften.[3:3] Eine der Hälften ist dabei zulässig, die andere nicht. Alle Ungleichungen zusammen beschreiben somit ein Polyeder (Vieleck) im n-Dimensionalen Raum, in welchem die zulässigen Punkte liegen dürfen. [3:4]
Lineare Programmierung wird damit zu einer Aufgabe in diesem Polyeder nach einem Punkt zu suchen, welcher die Zielfunktion optimiert.
¶ Dualität
Das Prinzip von Dualität besagt, dass es zu jedem LP-Problem (primales Problem) ein duales LP-Problem gibt. Das primale Problem kann in das Duale umgewandelt werden. Weiter gibt die Lösung des dualen LP Informationen über das primale. [4:1]
Mathematisch kann Dualität wie folgt beschrieben werden. Betrachtet man die standard LP-Formulierung (Ungleichungsform)
Dann kann das entsprechende duale Problem formuliert werden als
Der schwache Dualitätssatz besagt nun, dass das duale Problem eine obere Schranke für das primale Problem bildet. Es gilt weiter die folgende Ungleichung:[4:2]
wobei die optimale Lösung für ist und die Optimale Lösung für .
Neben der schwachen Dualität gibt es auch noch den starken Dualitätssatz. Dieser bildet, wie der Name impliziert eine Verstärkung des schwachen Dualitätssatzes. Er besagt, dass wenn entweder das primale oder duale Problem einen optimale und zulässige Lösung hat, so haben beide eine Optimale Lösung. Für die optimalen Lösungen und gilt weiter der Zusammenhang:[4:3]
¶ Simplex-Methode
¶ Idee
Die Simplex-Methode wurde 1947 von George Dantzig vorgestellt. [4:4] Die entscheidende Beobachtung von Dantzig war, dass die Randbedingungen einen Polyeder beschreiben. Wenn die Zielfunktion linear ist, so wird die optimale zulässige Lösung, sofern diese existiert, auf einer Ecke des Polyeder Liegen.[1:3]
Dies kann wie folgt intuitiv begründet werden. Es gibt drei mögliche Fälle:
- Das Optimum liegt im inneren des Polyeder
Dieser Fall kann nie eintreten. Dazu nehmen wir an, dass das Optimum im inneren des Polyeder liegt. Da die Zielfunktion allerdings linear ist und somit keine Sattelpunkte oder lokalen Maxima hat, gibt es eine Richtung in die die Zielfunktion verbessert werden kann. Weiter da der Punkt im inneren des Polyeder liegt, kann ein Betrag von in die Richtung des Gradienten "gegangen" werden. Dieser Punkt muss die Zielfunktion verbessern.
- Das Optimum liegt auf einer Kante/Seite
Dieser Fall ist möglich jedoch müssen dann alle Punkte der Kante den gleichen Wert haben und somit ist auch ein Eckpunkt ein Optimum. Ansonsten gilt wie bei Punkt 1. dass eine lineare Zielfunktion kein lokales Optimum oder Sattelpunkt auf der Kante haben kann.
- Das Optimum liegt auf einer Ecke
Diese Aussage gilt immer.
Damit ist es also nicht notwendig die Fläche des gesamten Polyeder zu durchsuchen sondern man kann entlang der Kanten die Ecken traversieren[1:4] (in die Richtung welche die Zielfunktion optimiert). Dann müssen die, so gefundenen, Eckpunkte nur noch verglichen werden.
Die Simplex-Methode hat im worst-case eine Exponentielle Laufzeit. In der Praxis ist der Simplex Algorithmus jedoch effizient und wird daher bis heute verwendet. [1:5]
¶ Erklärung
Hier soll der Simplex Algorithmus anhand eines Beispiels erklärt werden. Dazu betrachten wird ein klassisches LP-Problem.
Zu finden sind so dass:
und Nebenbedingung
Wir wissen, dass die Lösung auf der Kante des Polyeders liegen muss. Damit können die Ungleichungen durch Gleichungen ersetzt werden. Auch wurden hier die Bedingungen ignoriert (diese gelten aber weiterhin). Wir führen außerdem Hilfsvariablen ein. In wirtschaftlichen Problemen haben diese eine sehr elegante Interpretation. Die Variablen können als noch ungenutzte Ressourcen verstanden werden.
Initial setzen wir die Hilfsvariablen auf die Werte , , , und . Damit kann nun folgendes Gleichungssystem definiert werden:
Auch dieses Gleichungssystem hat eine intuitive Interpretation. Auf der linken Seite stehen die Belegten Ressourcen ist z.B. Anfangs bereits mit Kapazität ausgelastet ist zu Anfang gleich .
Nun wollen wir entlang einer Kante gehen. Wir wählen die Richtung durch, die die Zielfunktion am stärksten verbessert wird (steilster Gradient). Für ist das die Richtung (die partielle Ableitung der Zielfunktion ist wohingegen die partielle Ableitung nach gleich ist).
Wir variieren also und zwar bis wir das Ende der Kante erreichen. Anders gesagt, bis wir eine Randbedingung verletzen. Es ist zu sehen, dass wenn wir wählen, wird (1) ganz sicher verletzt werden. Somit können wir auf den Wert setzen.
Das Ergebnis setzen wir nun in die anderen Gleichungen ein. Zu bemerken ist, dass wir die erste Gleichung auch wie folgt umstellen könnten.
Wobei . Mathematisch entspricht dies einem Basiswechsel (deswegen ist die Simplex-Methode eine Basiswechsel-Methode oder Basisaustausch-Methode).
Die wirtschaftliche Intuition bleibt dabei erhalten. Auf der linken Seite stehen die belegten Ressourcen ist jetzt nämlich mit belegt.
Durch das Einsetzen von in die Zielfunktion, ergibt sich .
Die Einzige Richtung in die wir nun gehen können ist , und aus unserer neuen Gleichung wissen wir, dass sobald gilt, dass wir nicht mehr im Polyeder sind. Also setzen wir .
Das Optimum liegt somit bei .
¶ Ellipsoid-Methode
Die Ellipsoid-Methode war der erste Lösungsansatz für LP-Probleme mit einer garantierten polynomiellen Laufzeit. Obwohl sie somit theoretisch besser als die Simplex-Methode ist, weist die Simplex-Methode in der Praxis eine bessere Laufzeit auf. Somit hat die Ellipsoid-Methode eher historische und theoretische Relevanz.[5]
Mit der Ellipsoid-Methode kann festgestellt werden, ob ein Punkt in einem Polyeder enthalten ist oder ob es leer ist. Der Mathematiker Leonid Khachiyan wendete 1979 die allgemeine Ellipsoid-Methode auf LPs an. [5:1]
Die grundlegende Idee der Ellipsoid-Methode ist nicht direkt nach einem Optimalen Punkt zu suchen, sondern nach einem zulässigen Punkt im Polyeder. Dazu konstruiert man eine Ellipse, welche die Zulässige Region enthält.[1:6] Danach wird geprüft, ob das Zentrum der Ellipse im Polyeder liegt, wenn ja dann hat man einen Punkt im Polyeder gefunden. Wenn nicht wurde eine der Nebenbedingungen verletzt. Mit der verletzten Nebenbedingung kann man die Ellipse in zwei Teile unterteilen.[1:7] Der eine Teil der Ellipse kann ausgeschlossen werden. Jetzt konstruiert man im verbleibenden Teil eine neue Ellipse und wiederholt das Verfahren.[1:8]
¶ Karmarkar's-Methode
Bei Karmarkar's Algorithmus handelt es sich um eine Innere-Punkt-Methode.[2:5] Anders als bei der Simplex-Methode, welche eine Basisaustauschmethode darstellt, oder der Ellipsoid-Methode sucht Karmarkar's Methode strikt im Polyeder nach einer Lösung. Im Gegensatz zur Simplex-Methode garantiert Karmarkar's Methode eine Polynomielle Laufzeit. Anders als die Ellipsoid-Methode ist die Methode von Karmarkar auch in der Praxis effizienter. [1:9]
Konzeptionell ist der Ansatz von Karmarkar einfach zu verstehen. Der Algorithmus beginnt im Zentrum des Polyeders. [6] Von dort gehen wir in die Richtung, welche die Zielfunktion am besten optimiert. Das wird solange wiederholt, bis wir ein Optimum erreicht haben. Die Schwierigkeit, besteht darin, die Schrittweite so zu wählen, dass der neue Punkt strikt im Polyeder bleibt. Dazu verwendet der Karmarkar Algorithmus eine Methode namens projektive scaling.[6:1] Karmarkar's Algorithmus kann somit ähnlich wie Hill-Climbing oder Gradient descent Algorithmen verstanden werden.
¶ Bildquellen
Abb. 1: Graphische darstellung eines LP-Problems - Abgerufen von url Bild
Abb. 2: Erstellt mittels LibreOffice - Draw
Abb. 3: Darstellung des Simplex Algorithmus - Abgerufen von https://upload.wikimedia.org/wikipedia/commons/d/d4/Simplex-method-3-dimensions.png
Abb. 4: Erstellt mittels GeoGebra
Abb. 5: Darstellung der Ellipsoid Methode - Abgerufen von https://upload.wikimedia.org/wikipedia/commons/c/c9/Ellipsoid-method.png
Abb. 6: Vergleich des Simplex Algorithmus und Karmarkar - Entnommen aus [7] Bild
¶ Literatur
Goldfarb, Donald, and Michael J. Todd. "Chapter II linear programming." Handbooks in operations research and management science 1 (1989): 73-170. url ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Thie, Paul R., and Gerard E. Keough. An introduction to linear programming and game theory. John Wiley & Sons, 2011. ↩︎ ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Wikipedia contributors. (n.d.). Lineare Optimierung. In Wikipedia. Retrieved Jan. 12, 2026, from https://de.wikipedia.org/wiki/Lineare_Optimierung#Geometrische_Interpretation ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Goemans, Michel. Linear Programming, MIT, 2015 url ↩︎ ↩︎ ↩︎ ↩︎ ↩︎
Arora, Sanjeev. The Ellipsoid Algorithm for Linear Programming, Princeton Universtiy, 2005 pdf ↩︎ ↩︎
Karloff, H.. Karmarkar’s Algorithm. In: Linear Programming. Modern Birkhäuser Classics. Birkhäuser Boston. 2009 url ↩︎ ↩︎
Gkiotsalitis, K. Continuous Constrained Optimization. In: Public Transport Optimization. Springer, Cham. 2002 url ↩︎