Dualität bei Problemen mit der linearen Programmierung

Dualität bei Problemen mit der linearen Programmierung!

Für jedes lineare Programmierproblem gibt es ein entsprechendes eindeutiges Problem, das dieselben Daten enthält, und es beschreibt auch das ursprüngliche Problem. Das ursprüngliche Problem heißt Primal-Programm und das entsprechende eindeutige Problem heißt Dual-Programm. Die beiden Programme sind sehr eng miteinander verbunden und die optimale Lösung von dual gibt vollständige Informationen über die optimale Lösung von Primary und umgekehrt.

Verschiedene nützliche Aspekte dieser Eigenschaft sind:

(a) Wenn Primal eine große Anzahl von Konstanten und eine geringe Anzahl von Variablen hat, kann die Berechnung erheblich reduziert werden, indem das Problem in Dual konvertiert und anschließend gelöst wird.

(b) Die Dualität in der linearen Programmierung hat gewisse weitreichende wirtschaftliche Folgen. Auf diese Weise können Manager Fragen zu alternativen Vorgehensweisen und ihren relativen Werten beantworten.

(c) Bei der Berechnung der dualen Prüfung wird die Genauigkeit der Primärlösung geprüft.

(d) Dualität in der linearen Programmierung zeigt, dass jedes lineare Programm einem Zwei-Personen-Nullsummenspiel entspricht. Dies zeigt, dass zwischen der linearen Programmierung und der Spieltheorie ziemlich enge Beziehungen bestehen.

1. Dual bilden, wenn Primal in kanonischer Form vorliegt:

Aus den obigen beiden Programmen sind die folgenden Punkte klar:

(i) Das Maximierungsproblem im Primat wird zum Minimierungsproblem im Dualen und umgekehrt.

(ii) Das Maximierungsproblem hat () Einschränkungen.

(iii) Wenn das Primal n Variablen und m Einschränkungen enthält, enthält das Dual m Variablen und n Einschränkungen.

(iv) Die Konstanten b 1 b 2, b 3 ……… b m in den Beschränkungen des Primals erscheinen in der objektiven Funktion des Dualen.

(v) Die Konstanten c 1, c 2, c 3 c n in der objektiven Funktion des Primals erscheinen in den Einschränkungen des Dualen.

(vi) Die Variablen in beiden Problemen sind nicht negativ.

Die Randbedingungsverhältnisse von Prim und Dual sind unten dargestellt.

Beispiel 1:

Konstruieren Sie das Dual-Problem zum ursprünglichen Problem

Lösung:

Zunächst wird die ≥-Bedingung in ≤-Bedingung umgewandelt, indem beide Seiten mit -1 multipliziert werden.

Beispiel 2

Konstruieren Sie das Dual-Problem zum ursprünglichen Problem

Lösung:

Wenn Y 1, Y 2, V 3 und V 4 die entsprechenden dualen Variablen sind, dann ist das duale Problem durch gegeben

Da das duale Problem eine geringere Anzahl von Einschränkungen aufweist als das ursprüngliche (2 statt 4), erfordert es weniger Aufwand und Aufwand, um es zu lösen. Dies folgt aus der Tatsache, dass die rechnerische Schwierigkeit bei dem Problem der linearen Programmierung hauptsächlich mit der Anzahl von Beschränkungen und nicht mit der Anzahl von Variablen zusammenhängt.

Beispiel 3:

Konstruiere den Dual des Problems

Lösung:

Da das Problem der Minimierung besteht, sollten alle Einschränkungen vom Typ> sein. Wenn wir die dritte Bedingung auf beiden Seiten mit - 1 multiplizieren, erhalten wir.

-8x1 + 2x2 + 2x3 ≥ -10

Das duale des gegebenen Problems wird sein

wobei y 1, y 2, y 3, y 4 und y 5 die mit der ersten, zweiten, dritten, vierten und fünften Einschränkung verbundenen Doppelvariablen sind.