Lineare Optimierung

Die Lineare Optimierung oder auch Lineare Programmierung (kurz LP) ist eines der Hauptverfahren des Operations Research und beschäftigt sich mit dem Optimieren linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Häufig lässt sich die lineare Programmierung einsetzen, um Probleme zu lösen, für die keine speziell entwickelten Algorithmen bekannt sind.

Inhaltsverzeichnis

1 Normalformen 1.1 Standardform 1.2 Slackform 2 Lösbarkeit 3 Geometrische Interpretation 4 Diskrete Programmierung 5 Lösungsverfahren 6 Anwendungsbeispiele 6.3 Problem des Handlungsreisenden 7 Siehe auch 8 Literatur

Normalformen

Im Bereich der linearen Programmierung gibt es zwei Normalformen, die von Interesse sind. In der Standardform sind alle Bedingungen durch Ungleichungen definiert, in der Slackform durch Gleichungen. Jedes LP-Problem lässt sich durch geeignete Umformungen in beide Normalformen bringen.

Standardform

Ein lineares Programm in Standardform hat folgende Form:

Dabei ist AA eine reelle -Matrix und sind reelle Vektoren.

Mögliche Abweichungen von der Standardform sind

1. Minimierungsproblem statt Maximierungsproblem,
2. Variablen ohne Nichtnegativitätsbedingung,
3. Gleichheitsbedingungen statt Ungleichheitsbedingungen und
4. Größer-als- statt Kleiner-als-Bedingungen.

Formulierungen von linearen Optimierungsproblemen, in denen diese Fälle auftreten, lassen sich umformen durch einige einfache Operationen:

1. Negierung der Koeffizienten in der Zielfunktion
2. Ersetzung von durch mit
3. Ersetzung von durch
4. Negierung der Koeffizienten in der betreffenden Bedingung ii

Slackform

Häufig wird ein lineares Programm auf die Form

gebracht. Das ist nötig, um den Simplexalgorithmus zur Lösung des Problems anzuwenden. Dies geschieht, indem man jede Variable durch mit zwei positiven Variablen und ersetzt und sogenannte Schlupfvariablen einführt: , wobei die Einträge von AA sind.

Lösbarkeit

Ein lineares Programm muss nicht lösbar sein. Dieser Fall tritt unter folgenden Bedingungen ein:

1. Der zulässige Bereich ist leer
2. Die Zielfunktion ist auf dem zulässigen Bereich nicht nach oben beschränkt.

Im zweiten Fall kann durchaus eine (auf Grund der Bedingungen und in einigen Komponenten eindeutige) Lösung vorhanden sein.

Geometrische Interpretation

Ein lineares Programm (in Standardform) lässt sich geometrisch interpretieren: jede lineare Gleichung über die Variablen beschreibt eine Hyperebene im nn-dimensionalen Raum. Eine zugehörige lineare Ungleichung beschreibt dann einen Halbraum, nämlich alle Punkte, die auf der einen Seite der Hyperebene liegen (inklusive der Ebene selbst). Dieser Halbraum stellt die Menge aller gültigen Lösungen für die Ungleichung dar.

Kombiniert man eine endliche Anzahl linearer Ungleichungen zu einem Ungleichungssystem, so erhält man als Lösungsmenge gerade die Punkte, die alle Ungleichungen erfüllen, also den Schnitt der Halbräume. Dieser Schnitt definiert ein verallgemeinertes konvexes Polyeder, das im Gegensatz zu einem klassischen Polyeder mehrdimensional und nicht immer beschränkt ist. (Der Simplexalgorithmus verfolgt die Ecken dieses Zulässigkeit-Polyeders bis zu einem lokalen Maximum, das bei linearen Optimierungsaufgaben dem globalen Maximum entspricht.)

Die zu maximierende Zielfunktion stellt ebenfalls eine Hyperebene dar, allerdings mit noch unbekanntem Abstand vom Ursprung und damit unbekanntem Zielwert. Lässt man eine Ebene mit der entsprechenden Steigung vom Unendlichen auf den Ursprung zuwandern, so ist die Lösung erreicht, sobald die Ebene zum ersten Mal das Zulässigkeit-Polyeder berührt.

Diskrete Programmierung

Bei der Linearen Optimierung wird stillschweigend vorausgesetzt, dass beliebige reelle Zahlen als Lösungskomponenten zulässig sind. Kein Spezialfall ist deshalb die (wegen engl. integer linear programming) oft sogenannte "diskrete lineare Programmierung", womit eigentlich lineare diskretee Optimierung gemeint ist. Bei diesen Optimierungsproblemen muss zusätzlich zu den Einschränkungsungleichungen gelten, d.h. für die Komponenten von xx werden nur ganzzahlige Werte zugelassen.

Dazu gehört auch die lineare binäre Programmierung (engl. 0-1 integer linear programming), bei der die Lösungskomponenten nur die Werte 0 oder 1 annehmen dürfen, also gelten muss.

Diese Art von Problemen fällt in die Klasse der NP-schweren Probleme und ist daher vermutlich nicht effizient lösbar.

Die Lösung einer zugehörigen Lineare Optimierung, das heißt eine Lösung, die sich nicht auf ganze Zahlen beschränkt, kann in einigen Fällen zur Berechnung einer approximativen Lösung verwendet werden.

Lösungsverfahren

Zur Lösung von linearen Programmen wird meist der Simplexalgorithmus verwendet. Dieser Algorithmus ist in den meisten Fällen effizient, kann jedoch exponentielle Laufzeit besitzen, daher hielt man lange Zeit lineare Probleme für nicht effizient lösbar. In den letzten Jahren wurden jedoch Innere-Punkt-Verfahren zur linearen Programmierung entwickelt, deren Laufzeit polynomial ist. Diese beruhen auf dem Verfahren von Karmarkar. Ein polynomialer Algorithmus ist auch die Ellipsoid-Methode - sie kann jedoch nicht praktisch verwendet werden.

Will man lineare diskrete Programme lösen, werden häufig Cutting-Plane-Methoden eingesetzt: dabei wird mit einem der bekannten Verfahren eine optimale Lösung gesucht. Ist diese Lösung nicht diskret, so erweitert man das Ungleichungssystem um eine sogenannte cutting plane, eine Ungleichung, die das Polytop beschneidet, ohne gültige Lösungen zu verwerfen. Dieses Verfahren wird iterativ angewendet, bis als optimale Lösung ein Punkt gefunden wird, der nur aus diskreten Komponenten besteht.

Anwendungsbeispiele

Viele Probleme, die sich mit linearer Programmierung lösen lassen, sind im wirtschaftlichen Bereich zu finden. Aber auch abstraktere Probleme lassen sich damit lösen, beispielsweise in der Graphentheorie: das Finden kürzester Pfade, des maximalen Flusses oder eines minimalen Kostenflusses lässt sich als lineares Programm formulieren, obwohl dafür teilweise auch spezielle Algorithmen bekannt sind.

Problem des Handlungsreisenden

Das Problem des Handlungsreisenden (TSP) lässt sich als lineares binäres Optimierungsproblem darstellen, bei dem ein Inzidenzvektor xx als optimale Tour gesucht wird, der die Kosten minimiert. Hierzu kann das Verfahren der cutting planes angewendet werden. Tatsächlich hält diese Methode den Weltrekord der exakten Lösung eines TSPs für 15.112 Städte in Deutschland.

Siehe auch

• Nicht-lineare Optimierung
• Ungarische Methode

Literatur

• George B. Dantzig: Lineare Programmierung und Erweiterungen, Springer-Verlag 1966 (Titel der Orginalausgabe: Linear Programming and Extensions, Princeton University Press)

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project - Become an Editor