Branch & Bound für MILP - ÜA 2.4 Kurs 853

Woytek,

durch Hinzufügen der Restriktion x1 >= 2 erhältst Du eine neue Schlupfvariabe s1 (x1 - s1 = 2), die x1 in der Basis ersetzt, siehe Beispiel Seite 36-37. Außerdem müssen die Zeileneinträge durch Ersetzen der markierten Zeile modifiziert werden.

Dann führst Du einen dualen Simplex-Schritt durch, welcher x4 in die Basis bringt und s1 daraus verdrängt. s1 hat jetzt in der Kriteriumszeile den Wert 0 und somit ist x1 = 2 (wg. x1 - s1 = 2, s.o.).

Die Lösung ist dann x = (2, 15/4)^T mit z = 17...

Gruß Franz

FranzK schrieb:

Hallo Woytek,

durch Hinzufügen der Restriktion x1 >= 2 erhältst Du eine neue Schlupfvariabe s1 (x1 - s1 = 2), die x1 in der Basis ersetzt, siehe Beispiel Seite 36-37. Außerdem müssen die Zeileneinträge durch Ersetzen der markierten Zeile modifiziert werden.

Dann führst Du einen dualen Simplex-Schritt durch, welcher x4 in die Basis bringt und s1 daraus verdrängt. s1 hat jetzt in der Kriteriumszeile den Wert 0 und somit ist x1 = 2 (wg. x1 - s1 = 2, s.o.).

Die Lösung ist dann x = (2, 15/4)^T mit z = 17...

Gruß Franz 🙂

Zum Vergrößern anklicken....

Hallo Franz,

es hat zwar lange gedauert, aber jetzt hab´ ich´s verstanden 😀.
Danke für die Hilfe 🙂. Dabei war mein Fehler total einfach. Ich habe auf den Wert von x4 geschaut und mich gewundert, warum hier 7/4 anstatt 8/4 rauskommen. Man muss natürlich auf s1 schauen - die Variable kommt aus der Basis raus, hat also den Wert 0 und das führt zu x1 = 2. x1 kann man natürlich aus dem Tableau gar nicht direkt ablesen.

Das Beispiel auf S.37 ist ein bisschen verwirrend. Hier hat x4 den gleichen Wert wie x3 also 4. Wenn man nicht aufpasst, sucht man dann das Ergebnis direkt im Tableau und genau das ist mir passiert.

Im Anhang ist jetzt die modifizierte Lösung, die korrekt sein müsste.

Viele Grüße,
Woytek