Kurzbeschreibung des Simplex-Verfahrens

 

Die lineare Optimierungs-Aufgabe sei wie folgt gegeben:

cT x ---> max

A x < b               b > 0

x > 0                  x Î IRq, b Î IRm

 

 

Aufbau des Simplex-Tableaus

 

           j                        2’

   

 

k

 

1’

 

          ck,j

 

3’

 

rk

 

4’

 

 

 

7’

 

           dj

5’

 

6’

 

 

Bedeutung der Felder:

l' : Menge der Basisvariablen (BV)

2' : Menge der Nichtbasisvariablen (NBV)

3' : Elemente der Matrix der Nebenbedingungen

4' : Elemente der rechten Seite

5' : Elemente der Zielfunktion

6' : Wert der Zielfunktion

7' : Hilfsfeld

Alle anderen Felder werden nicht benutzt.

 

Die Felder werden beim Start des Verfahrens wie folgt initialisiert:

l': q + 1,q + 2,...,q + m = n (Die Indizes für die Schlupfvariablen )

2': 1,2,...,q (Die Indizes der gegebenen Variablen.)

3': Matrix A

4': rechte Seite b

5': Zielfunktionskoeffizienten c

6': 0

7': nicht belegt (Hilfsfeld für das Verfahren)

 

Aufbau des Simplex-Tableaus (nach der Initialisierung)

 

 

1         2           3        ....      q

   

     q + 1

     q + 2

    ............

    ............

    ............

    q + m

 

                       A

 

    b

 

 

c1         c2          c3       ....     cq

    0

 

(Statt der Variablen x1, x2,... wird im Tableau jeweils nur der Index 1,2,... geführt.)

 

Durchführung des Simplex-Verfahrens


In einem ersten Schritt werden die beiden Variablen ermittelt, die ausgetauscht werden (eine NBV, die Pivotspalte, und eine BV, die Pivotzeile). Das "Kreuzungselement" (das Element, das sowohl zur Pivotspalte als auch zur Pivotzeile gehört,) heißt Pivotelement.

Der zweite Schritt stellt die Umwandlung des Tableaus dar.

Die beiden Schritte werden (nacheinander) solange ausgeführt, bis das Verfahren beendet wird, d.h. es wird eine optimale Lösung gefunden oder es gibt keine optimale Lösung.

 

I. Auswahl eines Pivotelements

a) Suche in Feld 5' das maximale dj; dies liefert die Pivotspalte jo.
    Gibt es kein j mit dj > 0, so wurde die (eine) optimale Lösung gefunden.
    (Gibt es noch ein/mehrere j mit dj = 0, so gibt es noch weitere Lösungen.)

b) Bilde in Feld 7' rk / ck,j0 falls ck,jo > 0.
    Gibt es kein k mit ck,jo > 0, so existiert keine Lösung. Das Verfahren ist abzubrechen.
    Unter den Werten in Feld 7' wählt man das Minimum; dies liefert die Pivotzeile ko.

 

II. Umformen der Felder 1’ bis 6’

a) Das Pivotelement cko,jo wird durch 1 / cko,jo ersetzt.

b) Alle anderen Elemente der Pivotzeile ko (in 2' und 4') werden durch cko,jo (den ursprünglichen Wert) dividiert.

c) Alle anderen Elemente der Pivotspalte jo (in 3' und 5') werden durch -cko,jo (den ursprünglichen Wert) dividiert.

d) Alle übrigen Elemente (in 3', 4' und 5') sind nach der Rechteckregel zu ersetzen:

 

Pivotspalte

                cko,j0 ........................... b           Pivotzeile

                .                                      .

                .                                      .

                c          ......................... d

d ist zu ersetzen durch d - b * c / cko,jo ( jeweils die ursprünglichen Werte!)

 

e) Die Indizes jo und ko sind in den Feldern l' und 2' zu tauschen.

Die einzelnen Schritte werden an einem Beispiel verdeutlicht.

 

(Literatur: Lutz, Operations Research Verfahren- verstehen und anwenden, Fortis Verlag, 1998)


Tips und Anregungen an: emiel@informatik.fh-augsburg.de
Stand: 21.03.2003