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.

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:

$\max\{c^{T}x=\sum _{j=1}^{n}c_{j}x_{j}:Ax\leq b,x_{1}\ldots x_{n}\geq 0\}$

Dabei ist $A$ eine reelle $m\times n$-Matrix und $b=(\beta _{1}\ldots \beta _{m})^{T},c=(\gamma _{1}\ldots \gamma _{n})^{T}$ 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 $\gamma _{i}$ in der Zielfunktion
2. Ersetzung von $x_{j}$ durch $x_{j}'-x_{j}''$ mit $x_{j}',x_{j}''\geq 0$
3. Ersetzung von $a_{i}x=\beta$ durch $a_{i}x\leq \beta ,a_{i}x\geq \beta$
4. Negierung der Koeffizienten $\alpha _{ij},\beta _{i}$ in der betreffenden Bedingung $i$

Slackform

Häufig wird ein lineares Programm auf die Form

$\max\{c^{T}x=\sum _{j=1}^{n}c_{j}x_{j}:Ax=b,x_{1}\ldots x_{n}\geq 0\}$

gebracht. Das ist nötig, um den Simplexalgorithmus zur Lösung des Problems anzuwenden. Dies geschieht, indem man jede Variable $x_{j}$ durch $x_{j}^{+}-x_{j}^{-}$ mit zwei positiven Variablen $x_{j}^{+}$ und $x_{j}^{-}$ ersetzt und sogenannte Schlupfvariablen einführt: $x_{n+j}=\beta _{j}-\sum _{k=1}^{n}a_{jk}x_{k}$, wobei $a_{jk}$ die Einträge von $A$ sind.

Lösbarkeit

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

1. Der zulässige Bereich $\{x:Ax\leq b,x\geq 0\}$ ist leer
2. Die Zielfunktion $x\mapsto c^{T}x$ ist auf dem zulässigen Bereich nicht nach oben beschränkt.

Im zweiten Fall kann durchaus eine (auf Grund der Bedingungen $Ax\leq b$ und $x\geq 0$ 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 $x_{1}\ldots x_{n}$ beschreibt eine Hyperebene im $n$-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 diskrete Optimierung gemeint ist. Bei diesen Optimierungsproblemen muss zusätzlich zu den Einschränkungsungleichungen $x\in \mathbf {Z} ^{n}$ gelten, d.h. für die Komponenten von $x$ 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 $x\in \{0,1\}^{n}$ 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. Ein polynomialer Algorithmus ist auch die Ellipsoid-Methode.

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 $x$ als optimale Tour gesucht wird, der die Kosten $c^{T}x$ 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