Kursangebot | Operations Research 2 | Verfahren von Gomory

Operations Research 2

Verfahren von Gomory

ingenieurkurse JETZT WEITER LERNEN!

Weitere Lernvideos sowie zahlreiche Materialien erwarten dich:
Komplettpaket für Ingenieurstudenten


3108 Lerntexte mit den besten Erklärungen

501 weitere Lernvideos von unseren erfahrenen Dozenten

5120 Übungen zum Trainieren der Inhalte

3108 informative und einprägsame Abbildungen

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

Hinweis

Es liegt die Standardform vor. Alle Koeffizienten sind ganzzahlig, die rechte Seite ist ganzzahlig. Die Voraussetzungen für die Anwendung des Gomory-Verfahrens sind also gegeben.

Ü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:

Schnittebenenverfahren, Gomory
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:

Gomory, Simplexalgorithmus, primal
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, Gomory, Schnittebenenverfahren
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.

Beispiel

Haben wir zum Beispiel den Bruch $\frac{1}{3}$ gegeben, so liegt dieser bereits im Intervall (0,1). Der ganzzahlige Anteil ist demnach 0 und der Bruchanteil $\frac{1}{3}$.

Für $\frac{7}{3}$ zum Beispiel ist $\frac{6}{3} = 2$ der ganzzahlige Anteil und $\frac{1}{3}$ der Bruchanteil zwischen (0,1). Also $2 + \frac{1}{3}$.

Für $-\frac{7}{3}$ muss das Minuszeichen für den ganzzahligen Anteil übernommen werden, der Bruchanteil darf nicht negativ werden. Wir müssen nun also statt 2 + Bruchanteil von der -3 ausgehen und den Anteil addieren, so dass wieder $-\frac{7}{3}$ resultiert: $ -3 + \frac{2}{3}$.

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}$

Methode

$x_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} $

Hinweis

Nachdem der ganzzahlige Anteil auf die rechte Seite und der Bruchanteil auf die linke Seite gebracht wurden, sind die folgenden Schritte jedes Mal identisch. Es reicht also aus, wenn du ab dann die rechte Seite betrachtest und $\le 0$ setzt und dann die Konstante auf die rechte Seite des Ungleichzeichen bringst und die Schlupfvariable einfügst.

Heißt also:

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

Nur rechte Seite betrachten und kleiner gleich Null setzen:

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

Konstante auf rechte Seite bringen:

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


Gomory-Zeile in das Tableau einfügen:

Gomory-Zeile
Gomory-Zeile


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

Gomory, Schnittebenenverfahren
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.

Methode

Die Zielfunktion nimmt den Wert: $x_1 + 2x_2 = 2 + 2 \cdot 6 = 14$ an.

 

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':