zum Directory-modus

Grundlagen der Parameterschätzung/Optimierung

Lösungsmethoden mit Hilfe des Simplex-Verfahrens

Um Problemstellungen mit Hilfe des Simplex-Verfahrens zu lösen, gibt es zwei Möglichkeiten der Herangehensweise:

1. Grafische Lösung linearer Optimierungsprobleme

Die grafische Lösung lässt sich nur im 2-dimensionalen Raum durchführen, d.h. sie ist nur anwendbar, wenn nicht mehr als zwei Variablen (x1, x2) das Problem beschreiben. Zur Veranschaulichung möchten wir hier die grafische Lösung in der Animation etwas näher beleuchten:

Bitte Flash aktivieren.

Abb.1

2. Rechenschema des Simplex-Verfahrens

Mit Hilfe des Simplex-Verfahrens ist es möglich auch mehrdimensionale Optimierungsprobleme zu lösen. Das Simplex-Verfahren schematisiert die Maximumsuche. Dabei sei bemerkt, dass natürlich auch eine Minimumsuche mit diesem Verfahren möglich ist. Dazu muss lediglich die Zielfunktion mit (-1) multipliziert werden.

Man geht bei dem Simplex-Verfahren wie folgt vor:

Zunächst fügt man in die Nebenbedingungen, sofern es sich um Ungleichungen handelt, Schlupfvariablen ein (hier y). Diese dienen dazu, aus Ungleichungen Gleichungen zu erstellen. Generell kann man sagen, dass die Nebenbedingungen bei Maximierungsproblemen nur "Kleiner-Gleich-Beziehungen" enthalten, bei Minimierungsproblemen dagegen enthalten sie nur "Größer-Gleich-Beziehnungen".

M1: 3x1+2x2 ≤ 26 → y1+3x1+2x2=26

M2: x1+4x2 ≤ 36 → y2+x1+4x2=36

y1=26-3x1-2x2

y2=36-x1-4x2

Danach werden sowohl die Zielfunktion als auch die Nebenbedingungen in ein Simplextableau eingetragen.

Tab.1
Simplextableau
x1 x2 ... xn
z c1 c2 ... cn 0
y1 -a11 -a12 ... -a1n b1
y2 -a21 -a22 ... -a2n b2
..................
ym -am1 -am2 ... -amn bm

Für das Beispiel mit Z(x1,x2)=10x1+20x2 → max/min und o.g. Nebenbedingungen sieht dies dann so aus:

Tab.2
Beispiel
x1 x2
z10200
y1 -3-226
y2 -1-436

Die Variablen in der Kopfzeile x1, x2 sind Nichtbasisvariablen. Als Basisvariablen werden die Variablen der linken Spalte (y1, y2, ausgenommen z) bezeichnet. Das gesamte Rechenschema zu erläutern, würde an dieser Stelle zu weit führen.

Das Grundlegende dieser Methode ist das Austauschen der Basis- und Nichtbasisvariablen untereinander, wobei die Basisvariablen den Wert null annehmen und sich somit in Nichtbasisvariablen umwandeln und umgekehrt.

Seite 8 von 19