zum Artikel Simplex-Verfahren#Mathematische Beschreibung
Simplexbeschreibung

zum Artikel Simplex-Verfahren#Beispielrechnung
Syntaxbeispiele

Geordnete Liste der Belege: [1]


Die Schritte eines Simplexverfahrens lassen sich am einfachsten anhand von Beispielen beschreiben; mathematische Formeln dazu können wie weiter unten meist leicht aus diesen abgeleitet werden.

Beispielrechnung 1

Bearbeiten

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; in der Praxis können Optimierungsaufgaben leicht aus hunderttausenden Variablen und Nebenbedingungen bestehen, so dass man ihnen nicht einmal die Existenz einer Lösung und schon gar nicht den bestmöglichen Lösungswert 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 an, benötigt man dafür zunächst 1 Stunde die Maschine A und danach 1 Stunde die Maschine B. 1 ME von Produkt 2 dagegen 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, mit

 

Diese Funktion ist die sogenannte Zielfunktion, und   ist die Zielvariable.

Überführung in die Buchform

Bearbeiten

Für das Simplex-Verfahren werden die Ungleichungen zunächst in Gleichungen überführt, wobei

  1. sämtliche Variablen des Systems nichtnegative Werte annehmen müssen
  2. eine Teilmenge der Variablen bezüglich der restlichen Variablen freigelegt sein soll

Eine Aufgabestellung in dieser Form nennt sich Aufgabestellung in Buchform (englisch dictionary form, Benennung von Chvátal[1]), das dazugehörige Gleichungssystem ist in parametrischer Form.

Falls wie in der obigen Aufgabe die Strukturvariablen bereits nichtnegativ sein müssen und die Nebenbedingungen ausschließlich aus Ungleichungen bestehen, ist das besonders einfach, indem man sogenannte Schlupfvariablen  ,   und   einführt, welche hier die nicht genutzten Zeiten der einzelnen Maschinen darstellen. Offensichtlich dürfen Schlupfvariablen nicht negativ sein. Nun lässt sich das Problem unmittelbar so formulieren, dass die Schlupfvariablen bezüglich der ursprünglichen Variablen freilegt sind.

Maximiere die Zielvariable   unter den Nebenbedingungen:

 

    

Bestimmung eines zulässigen Ausgangssystems (Phase I)

Bearbeiten

Auch eine zulässigen Ausgangslösung ist in diesem Beispiel bereits gegeben, da die konstanten Größen des obigen Gleichungssystems keine negativen Werte enthalten.

In so einem Fall kann man die unabhängigen Variablen des Gleichungssystems (Nichtbasisvariablen) 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  ; die zugehörige Basislö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, da die Maschinen nicht genutzt werden.

Verbesserung der Ausgangslösung (Phase II)

Bearbeiten

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


Auswahl eines Pivotelements:

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

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.


Wiederholung der Simplexschritte:

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

 

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.


Datenstrukturen und Umwandlungsformeln

Bearbeiten

Das parametrische Gleichungssystem

 

kann man auch über eine Simplextafel, auch Simplex-Tableau genannt, darstellen:

 

 

 

Die Umwandlung der Einträge des Simplextableaus von einem Schritt auf den nächsten ist wie oben im Beispiel leicht abzuleiten und lässt sich in folgendem Schema zusammenfassen:

 

     

 

Hier steht das Zeichen   für den gemeinsamen Nenner des Gleichungssystems, das Zeichen   für den Zähler des Pivotelements,   für einen sonstigen Eintrag der Pivotzeile,   für einen sonstigen Eintrag der Pivotspalte, und   für einen beliebigen Eintrag abseits von Pivotzeile und Pivotspalte. Einträge der Zielbeitragszeile ( ) und der Basiswertspalte ( ) werden nach denselben Regeln umgewandelt.


Über die große Anzahl von Lehrbüchern verteilt findet sich auch eine große Anzahl verschiedener Darstellungen einer linearen Optimierungsaufgabe, und die Meinungen über die Zweckmäßigkeit der jeweils ausgewählten Darstellung gehen weit auseinander. Als Beispiel einer aufgeblähten und eher umständlichen, aber trotzdem weit verbreiteten Darstellung sei folgendes Spaltenbasistableau angeführt:

 


 

 

 

wobei die Bedeutung der einzelnen Einträge keineswegs festgeschrieben und sorgfältig zu dokumentieren ist. Zum Beispiel:


 

 

 


               
                 
                 
                 
                 


"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 Gesamtdeckungsbeitrags."

Der einzige Vorteil dieser Darstellung scheint darin zu liegen, dass sich ihre Umwandlung von einem Schritt auf den nächsten als Matrizenmultiplikation beschreiben lässt:

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.

Einträge in Bruchzahlform

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.


  1. a b Vašek Chvátal (1983): Linear Programming., Freeman and Company, ISBN 0-7167-1587-2