ZU DEN KURSEN!

Operations Research 2 - Beispiel: Verfahren von Gomory

Kursangebot | Operations Research 2 | Beispiel: Verfahren von Gomory

Operations Research 2

Beispiel: Verfahren von Gomory

In diesem Abschnitt folgt ein Beispiel zum Primal-Ganzzahligem Algorithmus von Gomory. Hierzu wird das Maximierungsproblem herangezogen, welches bereits im Abschnitt Grafisches Verfahren gelöst worden ist. Die optimale Lösung ohne Ganzzahligkeitsbedingung lag bei $x_1 = 1$ und $x_2 = 1,5$ mit dem Zielfunktionswert $f = 3,5$. Diese Lösung ist aber nicht zulässig, da die Ganzzahligkeitsbedingung für beide Variablen gegeben ist und damit nur ganze Zahlen als Ergebnis zulässig sind. Es wird demnach im Folgenden gezeigt, wie man dieses Problem mittels Gomory-Verfahren löst.

Gegeben sei das folgende Maximierungsproblem in Standardform:

$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   max!

u.d.N.

(1) $3x_1 + 2x_2 \le 6 $   

(2) $5x_1 + 2 x_2 \le 8$    


$x_1, x_2 \ge 0$    und ganzzahlig

Das Problem wird zunächst in die Normalform überführt:

$f(x_1, x_2) = 2x_1 +  x_2$    $\rightarrow$   max!

u.d.N.

(1) $3x_1 + 2x_2 + y_1           = 6 $   

(2) $5x_1 + 2 x_2         + y_2  = 8$    


$x_1, x_2 \ge 0$    und ganzzahlig

Danach wird das Problem in das Tableau eingetragen:

Gomery-Verfahren Beispiel

Für die Gomory-Zeile wird die Pivotzeile gewählt:

$5x_1 + 2 x_2 + y_2 = 8$

Diese wird durch das Pivotelement geteilt, wobei die Basisvariable $y_2 = y_{g1}$ gesetzt wird und nicht berücksichtigt wird:

$[5/5] x_1 + [2/5] x_2 + y_{g1} = [8/5]$

Die Quotienten in den Klammern werden abgerundet:

$[1] x_1 + [0] x_2 + y_{g1} = [1]$

Die Gomory-Zeile wird als letzte Zeile in das Tableau eingefügt:

Gomery-Verfahren Beispiel


Es wird als nächster der 1. Simplexschritt durchgeführt. Die Gomory-Zeile wird dabei einfach in das neue Tableau übernommen, ohne dass dort die Simplexschritte angewandt werden. Die Nichtbasisvariable in dessen Spalte sich das Pivotelement befindet ($x_1$) wird mit der Gomory-Variable getauscht.

Gomery-Verfahren Beispiel


Das Optimaltableau liegt noch nicht vor, da sich noch negative Werte in der Zielfunktionszeile befinden ($-1/5$). Das Tableau weist nur ganzzahlige Werte bzw. endliche Dezimalzahlen auf, die mittels Multiplikation von $10$, $100$ usw. in ganze Zahlen umgeformt werden können. Deswegen kann hier ein weiterer Schritt durchgeführt werden. Es wird zunächst wieder die Pivotspalte und dann die Pivotzeile ausgewählt:

Gomery-Verfahren Beispiel


Es wird wieder die Pivot-Zeile als Gomory-Zeile ausgewählt:

$-3/5 y_{g1} + 4/5 x_2 + y_1 = 6/5$

Diese wird wieder durch das Pivotelement geteilt, wobei gilt $y_1 = y_{g2}$ (Basisvariablen wird nicht berücksichtigt). Der Quotient wird wieder abgerundet:

$[0] y_{g1} + [1] x_2 + y_1 = [1]$

Die Gomory-Zeile wird als unterste Zeile eingefügt;

Gomery-Verfahren Beispiel


Es wird nun der 2. Simplexschritt durchgeführt, wobei die beiden untersten Zeilen nicht berücksichtigt werden, weil diese Gomory-Zeilen darstellen. Die Nichtbasisvariable in dessen Zeilen sich das Pivotelement befindet wird mit der neuen Gomory-Variable getauscht:

Gomery-Verfahren Beispiel

Das Verfahren ist beendet, da das Optimaltableau vorliegt (alle Werte der Zielfunktionszeile sind positiv). Die ganzzahlige Lösung für das obige Problem ist demnach:

$x_1 = 1$ und $x_2 = 1$ mit dem Zielfunktionswert:

$f(x_1, x_2) = 2 \cdot 1 +  1 = 3$ 

Dies entspricht auch der grafischen Lösung aus dem Abschnitt Grafisches Verfahren.