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.
Table of contents |
2 Lösbarkeit 3 Geometrische Interpretation 4 Diskrete lineare Programmierung 5 Lösungsverfahren 6 Anwendungsbeispiele 7 Siehe auch |
Im Bereich der linearen Programmierung gibt es zwei Normalformen, die von Interesse sind. In der Standarform sind alle Bedingungen durch Ungleichungen definiert, in der Slackform durch Gleichungen. Jedes LP-Problem lässt sich durch geeignete Umformungen in beide Normalformen bringen.
Ein lineares Programm in Standardform hat folgende Form:
Mögliche Abweichungen von der Standardform sind
Häufig wird ein lineares Programm auf die Form
Kombiniert man mehrere lineare 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 erzeugt immer ein konvexes Polytop, einen sogenannten Simplex. (Der Simplexalgorithmus verfolgt gierig die Ecken dieses Polytops bis zu einem lokalen Maximum, das in einem Simplex dem globalen Maximum entspricht.)
Die zu maximierende Zielfunktion stellt ebenfalls eine Hypereben 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 den Simplex berührt.
Ein Spezialfall der linearen Programmierung ist die sogenannte diskrete lineare Programmierung (engl. integer lineare programming). Bei diesen Optimierungsproblemen muss zusätzlich zu den Einschränkungsungleichungen gelten, d.h. für die Komponenten von werden nur ganzzahlige Werte zugelassen.
Eine weitere Spezialisierung dieser Art von Problemen ist die binäre diskrete lineare Programmierung (engl. 0-1 integer lineare programming), bei der gelten muss , also die Komponente nur die Werte 0 oder 1 annehmen.
Diese Art von Problemen fällt in die Klasse der NP-harten Probleme und ist daher vermutlich nicht effizient lösbar.
Will man diskrete lineare 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.
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.
Das Problem des Handlungsreisenden (TSP) lässt sich als binäres diskretes lineares Optimierungsproblem darstellen, bei dem ein Inzidenzvektor als optimale Tour gesucht wird, der die Kosten minimiert. Hierzu kann die 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ädten in Deutschland.Normalformen
Standardform
Dabei ist eine reelle -Matrix und sind reelle Vektoren.
Formulierungen von linearen Optimierungsproblemen, in denen diese Fälle auftreten, lassen sich umformen durch einige einfache Operationen:
Slackform
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 sind.Lösbarkeit
Ein lineares Programm muss nicht lösbar sein. Dieser Fall tritt unter folgenden Bedingungen ein:
Geometrische Interpretation
Ein lineares Programm (in Standardform) lässt sich geometrisch interpretieren: jede lineare Gleichung über die Variablen beschreibt eine Hyperebene im -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.Diskrete lineare Programmierung
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. Anwendungsbeispiele
Problem des Handlungsreisenden