Branch & Bound mit LP-Relaxation

Branch & Bound mit LP-Relaxation


Zu folgender Aufgabe habe ich Verständnisprobleme:
min z = -2y1 -y2
u.d.NB:
y1 +y2 +x1 = 5
-y1 +y2 +x2 = 0
6y1 +2y2 +x3 = 21
x1,x2,x3 >= 0
y1,y2 >= 0 und ganzzahlig
Im 1.Schritt (Relaxation) erhält man mit dem Simplex-Algorithmus folgende
erste Lösung :
z = (y1, y2, x1, x2, x3 ) = ( 11/4 , 9/4 , 0 , 1/2 , 0 ) ;
mit z = -7,75 (nicht ganzzahlig)

2.Schritt (Branch)
y1 = 2,75 und y2 = 2,25
weiter mit y1:
aufspalten in Y1 <= 2 und Y1 >=3

3.Schritt (Bound) mit Zweig y1 <=2
min z = -2y1 -y2
u.d.NB: y1 +y2 +x1 = 5
-y1 +y2 +x2 = 0
6y1 +2y2 +x3 = 21
x1,x2,x3 >= 0
y1 <= 2
y1,y2 >= 0 und ganzzahlig

Meine Frage:
Wie geht es ab hier weiter ? Wie erstelle jetzt das neue Tableau für
den Simplex-Algorithmus ? Dieses Tableaus muß sich doch vom ersten
unterscheiden. Wie muß ich die Bedingung Y1 <= 2 unterbringen ?

Danke im voraus .
LG Mareike