Duales lineares Programm - Dual linear program

Das Dual eines gegebenen linearen Programms (LP) ist eine andere LP, die auf folgende schematische Weise von der ursprünglichen (der ursprünglichen ) LP abgeleitet wird :

Jede Variable in der ursprünglichen LP wird zu einer Einschränkung in der doppelten LP.
Jede Einschränkung in der ursprünglichen LP wird zu einer Variablen in der doppelten LP;
Die objektive Richtung ist umgekehrt - das Maximum im Primären wird im Dualen zum Minimum und umgekehrt.

Der schwache Dualitätssatz besagt, dass der Zielwert der Doppel-LP bei jeder realisierbaren Lösung immer an das Ziel der Ur-LP bei jeder realisierbaren Lösung gebunden ist (obere oder untere Grenze, je nachdem, ob es sich um ein Maximierungs- oder Minimierungsproblem handelt). Tatsächlich gilt diese Begrenzungseigenschaft für die optimalen Werte der dualen und primären LPs.

Der Satz der starken Dualität besagt, dass, wenn das Ursprüngliche eine optimale Lösung hat, das Duale auch eine optimale Lösung hat und die beiden Optima gleich sind .

Diese Theoreme gehören zu einer größeren Klasse von Dualitätssätzen in der Optimierung . Der starke Dualitätssatz ist einer der Fälle, in denen die Dualitätslücke (die Lücke zwischen dem Optimum des Primären und dem Optimum des Dualen) 0 ist.

Aufbau der Doppel-LP

Bei einer ursprünglichen LP kann der folgende Algorithmus verwendet werden, um ihre doppelte LP zu konstruieren. Die ursprüngliche LP ist definiert durch:

Eine Menge von n Variablen : . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$
Für jede Variable eine Vorzeichenbeschränkung - sie sollte entweder nicht negativ ( ) oder nicht positiv ( ) oder nicht eingeschränkt ( ) sein. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i} \ geq 0}$ ${\ displaystyle x_ {i} \ leq 0}$ ${\ displaystyle x_ {i} \ in \ mathbb {R}}$
Eine objektive Funktion: ${\ displaystyle {\ text {maxim}} ~~~ c_ {1} x_ {1} + \ cdots + c_ {n} x_ {n}}$
Eine Liste von m Einschränkungen. Jede Einschränkung j ist: wobei das Symbol vor dem entweder oder oder sein kann . ${\ displaystyle a_ {j1} x_ {1} + \ cdots + a_ {jn} x_ {n} \ lesseqqgtr b_ {j}}$ ${\ displaystyle b_ {j}}$ ${\ displaystyle \ geq}$ ${\ displaystyle \ leq}$ ${\ displaystyle =}$

Die Doppel-LP ist wie folgt aufgebaut.

Jede ursprüngliche Einschränkung wird zu einer doppelten Variablen. Es gibt also m Variablen : . ${\ displaystyle y_ {1}, \ ldots, y_ {m}}$
Die Vorzeichenbeschränkung jeder dualen Variablen ist dem Vorzeichen ihrer ursprünglichen Beschränkung "entgegengesetzt". Also wird und wird und wird . ${\ displaystyle \ geq b_ {j}}$ ${\ displaystyle y_ {j} \ leq 0}$ ${\ displaystyle \ leq b_ {j}}$ ${\ displaystyle y_ {j} \ geq 0}$ ${\ displaystyle = b_ {j}}$ ${\ displaystyle y_ {j} \ in \ mathbb {R}}$
Die doppelte Zielfunktion ist ${\ displaystyle {\ text {minim}} ~~~ b_ {1} y_ {1} + \ cdots + b_ {m} y_ {m}}$
Jede ursprüngliche Variable wird zu einer doppelten Einschränkung. Es gibt also n Einschränkungen. Der Koeffizient einer Doppelvariablen in der Doppelbedingung ist der Koeffizient ihrer Urvariablen in ihrer Urbedingung. Jede Einschränkung i ist also : , wobei das Symbol vor dem der Einschränkung für die Variable i in der ursprünglichen LP ähnlich ist . So wird " " und wird " " und wird " ". ${\ displaystyle a_ {1i} y_ {1} + \ cdots + a_ {mi} y_ {m} \ lesseqqgtr c_ {i}}$ ${\ displaystyle c_ {i}}$ ${\ displaystyle x_ {i} \ leq 0}$ ${\ displaystyle \ leq c_ {i}}$ ${\ displaystyle x_ {i} \ geq 0}$ ${\ displaystyle \ geq c_ {i}}$ ${\ displaystyle x_ {i} \ in \ mathbb {R}}$ ${\ displaystyle = c_ {i}}$

Aus diesem Algorithmus ist leicht zu erkennen, dass das Dual des Dual das Primäre ist.

Vektorformulierungen

Wenn alle Einschränkungen das gleiche Vorzeichen haben, ist es möglich, das obige Rezept unter Verwendung von Matrizen und Vektoren kürzer darzustellen. Die folgende Tabelle zeigt die Beziehung zwischen verschiedenen Arten von Primalen und Dualen.

Ursprünglich	Dual	Hinweis
Maximiere c ^T x vorbehaltlich A x ≤ b , x ≥ 0	Minimieren Sie b ^T y vorbehaltlich A ^T y ≥ c , y ≥ 0	Dies wird als "symmetrisches" Doppelproblem bezeichnet
Maximiere c ^T x vorbehaltlich A x ≤ b	Minimieren Sie b ^T y vorbehaltlich A ^T y = c , y ≥ 0	Dies wird als "asymmetrisches" Doppelproblem bezeichnet
Maximiere c ^T x vorbehaltlich A x = b , x ≥ 0	Minimieren Sie b ^T y vorbehaltlich A ^T y ≥ c

Die Dualitätssätze

Angenommen, die ursprüngliche LP ist " c ^T x unter [Einschränkungen] maximieren " und die doppelte LP " b ^T y unter [Einschränkungen] minimieren ".

Schwache Dualität

Der schwache Dualitätssatz besagt, dass für jede realisierbare Lösung x des Primalen und jede realisierbare Lösung y des Dualen gilt: c ^T x ≤ b ^T y . Mit anderen Worten, der Zielwert in jeder realisierbaren Lösung des Dualen ist eine Obergrenze für den Zielwert des Primals, und der Zielwert in jeder realisierbaren Lösung des Primals ist eine Untergrenze für den Zielwert des Dualen. Dies impliziert:

max _x c ^T x ≤ min _y b ^T y

Insbesondere wenn das Primale unbegrenzt ist (von oben), hat das Dual keine realisierbare Lösung, und wenn das Dual unbegrenzt ist (von unten), dann hat das Primal keine realisierbare Lösung.

Der schwache Dualitätssatz ist relativ einfach zu beweisen. Angenommen, die ursprüngliche LP ist "Maximiere c ^T x vorbehaltlich A x ≤ b , x ≥ 0". Angenommen, wir erstellen eine lineare Kombination der Bedingungen mit positiven Koeffizienten, so dass die Koeffizienten von x in den Bedingungen mindestens c ^T betragen . Diese lineare Kombination gibt uns eine Obergrenze für das Ziel. Die Variablen y der dualen LP sind die Koeffizienten dieser linearen Kombination. Die Doppel-LP versucht, solche Koeffizienten zu finden, die die resultierende Obergrenze minimieren. Dies ergibt die LP "Minimiere b ^T y vorbehaltlich A ^T y ≥ c , y ≥ 0". Siehe das winzige Beispiel unten.

Starke Dualität

Der Satz der starken Dualität besagt, dass, wenn eines der beiden Probleme eine optimale Lösung hat, das andere auch eine optimale Lösung hat und dass die Grenzen des Satzes der schwachen Dualität eng sind, dh:

max _x c ^T x = min _y b ^T y

Der starke Dualitätssatz ist schwerer zu beweisen; Die Beweise verwenden normalerweise den Satz der schwachen Dualität als Unterroutine.

Ein Proof verwendet den Simplex-Algorithmus und stützt sich auf den Proof, dass er mit der geeigneten Pivot-Regel eine korrekte Lösung bietet. Der Beweis zeigt, dass, sobald der Simplex-Algorithmus mit einer Lösung für die ursprüngliche LP fertig ist, es möglich ist, aus dem endgültigen Tableau eine Lösung für die doppelte LP zu lesen. Wenn wir also den Simplex-Algorithmus ausführen, erhalten wir gleichzeitig Lösungen sowohl für das Primäre als auch für das Duale.

Ein weiterer Beweis verwendet das Farkas-Lemma .

Theoretische Implikationen

1. Der schwache Dualitätssatz impliziert, dass es genauso schwierig ist , eine einzige realisierbare Lösung zu finden wie eine optimale realisierbare Lösung. Angenommen, wir haben ein Orakel, das bei einer gegebenen LP eine willkürlich mögliche Lösung findet (falls es eine gibt). Wenn die LP "Maximiere c ^T x unter A x ≤ b , x ≥ 0" gegeben ist, können wir eine andere LP konstruieren, indem wir diese LP mit ihrem Dual kombinieren. Die kombinierte LP hat sowohl x als auch y als Variablen:

Maximieren Sie 1

vorbehaltlich A x ≤ b , A ^T y ≥ c , c ^T x ≥ b ^T y , x ≥ 0, y ≥ 0

Wenn die kombinierte LP eine realisierbare Lösung hat ( x , y ), dann ist durch schwache Dualität c ^T x = b ^T y . So x eine maximale Lösung der Erst - LP sein muss , und y muss eine minimale Lösung der Zweit - LP sein. Wenn die kombinierte LP keine realisierbare Lösung hat, hat die ursprüngliche LP auch keine realisierbare Lösung.

2. Das Theorem der starken Dualität liefert eine "gute Charakterisierung" des optimalen Wertes einer LP, indem es uns ermöglicht, leicht zu beweisen, dass ein Wert t das Optimum einer LP ist. Der Beweis erfolgt in zwei Schritten:

Zeigen Sie eine mögliche Lösung für die ursprüngliche LP mit dem Wert t ; dies beweist, dass das Optimum mindestens t ist .
Zeigen Sie eine mögliche Lösung für die Doppel-LP mit dem Wert t ; dies beweist, dass das Optimum höchstens t ist .

Beispiele

Winziges Beispiel

Betrachten Sie die ursprüngliche LP mit zwei Variablen und einer Einschränkung:

{\ displaystyle {\ begin {align} {\ text {maxim}} & 3x_ {1} + 4x_ {2} \\ {\ text {vorbehaltlich}} & 5x_ {1} + 6x_ {2} = 7 \\ & x_ { 1} \ geq 0, x_ {2} \ geq 0 \ end {align}}}

Wenn Sie das obige Rezept anwenden, erhalten Sie die folgende Doppel-LP mit einer Variablen und zwei Einschränkungen:

{\ displaystyle {\ begin {align} {\ text {minim}} & 7y_ {1} \\ {\ text {vorbehaltlich}} & 5y_ {1} \ geq 3 \\ & 6y_ {1} \ geq 4 \\ & y_ { 1} \ in \ mathbb {R} \ end {align}}}

Es ist leicht zu erkennen, dass das Maximum der ursprünglichen LP erreicht wird, wenn x ₁ auf seine Untergrenze (0) minimiert wird und x ₂ unter der Bedingung (7/6) auf seine Obergrenze maximiert wird. Das Maximum ist 4 · 7/6 = 14/3.

In ähnlicher Weise wird das Minimum der dualen LP erreicht, wenn y ₁ unter den Bedingungen auf seine Untergrenze minimiert wird: Die erste Bedingung ergibt eine Untergrenze von 3/5, während die zweite Bedingung eine strengere Untergrenze von 4/6 ergibt, so dass die Die tatsächliche Untergrenze beträgt 4/6 und das Minimum 7 · 4/6 = 14/3.

In Übereinstimmung mit dem Satz der starken Dualität entspricht das Maximum des Primalen dem Minimum des Dualen.

Wir verwenden dieses Beispiel, um den Beweis des schwachen Dualitätssatzes zu veranschaulichen. Angenommen, wir möchten in der ursprünglichen LP eine Obergrenze für das Ziel erhalten . Wir können die Beschränkung multipliziert mit einem Koeffizienten verwenden, sagen wir . Für jeden bekommen wir : . Nun, wenn und dann so . Daher ist das Ziel der Doppel-LP eine Obergrenze für das Ziel der Ur-LP. ${\ displaystyle 3x_ {1} + 4x_ {2}}$ ${\ displaystyle y_ {1}}$ ${\ displaystyle y_ {1}}$ ${\ displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2}) = 7y_ {1}}$ ${\ displaystyle y_ {1} \ cdot 5x_ {1} \ geq 3x_ {1}}$ ${\ displaystyle y_ {1} \ cdot 6x_ {2} \ geq 4x_ {2}}$ ${\ displaystyle y_ {1} \ cdot (5x_ {1} + 6x_ {2}) \ geq 3x_ {1} + 4x_ {2}}$ ${\ displaystyle 7y_ {1} \ geq 3x_ {1} + 4x_ {2}}$

Bauernbeispiel

Stellen Sie sich einen Landwirt vor, der Weizen und Gerste anbauen kann, wenn er L- Land, F- Dünger und P- Pestizide zur Verfügung stellt. Für den Anbau einer Einheit Weizen müssen eine Einheit Land, Einheiten Dünger und Einheiten Pestizid verwendet werden. Um eine Einheit Gerste anzubauen, müssen eine Einheit Land, Einheiten Dünger und Einheiten Pestizid verwendet werden. ${\ displaystyle F_ {1}}$ ${\ displaystyle P_ {1}}$ ${\ displaystyle F_ {2}}$ ${\ displaystyle P_ {2}}$

Das Hauptproblem wäre, dass der Landwirt entscheidet, wie viel Weizen ( ) und Gerste ( ) angebaut werden soll, wenn die Verkaufspreise und pro Einheit liegen. ${\ displaystyle x_ {1}}$ ${\ displaystyle x_ {2}}$ ${\ displaystyle S_ {1}}$ ${\ displaystyle S_ {2}}$

Maximieren: ${\ displaystyle S_ {1} \ cdot x_ {1} + S_ {2} \ cdot x_ {2}}$		(Maximieren Sie die Einnahmen aus der Herstellung von Weizen und Gerste)
vorbehaltlich:	${\ displaystyle x_ {1} + x_ {2} \ leq L}$	(kann nicht mehr Land als verfügbar nutzen)
	${\ displaystyle F_ {1} \ cdot x_ {1} + F_ {2} \ cdot x_ {2} \ leq F}$	(kann nicht mehr Dünger als verfügbar verwenden)
	${\ displaystyle P_ {1} \ cdot x_ {1} + P_ {2} \ cdot x_ {2} \ leq P}$	(kann nicht mehr Pestizide als verfügbar verwenden)
	${\ displaystyle x_ {1}, x_ {2} \ geq 0}$	(Kann keine negativen Mengen an Weizen oder Gerste produzieren).

In Matrixform wird dies:

Maximieren:

{\ displaystyle {\ begin {bmatrix} S_ {1} & S_ {2} \ end {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ {2} \ end {bmatrix}}}

vorbehaltlich:

{\ displaystyle {\ begin {bmatrix} 1 & 1 \\ F_ {1} & F_ {2} \\ P_ {1} & P_ {2} \ end {bmatrix}} {\ begin {bmatrix} x_ {1} \\ x_ { 2} \ end {bmatrix}} \ leq {\ begin {bmatrix} L \\ F \\ P \ end {bmatrix}}, \, {\ begin {bmatrix} x_ {1} \\ x_ {2} \ end {bmatrix}} \ geq 0.}

Für das Doppelproblem wird angenommen, dass y Stückpreise für jedes dieser Produktionsmittel (Inputs) von einer Plantafel festgelegt werden. Die Planungsbehörde hat die Aufgabe, die Gesamtkosten für die Beschaffung der festgelegten Mengen an Inputs zu minimieren und dem Landwirt einen Mindestpreis für jede seiner Kulturen (Outputs), S ₁ für Weizen und S ₂ für Gerste, zur Verfügung zu stellen. Dies entspricht der folgenden LP:

Minimieren: ${\ displaystyle L \ cdot y_ {L} + F \ cdot y_ {F} + P \ cdot y_ {P}}$		(Minimierung der Gesamtkosten der Produktionsmittel als "Zielfunktion")
vorbehaltlich:	${\ displaystyle y_ {L} + F_ {1} \ cdot y_ {F} + P_ {1} \ cdot y_ {P} \ geq S_ {1}}$	(Der Landwirt muss nicht weniger als S ₁ für seinen Weizen erhalten.)
	${\ displaystyle y_ {L} + F_ {2} \ cdot y_ {F} + P_ {2} \ cdot y_ {P} \ geq S_ {2}}$	(Der Landwirt muss mindestens S ₂ für seine Gerste erhalten.)
	${\ displaystyle y_ {L}, y_ {F}, y_ {P} \ geq 0}$	(Preise können nicht negativ sein).

In Matrixform wird dies:

Minimieren:

{\ displaystyle {\ begin {bmatrix} L & F & P \ end {bmatrix}} {\ begin {bmatrix} y_ {L} \\ y_ {F} \\ y_ {P} \ end {bmatrix}}}

vorbehaltlich:

{\ displaystyle {\ begin {bmatrix} 1 & F_ {1} & P_ {1} \\ 1 & F_ {2} & P_ {2} \ end {bmatrix}} {\ begin {bmatrix} y_ {L} \\ y_ {F} \ \ y_ {P} \ end {bmatrix}} \ geq {\ begin {bmatrix} S_ {1} \\ S_ {2} \ end {bmatrix}}, \, {\ begin {bmatrix} y_ {L} \\ y_ {F} \\ y_ {P} \ end {bmatrix}} \ geq 0.}

Das Hauptproblem betrifft physikalische Größen. Wenn alle Inputs in begrenzten Mengen verfügbar sind und die Stückpreise aller Outputs bekannt sind, welche Outputmengen müssen produziert werden, um den Gesamtumsatz zu maximieren? Das doppelte Problem betrifft wirtschaftliche Werte. Welches Preisschema für die Eingabeeinheit muss festgelegt werden, um die Gesamtausgaben zu minimieren, da Mindestgarantien für alle Produktionseinheitenpreise gelten und die verfügbare Menge aller Produktionsmengen bekannt ist?

Jeder Variablen im ursprünglichen Raum entspricht eine im dualen Raum zu erfüllende Ungleichung, die beide nach Ausgabetyp indiziert sind. Jeder im Urraum zu erfüllenden Ungleichung entspricht eine Variable im Doppelraum, die beide nach Eingabetyp indiziert sind.

Die Koeffizienten, die die Ungleichungen im Urraum begrenzt haben, werden verwendet, um das Ziel im Doppelraum zu berechnen, in diesem Beispiel Eingangsgrößen. Die Koeffizienten, die zur Berechnung des Ziels im Urraum verwendet wurden, begrenzten die Ungleichungen im Doppelraum und gaben in diesem Beispiel die Einheitspreise aus.

Sowohl das ursprüngliche als auch das doppelte Problem verwenden dieselbe Matrix. Im Urraum drückt diese Matrix den Verbrauch physikalischer Mengen von Eingaben aus, die zur Erzeugung festgelegter Mengen von Ausgaben erforderlich sind. Im dualen Raum drückt es die Schaffung der wirtschaftlichen Werte aus, die mit den Outputs aus festgelegten Input-Einheitspreisen verbunden sind.

Da jede Ungleichung durch eine Gleichheits- und eine Slack-Variable ersetzt werden kann, bedeutet dies, dass jede Urvariable einer Dual-Slack-Variablen entspricht und jede Dual-Variable einer Primal-Slack-Variablen entspricht. Diese Beziehung erlaubt es uns, über komplementäre Schlaffheit zu sprechen.

Unmögliches Programm

Eine LP kann auch unbegrenzt oder nicht realisierbar sein. Die Dualitätstheorie sagt uns, dass:

Wenn das Ursprüngliche unbegrenzt ist, ist das Dual nicht durchführbar;
Wenn das Dual unbegrenzt ist, ist das Ursprüngliche nicht realisierbar.

Es ist jedoch möglich, dass sowohl das Doppelte als auch das Ursprüngliche nicht realisierbar sind. Hier ist ein Beispiel:

Maximieren: ${\ displaystyle 2x_ {1} -x_ {2}}$
Vorbehaltlich:	${\ displaystyle x_ {1} -x_ {2} \ leq 1}$
	${\ displaystyle -x_ {1} + x_ {2} \ leq -2}$
	${\ displaystyle x_ {1}, x_ {2} \ geq 0.}$

Anwendungen

Der Max-Flow-Min-Cut-Satz ist ein Sonderfall des starken Dualitätssatzes: Die Flussmaximierung ist die ursprüngliche LP und die Cut-Minimierung ist die doppelte LP. Siehe Max-Flow-Min-Cut-Theorem # Lineare Programmformulierung .

Andere graphbezogene Theoreme können unter Verwendung des starken Dualitätssatzes, insbesondere des Konigschen Theorems, bewiesen werden .

Der Minimax-Satz für Nullsummenspiele kann mit dem Satz der starken Dualität bewiesen werden.

Alternativer Algorithmus

Manchmal kann es intuitiver sein, das duale Programm zu erhalten, ohne die Programmmatrix zu betrachten. Betrachten Sie das folgende lineare Programm:

Minimieren	${\ displaystyle \ sum _ {i = 1} ^ {m} c_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} d_ {j} t_ {j}}$
vorbehaltlich	${\ displaystyle \ sum _ {i = 1} ^ {m} a_ {ij} x_ {i} + e_ {j} t_ {j} \ geq g_ {j},}$	${\ displaystyle 1 \ leq j \ leq n}$
	${\ displaystyle f_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} b_ {ij} t_ {j} \ geq h_ {i},}$	${\ displaystyle 1 \ leq i \ leq m}$
	${\ displaystyle x_ {i} \ geq 0, \, t_ {j} \ geq 0,}$	${\ displaystyle 1 \ leq i \ leq m, 1 \ leq j \ leq n}$

Wir haben m + n Bedingungen und alle Variablen sind nicht negativ. Wir werden m + n duale Variablen definieren: y _j und s _i . Wir bekommen:

Minimieren	${\ displaystyle \ sum _ {i = 1} ^ {m} c_ {i} x_ {i} + \ sum _ {j = 1} ^ {n} d_ {j} t_ {j}}$
vorbehaltlich	${\ displaystyle \ sum _ {i = 1} ^ {m} a_ {ij} x_ {i} \ cdot y_ {j} + e_ {j} t_ {j} \ cdot y_ {j} \ geq g_ {j} \ cdot y_ {j},}$	${\ displaystyle 1 \ leq j \ leq n}$
	${\ displaystyle f_ {i} x_ {i} \ cdot s_ {i} + \ sum _ {j = 1} ^ {n} b_ {ij} t_ {j} \ cdot s_ {i} \ geq h_ {i} \ cdot s_ {i},}$	${\ displaystyle 1 \ leq i \ leq m}$
	${\ displaystyle x_ {i} \ geq 0, \, t_ {j} \ geq 0,}$	${\ displaystyle 1 \ leq i \ leq m, 1 \ leq j \ leq n}$
	${\ displaystyle y_ {j} \ geq 0, \, s_ {i} \ geq 0,}$	${\ displaystyle 1 \ leq j \ leq n, 1 \ leq i \ leq m}$

Da dies ein Minimierungsproblem ist, möchten wir ein duales Programm erhalten, das eine Untergrenze des Primals darstellt. Mit anderen Worten, wir möchten, dass die Summe aller rechten Seiten der Bedingungen das Maximum ist, unter der Bedingung, dass für jede Urvariable die Summe ihrer Koeffizienten ihren Koeffizienten in der linearen Funktion nicht überschreitet. Zum Beispiel erscheint x ₁ in n + 1 Einschränkungen. Wenn wir die Koeffizienten seiner Bedingungen summieren, erhalten wir a _1,1 y ₁ + a _1,2 y ₂ + ... + a _{1, ;; n ;;} y _n + f ₁ s ₁ . Diese Summe darf höchstens c ₁betragen . Als Ergebnis erhalten wir:

Maximieren	${\ displaystyle \ sum _ {j = 1} ^ {n} g_ {j} y_ {j} + \ sum _ {i = 1} ^ {m} h_ {i} s_ {i}}$
vorbehaltlich	${\ displaystyle \ sum _ {j = 1} ^ {n} a_ {ij} y_ {j} + f_ {i} s_ {i} \ leq c_ {i},}$	${\ displaystyle 1 \ leq i \ leq m}$
	${\ displaystyle e_ {j} y_ {j} + \ sum _ {i = 1} ^ {m} b_ {ij} s_ {i} \ leq d_ {j},}$	${\ displaystyle 1 \ leq j \ leq n}$
	${\ displaystyle y_ {j} \ geq 0, \, s_ {i} \ geq 0,}$	${\ displaystyle 1 \ leq j \ leq n, 1 \ leq i \ leq m}$

Beachten Sie, dass wir in unseren Berechnungsschritten davon ausgehen, dass das Programm in Standardform vorliegt. Jedes lineare Programm kann jedoch in eine Standardform umgewandelt werden und ist daher kein einschränkender Faktor.

Interpretationen aus dem wirklichen Leben

Der Dualitätssatz hat eine ökonomische Interpretation. Wenn wir die ursprüngliche LP als ein klassisches Problem der "Ressourcenzuweisung" interpretieren, kann ihre doppelte LP als ein Problem der "Ressourcenbewertung" interpretiert werden. Siehe auch Schattenpreis .

Der Dualitätssatz hat auch eine physikalische Interpretation.

Languages

In other projects