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?
Formel mit Erklärung
- 1Schlupfvariablen s₁, s₂, … ≥ 0 einführen: aus ≤ wird =
- 2Starttableau: Nebenbedingungen als Zeilen, Zielfunktion als unterste Zeile (rechts 0)
- 3Pivotspalte: größter positiver Wert in der untersten Zeile
- 4Pivotzeile: kleinster Quotient (rechte Seite : Eintrag der Pivotspalte), nur positive Einträge
- 5Pivotzeile durch das Pivotelement teilen, dann alle anderen Einträge der Pivotspalte zu 0 machen
- 6Wiederholen, bis unten keine positiven Werte mehr stehen
Beispiele
Zusammenfassung
Jetzt üben
Kostenlose Aufgaben mit Lösungsweg zu diesem Begriff:
