Mathematische Formulierung

Bei einem linearen Programm (LP) sind eine Matrix ${\displaystyle A\in \mathbb {R} ^{m,n}}$ und zwei Vektoren ${\displaystyle b\in \mathbb {R} ^{m,1}}$ und ${\displaystyle c\in \mathbb {R} ^{1,n}}$ gegeben. Eine zulässige Lösung ist ein Vektor ${\displaystyle x\in \mathbb {R} ^{n}}$ mit nichtnegativen Einträgen, der die linearen Bedingungen

${\displaystyle {\begin{matrix}a_{11}x_{1}&+\ldots &+a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}&+\ldots &+a_{2n}x_{n}&\leq b_{2}\\\vdots &\vdots &\vdots &\vdots \\a_{m1}x_{1}&+\ldots &+a_{mn}x_{n}&\leq b_{m}\end{matrix}}}$

erfüllt. Ziel ist es, unter allen zulässigen Vektoren ${\displaystyle x}$ einen zu finden, der das Standardskalarprodukt

${\displaystyle cx=c_{1}x_{1}+\ldots +c_{n}x_{n}}$

maximiert. Dieses Optimierungsproblem in der sogenannten Standardform (auch als Ungleichungsform bezeichnet) wird oft abkürzend als

${\displaystyle \max\{cx\;|\;Ax\leq b,x\geq 0\}}$

geschrieben, wobei die Bedingungen ${\displaystyle Ax\leq b}$ und ${\displaystyle x\geq 0}$ komponentenweise zu verstehen sind.

Darüber hinaus gibt es noch weitere äquivalente Formulierungen, die sich durch einfache Operationen in diese Standardform bringen lassen:

• Minimierungsproblem statt Maximierungsproblem: Multiplikation des Zielfunktionsvektors ${\displaystyle c}$ mit ${\displaystyle -1}$
• Größer-gleich- statt Kleiner-gleich-Bedingungen: Multiplikation der entsprechenden Ungleichungen mit ${\displaystyle -1}$
• Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von ${\displaystyle a_{i}x=b_{i}}$ durch ${\displaystyle a_{i}x\leq b_{i}}$ und ${\displaystyle -a_{i}x\leq -b_{i}}$
• Variablen ohne Nichtnegativitätsbedingung: Ersetzung von ${\displaystyle x}$ durch ${\displaystyle x'-x''}$ mit ${\displaystyle x',x''\geq 0}$

Die lineare Optimierung behandelt 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, sondern – im Gegenteil – eine Verallgemeinerung. Solche Optimierungsprobleme sind im Allgemeinen NP-äquivalent, d. h. vermutlich nicht effizient lösbar. Dieser Fall wird von der ganzzahligen linearen Optimierung behandelt.

Geometrische Interpretation

Ein lineares Programm lässt sich geometrisch interpretieren. Wenn ${\displaystyle a_{i}x\leq b_{i}}$ die i. Zeile eines linearen Programms in Standardform ist, dann beschreibt die Menge ${\displaystyle \{x\;|\;a_{i}x=b_{i}\}}$ aller Punkte ${\displaystyle x}$, die die zugehörige lineare Gleichung ${\displaystyle a_{i}x=b_{i}}$ erfüllen, eine Hyperebene im ${\displaystyle n}$-dimensionalen Raum. Die Menge der Punkte, die die lineare Ungleichung ${\displaystyle a_{i}x\leq b_{i}}$ erfüllen, besteht aus allen Punkten auf der einen Seite der Hyperebene (inklusive der Hyperebene selbst), bildet also einen Halbraum. Jede Zeile ${\displaystyle a_{i}x\leq b_{i}}$ teilt daher den ${\displaystyle n}$-dimensionalen Raum in zwei Hälften, wobei die Punkte in der einen Hälfte zulässig sind und in der anderen nicht. Die Menge

${\displaystyle P:=\{x\;|\;Ax\leq b,\;x\geq 0\}=\{x\;|\;a_{i}x\leq b_{i},\;i=1,\ldots ,m,\;x\geq 0\}}$

