Inhaltsverzeichnis
In diesem Abschnitt soll ausführlich beschrieben werden, wie ein gegebenes Minimierungsproblem gelöst werden kann. Hierzu wird dieses zunächst dualsiert, d.h. also in ein Maximierungsproblem in kanonischer Form umgewandelt. Danach wird der primale Simplexalgorithmus angewandt um eine Optimallösung zu erhalten. Es wird gezeigt, wie man die Optimallösung des primalen Problems aus den Optimaltableau für das duale Problem ermittelt.
Beispiel: Duales Maximierungsproblem lösen
Gegeben sei das folgende Minimierungsproblem
u.d.N.
Beispiel
Das Problem soll mit dem primalen Simplexalgorithmus gelöst werden!
Um das Problem mit dem primalen Simplexlagorithmus lösen zu können, muss dieses in ein duales Maximierungsproblem umgewandelt werden. Hierzu muss das Minimierungsproblem zunächst die Form "Größer/Gleich-Nebenbedingung, Nichtnegativitätsbedingung" überführt werden. Da das Problem bereits in dieser Form vorliegt, kann mit der Dualisierung begonnen werden:
Das Problem wird in eine Matrix eingetragen. Die Zielfunktionszeile geht als letztes in die Matrix ein:
Danach wird die Matrix transponiert:
Das neue Problem wird aus der Matrix abgelesen, wobei die letzte Zeile die Zielfunktionszeile des dualen Problems darstellt:
Das duale Maximierungsproblem liegt in kanonischer Form vor, es kann hier also der primale Simplexalgorithmus angewandt werden. Hierzu muss das Problem in die Normalform überführt werden:
Nachdem die Schlupfvariablen eingefügt worden sind, kann das Problem nun in das Tableau eingetragen werden und der primale Simplexalgorithmus angewandt werden:
Nachdem alle Werte in der Zielfunktionszeile positiv sind, ist die optimale Lösung erreicht. Für das duale Maximierungsproblem beträgte diese
Die optimale Lösung für das primale Minimierungsproblem kann ebenfalls dem Tableau entnommen werden. Und zwar gilt
Merke
Die Zielfunktionswerte beider Modelle sind im Optimum identisch!
Weitere interessante Inhalte zum Thema
-
Dualität - Dualproblem in Primalproblem
Vielleicht ist für Sie auch das Thema Dualität - Dualproblem in Primalproblem (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.
-
Dualität - Primalproblem als Minimierungsproblem
Vielleicht ist für Sie auch das Thema Dualität - Primalproblem als Minimierungsproblem (Lineare Programmierung) aus unserem Online-Kurs Operations Research 1 interessant.