Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


43. Lineare Programmierung



Geometrische Interpretation

Lineare Optimierungsaufgaben gestatten eine geometrische Interpretation. Die folgende lineare Optimierungsaufgabe kann leicht veranschaulicht werden, da nur zwei Variablen auftreten:

Maximiere x1 + x2
unter Berücksichtigung der Nebenbedingungen

-x1 + x2 <= 5,
x1 + 4x2 <= 45,
2x1 + x2 <= 27,
3x1 - 4x2 <= 24,
x1, x2 >= 0.

Diese lineare Optimierungsaufgabe entspricht der in Abbildung 43.1 dargestellten geometrischen Situation. Jede Ungleichung definiert eine Halbebene, in der jede Lösung der linearen Optimierungsaufgabe liegen muß. Zum Beispiel bedeutet x1 >= 0, daß jede Lösung der x2-Achse liegen muß, und -x1 + x2 <= 5 bedeutet, daß jede Lösung unterhalb und rechts von der Geraden -x1 + x2 = 5 liegen muß (die durch (0, 5) und (5, 10) verläuft). Jede Lösung der linearen Optimierungsaufgabe muß allen diesen Nebenbedingungen genügen, so daß das durch die Schnittmenge aller dieser Halbebenen definierte Gebiet (in der Abbildung schattiert) die Menge aller möglichen Lösungen darstellt. Um die lineare Optimierungsaufgabe zu lösen, müssen wir denjenigen Punkt innerhalb dieses Gebiets finden, für den die Zielfunktion maximal wird.

Ein Gebiet, das als Schnitt von Halbebenen definiert ist, ist immer konvex (diese Tatsache ist uns bereits aus einer der Definitionen der konvexen Hülle in Kapitel 25 bekannt). Dieses konvexe Gebiet, das Simplex genannt wird, bildet die Grundlage für einen Algorithmus zur Bestimmung der Lösung der linearen Optimierungsaufgabe, für die die Zielfunktion ihren maximalen Wert annimmt.

Eine grundlegende Eigenschaft des mit Hilfe dieses Algorithmus untersuchten Simplex besteht darin, daß die Zielfunktion ihr Maximum in einem der Eckpunkte des Simplex annimmt; daher brauchen nur die Eckpunkte untersucht zu werden und nicht alle Punkte im Inneren. Um zu sehen, warum das so ist, betrachten wir die durch eine Schattierung gekennzeichnete Gerade im rechten oberen Teil von Abbildung 43.1, die der Zielfunktion entspricht. Die Zielfunktion kann man sich in der Weise vorstellen, daß sie eine Gerade mit bekannter Steigung (in diesem Falle -1) und unbekannter Lage definiert. Uns interessiert der Punkt, in dem die Gerade erstmals das Simplex berührt, wenn sie sich aus dem Unendlichen nähert. Dieser Punkt ist die Lösung der linearen Optimierungsaufgabe: Er genügt allen Ungleichungen, da er dem Simplex angehört, und er maximiert die Zielfunktion, da keine Punkte mit größeren Werten angetroffen wurden. In unserem Beispiel berührt die Gerade das Simplex im Punkt (9, 9), für den die Zielfunktion den maximalen Wert 18 annimmt.

Abbildung 43.1
Abbildung 43.1 Ein zweidimensionales Simplex.

Andere Zielfunktionen entsprechen Geraden mit anderen Steigungen, das Maximum wird jedoch stets in einem der Eckpunkte des Simplex angenommen. Der Algorithmus, den wir weiter unten betrachten, ist eine systematische Methode, wie man sich von einem Eckpunkt zum nächsten bewegen kann, um das Maximum zu finden. Bei zwei Dimensionen gibt es nicht viele Auswahlmöglichkeiten, doch wie wir sehen werden, ist das Simplex ein wesentlich komplizierteres Gebilde, wenn mehr Variablen vorhanden sind.

Anhand Abbildung 43.1 kann man auch erkennen, warum die Behandlung mathematischer Optimierungsaufgaben, bei denen nichtlineare Funktionen auftreten, bedeutend komplizierter ist. Wenn zum Beispiel die Zielfunktion nichtlinear ist, kann es sich um eine Kurve handeln, die das Simplex an einer seiner Seiten und nicht in einem Eckpunkt berührt. Falls die Ungleichungen ebenfalls nichtlinear sind, können anstelle des Simplex sehr komplizierte geometrische Formen auftreten.