der Punkte, die alle Ungleichungen des LPs erfüllen, ist genau der Schnitt dieser Halbräume, also die Menge aller Punkte, die für jede Ungleichung in der jeweiligen zulässigen Hälfte des Raumes liegen. Diese Lösungsmenge ${\displaystyle P}$ des linearen Programms bildet ein konvexes Polyeder, also ein ${\displaystyle n}$-dimensionales Vieleck, in dem die Verbindungslinie zwischen zwei beliebigen Punkten von ${\displaystyle P}$ vollständig in ${\displaystyle P}$ enthalten ist. Ziel der Optimierung ist es, unter allen Punkten des Polyeders einen zu finden, der die lineare Funktion ${\displaystyle c\colon \,x\to c^{T}x}$ maximiert. Geometrisch entspricht dies der Verschiebung der Hyperebene ${\displaystyle \{x\;|\;c^{T}x=0\}}$ in Richtung des Vektors ${\displaystyle c}$, 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.

Im nebenstehenden Bild ist diese Anordnung für den Fall von nur zwei Variablen dargestellt. Eine Hyperebene im zweidimensionalen Raum ist eine Gerade, im Bild grün dargestellt. Jede dieser Geraden teilt den Raum in eine zulässige und eine unzulässige Hälfte. Die Menge der Punkte, die auf der zulässigen Seite jeder Geraden liegen, bilden das blau dargestellte Polyeder (Vieleck). Die rote Gerade stellt die Zielfunktion dar. Ziel ist es, sie so weit wie möglich in Richtung des roten Vektors ${\displaystyle c}$ zu verschieben, ohne das Polyeder zu verlassen. Im nebenstehenden Bild ist der rote Berührungspunkt der Zielfunktionsgeraden mit dem Polyeder die einzige Optimallösung.

Mathematische Modellierung

Angenommen, der Betrieb fertigt pro Monat ${\displaystyle x_{1}}$ ME von Produkt 1 und ${\displaystyle x_{2}}$ ME von Produkt 2. Dann beträgt der Gesamtdeckungsbeitrag

${\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}.}$

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

${\displaystyle {\begin{alignedat}{3}x_{1}&+&2x_{2}&\leq 170&&{\text{ (Maschine A, rechts in schwarz eingezeichnet)}}\\x_{1}&+&x_{2}&\leq 150&&{\text{ (Maschine B, rechts in tuerkis eingezeichnet)}}\\&&3x_{2}&\leq 180&&{\text{ (Maschine C, rechts in violett eingezeichnet)}}\end{alignedat}}}$

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

Geometrische Interpretation als Polyeder

Im nebenstehenden Bild sind die Ungleichungen aus dem obigen Beispiel als türkise, schwarze und violette Beschränkungen eingezeichnet. Zusammen definieren sie das (blau 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 das Unternehmen möglichst viel Gewinn erzielen will, ist das Ziel der Optimierung, solch eine rot gestrichelte Linie so weit nach rechts oben zu schieben, dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal. In diesem Fall ist der Punkt (130,20) die eindeutige optimale Ecke, und der optimale Zielfunktionswert beträgt 49.000 Euro.

Im Allgemeinen ist die Optimallösung eines linearen Optimierungsproblems allerdings weder eindeutig noch ganzzahlig. Wenn beispielsweise beide Produkte den gleichen Deckungsbeitrag hätten, wären die roten Iso-Gewinnfunktionen parallel zur Ungleichung ${\displaystyle x_{1}+x_{2}\leq 150}$. In diesem Fall wäre jeder Punkt auf der Strecke zwischen (130,20) und (150,0) optimal, es gäbe also unendlich viele Optimallösungen.

Produktionsplanung

Wie in dem obigen Beispiel kann ein Unternehmen 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, Arbeitszeit etc.). Die Aufgabe ist die Erstellung eines Produktionsprogramms, d. h. die Festlegung, wie viel von jedem Produkt produziert werden soll, so dass der Gewinn des Unternehmens maximiert wird, ohne die Ressourcenbeschränkungen zu verletzen. Ein weiteres Beispiel sind Zuschnittsprobleme.

Mischungsprobleme

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 1947 von George Dantzig 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. Auch bei Schmelzvorgängen treten solche Mischungsprobleme auf, wie z. B. in der Stahlherstellung.

Routing in Telekommunikations- oder Verkehrsnetzen

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 (englisch multicommodity flow) sind 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.

Spieltheorie

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.

