Dat sind wir ...
 
Home
Uni
AImSIiAM
Informatik
BWL
 - IBL
 - WI
 - OR + UF
Maschinenbau
Seminare
Diplomarbeit
Copy + Down
 
Reisen
Musik

 friese-total.de
   Home     Uni     Reisen     Musik 
   Sitemap 

Simplex-Verfahren

Das Simplex-Verfahren ist eine Lösungsmethode um Lineare Optimierungsmodelle der Form
Max cTx
unter den Nebenbedingungen
Ax=b
x >= 0
zu lösen.
Diese Form bezeichnet man auch als Standardform, alle anderen linearen Optimierungsmodelle (z.B. Min cTx oder Ax > b etc.) lassen sich aber in diese Standardform umwandeln, so daß das Simplex-Verfahren generell anwendbar ist (wichtig ist nur, daß das Lineare Optimierungsproblem in der obigen Standardform ist!).

Beispiel:
Ein Unternehmen stellt zwei Güter her, welche mit Hilfe von drei Maschinen produziert werden. Die entsprechenden Daten sind der folgenden Tabelle zu entnehmen.
 
Produkt 1 Produkt 2 Einheit max. Kapazität [Min]
Maschine 1 4 2 Min/St 200
Maschine 2 2 4 Min/St 200
Maschine 3 2 2 Min/St 120
DB pro Einheit 150 100 DM/St
 
Die Zielsetzung besteht darin, ein Produktionsprogramm zu bestimmen, welches den Gesamtdeckungsbeitrag maximiert (Operative Programmplanung bei mehreren Engpässen).

Entscheidungsfrage:

    Wieviel soll von Produkt 1, wieviel von Produkt 2 hergestellt werden?
Entscheidungsvariablen:
    x1 = Anzahl der produzierten Menge von Produkt 1
    x2 = Anzahl der produzierten Menge von Produkt 2
Nebenbedingungen:
  • Maximale Kapazität pro Maschine

    • 4x1 + 2x2 <= 200
    2x1 + 4x2 <= 200
    2x1 + 2x2 <= 120
  • Nichtnegativität

    • x1, x2 >= 0
Zielfunktion:
    Maximiere DB also
    150x1 + 100x2 ---> Max
Zunächst wird diese Problem in mathematischer Form dargestellt, also:
Max cTx
unter den Nebenbedingungen
Ax<=b
x >= 0
Mit
    cT = (150, 100)
    x = x1, x2
    A= 4 2
    2 4
    2 2
    bT = (200, 200, 120)
Das Simplex-Verfahren beinhaltet insgesamt 10 Schritte:

Schritt 1: Überführen in Standardform

Die Forderung für das Simplexstarttableau ist Ax=b (und nicht wie hier Ax<=b). Man behilft sich, indem für jede Nebenbedingung ein sog. Schlupfvariable eingeführt wird, die die Ungleichung dann in eine Gleichung umwandelt:
    4x1 + 2x2 + x3                 = 200
    2x1 + 4x2         + x4         = 200
    2x1 + 2x2                 + x5 = 120

Schritt 2: Aufstellen des Start-Tableaus

Damit kann nun das Start-Tableau für das Simplex-Verfahren direkt angegeben werden. Dabei werden die Koeffizienten der Nebenbedingungen und deren Funktionswert zeilenweise eingetragen. In die unterste Zeile wird die Zielfunktion mit negativem Vorzeichen eingetragen.
     
    x1 x2 x3 x4 x5 Funktionswert
    4 2 1 0 0 200
    2 4 0 1 0 200
    2 2 0 0 1 120
    -150 -100 0 0 0 0
     
An diesem Tableau kann nun (und in jedem weiteren Schritt ebenfalls) direkt eine sog. Basislösung abgelesen werden. Diese ist hier (0, 0, 200, 200, 120), also die entsprechenden Funktionswerte der in dem Tableau stehenden Einheitsvektoren (bei x3, x4 und x5 = Basisvariablen) mit den zu Null gesetzten Nichtbasisvariablen. Diese Lösung ist sicherlich nicht optimal, was man daran erkennt, daß der Zielfunktionswert = 0 ist (das rote Feld), was nichts anderes bedeutet, als daß man keinen DB erwirtschaftet (klar, man produziert ja auch nichts, die Produkte x3, x4 und x5 sind ja nur "imaginär"). Die Idee des Simplex-Verfahrens ist nun, diese Einheitsvektoren Spaltenweise zu vertauschen, so daß der Zielfunktionswert maximal wird!

Schritt 3: Bestimmen der Pivot-Spalte

Es stellt sich zunächst die Frage, welches Produkt denn nun mit in die Programmplanung aufgenommen werden soll. Dafür durchsucht man die Zielfunktionszeile nach negativen Werten und bestimmt davon den betragsmäßig kleinsten Wert. Die zugehörige Spalte i wird als Pivot-Spalte bezeichnet.
     
    x1 x2 x3 x4 x5 Funktionswert
    4 2 1 0 0 200
    2 4 0 1 0 200
    2 2 0 0 1 120
    -150 -100 0 0 0 0
     

Schritt 4: Positive Elemente der Pivot-Spalte suchen

Für die gefundene Pivot-Spalte werden nun alle positiven Werte xi bestimmt. Das sind hier:
    a11 = 4
    a12 = 2
    a13 = 2

Schritt 5: Berechnen des Quotienten Funktionswertj/aij

Für jedes der in Schritt 4 identifizierten Elemente wird nun der Quotient aus der zugörigen rechten Seite und dem Element berechnet:
    Fwi/a11 = 200/4 = 50
    Fwi/a12 = 200/2 = 100
    Fwi/a13 = 120/2 = 60

