Simplex-Verfahren

Eine Firma will möglichst viel Gewinn machen, hat aber nur begrenzt Maschinenzeit und Material. Bei zwei Produkten kann man das Lineare Optimierung|Optimierungsproblem zeichnerisch lösen. Bei mehr Produkten braucht man ein Rechenverfahren: das Simplex-Verfahren . Es springt von Ecke zu Ecke des erlaubten Bereichs, immer zu einer besseren, bis es nicht mehr besser geht. Gilt hier für: Maximieren, Nebenbedingungen mit le , alle Variablen ge 0 . Unten rechts steht am Ende -Z { max} . Mache aus den Nebenbedingungen x + y le 4 und x + 3y le 6 Gleichungen. Lösung: Mit Schlupfvariablen s 1, s 2 ge 0 (der „ungenutzte Rest“): x + y + s 1 = 4 qquad x + 3y + s 2 = 6 Stelle das Starttableau für „Maximiere Z = 2x + 3y “ auf und bestimme das erste Pivotelement. | | x | y | s 1 | s 2 | rechts | Quotient | |---|---|---|---|---|---|---| | I | 1 | 1 | 1 | 0 | 4 | 4 : 1 = 4 | | II | 1 | 3 | 0 | 1 | 6 | 6 : 3 = 2 ← kleinster | | Z | 2 | 3 | 0 | 0 | 0 | | Pivotspalte y (größter Wert 3 ), Pivotzeile II → Pivotelement 3 . Führe das Verfahren zu Ende. 1. Schritt (II : 3 , dann Spalte y ausräumen): | | x | y | s 1 | s 2 | rechts | |---|---|---|---|---|---| | I | frac{2}{3} | 0 | 1 | - frac{1}{3} | 2 | | II | frac{1}{3} | 1 | 0 | frac{1}{3} | 2 | | Z | 1 | 0 | 0 | -1 | -6 | Unten steht noch 1 0 → Pivotspalte x . Quotienten: 2 : frac{2}{3} = 3 und 2 : frac{1}{3} = 6 → Pivotzeile I. 2. Schritt: | | x | y | s 1 | s 2 | rechts | |---|---|---|---|---|---| | I | 1 | 0 | frac{3}{2} | - frac{1}{2} | 3 | | II

Worum geht's?

Eine Firma will möglichst viel Gewinn machen, hat aber nur begrenzt Maschinenzeit und Material. Bei zwei Produkten kann man das Optimierungsproblem zeichnerisch lösen. Bei mehr Produkten braucht man ein Rechenverfahren: das Simplex-Verfahren . Es springt von Ecke zu Ecke des erlaubten Bereichs, immer zu einer besseren, bis es nicht mehr besser geht.
Erlaubter Bereich: x + y ≤ 4 und x + 3y ≤ 6
f(x) = −x + 4g(x) = −0,333x + 2
1234560,511,522,533,54xyfgA(3|1)B(4|0)C(0|2)

Formel mit Erklärung

Gilt hier für: Maximieren, Nebenbedingungen mit ≤ \le ≤ , alle Variablen ≥ 0 \ge 0 ≥ 0 .
Simplex-Verfahren
  1. 1
    Schlupfvariablen s₁, s₂, … ≥ 0 einführen: aus ≤ wird =
  2. 2
    Starttableau: Nebenbedingungen als Zeilen, Zielfunktion als unterste Zeile (rechts 0)
  3. 3
    Pivotspalte: größter positiver Wert in der untersten Zeile
  4. 4
    Pivotzeile: kleinster Quotient (rechte Seite : Eintrag der Pivotspalte), nur positive Einträge
  5. 5
    Pivotzeile durch das Pivotelement teilen, dann alle anderen Einträge der Pivotspalte zu 0 machen
  6. 6
    Wiederholen, bis unten keine positiven Werte mehr stehen
Unten rechts steht am Ende − Z max ⁡ -Z_{\max} − Z m a x ​ .

Beispiele

Leicht#1
Mache aus den Nebenbedingungen x + y ≤ 4 x + y \le 4 x + y ≤ 4 und x + 3 y ≤ 6 x + 3y \le 6 x + 3 y ≤ 6 Gleichungen. Lösung: Mit Schlupfvariablen s 1 , s 2 ≥ 0 s_1, s_2 \ge 0 s 1 ​ , s 2 ​ ≥ 0 (der „ungenutzte Rest“): x + y + s 1 = 4 x + 3 y + s 2 = 6 x + y + s_1 = 4 \qquad x + 3y + s_2 = 6 x + y + s 1 ​ = 4 x + 3 y + s 2 ​ = 6

Zusammenfassung

Simplex: rechnerisches Verfahren der linearen Optimierung. Schlupfvariablen machen aus ≤ \le ≤ Gleichungen. Pivotspalte: größter positiver Wert unten; Pivotzeile: kleinster Quotient. Fertig, wenn unten nichts Positives mehr steht; unten rechts steht − Z max ⁡ -Z_{\max} − Z m a x ​ .

Jetzt üben

Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff: