Lineare Optimierung

Die Lineare Optimierung oder auch Lineare Programmierung ist eines der Hauptverfahren des Operations Research und beschäftigt sich mit der Optimierung 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. Die lineare Optimierung ist ein Spezialfall der konvexen Optimierung. Gleichzeitig ist sie Grundlage mehrerer Lösungsverfahren in der ganzzahligen Optimierung und der nichtlinearen Optimierung. Viele Eigenschaften linearer Programme lassen sich auch als Eigenschaften von Polyedern interpretieren und auf diese Art geometrisch motivieren und beweisen.

Der Begriff „Programmierung" ist eher im Sinne von „Planung" zu verstehen als im Sinne eines Computerprogramms. Er wurde schon Mitte der 1940er Jahre von George Dantzig, einem der Begründer der Linearen Optimierung, geprägt, bevor Computer zur Lösung linearer Optimierungsprobleme eingesetzt wurden.

Die lineare Optimierung wurde erstmals 1939 von dem russischen Mathematiker Leonid Witaljewitsch Kantorowitsch in seinem Buch „Mathematische Methoden in der Organisation und Planung der Produktion" behandelt. Kurz danach veröffentlichte der Amerikaner F.L. Hitchcock eine Arbeit zu einem Transportproblem. Damals erkannte man noch nicht die Bedeutung dieser Arbeiten. Unter anderem für seinen Beitrag zur linearen Optimierung bekam Kantorowitsch aber 1975 den Nobelpreis für Wirtschaftswissenschaften.

Mitte der 1940er Jahre erkannte George Dantzig, dass sich viele praktische Beschränkungen durch lineare Ungleichungen beschreiben ließen, und ersetzte erstmals die bis dahin vorherrschenden Ad-Hoc-Regeln zur Lösung von Planungsproblemen durch eine (lineare) Zielfunktion. Insbesondere etablierte er damit erstmals eine klare Trennung zwischen dem Ziel der Optimierung und den Mitteln zur Lösung des Planungsproblems.

Den Durchbruch für die lineare Optimierung schaffte Dantzig 1947, als er eine Arbeit über das Simplex-Verfahren veröffentlichte, das heute eines der meistgenutzten Verfahren zur Lösung linearer Programme ist. Interesse an dieser Arbeit zeigten zunächst die amerikanischen Militärs, speziell die US Air Force, die militärische Einsätze optimieren wollten. In den Folgejahren entwickelten Dantzig, John von Neumann, Oscar Morgenstern, Tjalling Koopmans und andere das Verfahren und die zugehörige Theorie weiter und stellten Zusammenhänge zur Spieltheorie her. Mit dem Aufkommen von Computern Mitte der 1950er Jahre konnte man auch größere Probleme lösen. Etwa ab 1950 entdeckte die Wirtschaft, insbesondere Ölraffinerien, die Anwendungsmöglichkeiten der linearen Optimierung.

Im Jahre 1979 veröffentlichte Leonid Khachiyan die Ellipsoidmethode, mit der lineare Programme erstmals – zumindest theoretisch – polynomial gelöst werden konnten. Mitte der 1980er Jahre begannen Narendra Karmarkar und andere mit der Entwicklung von Innere-Punkte-Verfahren zur Lösung linearer Programme. Sowohl das Simplex-Verfahren als auch Innere-Punkte-Verfahren sind nach wie vor Gegenstand aktueller Forschung. Die lineare Optimierung wird heute in sehr vielen Bereichen zur Lösung praktischer Probleme eingesetzt. Durch große Fortschritte in der Entwicklung der Algorithmen in den 1990er Jahren und die gleichzeitige starke Zunahme der Rechenleistung von Computern können inzwischen lineare Programme mit mehreren Millionen Variablen und Ungleichungen gelöst werden.

Ein lineares Programm (LP) in Standardform hat die Form

${\displaystyle \max\{c^{T}x=\sum _{i=1}^{n}c_{i}x_{i}\;|\;Ax\leq b,x\geq 0\}.}${\displaystyle \max\{c^{T}x=\sum _{i=1}^{n}c_{i}x_{i}\;|\;Ax\leq b,x\geq 0\}.}

Dabei ist ${\displaystyle A}${\displaystyle A} eine reelle ${\displaystyle m\times n}${\displaystyle m\times n}-Matrix und ${\displaystyle b=(\beta _{1}\ldots \beta _{m})^{T}}${\displaystyle b=(\beta _{1}\ldots \beta _{m})^{T}} und ${\displaystyle c=(c_{1}\ldots c_{n})^{T}}${\displaystyle c=(c_{1}\ldots c_{n})^{T}} sind reelle Vektoren. Die Bedingung ${\displaystyle Ax\leq b}${\displaystyle Ax\leq b} ist komponentenweise zu verstehen, also als

${\displaystyle a_{i}\cdot x=\sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}}${\displaystyle a_{i}\cdot x=\sum _{j=1}^{n}a_{ij}x_{j}\leq b_{i}}

für alle Zeilen ${\displaystyle i}${\displaystyle i} der Matrix ${\displaystyle A}${\displaystyle A}. Genauso bedeutet die Bedingung ${\displaystyle x\geq 0}${\displaystyle x\geq 0}, dass alle Einträge des Vektors ${\displaystyle x}${\displaystyle x} nichtnegativ sein müssen.

Außer der oben angegebenen Standardform eines LPs gibt es noch weitere äquivalente Formulierungen, die sich durch einfache Operationen in die Standardform bringen lassen:

• Minimierungsproblem statt Maximierungsproblem (Umformung: Negierung der Koeffizienten ${\displaystyle c_{i}}${\displaystyle c_{i}} in der Zielfunktion)
• Variablen ohne Nichtnegativitätsbedingung (Umformung: Ersetzung von ${\displaystyle x_{j}}${\displaystyle x_{j}} durch ${\displaystyle x_{j}'-x_{j}''}${\displaystyle x_{j}'-x_{j}''} mit ${\displaystyle x_{j}',x_{j}''\geq 0}${\displaystyle x_{j}',x_{j}''\geq 0})
• Gleichheitsbedingungen statt Ungleichheitsbedingungen (Umformung: Ersetzung von ${\displaystyle a_{i}\cdot x=\beta }${\displaystyle a_{i}\cdot x=\beta } durch ${\displaystyle a_{i}\cdot x\leq \beta }${\displaystyle a_{i}\cdot x\leq \beta } und ${\displaystyle a_{i}\cdot x\geq \beta }${\displaystyle a_{i}\cdot x\geq \beta })
• Größer-als- statt Kleiner-als-Bedingungen (Umformung: Multiplikation der entsprechenden Ungleichungen mit (-1)).

Die lineare Optimierung umfasst nur Probleme, bei denen die Variablen beliebige reelle Zahlen annehmen dürfen. Ein (gemischt-)ganzzahliges lineares Programm, bei dem einige Variablen nur ganzzahlige Werte annehmen dürfen, ist kein Spezialfall. Solche Optimierungsprobleme sind im allgemeinen NP-schwer, d. h. vermutlich nicht effizient lösbar. Dieser Fall wird von der ganzzahligen linearen Optimierung behandelt.

Ein lineares Programm (in Standardform) lässt sich geometrisch interpretieren: jede lineare Gleichung ${\displaystyle a_{i}\cdot x=b_{i}}${\displaystyle a_{i}\cdot x=b_{i}} beschreibt eine Hyperebene im ${\displaystyle n}${\displaystyle n}-dimensionalen Raum. Eine zugehörige lineare Ungleichung beschreibt dann einen Halbraum, d. h. 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.

Die Menge

${\displaystyle P:=\{x\;|\;Ax\leq b,\;x\geq 0\}}${\displaystyle P:=\{x\;|\;Ax\leq b,\;x\geq 0\}}

aller Punkte, die alle Ungleichungen des LPs erfüllen, bildet ein konvexes Polyeder im ${\displaystyle n}${\displaystyle n}-dimensionalen Raum. Dieses Polyeder ist genau der Schnitt der zugehörigen Halbräume. Ziel der Optimierung ist es also, unter allen Punkten des Polyeders einen zu finden, der die lineare Funktion ${\displaystyle c:,円x\to c^{T}x}${\displaystyle c:,円x\to c^{T}x} maximiert. Geometrisch entspricht dies der Verschiebung der Hyperebene ${\displaystyle \{x\;|\;c^{T}x=0\}}${\displaystyle \{x\;|\;c^{T}x=0\}} aus dem Ursprung heraus, 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.

Ein Punkt ${\displaystyle x}${\displaystyle x} der alle Ungleichungen erfüllt (also in P ist), wird als zulässige Lösung (oder kurz als zulässig) bezeichnet, die Menge P selber als zulässige Menge.

Ein kleines Beispiel aus der Produktionsplanung soll die obige Formulierung verdeutlichen.

Eine Firma stellt zwei verschiedene Produkte her, für deren Fertigung drei Maschinen A, B, C zur Verfügung stehen. Diese Maschinen haben eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden (A), 150 Stunden (B) bzw. 180 Stunden (C). Die Fixkosten betragen 36.000 Euro. Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man eine ME von Produkt 1, dann benötigt man dafür eine Stunde die Maschine A und eine Stunde die Maschine B. Eine Einheit von Produkt 2 belegt zwei Stunden lang Maschine A, eine Stunde Maschine B und drei Stunden Maschine C. Ziel ist es, den Gewinn der Firma zu maximieren, ohne dass die Maschinenkapazitäten überschritten werden.

Angenommen, der Betrieb fertigt pro Monat x₁ ME von Produkt 1 und x₂ ME von Produkt 2. Dann beträgt der Erfolg (Gewinn oder Verlust)

${\displaystyle G=300x_{1}+500x_{2}-36.000}${\displaystyle G=300x_{1}+500x_{2}-36.000}

Diesen Erfolg möchte die Firma maximieren. Da die Maschinenkapazitäten eingehalten werden müssen, ergeben sich die Nebenbedingungen:

${\displaystyle {\begin{matrix}x_{1}+&2x_{2}&\leq 170&{\mbox{(Maschine A)}}\\x_{1}+&x_{2}&\leq 150&{\mbox{(Maschine B)}}\\&3x_{2}&\leq 180&{\mbox{(Maschine C)}}\end{matrix}}}${\displaystyle {\begin{matrix}x_{1}+&2x_{2}&\leq 170&{\mbox{(Maschine A)}}\\x_{1}+&x_{2}&\leq 150&{\mbox{(Maschine B)}}\\&3x_{2}&\leq 180&{\mbox{(Maschine C)}}\end{matrix}}}

Da außerdem keine negativen Produktionsmengen möglich sind, muss ${\displaystyle x_{1},\;x_{2}\geq 0}${\displaystyle x_{1},\;x_{2}\geq 0} gelten (Nichtnegativitätsbedingung).

Im nebenstehenden Bild sind die Ungleichungen aus dem obigen Beispiel als grüne, blaue und violette Beschränkungen eingezeichnet. Zusammen definieren sie das (rosa umrandete) Polyeder der zulässigen Punkte. Die rotgestrichelten Linien stellen Iso-Gewinnfunktionen dar, d. h. alle Punkte auf einer solchen Linie haben denselben Zielfunktionswert. Da die Firma möglichst viel produzieren will, ist das Ziel der Optimierung, solch eine rot gestrichelte Linie soweit nach rechts oben zu schieben, so dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal. In diesem Fall ist die eindeutige optimale Ecke (130,20), und der optimale Zielfunktionswert beträgt 13.000 Euro.

Die lineare Optimierung hat viele Anwendungen in der Praxis, von denen hier einige beispielhaft vorgestellt werden sollen.

Ein klassisches Anwendungsgebiet der linearen Optimierung ist die Bestimmung eines Routings für Verkehrsanforderungen in Telekommunikations- oder Verkehrsnetzen, oft in Verbindung mit Kapazitätsplanung. Dabei müssen Verkehrsflüsse so durch ein Netz geroutet werden, dass alle Verkehrsanforderungen erfüllt werden, ohne die Kapazitätsbedingungen zu verletzen. Diese sogenannten Mehrgüterflüsse (engl. multicommodity flow) sind auch ein Beispiel für ein Problem, das mit linearer Optimierung gut lösbar ist, für das aber im allgemeinen Fall kein exakter Algorithmus bekannt ist, der nicht auf LP-Theorie basiert.

Ein Unternehmen kann eine Reihe von Produkten mit bekanntem Deckungsbeitrag herstellen. Die Herstellung einer Einheit jedes dieser Produkte benötigt eine bekannte Menge an beschränkten Ressourcen (Produktionskapazität, Rohmaterialien, etc). Die Aufgabe ist die Erstellung eines Produktionsplans, d. h. die Festlegung, wieviel von jedem Produkt produziert werden soll, so dass der Profit der Firma maximiert wird, ohne die Ressourcenbeschränkungen zu verletzen. Ein Beispiel dafür wird weiter oben ausführlich erklärt.

Eine ähnliche Anwendung sind Mischungsprobleme, bei denen es darum geht, Zutaten zu einem Endprodukt zusammenzustellen, wobei die Menge der jeweiligen Zutaten innerhalb eines bestimmten Bereichs variiert werden kann. Ein Beispiel hierfür ist das von George Dantzig 1947 untersuchte Diät-Problem: Gegeben sind eine Reihe von Rohmaterialien (z. B. Hafer, Schweinefleisch, Sonnenblumenöl, etc) zusammen mit ihrem Gehalt an bestimmten Nährwerten (z. B. Eiweiß, Fett, Vitamin A, etc) und ihrem Preis pro Kilogramm. Die Aufgabe besteht darin, eines oder mehrere Endprodukte mit minimalen Kosten aus den Rohmaterialien zu mischen, unter der Nebenbedingung, dass bestimmte Mindest- und Höchstgrenzen für die einzelnen Nährwerte eingehalten werden.

Innerhalb der mathematischen Spieltheorie kann die lineare Optimierung dazu verwendet werden, optimale Strategien in Zwei-Personen-Nullsummenspielen zu berechnen. Dabei wird für jeden Spieler eine Wahrscheinlichkeitsverteilung berechnet, bei der es sich um ein zufälliges Mischungsverhältnis seiner Strategien handelt. „Würfelt" ein Spieler seine Strategie gemäß dieser Wahrscheinlichkeitsverteilung zufällig aus, ist ihm die bestmögliche Gewinnerwartung sicher, die er haben kann, wenn er seine Strategie unabhängig von der seines Gegners wählt.

Viele Anwendungsprobleme lassen sich mit kontinuierlichen Variablen nicht sinnvoll modellieren, sondern erfordern die Ganzzahligkeit einiger Variablen. Beispielsweise können keine 3,7 Flugzeuge gekauft werden, sondern nur eine ganze Anzahl. Bei der Verwendung von Branch and Bound oder Schnittebenenverfahren zur Lösung eines solchen ganzzahligen linearen Optimierungsproblems müssen als Unterproblem sehr viele ähnliche lineare Programme hintereinander gelöst werden. Auch zur Lösung nichtlinearer Optimierungsprobleme gibt es Algorithmen, in denen lineare Programme als Unterproblem gelöst werden müssen (z. B. Sequential Linear Programming).

Ein lineares Programm hat nicht immer eine Optimallösung. Drei Fälle sind zu unterscheiden:

1. Das LP ist unzulässig, weil sich Ungleichungen widersprechen (z. B. ${\displaystyle x\leq 1}${\displaystyle x\leq 1} und ${\displaystyle x\geq 2}${\displaystyle x\geq 2}). In diesem Fall gibt es keine Lösung, die alle Ungleichungen erfüllt, d. h. das zugehörige Polyeder ist die leere Menge.
2. Das LP ist unbeschränkt, d. h. es gibt zulässige Lösungen mit beliebig hohen Zielfunktionswerten.
3. Das LP besitzt mindestens eine Optimallösung. Dies ist unter anderem dann gegeben, wenn das zugehörige Polyeder beschränkt, also ein (nichtleeres) Polytop ist.

Die Menge der Optimallösungen bildet eine Seitenfläche (Ecke, Kante,...) des Polyeders, so dass es entweder keine, genau eine oder unendlich viele Optimallösungen gibt. Wenn das LP lösbar und beschränkt ist, gibt es auch immer eine optimale Ecke. Diese Eigenschaft macht sich u. a. das Simplex-Verfahren zunutze.

siehe Hauptartikel: Simplex-Verfahren

Das Simplex-Verfahren, im Jahre 1947 von George Dantzig entwickelt, ist der wichtigste Algorithmus zur Lösung linearer Programme in der Praxis. Die Grundidee besteht darin, von einer Ecke des Polyeders zu einer benachbarten Ecke mit besserem Zielfunktionswert zu laufen, bis dies nicht mehr möglich ist. Da es sich bei der linearen Optimierung um ein konvexes Optimierungsproblem handelt, ist die damit erreichte lokal optimale Ecke auch global optimal. Unter der Voraussetzung, dass die Matrix ${\displaystyle A}${\displaystyle A} dünnbesetzt ist (d. h. nur wenige Koeffizienten ungleich Null enthält), was in der Praxis fast immer der Fall ist, können mit dem Simplex-Verfahren heute LPs mit bis zu mehreren Millionen Variablen und Ungleichungen gelöst werden.

Aus komplexitätstheoretischer Sicht benötigt der Simplex-Algorithmus im schlechtesten Fall exponentielle Laufzeit. Für jede Variante des Algorithmus wurde bisher ein Beispiel gefunden, bei dem der Algorithmus alle Ecken des Polyeders abläuft. Aus praktischer Sicht sind solche Fälle allerdings sehr selten. Allerdings kann es bei sogenannten degenerierten linearen Programmen passieren, dass der Algorithmus immer wieder dieselbe Ecke betrachtet, anstatt zur nächsten Ecke zu wechseln. Dieses Problem tritt bei praktischen Planungsproblemen häufig auf und kann dazu führen, dass der Algorithmus nicht terminiert oder der Zielfunktionswert sich über viele Iterationen hinweg nicht verbessert. Gute Simplex-Implementierungen entdecken solche Fälle und behandeln sie beispielsweise durch eine leichte Perturbation (absichtliche numerische Störung) des Problems, die später wieder rückgängig gemacht wird.

Ein großer Vorteil des Simplex-Verfahrens besteht darin, dass es nach dem Hinzufügen einer Ungleichung oder Variable im LP oder nach einer leichten Änderung der Koeffizienten einen „Warmstart" von einer vorher bereits erreichten Ecke aus durchführen kann, während andere Algorithmen von vorne starten müssen. Dies ist insbesondere im Zusammenhang mit Schnittebenenverfahren und Branch and Bound zur Lösung ganzzahliger lineare Programme von großer Bedeutung, wo viele sehr ähnliche LPs in Serie gelöst werden müssen.

siehe Hauptartikel: Innere-Punkte-Verfahren

Innere-Punkte-Verfahren, auch Barrier-Verfahren genannt, nähern sich einer optimalen Ecke durch das Innere des Polyeders. Der erste solche Algorithmus wurde 1984 von Narendra Karmarkar beschrieben. Seine Bedeutung lag vor allem darin, dass er der erste polynomiale Algorithmus zum Lösen linearer Programme war, der das Potential hatte, auch praktisch einsetzbar zu sein. Die entscheidenden Durchbrüche, die Innere-Punkte-Verfahren konkurrenzfähig zum Simplex-Algorithmus machten, wurden aber erst in den 1990er Jahren erzielt. Ein Vorteil dieser Verfahren ist, dass sie, im Gegensatz zum Simplex-Verfahren, in leichter Abwandlung auch zum Lösen quadratischer oder bestimmter nichtlinearer Programme eingesetzt werden können. Des weiteren sind sie für große, dünnbesetzte Probleme häufig dem Simplex-Verfahren überlegen. Ein Nachteil ist, dass sie sich nach dem Hinzufügen einer Nebenbedingung oder Variablen im LP bei weitem nicht so effizient „warmstarten" lassen wie das Simplex-Verfahren.

siehe Hauptartikel: Ellipsoidmethode

Die Ellipsoidmethode zur Lösung linearer Programme wurde 1979 von Leonid Khachiyan veröffentlicht und war das erste polynomiale Verfahren für dieses Problem. Für praktische Zwecke ist sie allerdings nicht geeignet. Die Ellipsoidmethode dient dazu, einen beliebigen Punkt in einem volldimensionalen Polyeder zu finden oder festzustellen, dass das Polyeder leer ist. Man kann zeigen, dass sich auf diese Art (theoretisch) ein LP lösen lässt.

Die Grundidee des Verfahrens besteht darin, ein Ellipsoid zu definieren, das alle Ecken des Polyeders enthält. Anschließend wird festgestellt, ob der Mittelpunkt dieses Ellipsoids im Polyeder enthalten ist. Falls ja, hat man ein Punkt im Polyeder gefunden. Andernfalls kann man das Halbellipsoid bestimmen, in dem das Polyeder enthalten sein muss, und ein neues, kleineres Ellipsoid um das Polyeder legen. Nach einer Anzahl von Schritten, die polynomial von der Kodierungslänge des LPs abhängt, hat man entweder einen Punkt im Polyeder gefunden oder weiß, dass das Polyeder leer ist, weil es sonst größer sein müßte als das aktuelle Ellipsoid.

Für einige Klassen von linearen Programmen gibt es spezielle Algorithmen, die theoretisch oder praktisch schneller laufen als z. B. der Simplexalgorithmus. Ein Beispiel hierfür ist die Ungarische Methode, die auf Zuordnungsprobleme angewandt werden kann. Lineare Programme mit zwei Variablen lassen sich auch näherungsweise zeichnerisch lösen (siehe oben). Diese Methode hat aber hauptsächlich didaktischen Wert, da in der Praxis auftretende LPs leicht mehrere Hunderttausende Variablen besitzen können. Es ist bis heute unbekannt, ob es einen streng polynomialen Algorithmus zum Lösen allgemeiner linearer Programme gibt, d. h. einen Algorithmus, dessen Laufzeit nicht von der Größe der auftretenden Zahlen abhängt.

Jedem linearen Programm (dem primalen Problem) ist ein anderes lineares Programm zugeordnet: das duale Problem. Zwischen dem primalen und seinem dualen Problem gibt es enge Zusammenhänge, die sowohl beim Beweis von Sätzen der linearen Optimierung als auch bei der praktischen Lösung linearer oder ganzzahliger Programme ausgenutzt werden können. Einige dieser Zusammenhänge sind Spezialfälle der entsprechenden Sätze aus der konvexen Optimierung.

Einem primalen LP in Standardform

${\displaystyle \max \;\{c^{T}x,円:,円Ax\leq b,\;x\geq 0\}}${\displaystyle \max \;\{c^{T}x,円:,円Ax\leq b,\;x\geq 0\}}

ist das duale LP

${\displaystyle \min \;\{b^{T}y,円:,円A^{T}y\geq c,\;y\geq 0\}}${\displaystyle \min \;\{b^{T}y,円:,円A^{T}y\geq c,\;y\geq 0\}}

zugeordnet, bei dem die Anzahl der Zeilen und Spalten gegenüber dem Ausgangsproblem vertauscht sind. Jeder Ungleichung des primalen Problems ist dabei eine sogenannte Dualvariable ${\displaystyle y_{i}}${\displaystyle y_{i}} zugeordnet, und jeder Variable ${\displaystyle x_{j}}${\displaystyle x_{j}} des primalen Problems entspricht eine duale Ungleichung. Das duale Problem des dualen Problems ist wieder das Ursprungsproblem.

Die Zusammenhänge zwischen dem primalen und dualen Problem werden durch die sogenannten Dualitätssätze beschrieben, die alle auf Farkas' Lemma basieren. Nach dem schwachen Dualitätssatz der linearen Optimierung gilt für alle zulässigen Lösungen ${\displaystyle x}${\displaystyle x} und ${\displaystyle y}${\displaystyle y} des primalen bzw. dualen Problems

${\displaystyle c^{T}x\leq b^{T}y}${\displaystyle c^{T}x\leq b^{T}y},

d. h. der Wert jede dualen Lösung ist mindestens so hoch wie der Wert jeder primalen Lösung.

Der starke Dualitätssatz verschärft diese Aussage: wenn eins der beiden LPs eine beschränkte Optimallösung besitzt, dann auch das andere, und die optimalen Zielfunktionswerte sind in diesem Fall gleich. Für alle optimalen Lösungen ${\displaystyle x^{*},y^{*}}${\displaystyle x^{*},y^{*}} des primalen und dualen Problems gilt also ${\displaystyle c^{T}x^{*}=b^{T}y^{*}}${\displaystyle c^{T}x^{*}=b^{T}y^{*}}.

Man kann zeigen, dass folgende Zusammenhänge gelten:

• Das duale Problem hat eine (beschränkte) Lösung genau dann, wenn das primale Problem eine (beschränkte) Lösung hat.
• Wenn das primale Problem keine zulässige Lösung hat, ist das duale Problem unbeschränkt oder hat auch keine zulässige Lösung.
• Wenn das primale Problem unbeschränkt ist, hat das duale Problem keine zulässige Lösung.

Diese und weitere Sätze bilden die Grundlage für alle Verfahren, die mit primalen und dualen Schranken für den Wert einer Optimallösung arbeiten, wie beispielsweise Branch and Bound und Schnittebenenverfahren.

• George B. Dantzig: Lineare Programmierung und Erweiterungen. Springer-Verlag 1966 (Originalausgabe: Linear Programming and Extensions, Princeton University Press, ISBN 0-691-05913-6.)
• Vašek Chvátal: Linear Programming. W. H. Freeman and Company, New York, 1983, ISBN 0-716-71587-2.
• Alexander Schrijver: Theory of Linear and Integer Programming. John Wiley and Sons. 1998, ISBN 0-471-98232-6.

• Linear Programming FAQ (engl.)
• Vergleich nichtkommerzieller LP-Codes (engl.) von Hans Mittelmann, Arizona State University, mit Links zu den Codes
• Das Diät-Problem (engl.)

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Lineare_Optimierung&oldid=16223362"

Kategorie:

• Optimierung