Erstellung des Starttableaus bei der M

Erstellung des Starttableaus bei der M-Methode
1. Schritt: Gegebenenfalls ein Minimierungsproblem in ein Maximierungsproblem
umwandeln (min F(x) ⇔ max -F(x)). Alle Nebenbedingungen so
umwandeln, dass auf der rechten Seite nichtnegative Werte stehen.
2. Schritt: Einfügen von Schlupfvariablen: bei ≥“-Nebenbedingungen haben diese ein
”
negatives Vorzeichen, Gleichungen bleiben Gleichungen (hier werden keine
Schlupfvariablen eingefügt). Beispiel:
• x1 + x2 ≤ 100 ⇒ x1 + x2 + s1 = 100
• x1 + x2 ≥ 100 ⇒ x1 + x2 − s1 = 100
• x1 + x2 = 100 ⇒ x1 + x2 = 100
3. Schritt: In jede Nebenbedingung, die keine Schlupfvariable mit positivem Vorzeichen
besitzt, wird eine künstliche Variable (yi ≥ 0) eingefügt. In der Zielfunktion
werden diese mit M bewertet. Beispiel:
• x1 + x2 + s1 = 100 ⇒ x1 + x2 + s1 = 100
• x1 + x2 − s1 = 100 ⇒ x1 + x2 − s1 + y1 = 100
• x1 + x2 = 100 ⇒ x1 + x2 + y2 = 100
• max F (x) = x1 + x2 ⇒ max F (x) = x1 + x2 − M (y1 + y2 )
4. Schritt: Für eine bessere Übersichtlichkeit wird die Zielfunktionszeile in eine F-Zeile
und eine M-Zeile unterteilt (was nicht nötig wäre). Die F-Zeile wird wie
beim primalen Simplex gebildet (mit (-1) multipliziert). In der M-Zeile
lassen sich die Einträge unter einem xk im Starttableau und in allen
folgenden Tableaus auf folgende Weise bestimmen:
-M·(Summe der Koeffizienten von xk in allen Zeilen, in denen ein y als BV
dient)
(Man kann die Einträge in der M-Zeile auch durch Eliminieren der yi aus der
Zielfunktion direkt ermitteln; vgl. hierzu die kommentierte Lösung zu Aufgabe 2.12
von Christian)
Nachdem das Starttableau erfolgreich aufgestellt wurde, wendet man nun den
primalen Simplex-Algorithmus auf das erweiterte Problem an. Die Wahl der
Pivotspalte erfolgt aber unter Betrachtung der M-Zeile (suche nach dem kleinsten,
negativen Eintrag in der M-Zeile). Nur wenn anhand der M-Zeile keine eindeutige
Spalte ausgewählt werden kann, erfolgt die Wahl unter diesen Kandidaten“ mit
”
Hilfe der F-Zeile.
Wird bei einer Iteration ein y aus der Basis entfernt, so wird dieses nie wieder in
die Basis aufgenommen werden und die entsprechende Spalte muß von nun an
nicht mehr betrachtet werden.
1

Download Report