Gomory-Verfahren ---> dürfen Schupfvariablen nicht ganzzahlig sein?

ich darf die Vermutung aufstellen, dass in der Klausur am Montag sehr wahrscheinlich eine Aufgabe zur Ganzzahligkeit drankommt.

Dies dürfte wohl eine der Aufgaben aus der zweiten EA SS 2010 sein, nämlich entweder a.) Branch & Bound oder b.) Gomory-Verfahren oder c.) Rekursion.

Die Frage, die ich aufwerfen möchte, ist eher speziell und führt stark ins Detail ð muss auch dann der Gomory-Schnitt durchgeführt werden, wenn die Schlupfvariablen – also S1, S2, etc. – nicht ganzzahlig sind?

Bsp.:

In der Aufgabe 2, EA SS 2010 ist X2 nicht ganzzahlig, nämlich X2 = 5/2

Die Aufgabe wird wie folgt gelöst:

Schritt 1 ð Man betrachtet das optimale nichtganzzahlige Simplextableu und stellt fest X2 = 5/2 ist nicht ganzzahlig


Schritt 2 ð Aufstellen der Schnittrestriktion, s. Vorgehensweise auf der S. 45:

-10/39 * S1 – 35/39 * S3 + G = - 0,5


Schritt 3 ð Hinzufügen der Restriktion in das nichtganzzahlige Simplextableau

Nebenfrage in diesem Zusammenhang: Nach welchen Kriterien bestimme ich hier das Pivotelement?

Der Prof hatte -35/39 als Pivotelement genommen, aber ich meine -10/39 wäre auch korrekt, Hauptsache G wird aus der Basis rausgenommen

Schritt 4 ð Einen Schritt durchfahren, G kommt aus der Basis. Lösung angeben

Kommentare?

Gruß,
Sus

Pawel,

gem. den Regeln des Dualen Simplex ist -35/39 das Pivotelement. -10/39 führt zu einer dual unzulässigen Lösung (neg. Kriteriumszeile).

Gruß

Das stimmt, aber wie willst Du das vorab sehen?

Ich glaube, das hat eher mit folgender Logik zu tun:

Vergleiche das Ergebnis von -0,5 / (-10/39) und -0,5 / (-35/39) und nehme die Zahl als Pivotelement, wo das Ergebnis kleiner wird.
-0,5 / (-10/39) = 1,95 und -0,5 / (-35/39) = 0,56 Also, ich meine, offenbar muss das kleinere Ergebnis genommen werden bzw. die Zahl, welche zum kleineren Ergebnis führt. Aber so 100% sicher bin ich mir nicht...

Was meinst Du?

Pawel