Cutting Planes

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

Idee

Die grundlegende Idee besteht darin, den Lösungsraum durch das Hinzufügen weiterer Restriktionen (sogenannte Cutting Planes) so einzuengen, dass seine Ecken in ganzzahligen Punkten liegen. Dadurch liegen auch die möglichen Optimallösungen in ganzzahligen Punkten.

Vorgehensweise

Vor dem ersten Schritt sollten alle Ungleichungen durch den jeweils größten gemeinsamen Teiler aller aij der Zeile geteilt werden. Dabei wird die rechte Seite auf den nächstkleineren ganzzahligen Wert gerundet.

Beispiel: aus 3*x1+ 9*x2 ≤20 | ggT = 3 wird

x1+ 3*x2 ≤ 6


(1) Man sucht das kontinuierliche Optimum des Problems mit Hilfe des Simplex-Algorithmus. Falls dieses ganzzahlig ist, ist die Lösung gefunden.

(2) Sonst fügt man einen Cutting Plane in das Tableau ein:

Quellzeile des Cutting Planes: Zeile i, in der bi den größten gebrochenen Anteil hat.
Man hat nun eine Quellzeile r in der Form: BVr + ∑ (arj*NBV j) = br
Umformung der Quellzeile r: Man zerlegt alle arj und das br jeweils in den nächstkleineren ganzzahligen grj und in einen nicht-ganzzahligen frj Anteil:
arj = grj + frj ∀j mit 0≤frj <1 und grj ≤ arj bzw.
br = gr + fr mit 0 ≤ fr und gr ≤ br
Die Quellenzeile r hat nun die Form: BVr + ∑ ((frj+grj)*NBV j) = gr +fr
Nun bringt man alle ganzzahligen Anteile auf dir rechte Seite der Gleichung: ∑ (frj*NBV j) = gr +fr - ∑ (grj*NBV j) - BVr
und fasst die ganzzahligen Anteile in einer neuen Schlupfvariablen zusammen yneu = gr - ∑ (grj*NBV j) - BVr .
Die so erhaltene Zeile ∑(frj*NBV j) = fr + yneu muss nun nur noch in die gleiche Form wie die übrigen Gleichungen gebracht werden. Alle Anteile, die eine Variable enthalten stehen auf der linken, der Anteil ohne Variable steht auf der rechten Seite der Gleichung. Dabei ist zu beachten, dass die Variable yneu kein Vorzeichen haben darf!
Die so erhaltene Zeile yneu - (frj*NBV j) = - fr wird als neue Zeile in das Simplex Tableau eingefügt und man kehrt zu Schritt (1) zurück.
Dieser Cutting-Plane beschneidet den Lösungsraum so, dass er das kontinuierliche Optimtium nicht mehr enthält. Um ihn in die graphische Lösung eintragen zu können, muss yneu in Abhängigkeit der Strukturvariablen x ausgedrückt werden.

Beispiel

max G = 5x1 + 2x2
u.d. NB 4xi-2x2 ≤17
2x1+8x2 ≤31
x1,x2 ≥0 & ganzzahlig

(0) wenn möglich Runden

1.NB: 4xi-2x2 ≤17 |:2
(Pfeil) 2xi-1x2 ≤8
2.NB: 2x1+8x2 ≤31 |:2
(Pfeil) 1x1+4x2 ≤31

(1) Simplex-Tableau erstellen und kontinuierliches Optimum berechnen Grafik / Tabelle einfügen: Anfangstableau & Endtableau Anfangstableau:

x1 x2
z -5 -2 0
y1 2 -1 8
y2 1 4 15

Abb 1: Anfangstableau


Nach 2 Simplex-Iteration kommt man auf folgendes kontinuierliche Optimum :



y1 y2
z 2 1 31
x1 4/9 1/9 47/9
x2 -1/9 2/9 22/9

Abb 2: kontinuierliches Optimum


Da sowohl x1 als auch x2 nicht ganzzahlig sind, muss man einen Cutting Plane einfügen.--> Schritt (2)

(2) Als Quellzeile des Cutting Planes wählt man die Zeile von x2.

Quellzeile: x2 + y1* -1/9 +y2* 2/9 = 22/9
getrennt: x2 + y1*(-1 + 8/9) +y 2*(0+1/9) = 2 + 4/9
mit neuer Schlupfvariable: x2 + y1*8/9 + y 2*1/9 = 2 + 4/9 - y1 = 4/9 + y 3
Gleichung in richtige Form für Simplex-Tableau gebracht: y3 - y1*8/9 - y 2*1/9 = -4/9

Erweitertes Simplex-Tableau:

y1 y2
z 2 1 31
x1 4/9 1/9 47/9
x2 -1/9 2/9 22/9
y3 -8/9 -2/9 -4/9

Abb 3: 1. erweitertes Tableau


--> Schritt (1)


(1) Nach 2 weiteren Iterationen kommt man zu folgendem kontinuierlichem Optimum:

y2 y3
z 1/2 9/4 30
x1 0 1/2 5
x2 1/4 -1/8 5/2
y1 1/4 -9/8 1/2

Abb 4: kontinuierliches Optimum des 1. erweitertes Tableaus


Da x2 nicht ganzzahlig ist, muss ein weiterer Cutting Plane eingefügt werden.--> Schritt (2)

(2) Als Quellzeile des Cutting Planes wählt man die Zeile von x2.

Quellzeile: x2 + y2* 1/4 +y3* -1/8 = 5/2
getrennt: x2 + y1*(0 + 1/4) +y 3*(-1 + 7/8) = 2 + 1/2
mit neuer Schlupfvariable: x2 + y2*1/4 + y 3*7/8 = 2 + 1/2 - y3 = 1/2 + y 4
Gleichung in richtige Form für Simplex-Tableau gebracht: y4 - y2*1/4 - y 3*7/8 = -1/2

Erweitertes Simplex-Tableau:

y2 y3
z 1/2 9/4 30
x1 0 1/2 5
x2 1/4 -1/8 5/2
y1 1/4 -9/8 1/2
y4 -1/4 -7/8 -1/2

Abb 5: 2. erweitertes Tableau


--> Schritt (1)


(1) Nach 2 weiteren Iterationen kommt man zu folgendem kontinuierlichem Optimum:

y1 y4
z 1/4 9/4 29
x1 1/4 2/7 5
x2 -1/2 -13/56 2
y2 1/4 -9/8 1/2
y3 -1/2 -1/2 0

Abb 6: kontinuierliches Optimum des 2. erweitertes Tableaus


Die gefundene Lösung ist ganzzahlig, also ist das ganzzahlige Optimum gefunden.


Bemerkungen

Natürlich gibt es auch in der ganzzahligen Optimierung Probleme, welche unlösbar sind oder eine unbegrenzte Lösung besitzen. Solche Probleme erkennt man genau wie in der lineare Planungsrechnung:

(1) Unlösbarkeit: Ein bi der rechten Seite ist negativ, aber für alle aij dieser Zeile gilt: aij ≥ 0.

(2) unbegrenzte Lösung: Ein Zielfunktionskoeffizient cj negativ, aber für alle aij dieser Spalte p gilt: aip ≤0. Somit kann kein Pivotelement gewählt werden und man hat den Fall des Schlaraffenlandes.


Literatur

Müller-Merbach (1973): Operations Research Kapitel 11.2;

Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Wintersemester 2007/2008

Vorlesungsmitschnitt zum Thema Cutting Planes