Aus der geometrischen Veranschaulichung wird deutlich, daß verschiedene anomale Situationen eintreten können. Nehmen wir zum Beispiel an, daß wir der linearen Optimierungsaufgabe in dem obigen Beispiel die Ungleichung x1 >= 13 hinzufügen. Aus Abbildung 43.1 ist dann ersichtlich, daß in diesem Fall der Schnitt der Halbebenen leer ist. Eine solche lineare Optimierungsaufgabe heißt unlösbar: Es existieren keine Punkte, die den Ungleichungen genügen, so daß sich die Frage nach Punkten, die die Zielfunktion maximieren, erübrigt. Dagegen ist die Ungleichung x1 <= 13 redundant: Das Simplex ist vollständig in dieser Halbebene enthalten, so daß diese Ungleichung nicht an der Darstellung des Simplex beteiligt ist. Redundante Ungleichungen beeinflussen die Lösung keineswegs, müssen jedoch im Verlaufe der Suche nach der Lösung mit betrachtet werden.

Ein ernsthafteres Problem besteht darin, daß das Simplex ein offenes (unbeschränktes) Gebiet sein kann; in diesem Fall ist es möglich, daß die Lösung nicht wohldefiniert ist. Dieser Fall würde in unserem Beispiel dann eintreten, wenn die zweite und dritte Ungleichung weggelassen würden. Auch wenn das Simplex unbeschränkt ist, ist es möglich, daß für gewisse Zielfunktionen die Lösung wohldefiniert ist, doch ein Algorithmus zu ihrer Ermittlung könnte beträchtliche Schwierigkeiten haben, das unbeschränkte Gebiet zu umgehen.

Es muß unterstrichen werden, daß diese Probleme, auch wenn sie im Falle von zwei Variablen und nur wenigen Ungleichungen sehr leicht zu erkennen sind, für ein allgemeines Problem mit vielen Variablen und Ungleichungen weit weniger offensichtlich sind. Tatsächlich verursacht die Ermittlung dieser anomalen Situationen einen beträchtlichen Teil des numerischen Aufwands bei der Lösung linearer Optimierungsaufgaben.

Die gleiche geometrische Interpretation ist für mehrere Variablen möglich. Im dreidimensionalen Fall ist das Simplex ein konvexer dreidimensionaler Körper, der als Schnittmenge von Halbräumen gebildet wird, die durch die Ebenen definiert sind, deren Gleichungen man erhält, wenn man die Ungleichungen in Gleichungen umwandelt. Wenn wir zum Beispiel zu der obigen linearen Optimierungsaufgabe die Ungleichungen x3 <= 4 und x3 >= 0 hinzufügen, entsteht als Simplex der in Abbildung 43.2 dargestellte Körper.

Abbildung 43.2
Abbildung 43.2 Ein dreidimensionales Simplex.

Um den dreidimensionalen Charakter des Beispiels zu verstärken, nehmen wir an, daß wir die Zielfunktion in x1 + x2 + x3 abändern. Dadurch wird eine Ebene definiert, die senkrecht zu der Geraden x1 = x2 = x3 verläuft. Wenn sich eine Ebene längs dieser Geraden vom Unendlichen her nähert, berührt sie das Simplex im Punkt (9, 9, 4), welcher die Lösung ist. (In Abbildung 43.2 ist außerdem noch ein Pfad entlang der Eckpunkte des Simplex von (0, 0, 0) zur Lösung dargestellt, der für die Bezugnahme in der nachfolgenden Beschreibung des Algorithmus bestimmt ist.)

Im n-dimensionalen Fall bilden wir die Schnittmenge von Halbräumen, die durch (n - 1)-dimensionale Hyperebenen definiert sind, um das n-dimensionale Simplex zu definieren, und nähern eine (n - 1)-dimensionale Hyperebene vom Unendlichen her, welche das Simplex in dem Punkt berührt, der der Lösung entspricht. Wie bereits erwähnt wurde, besteht die Gefahr einer zu starken Vereinfachung, wenn wir uns auf die intuitiv vorstellbaren zwei- und dreidimensionalen Situationen konzentrieren, doch Beweise der obengenannten, Konvexität, Schnitte von Hyperebenen usw. betreffenden Tatsachen erfordern eine Vertrautheit mit linearer Algebra, die für dieses Buch nicht vorausgesetzt wird. Dennoch ist die geometrische Intuition wertvoll, da sie uns helfen kann, die Hauptmerkmale der grundlegenden Methode zu verstehen, die in der Praxis für die Lösung von Problemen höherer Dimension angewandt wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]