Verfahren von Gomory

In diesem Abschnitt soll das Verfahren von Gomory aufgezeigt werden. Hierbei handelt es sich um ein Schnittebenenverfahren, bei welchem eine ganzzahlige Lösung des linearen Optimierungsproblems resultiert. In diesem Abschnitt soll aufgezeigt werden, wie ein lineares Maximierungsproblem mit Ganzzahligkeitsbedingung mittels primalen und dualen Simplexalgorithmus und dem Schnittebenenverfahren von Gomory gelöst werden kann. Der primale und duale Simplex-Algorithmus sollte bereits aus dem Kurs Operations-Research 1 bekannt sein. Im Kapitel Wiederhoung: Operations Research 1 werden beide nochmals wiederholt.

Voraussetzungen:

1. Das lineare Optimierungsproblem muss in Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)
   
   
2. Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.
   
   
3. Es müssen nicht-negative Koeffizienten auf der rechten Seite der Nebenbedingungen vorliegen ($b_i \ge 0$, für alle $i$).
   
   
4. Die Werte der rechten Seite müssen ganzzahlig sein $b_i \in \mathbb{N}$.
   
   
5. Alle Koeffizienten (auch Zielfunktionskoeffizienten) müssen ganzzahlig sein oder mittels Multiplikation von $10$, $100$ usw. ganzzahlig gemacht werden können, d.h. wenn Dezimalzahlen vorliegen, dann endliche und keine unendlichen (endlich = $2,5$, unendlich = $1/3$). Liegen unendliche Dezimalzahlen vor, so ist das Verfahren beendet.
   
   

Vorgehensweise

1. Überführung des ganzzahligen Optimierungsproblems in die Normalform. Dazu wird für jede Nebenbedingung eine Schlupfvariable eingefügt und aus den Ungleichungen werden Gleichungen.
2. Eintragen der Normalform in das Ausgangstableau. Die Variablen der Zielfunktion (Entscheidungsvariablen) gehen in die Nichtbasis, die Schlupfvariablen in die Basis. Die Zielfunktionskoeffizienten werden mit (-1) multipliziert und in die letzte Zeile des Tableaus eingetragen. Die rechte Seite wird als letzte Spalte in das Tableau eingetragen. Mittig stehen die Koeffizienten der Nebenbedingungen.
   
   
3. Sind negative Werte auf der rechten Seite gegeben, wird für das Problem zunächst mittels dualen Simplexalgorithmus eine zulässige Lösung ermittelt. Diese liegt vor, wenn nur positive Werte auf der rechten Seite gegeben sind. Ist eine zulässige Lösung bestimmt bzw. liegt bereits eine zulässige Lösung vor (Werte der rechten Seite sind alle positiv), kann der primale Simplexalgorithmus angewandt werden, um eine optimale Lösung zu bestimmen. Eine optimale Lösung liegt dann vor, wenn die Werte der Zielfunktion im Tableau alle größer gleich Null sind.
   
   Der primale Simplexalgorithmus wird angewandt und die Ganzzahligkeitsbedingung aufgehoben, bis eine optimale Lösung vorliegt. Sind alle Werte der rechten Seite ganzzahlig ($b_i \in \mathbb{N}$), so ist die optimale Lösung gleich der optimalen ganzzahligen Lösung und das Problem wurde gelöst. Sind noch Werte auf der rechten Seite gegeben, die nicht ganzzahlig sind ($b_i \notin \mathbb{N}$), dann wird ein Gomory-Schnitt durchgeführt.
   
   
4. Für den Gomory-Schnitt wird eine Zeile ausgewählt, für welche die rechte Seite einen nicht ganzzahligen Wert annimmt. Für diese Zeile werden alle Brüche in einen ganzzahligen Anteil und einen Bruchanteil aus dem Intervall (0,1) gespalten. Die ganzzahligen Anteile werden auf die linken Seite, die Bruchanteile auf die rechte Seite gebracht. Die rechte Seite geht als Gomory-Zeile $y_{gi}$ wieder in das Tableau ein. Danach wird ein dualer Simplexschritt durchgeführt.

Beispiel: Verfahren von Gomory

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

u.d.N.

(1) $2x_1 + x_2 \le 10$   

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

(3) $x_1             \le 4$

$x_1, x_2 \ge 0$    und ganzzahlig

Überführung in die Normalform

Es werden als nächstes die Schlupfvariablen $y_i$ eingeführt um statt der Ungleichungen $\le$ Gleichungen $=$ zu erhalten. Wir erhalten somit die folgende Normalform:

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

 u.d.N.

(1) $2x_1 + x_2 + y_1 \le 10$   

(2) $-x_1 +  x_2 + y_2 \le 5$    

(3) $x_1              + y_3 \le 4$

$x_1, x_2, y_1, y_2, y_3 \ge 0$    und ganzzahlig

Alle Werte der rechten Seite sind positiv. Demnach wird zunächst der primale Simplexalgorithmus angewandt bis eine optimale Lösung erreicht ist.

Wir beginnen zunächst das obige Problem in das Simplextableau zu überführen. Dabei sind die Zielfunktionsvariablen (auch: Entscheidungsvariablen) $x_1$ und $x_2$ die Nichtbasisvariablen und die Schlupfvariablen die Basisvariablen. Die Zielfunktionszeile wird mit (-1) multipliziert und als letzte Zeile in das Tableau eingetragen. Die Werte der rechten Seite werden als letzte Spalte in das Tableau eingetragen:

Verfahren von Gomory

In dem obigen Tableau ist bereits eine zulässige (aber nicht optimale) Lösung gegeben. Die Basisvariablen nehmen immer die Werte der rechten Seite an, die Nichtbasisvariablen (NBV) sind immer Null:

$\overline{x} = \{0,0\}$

$\overline{y} = \{10, 5 , 4 \}$

Die Werte sind nicht-negativ (also größer gleich Null) und ganzzahlig. Demnach liegt hier eine zulässige, aber nicht optimale Lösung vor. Beim Vorliegen einer zulässigen Lösung kann der primale Simplexalgorithmus angewandt werden, um zu einer optimalen Lösung zu gelangen. Der nächste Schritt ist also die Bestimmung der optimale Lösung mittels primalen Simplexalgorithmus:

Primales Simplexverfahren - 1. Schritt

Da noch ein negativer Wert in der Zielfunktionszeile (unterste Zeile) gegeben ist, wird als nächstes ein weiterer Simplexschritt (primal) durchgeführt:

Primales Simplexverfahren - 2. Schritt

Das Tableau weist keine negativen Werte innerhalb der Zielfunktionszeile mehr auf. Die optimale Lösung ist somit erreicht:

$x_1 = \frac{5}{3}$, $x_2 = \frac{20}{3}$

$y_3 = \frac{7}{3}$ $y_1 = y_2 = 0$

Da das Ergebnis nicht ganzzahlig ist, ist die optimale Lösung nicht gleich der ganzzahligen optimalen Lösung. Wir müssen also als nächstes einen Gomory-Schnitt durchführen. Dazu wählen wir eine Zeile aus, für welche die rechte Seite nicht-ganzzahlige Werte annimmt. In allen drei Zeile nimmt die rechte Seite $b_i$ nicht-ganzzahlige Werte an, d.h. wir können eine beliebige Zeile auswählen.

Wir wählen im Weiteren die 1. Zeile aus dem Simplextableau:

$x_1 + \frac{1}{3} y_1 - \frac{1}{3} y_2 = \frac{5}{3}$

Wir spalten die nicht-ganzzzahligen Koeffizienten in eine ganzzahligen Anteil und in einen Bruchanteil auf. Wichtig ist, dass der Bruchanteil im Intervall (0,1) liegen muss.

Für unsere Gomory-Zeile gilt dann:

$x_1 +(0 +  \frac{1}{3}) y_1 + (-1 + \frac{2}{3}) y_2 = 2 + \frac{2}{3}$

Die ganzzahligen Anteile werden auf die linke Seite des Gleichheitszeichens gebracht, die Bruchanteile auf die rechte Seite:

$x_1 + 0 y_1 - 1 y_2 - 2 =  - \frac{1}{3} y_1 - \frac{2}{3} y_2 + \frac{2}{3}$

Da $y_1 \ge 0$ und $y_2 \ge 0$ sein müssen (Nichtnegativitätsbedingung), nimmt $- \frac{1}{3} y_1 - \frac{2}{3} y_2 \le 0$ an. Mit Berücksichtigung von $\frac{2}{3}$ ergibt sich dann:

$- \frac{1}{3} y_1 - \frac{2}{3} y_2 + \frac{2}{3} \le \frac{2}{3} $

Diese Gleichung nimmt bei $y_1 = y_2 = 0$ den Wert $\frac{2}{3}$ an. Mit zunehmenden $y_1$ bzw. $y_2$ wird das Ergebnis kleiner, damit ist diese Gleichung also immer $\le \frac{2}{3}$.

Andererseits wird die linke Seite der Gomory-Zeile ganzzahlig:

$x_1 - y_2 - 2 \in \mathbb{N}$

weil die Variablen $x_1$ und $y_2$ nur ganze Werte annehmen. Da linke und rechte Seite gleich sind, kann auch die rechte Seite nur ganzzahlige Werte annehmen. Der nächste ganzzahlige Wert unter $\frac{2}{3}$ ist Null:

$- \frac{1}{3} y_1 - \frac{2}{3} y_2 + \frac{2}{3} \le 0 $

Es wird nun die Konstante $\frac{2}{3}$ auf die rechte Seite des Ungleichzeichens gebracht:

$- \frac{1}{3} y_1 - \frac{2}{3} y_2  \le - \frac{2}{3} $

Einfügen der Schlupfvariablen $y_{g1}$ um eine Gleichung zu erhalten:

$- \frac{1}{3} y_1 - \frac{2}{3} y_2 + y_{g1} = - \frac{2}{3} $

Gomory-Zeile in das Tableau einfügen:

Gomory-Zeile

Als nächstes wird der duale Simplexalgorithmus angewandt, um eine zulässige Lösung zu erhalten:

Dualer Simplexalgorithmus

Nach Anwendung des dualen Simplexalgorithmus resultiert die optimale Lösung des ganzzahligen Optimierungsproblems mit:

$x_1 = 2$ und $x_2 = 6$ sowie $y_1 = 0$, $y_2 = 1$ und $y_3 = 2$.

Bei dieser Lösung sind also in der Nebenbedingung 1 keine Kapazitäten mehr vorhanden ($y_1 = 0$), in der Nebenbedingung 2 noch 1 Kapazität ($y_2 = 1$) und in der Nebenbedingung 3 noch 2 Kapazitäten ($y_3 = 2$) vorhanden.

Videoreihe zum Gomory-Verfahren

1. In diesem Video werden die Voraussetzungen für die Anwendungen des Gomory-Verfahrens aufgezeigt.

2. Es folgt das Einfügen der Schlupfvariablen um das ganzzahlige Optimierungsproblem in die Normalform zu überführen:

 
3. Auswahl der Pivotspalte und Pivotzeile:

 
4. Der erste primale Simplexschritt wird durchgeführt:

 
5. Der zweite primale Simplexschritt wird durchgeführt:

 
6. Auswahl der Gomory-Zeile:

 
7. Anwendung des dualen Simplexalgorithmus':