Nichtlineare und ganzzahlige Optimierung

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, und ein Bus kann nur ganz oder gar nicht fahren, aber nicht zu zwei Dritteln. Bei der Verwendung von Branch-and-Cut zur Lösung eines solchen ganzzahligen linearen Optimierungsproblems müssen sehr viele ähnliche lineare Programme hintereinander als Unterproblem gelöst werden. Eine optimale ganzzahlige Lösung eines linearen Programms zu finden ist NP-vollständig, aber parametrisierbar in der Anzahl der Variablen. Es ist sogar NP-vollständig, irgendeine ganzzahlige Lösung eines linearen Programms zu finden. Eine Ausnahme ist hier, wenn die Restriktionsmenge durch eine total unimodulare Matrix gegeben ist, dann sind alle Ecken des Polyeders ganzzahlig. 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).

Simplex-Verfahren

Das Simplex-Verfahren ist ein Basisaustauschverfahren, das im Jahre 1947 von George Dantzig entwickelt und seitdem wesentlich verbessert wurde; es 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. Das Verfahren ist im nebenstehenden Bild illustriert: Ziel ist es, einen möglichst weit oben liegenden Punkt des Polyeders zu finden. In roter Farbe ist ein möglicher Pfad des Simplex-Verfahrens entlang der Ecken des Polyeders dargestellt, wobei sich der Zielfunktionswert mit jedem Schritt verbessert.

Aus komplexitätstheoretischer Sicht benötigt der Simplex-Algorithmus im schlechtesten Fall exponentielle Laufzeit. Für jede Variante des Algorithmus konnte bisher ein Beispiel konstruiert werden, bei dem der Algorithmus alle Ecken des Polyeders abläuft, meist basierend auf dem Klee-Minty-Würfel. Aus praktischer Sicht sind solche Fälle allerdings sehr selten. Bei sogenannten entarteten linearen Programmen, bei denen eine Ecke durch mehr Ungleichungen definiert wird als unbedingt nötig (beispielsweise durch drei Ungleichungen im zweidimensionalen Raum), kann es allerdings passieren, dass der Algorithmus, wie in diesem Beispiel, 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.

Unter der Voraussetzung, dass die Matrix ${\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 sehr große LPs in annehmbarer Zeit optimal gelöst werden. 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, so dass nur wenige Iterationen zum erneuten Finden einer Optimallösung notwendig sind. Dies ist insbesondere im Zusammenhang mit Schnittebenenverfahren oder Branch-and-Cut zur Lösung ganzzahliger linearer Programme von großer Bedeutung, wo sehr viele ähnliche LPs in Serie gelöst werden müssen.

Innere-Punkte-Verfahren

Innere-Punkte-Verfahren, auch Barrier-Verfahren genannt, nähern sich einer optimalen Ecke durch das Innere des Polyeders (siehe Bild). 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.

Ellipsoidmethode

Die Ellipsoidmethode wurde ursprünglich in den Jahren 1976 und 1977 von David Yudin und Arkadi Nemirovski und unabhängig davon von Naum Schor zur Lösung konvexer Optimierungsprobleme entwickelt. Im Jahre 1979 modifizierte der sowjetische Mathematiker Leonid Khachiyan das Verfahren und entwickelte damit den ersten polynomialen Algorithmus zur Lösung linearer Programme. Für praktische Zwecke ist er allerdings nicht geeignet. Die Ellipsoidmethode dient dazu, einen beliebigen Punkt in einem volldimensionalen Polyeder zu finden oder festzustellen, dass das Polyeder leer ist. Da man zeigen kann, dass die Lösung eines LPs äquivalent ist zum Finden eines zulässigen Punktes in einem geeignet definierten Hilfspolyeder, lässt sich mit Hilfe der Ellipsoidmethode (theoretisch) auch ein LP lösen.

Die Grundidee des Verfahrens besteht darin, ein Ellipsoid (im Bild rot) zu definieren, das alle Ecken des Polyeders (blau) enthält. Anschließend wird festgestellt, ob der Mittelpunkt dieses Ellipsoids im Polyeder enthalten ist. Falls ja, hat man einen Punkt im Polyeder gefunden und kann aufhören. Andernfalls kann man das Halbellipsoid bestimmen, in dem das Polyeder enthalten sein muss, und ein neues, kleineres Ellipsoid um das Polyeder legen (im Bild grün). 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üsste als das aktuelle Ellipsoid.

Weitere Methoden

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 näherungsweise zeichnerisch lösen. Diese Methode hat aber hauptsächlich didaktischen Wert, da in der Praxis auftretende LPs leicht mehrere Hunderttausende Variablen besitzen können.

Obere Schranken

Um zu verifizieren, dass eine gültige Lösung ${\displaystyle x^{*}}$ optimal für ein lineares Programm ist, versucht man, den Zielfunktionswert des Programms nach oben abzuschätzen. Für das obige Beispiel gilt etwa

${\displaystyle x_{1}+x_{2}\leq 150\;\Rightarrow \;500x_{1}+500x_{2}\leq 500\cdot 150=75000}$

Da ${\displaystyle x_{1}\geq 0}$ und ${\displaystyle x_{2}\geq 0}$ folgt daraus, dass

${\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 500x_{1}+500x_{2}\leq 75000}$

Die Optimallösung kann somit keinen Zielfunktionswert größer als ${\displaystyle 75000}$ haben. Eine bessere Abschätzung erhält man, indem man ${\displaystyle 300}$ Mal die zweite und ${\displaystyle 100}$ Mal die dritte Ungleichung addiert:

${\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 300\cdot (x_{1}+x_{2})+100\cdot (3x_{2})=300x_{1}+600x_{2}\leq 63000}$

Dieses Verfahren lässt sich leicht verallgemeinern: Wählt man für ein gegebenes LP in Standardform Multiplikatoren ${\displaystyle y\in \mathbb {R} _{+}^{m}}$, so ist jeder Vektor ${\displaystyle y^{T}A}$ eine obere Schranke, sofern ${\displaystyle y^{T}A\geq c^{T}}$. Dies entspricht einer konischen Kombination der Spalten von ${\displaystyle A}$. Die Bedingung ${\displaystyle y^{T}A\geq c^{T}}$ stellt sicher, dass sich die Koeffizienten von ${\displaystyle c^{T}}$ für ${\displaystyle x\geq 0}$ gegen ${\displaystyle y^{T}A}$ abschätzen lassen. Der Zielfunktionswert der durch ${\displaystyle y}$ gegebenen obere Schranke ist somit ${\displaystyle y^{T}b}$. Um die beste obere Schranke zu finden, kann man nun ein weiteres LP aufstellen:

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

Dieses LP nennt man das duale Problem zu dem primalen Problem

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

Die Einträge des Vektors ${\displaystyle y}$ werden als Multiplikatoren oder Dualvariablen bezeichnet. Die Dualität Linearer Programme ist ein Spezialfall der Lagrange-Dualität.

Falls ein lineares Programm aus einem kombinatorischen Optimierungsproblem entsteht, so hat das duale Programm oft eine anschauliche Interpretation; die nachfolgenden Sätze können dann auch benutzt werden, um Resultate wie das Max-Flow-Min-Cut-Theorem herzuleiten.

Dualisierung beliebiger linearer Programme

Für lineare Programme, welche nicht in Standardform vorliegen, gelten die folgenden Vorschriften zur Dualisierung:

primales LP	duales LP
${\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}$	${\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T},\;y\geq 0\}}$
${\displaystyle \max \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}$	${\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T}\}}$
${\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b\}}$	${\displaystyle \min \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}$

Für Minimierungsprobleme gilt analog:

primales LP	duales LP
${\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b,\;x\geq 0\}}$	${\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T},\;y\geq 0\}}$
${\displaystyle \min \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}$	${\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T}\}}$
${\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b\}}$	${\displaystyle \max \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}$

Im Allgemeinen gilt:

Dabei ist zu beachten, dass bei Maximierungsproblemen die Ungleichungen stets in der Form ${\displaystyle Ax\leq b}$ und bei Minimierungsproblemen in der Form ${\displaystyle Ax\geq b}$ aufgeschrieben werden.

Eigenschaften des dualen Programms

Das primale und duale LP bilden ein duales Paar, es gilt also, dass aus der Dualisierung des dualen LP wieder das primale LP entsteht.

Des Weiteren gilt für beliebige zulässige primale bzw. duale Lösungen ${\displaystyle x,y}$:

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

Dabei gilt die erste Ungleichung, da ${\displaystyle x\geq 0}$ und ${\displaystyle y^{T}A\geq c^{T}}$ und die zweite, weil ${\displaystyle Ax\leq b}$ und ${\displaystyle y\geq 0}$. Dieses Resultat ist als der schwache Dualitätssatz bekannt. Er entspricht der schwachen Dualität in der Lagrange-Dualität.

Der starke Dualitätssatz

Der starke Dualitätssatz verschärft die obige Aussage: Wenn eines der beiden LPs eine beschränkte Optimallösung besitzt, dann auch das andere, und die optimalen Zielfunktionswerte sind in diesem Fall gleich. Für jede optimale Lösung ${\displaystyle x^{*}}$ des primalen und jede optimale Lösung ${\displaystyle y^{*}}$ des dualen Problems gilt also

${\displaystyle c^{T}\;x^{*}=(y^{*})^{T}b}$.

Dies entspricht der starken Dualität in der Lagrange-Dualität. Man kann zeigen, dass folgende Zusammenhänge gelten:

• Das duale Problem hat genau dann eine beschränkte Optimallösung, wenn das primale Problem eine beschränkte Optimallösung besitzt.
• 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-Cut und Schnittebenenverfahren.

Der Satz vom komplementären Schlupf

Zusätzlich zu den obigen Zusammenhängen über die Lösbarkeit des primalen bzw. dualen Problems gilt die folgende Aussage:

Falls sowohl das primale als auch das duale Problem zulässige Lösungen haben, so existiert ein Paar ${\displaystyle x^{*},y^{*}}$ von Lösungen mit der Eigenschaft, dass

${\displaystyle y_{i}^{*}\cdot (b_{i}-(Ax^{*})_{i})=0\;\;\;\forall i=1,\ldots ,m}$

Dies bedeutet, dass ${\displaystyle y_{i}^{*}>0\;\Rightarrow \;(Ax^{*})_{i}=b_{i}}$ und umgekehrt ${\displaystyle (Ax^{*})_{i}<b_{i}\;\Rightarrow \;y_{i}^{*}=0}$. Hierbei bezeichnet ${\displaystyle (Ax^{*})_{i}}$ die ${\displaystyle i}$-te Komponente des Vektors ${\displaystyle Ax^{*}}$.

Diese Lösungen sind auch optimal, da in diesem Fall die obigen Ungleichungen mit Gleichheit erfüllt sind:

${\displaystyle c^{T}x^{*}=(y^{*})^{T}Ax^{*}=(y^{*})^{T}b}$.

Diese zusätzliche Eigenschaft wird zum Beispiel bei primal-dualen Algorithmen ausgenutzt, um die Optimalität einer Lösung zu verifizieren.

Äquivalenz von Optimierungs- und Zulässigkeitsproblemen

Der starke Dualitätssatz ermöglicht es ebenfalls, Optimierungsprobleme auf Zulässigkeitsprobleme zu reduzieren: Anstatt das Problem ${\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}$ zu lösen, kann man ebenso gut ein Paar von Lösungen finden, die den folgenden Bedingungen gehorchen:

${\displaystyle {\begin{aligned}Ax&\leq b,\;x\geq 0\\y^{T}A&\geq c^{T},\;y\geq 0\\c^{T}x&\geq y^{T}b\\\end{aligned}}}$

Dabei stellen die ersten beiden Bedingungen sicher, dass ${\displaystyle x}$ eine zulässige Lösung des Problems ist, während die nächsten Bedingungen dafür sorgen, dass ${\displaystyle y}$ gültig für das duale Programm ist. Die letzte Ungleichung wird nur von solchen Lösungspaaren ${\displaystyle x,y}$ erfüllt, deren Zielfunktionswerte übereinstimmen. Dies ist genau dann der Fall, wenn es sich bei ${\displaystyle x}$ und ${\displaystyle y}$ um die Optimallösungen der beiden Probleme handelt. Das obige Optimierungsproblem hat damit eine Optimallösung genau dann wenn der obige Polyeder nicht leer ist. Offensichtlich kann man die Zulässigkeit eines Problems auch durch Lösung eines Optimierungsproblems entscheiden, man wählt dazu beispielsweise den Nullvektor als Zielfunktion. Damit sind lineare Optimierungsprobleme und Zulässigkeitsprobleme von Polyedern äquivalent bezüglich ihrer Zeitkomplexität.