Benutzer:Schafholt/Beispielrechnung Simplex-Verfahren

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Beispielrechnung

[Bearbeiten | Quelltext bearbeiten]
Veranschaulichung des Beispiels (Erklärung siehe Text)

Anhand eines einfachen Beispiels zur Produktionsplanung mit zwei Variablen soll der Lösungsweg Schritt für Schritt gezeigt werden. In diesem einfachen Fall ist eine Optimallösung leicht zu finden. Reale Probleme können dagegen leicht aus mehreren Hunderttausend Variablen und Nebenbedingungen bestehen, so dass man ihnen meistens die Existenz einer Lösung oder den Wert einer Optimallösung nicht unmittelbar ansehen kann.

Eine Firma stelle 2 verschiedene Produkte her. Es stehen 3 Maschinen A, B, C zur Verfügung. Maschine A hat eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden, Maschine B von 150 Stunden und Maschine C von 180 Stunden. Eine Mengeneinheit (ME) von Produkt 1 liefert einen Deckungsbeitrag von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man 1 ME von Produkt 1, benötigt man dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde die Maschine B. 1 ME von Produkt 2 belegt nacheinander 2 Stunden Maschine A, 1 Stunde Maschine B und 3 Stunden Maschine C.

Daraus erhält man folgende Bedingungen:


Die Firma möchte den Deckungsbeitrag maximieren:

ist daher der sogenannte Zielfunktionswert.

Eventuelle Fixkosten sind unabhängig von der Produktionsmenge und können daher einfach am Ende der Berechnung vom Gesamtdeckungsbeitrag abgezogen werden, um den Gewinn zu erhalten.

Überführung in Gleichungen

[Bearbeiten | Quelltext bearbeiten]

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt. Dazu führt man so genannte Schlupfvariablen , und  ein, welche die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen die Schlupfvariablen nicht negativ sein. Damit lässt sich das Problem so formulieren, dass man die Schlupfvariablen bezüglich der ursprünglichen Variablen freilegt. Ein derart genormtes Gleichungssystem heißt im Englischen dictionary (Benennung von V. Chvátal):

Maximiere die Zielfunktion  unter den Nebenbedingungen:


Die obigen Gleichungen kann man in das vorher beschriebene Simplex-Tableau übertragen:

      -----------------------------
      |  x1     x2   | rechte Seite
  ---------------------------------
  -z  |  300   500  |      0
  ---------------------------------
  y1  |   1      2   |      170  = b1
  y2  |   1      1   |      150  = b2
  y3  |   0      3   |      180  = b3

In der Kopfzeile stehen die Nichtbasisvariablen mit dem Wert 0, während die Basisvariablen in der ersten Spalte stehen. In der obersten Zeile – der Gleichung für die Zielfunktion – stehen die Zielfunktionskoeffizienten , also 300 und 500. Auf der rechten Seite steht die aktuelle Basislösung, was in diesem Fall genau ist. In der obersten Zeile der rechten Seite steht das Negative des Zielfunktionswertes für die aktuelle Basislösung, im Beispiel also das Negative des Gesamtdeckungsbeitrag. Dieser ist momentan 0, da nichts produziert wird.

Bestimmung einer zulässigen Ausgangslösung (Phase I)

[Bearbeiten | Quelltext bearbeiten]

Da die konstanten Größen des obigen Gleichungssystems nichtnegativ sind, kann man die unabhängigen Variablen des Gleichungssystems (Basisvariablen) auf Null setzen und so eine triviale zulässige Lösung angeben, mit der direkt die Phase II gestartet werden kann:

Die Variablen bilden eine zulässige Basis , deren Basismatrix die Einheitsmatrix ist. Die zugehörige Basislösung ist also . Diese Lösung entspricht dem Fall, dass nichts produziert wird (). Die Restkapazität der Maschinen, die durch die Werte der angegeben wird, ist hier deren Gesamtkapazität (170, 150 und 180), da die Maschinen nicht genutzt werden.

Verbesserung der Lösung mittels einer Simplex-Iteration (Phase II)

[Bearbeiten | Quelltext bearbeiten]

Da die soeben berechnete Ausgangslösung unbefriedigend ist, wird nun in Phase II versucht, bessere zulässige Lösungen zu finden.

Auswahl einer Pivotspalte und -zeile

[Bearbeiten | Quelltext bearbeiten]

In einer Simplex-Iteration wird eine Basisvariable gegen eine der unabhängigen Variablen ausgetauscht. In Frage kommen Nichtbasisvariablen mit positivem Zielfunktionskoeffizienten, da deren Aufnahme in die Basis den Zielfunktionswert verbessern kann. Diese Variable soll so weit erhöht werden, bis eine oder mehrere der Basisvariablen auf 0 stoßen. Eine beliebige dieser Basisvariablen verlässt dann die Basis und wird gegen die Nichtbasisvariable ausgetauscht.

Variable  hat den positiven Zielfunktionskoeffizienten 300; indem sie erhöht wird, lässt sich die Zielfunktion vergrößern; sie kommt also als basis-eintretende Pivotvariable in Frage. Solange  die einzige erhöhte Nichtbasisvariable ist, soll diese Erhöhung  durch folgende Bedingungen eingeschränkt werden:

In anderen Worten,

 oder 

Die erste der Basisvariablen, die in diesem Fall auf Null stößt, erhält man über den Quotienten  und ist . Diese ist die Variable, die gegebenenfalls gegen  ausgetauscht werden müsste. Der neue Wert der Zielfunktion wäre dann .


Auch Variable  hat mit 500 einen positiven Zielfunktionskoeffizienten, kommt also ebenfalls als eintretende Nichtbasisvariable in Frage. Nach der obigen Vorgehensweise erhalten wir

und somit

Der minimale Quotient  gehört zur Basisvariable . Der neue Wert der Zielfunktion wäre .


Für den Zuwachs der Zielfunktion in diesem Schritt ist es also am günstigsten, den ersten Fall zu wählen und die unabhängige Variable  anstelle der Basisvariablen  freizulegen.

Durchführung eines Austauschschrittes

[Bearbeiten | Quelltext bearbeiten]

Mit dem Austauschschritt wird die Basisvariable gegen die Nichtbasisvariable ausgetauscht. Zuerst legen wir in der Gleichung für die unabhängige Unbekannte frei,

und anschließend ersetzen wir in den restlichen Gleichungen für den so erhaltenen Ausdruck:


Das führt zu den oben beschriebenen Verwandlungsregeln für das Simplex-Tableau nach dem Pivotelement . Wenn die Zeile von besetzt und die Spalte von , dann ist das neue Gleichungssystem

Die Unbekannte  ist in die Basis gerückt, die jetzt unabhängige Unbekannte  ist eine Nichtbasisvariable und erscheint in der Kopfzeile.

Diese Lösung bedeutet: Es werden  ME von Produkt 1 (Gleichung mit freigelegtem ) produziert. Von Produkt 2 wird nichts gefertigt ( ist Nichtbasisvariable). Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 45.000 Euro. Maschine A steht  Stunden pro Monat still (sie läuft nur 150 der 170 möglichen Stunden). Maschine B hat keine Leerlaufzeit. Maschine C steht  Stunden still, das heißt, sie wird überhaupt nicht benötigt. Dies ergibt sich auch direkt aus der Aufgabenstellung: Maschine C wird nur bei der Herstellung von Produkt 2 benötigt. Da dieses nicht gefertigt wird, braucht man Maschine C noch nicht.


Das zum obigen Gleichungssystem gehörende neue Simplex-Tableau ist

      -----------------------------
      |  yB     x2   | rechte Seite
  ---------------------------------
  -z  |  -300   200  |      -45000
  ---------------------------------
  yA  |  -1      1   |       20  = b1
  x1  |   1      1   |      150  = b2
  yC  |   0      3   |      180  = b3

Die Einträge des neuen Simplex-Tableaus können anhand der oben angeführten Formeln errechnet werden.

Nochmalige Verbesserung der Lösung

[Bearbeiten | Quelltext bearbeiten]

Da die Zielfunktion im entstandenen Simplex-Tableau noch einen positiven Koeffizienten enthält, kann man die Lösung noch verbessern. Dies geschieht mittels einer weiteren Simplex-Iteration. Bei der Auswahl des Pivotelementes kommt nur die Unbekannte in Frage, da nur hier der Zielfunktionskoeffizient positiv ist. Die Basisvariable des Pivots ergibt sich aus

und somit

Damit ist Zeile die einzige Basisunbekannte, die für einen Pivot in Frage kommt. Die Basisvariable wird gegen die Nichtbasisvariable ausgetauscht; das Pivotelement ist . Mit den gleichen Umrechnungen wie oben erhält man als neues Gleichungssystem


beziehungsweise ein neues Simplex-Tableau

      -----------------------------
      |  yB     yA   | rechte Seite
  ---------------------------------
  -z  | -100   -200  |   -49000
  ---------------------------------
  x2  |  -1      1   |       20 
  x1  |   2     -1   |      130 
  yC  |   3     -3   |      120

Da die Zielfunktion nun keine positiven Koeffizienten mehr enthält, ist eine optimale Lösung erreicht. Es werden  ME von Produkt 1 und  ME von Produkt 2 hergestellt. Damit erzielt die Firma einen Gesamtdeckungsbeitrag von 49.000 Euro. Maschine A und Maschine B sind voll ausgelastet. Maschine C läuft 60 Stunden und hat daher noch eine ungenutzte Kapazität von Stunden.


Einträge in Bruchzahlform

[Bearbeiten | Quelltext bearbeiten]

Das obige Beispiel wurde in algebraischer Notation gelöst, indem man im Gleichungssystem die Basisvariablen bezüglich der restlichen, unabhängigen Variablen freilegt. Um Rundungsfehler zu vermeiden, kann man mit Bruchzahlen arbeiten und einen gemeinsamen Nenner für das gesamte Gleichungssystem wählen (dass dieser Nenner oben immer war, ist Zufall). Um in jedem Schritt den gemeinsamen Nenner für das Gesamtsystem zu finden, müssen wir die Einträge nicht zusätzlich analysieren. Falls das Startsystem ganzzahlig ist (was sich normalerweise durch Erweiterung erreichen lässt), gilt die Regel:

  • Der Zähler des gewählten Pivotelements ist ein gemeinsamer Nenner für das darauffolgende System

Wenn wir die neuen Tableau-Einträge mit diesem gemeinsamen Nenner multiplizieren, erhalten wir stets ganzzahlige Zähler. Bei der Berechnung dieser Zähler für die neuen Tableau-Einträge wird dann ungeprüft durch den alten Nenner geteilt, wobei das Ergebnis ganzzahlig sein muss.


Als Beispiel für diese Vorgehensweise lösen wir dieselbe Aufgabe wie oben noch einmal mit Dantzigs Pivotauswahl; hierbei wird als eingehende Pivotvariable diejenige mit größtem Zielfunktionskoeffizienten gewählt:

Durch Erhöhung der unabhängigen Variable lässt sich die Zielfunktion vergrößern; die erste der Basisvariablen, die in diesem Fall auf Null stößt, ist . Folglich kann man  anstelle von freilegen und erhält folgendes System mit :

Wenn man die unabhängige Variable erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist . Folglich legt man  anstelle von frei und erhält folgendes System mit :

Wenn man die unabhängige Variable erhöht, vergrößert man die Zielfunktion; die erste der Basisvariablen, die dann auf Null stößt, ist . Folglich legt man  anstelle von frei und erhält folgendes System mit :

Die Zielfunktion hat Wert und lässt sich nicht mehr erhöhen; die Lösung ist wie oben .  Wir beobachten nebenher, dass Dantzigs Pivotauswahl im Vergleich zur anfangs gewählten Alternative einen Schritt mehr gebraucht hat, um zur Lösung zu gelangen.