Inhaltsverzeichnis
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:
- Das lineare Optimierungsproblem muss in Standardform vorliegen (Maximierungsproblem, Kleiner/Gleich-Nebenbedingung, Nichtnegativitätsbedingung)
- Die Standardform muss dann in die Normalform überführt werden (Gleichheitsbedingung) mittels Einführung von Schlupfvariablen.
- Es müssen nicht-negative Koeffizienten auf der rechten Seite der Nebenbedingungen vorliegen (
, für alle ). - Die Werte der rechten Seite müssen ganzzahlig sein
. - Alle Koeffizienten (auch Zielfunktionskoeffizienten) müssen ganzzahlig sein oder mittels Multiplikation von
, usw. ganzzahlig gemacht werden können, d.h. wenn Dezimalzahlen vorliegen, dann endliche und keine unendlichen (endlich = , unendlich = ). Liegen unendliche Dezimalzahlen vor, so ist das Verfahren beendet.
Vorgehensweise
- Überführung des ganzzahligen Optimierungsproblems in die Normalform. Dazu wird für jede Nebenbedingung eine Schlupfvariable eingefügt und aus den Ungleichungen werden Gleichungen.
- 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.
- 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 (), 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 ( ), dann wird ein Gomory-Schnitt durchgeführt. - 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
wieder in das Tableau ein. Danach wird ein dualer Simplexschritt durchgeführt.
Beispiel: Verfahren von Gomory
u.d.N.
(1)
(2)
(3)
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
u.d.N.
(1)
(2)
(3)
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)
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:
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:
Da noch ein negativer Wert in der Zielfunktionszeile (unterste Zeile) gegeben ist, wird als nächstes ein weiterer Simplexschritt (primal) durchgeführt:
Das Tableau weist keine negativen Werte innerhalb der Zielfunktionszeile mehr auf. Die optimale Lösung ist somit erreicht:
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
Wir wählen im Weiteren die 1. Zeile aus dem Simplextableau:
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
Für
Für
Für unsere Gomory-Zeile gilt dann:
Die ganzzahligen Anteile werden auf die linke Seite des Gleichheitszeichens gebracht, die Bruchanteile auf die rechte Seite:
Methode
Da
Diese Gleichung nimmt bei
Andererseits wird die linke Seite der Gomory-Zeile ganzzahlig:
weil die Variablen
Es wird nun die Konstante
Einfügen der Schlupfvariablen
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
Heißt also:
Nur rechte Seite betrachten und kleiner gleich Null setzen:
Konstante auf rechte Seite bringen:
Gomory-Zeile in das Tableau einfügen:
Als nächstes wird der duale Simplexalgorithmus angewandt, um eine zulässige Lösung zu erhalten:
Nach Anwendung des dualen Simplexalgorithmus resultiert die optimale Lösung des ganzzahligen Optimierungsproblems mit:
Bei dieser Lösung sind also in der Nebenbedingung 1 keine Kapazitäten mehr vorhanden (
Methode
Die Zielfunktion nimmt den Wert:
Videoreihe zum Gomory-Verfahren
1. In diesem Video werden die Voraussetzungen für die Anwendungen des Gomory-Verfahrens aufgezeigt.
This browser does not support the video element.
2. Es folgt das Einfügen der Schlupfvariablen um das ganzzahlige Optimierungsproblem in die Normalform zu überführen:
This browser does not support the video element.
3. Auswahl der Pivotspalte und Pivotzeile:
This browser does not support the video element.
4. Der erste primale Simplexschritt wird durchgeführt:
This browser does not support the video element.
5. Der zweite primale Simplexschritt wird durchgeführt:
This browser does not support the video element.
6. Auswahl der Gomory-Zeile:
This browser does not support the video element.
7. Anwendung des dualen Simplexalgorithmus':
This browser does not support the video element.
Weitere interessante Inhalte zum Thema
-
Operations Research 2: Überblick
Vielleicht ist für Sie auch das Thema Operations Research 2: Überblick (Grundlagen des Operations Research 1) aus unserem Online-Kurs Operations Research 2 interessant.