Schritt 6: Bestimmen des kleinsten Quotienten

Aus den in Schritt 5 berechneten Werten wird nun der kleinste bestimmt. Die entsprechende Zeile wird als Pivot-Zeile, das zugehörige Element der Pivot-Spalte als Pivot-Element bezeichnet. Für das Beispiel ist dies die Zeile 1 (Fwi/a11 = 50), mit dem Pivot-Element a11.

Schritt 7:

Nun wird in der Pivot-Zeile die Basisvariable gesucht, die den Wert 1 hat:
     
    x1 x2 x3 x4 x5 Funktionswert
    4 2 1 0 0 200
    2 4 0 1 0 200
    2 2 0 0 1 120
    -150 -100 0 0 0 0
     

Schritt 8: Austauschschritt

Die beiden Spalten werden "getauscht". Es wird also nun - im obigen Beispiel - die Nichtbasisvariable x1 zur Basisvariablen, d.h. in dieser Spalte muß im folgenden der Einheitsvektor stehen:
     
    x1 x2 x3 x4 x5 Funktionswert
    1 1/2 1/4 0 0 50
    0          
    0          
    0          
     
Die einzelnen Zeilen berechnen sich durch Addition und Subtraktion der jeweiligen Zeile mit einem Vielfachen der Pivot-Zeile, also:
     
    x1 x2 x3 x4 x5 Funktionswert
    1 1/2 1/4 0 0 50
    0 3  -1/2  1  0  100 
    0 1  -1/2  0  1  20 
    0 -25  37,5  0  0  7.500 
     
Damit ergibt sich die nächste Basislösung zu (50, 0, 0, 100, 20), mit dem Funktionswert 7.500. D.h wenn 50 Teile von x1 produziert werden, kann ein DB von 7.500 erzielt werden.
 

Schritt 9: Prüfen, ob optimale Lösung

Es stellt sich nur die Frage, ob es noch einen besseren Wert gibt. Da immer noch einer der Zielfunktionskoeffizienten negativ ist (im Klartext bedeutet das "das Hinzufügen dieser Variable erhöht den Zielfunktionswert) werden die Schritte 3 - 8 wiederholt. Dies geschieht solange, bis alle Zielfunktionskoeffizienten größer 0 Null sind.
    Schritt 3 ergibt Spalte 2 (= x2)
    Schritt 4 ergibt (1/2, 3, 1)
    Schritt 5 ergibt:
    • 50/0,5 = 100
    • 100/3 = 33,33
    • 20/1 = 20
    Schritt 6 ergibt Element a23 als kleinsten Quotienten und damit ist die 3. Zeile die Pivot-Zeile
    Schritt 7 ergibt "Tausche mit 5. Spalte

    Damit folgt das Tableau (bereits komplett berechnet):
     
    x1 x2 x3 x4 x5 Funktionswert
    1 0 1/2 0 -1/2 40
    0 0 1 1 -3 40
    0 1 -1/2 0 1 20
    0  0 25  0  25  8.000 
     

Es gibt keine Zielfunktionskoeffizienten mehr, die den Zielfunktionswert vergrößern können.

Schritt 10: Optimale Lösung gefunden

Die Optimale Lösung kann nun aus dem Tableau direkt abgelesen werden. Es ergibt damit:
    x1 = 40
    x2 = 20
    Maximale DB ist 8.000
D.h. das optimale Produktionsprogramm ist 40 Stück von Produkt 1 und 20 Stück von Produkt 2 herzustellen. Damit läßt sich ein Deckungsbeitrag von 8.500 GE erzielen.

Diese Problem und dessen Lösung läßt sich auch einfach  grafisch nachvollziehen.

Der grauschraffierte Bereich stellt die gesamte Lösungsmenge dar, d.h eine Lösung kann nur innerhalb dieses Bereiches vorhanden sein. Betrachtet man nun noch die Zielfunktion (eine Schar paralleler Geraden), so ergibt sich folgendes Bild:
Man kann also das Ergebnis ablesen, indem einfach die Zielfunktion über den Zielbereich (in Richtung einer Vergrößerung des Zielfunktionswertes) verschoben wird, bis das der Funktionswert maximal wird. Die entsprechenden Mengen von x1 und x2 können dann abgelesen werden.
    x1 = 40
    x2 = 20
 Diese Eigenschaften kann man sich für ein allgemeines Lösungsverfahren zu Nutze machen, wenn man sich folgende Zusammenhänge klar macht:
  • Eine Lösung liegt immer in einem der Eckpunkte des eingegrenzten Zielbereiches


    • Man braucht also nur diese Eckpunkte "abzusuchen", der maximale gefundene Funktionswert der Zielfunktion ist dann die Lösung.
  • Das ganze gilt ebenso für mehr als zwei Variablen (allerdings dürfte die zeichnerische Lösung dann um einiges schwieriger werden)
  • Das Simplex-Verfahren macht sich das Absuchen der Eckpunkte zunutze, indem nach und nach Basisvariablen und Nichtbasisvariablen vertauscht werden, bis das der Zielfunktionswert maximal ist (dann erreicht, wenn es keine NBV mehr gibt, die diesen Wert erhöhen kann, also alle >= 0 sind!)
Bitte lesen: Wichtige Hinweise zu diesen Seiten!
 
Last update: Wed, 01.May.2002 17:02:00 
© 2001, Guido Friese 
Bei Problemen mit der Anzeige, bitte diese Hinweise lesen.