Minimierungsprobleme

Operations Research

Das Kapitel Minimierungsprobleme in unserem Online-Kurs Operations Research besteht aus folgenden Inhalten:

1. Minimierungsprobleme

   Minimierungsprobleme

   

   Das folgende Lernvideo beschreibt die sog. "Minimierungsprobleme". Im Wesentlichen lassen sich Minimierungsprobleme ebenfalls als Maximierungsprobleme ausdrücken, wodurch die Anwendung des Simplex-Algorithmus zulässig wird:Das Video wird geladen...(max-zu-minimierungsproblem) 

2. Zweiphasenmethode

   Minimierungsprobleme > Zweiphasenmethode > Zweiphasenmethode

   

   Anzuwenden ist das vorgestellte Simplex-Verfahren für…Maximierungsprobleme,bei positiv stehenden Werten auf der rechten Seite undim Falle dessen, dass eine Ausgangslösung sofort abzulesen ist (Zuverlässigkeit).Zu begutachten ist dieses Problem:2x1 + x2 ≥ 83x1 + 3x2 ≥ 12x1 + 3x2 ≥ 6x1, x2 ≥ 0.Die Zielfunktion K lautet: 10x1 + 12x2 →  min!Die Lösung ist mit der Zweiphasenmethode zu bestimmen.Die oben genannten Anforderungen sind bei dem betrachteten ...

3. Beginn der ersten Phase

   Minimierungsprobleme > Zweiphasenmethode > Beginn der ersten Phase

   

    x1x2y1y2y3k1k2k3RSk121-1001008k2330-1001012k31300-10016K-10-120000000K´67-1-1-100026Tab. 17: Ausgangstableau ZweiphasenmethodeGerechnet wird mit der Zielfunktionszeile K´*. Der höchste Wert beträgt 7, weswegen die Zahlen unterhalb von x2 die Pivot-Spalte ergeben. Die Quotienten sind 8:1 = 8, 12:3 = 4, 6:3 = 2. Eine Pivot-Zeile ist k3, weil die Zahl 2 minimal ist. Demnach wird 3 zum Pivot-Element. Durch den ersten Basistausch ergibt sich: x1x2y1y2y3k1k2k3RSk15/30-101/310-1/36k2200-1101-16x21/3100-1/3001/32K-6000-400424K´*11/30-1-14/300-7/312Tab. ...

4. Beginn der zweiten Phase

   Minimierungsprobleme > Zweiphasenmethode > Beginn der zweiten Phase

   

   Gestrichen wird jetzt die letzte Zeile K´* und die beiden Blöcke unterhalb von k1, k2, k3. Dadurch ergibt sich: x1x2y1y2y3RSy200-6/51-3/56/5x110-3/501/518/5x2011/50-2/54/5K00-18/50-14/545,6Tab. 21: Endtableau zweite PhaseAusgangstableau der zweiten PhaseDie Zielfunktionszeile bildet hier erneut K. Es werden weitere Simplex-Schritte vorgenommen, wenn Zahlen am unteren Rand stehen, welche echt größer sind als null. Weil das hier nicht vorliegt, müssen wir an dem Punkt ...

5. Dualität

   Minimierungsprobleme > Zweiphasenmethode > Dualität

   

   Wir haben bislang das Maximierungsprobleme mit „≤“-Restriktionen thematisiert, wodurch sich diese Definition ergab: Man kann von einem Primalproblem in Normalform sprechen, wenn die Aufgabe wie folgt aussieht:x1 ... xna11 ... a1n ≤ b1⋮ ⋮ ⋮am1 ... amn ≤ bmc1 ... cn → max!X1, ..., xn ≥ 0.Charakteristisch für die Normalform sind: Restriktionen, Nichtnegativitätsbedingungen und ein Maximierungsproblem. Es ...

6. Dualer Simplex-Algorithmus

   Minimierungsprobleme > Zweiphasenmethode > Dualer Simplex-Algorithmus

   

   ... unterscheiden sind zueinander. Minimierungsprobleme LösenBei Minimierungproblemen sind wir bislang so vorgegangen, dass diese mit Hilfe der Dualisierung in ein Maximierungsproblem umgewandelt wurde und folglich als Simplex-Algorithmus gelöst werden konnte. Bei dem dualen Simplex-Algorithmus wird auf diese Form der Umwandlung verzichtet.Wir schauen uns für ein Minimierungsproblem mit ≥-Restriktionen folgendes an:SCHEMA DUALER SIMPLEX-ALGORITHMUS:1. Vorbereitung- ...