Lineare Optimierung

Problemdefinition

Geometrische Interpretation

Ein lineares Programm lässt sich geometrisch interpretieren. Wenn die i. Zeile eines linearen Programms in Standardform ist, dann beschreibt die Menge {x | a_i x = b_i } aller Punkte x, die die zugehörige lineare Gleichung a_i x = b_i erfüllen, eine Hyperebene im n-dimensionalen Raum. Die Menge der Punkte, die die lineare Ungleichung erfüllen, besteht aus allen Punkten auf der einen Seite der Hyperebene (inklusive der Hyperebene selbst), bildet also einen Halbraum. Jede Zeile teilt daher den n-dimensionalen Raum in zwei Hälften, wobei die Punkte in der einen Hälfte zulässig sind und in der anderen nicht. Die Menge

der Punkte, die alle Ungleichungen des LPs erfüllen, ist genau der Schnitt dieser Halbräume, also die Menge aller Punkte, die für jede Ungleichung in der jeweiligen zulässigen Hälfte des Raumes liegen. Diese Lösungsmenge P des linearen Programms bildet ein konvexes Polyeder, also ein n-dimensionales Vieleck, in dem die Verbindungslinie zwischen zwei beliebigen Punkten von P vollständig in P enthalten ist. Ziel der Optimierung ist es, unter allen Punkten des Polyeders einen zu finden, der die lineare Funktion maximiert. Geometrisch entspricht dies der Verschiebung der Hyperebene {x | c^T x = 0} in Richtung des Vektors c, bis die verschobene Hyperebene das Polyeder gerade noch berührt. Die Menge aller Berührungspunkte ist genau die Menge der Optimallösungen des linearen Programms.

Zulässige Menge (blau) eines LPs in Standardform mit einschränkenden Ungleichungen (grün), Zielfunktion (rote Linie) und einer optimalen Lösung (roter Punkt).

Im nebenstehenden Bild ist diese Anordnung für den Fall von nur zwei Variablen dargestellt. Eine Hyperebene im zweidimensionalen Raum ist eine Gerade, im Bild grün dargestellt. Jede dieser Geraden teilt den Raum in eine zulässige und eine unzulässige Hälfte. Die Menge der Punkte, die auf der zulässigen Seite jeder Geraden liegen, bilden das blau dargestellte Polyeder (Vieleck). Die rote Gerade stellt die Zielfunktion dar. Ziel ist es, sie so weit wie möglich in Richtung des roten Vektors c zu verschieben, ohne das Polyeder zu verlassen. Im nebenstehenden Bild ist der rote Berührungspunkt der Zielfunktionsgeraden mit dem Polyeder die einzige Optimallösung.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Lineare Optimierung aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung