Kurs 853 Schnittebenenverfahren

ich hänge an dem Algorithmus zum Schnittebenenverfahren.

Im Skript "Ganzzahlige Optimierung" wird dieser auf Seite 60 erläutert.

Schritt 4 geht noch. Hier wird (denke ich zumindest) einfach die RHS der betrachteten Zeile verrechnet. Die Weise wie verrechnet wird ist mir auch klar.

Aber in Schritt 5 wird auf Formel 3.20 verwiesen und diese Tabelle verstehe ich nicht. Was wird unter ganzzahlig verstanden und wo ist der Unterrschied zwischen f_0 und diesem ALPHA?

Konkret:

Beispiel 3.3 S. 61
f_0 ist klar 48/31 - 31/31 = 17/31
Bei der neuen Restriktion wird vor x3 "-Yrj" genommen. Das ist in Formel 3.20 die erste Zeile.
Bei x4 wird dann die zweite Zeile genommen.
Warum werden diese Zeilen der Formel 3.20 genommen?

Ü3.3 S.62:
f_0 ist wieder klar 3/2 - 2/2 =1/2
Auch hier frage ich mich, wonach entschieden wird, welche Zeilen der Formel 3.20 genommen werden müssen.

VG,
Mattes

Kann hier keiner helfen?

Mattes,

ich weiß nicht ob es noch aktuell ist, aber anbei mal meine Lösung. Angesichts meiner Schwierigkeiten mit diesem Skript bin ich noch etwas skeptisch, aber ich glaube, ich habe tatsächlich mal was verstanden 🙂.

zur Formel 3.20:
du muss alle x betrachten, die in deinem letzten Tableau nicht Basisvariable sind
für die guckst du dann ob sie laut Aufgabenstellung ganzz. oder reel sein sollen
dementsprechend musst du dann nur noch nach yrj oder aj entscheiden.

Zum Bsp. für das Bsp. 3.3 S. 61:
im letzten Tableau sind x3 und x4 Nicht Basisvariable, d.h. du muss f3 und f4 ausrechnen.
Da es sich um Schlupfvariablen handelt, dürfen diese reel sein.
Für f3 gilt nun:
x3 reel und y13=3/31 >= 0, also f3 = y13 = 3/31
x4 reel und y14=-8/31 <0, also f4 = (f0*y14)/(f0-1) = (17/31*-8/31)/(17/31-1)=68/217

Also lautet die Restriktion (! laut Vorgabe bekommen alle ein Minus):
-3/31x3 - 68/217x4 <= - 17/31

Für die Übungsaufgabe siehe Anhang, dort ist auch Alpha erkärt