Start / Leistungsangebot / Mathematik / Üben mit Max / Lineare Optimierung - Simplexalgorithmus
Mathematik · Themen Wirtschaftsmathematik (BHS)
Lineare Optimierung – Simplexalgorithmus
Zielfunktion maximieren unter Nebenbedingungen: grafische Lösung und das Simplexverfahren.
Lass es dir von Max erklären
Max führt dich in wenigen Minuten durch das Thema – mit Sprachausgabe, Animationen und einem kurzen Quiz. Unter „Frag Max“ beantwortet er dir häufige Fragen – mit Bild.
Frag Max
Max ist ein vorbereiteter Lernbegleiter (keine KI): Er kennt die Antworten auf häufige Fragen zu diesem Thema. Es wird nichts gespeichert oder übertragen; die Sprachausgabe erfolgt direkt auf deinem Gerät. Hinweis: Die Nutzung von Max ist kostenlos. Für das Herunterladen der Seiten auf dein Gerät verrechnet dir jedoch dein Internet- bzw. Mobilfunkanbieter je nach Tarif eventuell Gebühren (z. B. für mobile Daten oder Roaming). Diese Kosten liegen außerhalb unseres Einflusses und sind von dir selbst zu tragen.
Lineare Optimierung – Simplexalgorithmus
① Das Modell
② Grafische Lösung
③ Simplexalgorithmus
④ Beispiele, Aufgaben mit Lösungsweg, Fehler, Quiz
Das Modell
• Zielfunktion: (oder min)
• Nebenbedingungen: lineare Ungleichungen (Ressourcen)
• Nichtnegativität: ,
Simplexalgorithmus
Für mehr als zwei Variablen: Schlupfvariablen einführen, Simplextableau aufstellen, Pivotspalte (negativster Wert in der Zielzeile) und Pivotzeile (kleinster Quotient) wählen und so lange umformen, bis die Zielzeile keine negativen Werte mehr hat.
Beispiel
, , : Ecken (0|0) → 0, (4|0) → 12, (2|4) → 22, (0|5) → 20 → Optimum (2|4)
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
① Gegeben ist der Lösungsbereich durch seine vier Ecken (0|0), (3|0), (2|2) und (0|3); gesucht ist das Maximum von .
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
① Gegeben ist der Lösungsbereich durch seine vier Ecken (0|0), (3|0), (2|2) und (0|3); gesucht ist das Maximum von .
② Grundidee: Weil Z linear ist, liegt das Optimum immer in einer Ecke des Lösungsbereichs – wir müssen also nur die Ecken prüfen.
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
① Gegeben ist der Lösungsbereich durch seine vier Ecken (0|0), (3|0), (2|2) und (0|3); gesucht ist das Maximum von .
② Grundidee: Weil Z linear ist, liegt das Optimum immer in einer Ecke des Lösungsbereichs – wir müssen also nur die Ecken prüfen.
③ Ecke (0|0): .
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
② Grundidee: Weil Z linear ist, liegt das Optimum immer in einer Ecke des Lösungsbereichs – wir müssen also nur die Ecken prüfen.
③ Ecke (0|0): .
④ Ecke (3|0): .
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
③ Ecke (0|0): .
④ Ecke (3|0): .
⑤ Ecke (2|2): .
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
④ Ecke (3|0): .
⑤ Ecke (2|2): .
⑥ Ecke (0|3): .
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
⑤ Ecke (2|2): .
⑥ Ecke (0|3): .
⑦ Vergleich: Der größte Wert ist 4. Kontrolle in der Grafik: Die Gerade berührt den Bereich nur noch im Punkt (2|2).
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
⑥ Ecke (0|3): .
⑦ Vergleich: Der größte Wert ist 4. Kontrolle in der Grafik: Die Gerade berührt den Bereich nur noch im Punkt (2|2).
⑧ Ergebnis: Das Maximum wird im Punkt (2 | 2) erreicht.
Aufgabe 2
Wo liegt das Optimum immer?
① Die Zielfunktion ist linear. Für einen festen Wert von Z ist das eine Gerade – die Zielgerade.
Aufgabe 2
Wo liegt das Optimum immer?
① Die Zielfunktion ist linear. Für einen festen Wert von Z ist das eine Gerade – die Zielgerade.
② Verschiedene Werte von Z ergeben parallele Geraden: Sie haben alle dieselbe Steigung .
Aufgabe 2
Wo liegt das Optimum immer?
① Die Zielfunktion ist linear. Für einen festen Wert von Z ist das eine Gerade – die Zielgerade.
② Verschiedene Werte von Z ergeben parallele Geraden: Sie haben alle dieselbe Steigung .
③ Je weiter wir die Zielgerade (beim Maximieren) nach außen schieben, desto größer wird Z.
Aufgabe 2
Wo liegt das Optimum immer?
② Verschiedene Werte von Z ergeben parallele Geraden: Sie haben alle dieselbe Steigung .
③ Je weiter wir die Zielgerade (beim Maximieren) nach außen schieben, desto größer wird Z.
④ Wir dürfen aber nur Punkte im Lösungsbereich nehmen. Also schieben wir, bis die Gerade den Bereich gerade noch berührt.
Aufgabe 2
Wo liegt das Optimum immer?
③ Je weiter wir die Zielgerade (beim Maximieren) nach außen schieben, desto größer wird Z.
④ Wir dürfen aber nur Punkte im Lösungsbereich nehmen. Also schieben wir, bis die Gerade den Bereich gerade noch berührt.
⑤ Der Lösungsbereich ist ein Vieleck mit geraden Rändern – die letzte Berührung passiert an einer Ecke (oder entlang einer ganzen Kante, dann sind beide Ecken optimal).
Aufgabe 2
Wo liegt das Optimum immer?
④ Wir dürfen aber nur Punkte im Lösungsbereich nehmen. Also schieben wir, bis die Gerade den Bereich gerade noch berührt.
⑤ Der Lösungsbereich ist ein Vieleck mit geraden Rändern – die letzte Berührung passiert an einer Ecke (oder entlang einer ganzen Kante, dann sind beide Ecken optimal).
⑥ Ergebnis: Das Optimum liegt immer in einer Ecke des Lösungsbereichs.
Aufgabe 3
Was sind Schlupfvariablen?
① Ausgangspunkt ist eine Nebenbedingung als Ungleichung, zum Beispiel x + y ≤ 10 (10 Stunden Maschinenzeit).
Aufgabe 3
Was sind Schlupfvariablen?
① Ausgangspunkt ist eine Nebenbedingung als Ungleichung, zum Beispiel x + y ≤ 10 (10 Stunden Maschinenzeit).
② Der Simplexalgorithmus rechnet aber mit Gleichungen. Deshalb fügen wir eine neue Variable s hinzu: .
Aufgabe 3
Was sind Schlupfvariablen?
① Ausgangspunkt ist eine Nebenbedingung als Ungleichung, zum Beispiel x + y ≤ 10 (10 Stunden Maschinenzeit).
② Der Simplexalgorithmus rechnet aber mit Gleichungen. Deshalb fügen wir eine neue Variable s hinzu: .
③ s gleicht den Unterschied aus: Werden nur 7 Stunden verbraucht , dann ist .
Aufgabe 3
Was sind Schlupfvariablen?
② Der Simplexalgorithmus rechnet aber mit Gleichungen. Deshalb fügen wir eine neue Variable s hinzu: .
③ s gleicht den Unterschied aus: Werden nur 7 Stunden verbraucht , dann ist .
④ Weil man nicht mehr als die Ressource verbrauchen darf, gilt .
Aufgabe 3
Was sind Schlupfvariablen?
③ s gleicht den Unterschied aus: Werden nur 7 Stunden verbraucht , dann ist .
④ Weil man nicht mehr als die Ressource verbrauchen darf, gilt .
⑤ Jede ≤-Bedingung bekommt ihre eigene Schlupfvariable s₁, s₂, … – im Starttableau sind sie die Basisvariablen.
Aufgabe 3
Was sind Schlupfvariablen?
④ Weil man nicht mehr als die Ressource verbrauchen darf, gilt .
⑤ Jede ≤-Bedingung bekommt ihre eigene Schlupfvariable s₁, s₂, … – im Starttableau sind sie die Basisvariablen.
⑥ Ergebnis: Schlupfvariablen geben an, wie viel einer Ressource ungenutzt bleibt.
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
① Gegeben: mit dem Lösungsbereich aus dem Beispiel, Ecken (0|0), (4|0), (2|4), (0|5).
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
① Gegeben: mit dem Lösungsbereich aus dem Beispiel, Ecken (0|0), (4|0), (2|4), (0|5).
② Wieder gilt: Das Maximum liegt in einer Ecke, also setzen wir alle Ecken ein.
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
① Gegeben: mit dem Lösungsbereich aus dem Beispiel, Ecken (0|0), (4|0), (2|4), (0|5).
② Wieder gilt: Das Maximum liegt in einer Ecke, also setzen wir alle Ecken ein.
③ (0|0): .
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
② Wieder gilt: Das Maximum liegt in einer Ecke, also setzen wir alle Ecken ein.
③ (0|0): .
④ (4|0): .
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
③ (0|0): .
④ (4|0): .
⑤ (2|4): .
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
④ (4|0): .
⑤ (2|4): .
⑥ (0|5): .
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
⑤ (2|4): .
⑥ (0|5): .
⑦ Vergleich: 20 ist der größte Wert. Weil x hier viel mehr bringt (5 statt 2), lohnt es sich, nur x zu produzieren.
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
⑥ (0|5): .
⑦ Vergleich: 20 ist der größte Wert. Weil x hier viel mehr bringt (5 statt 2), lohnt es sich, nur x zu produzieren.
⑧ Ergebnis: Optimum bei (4 | 0) mit .
Typische Fehler
✗ Die Nichtnegativitätsbedingungen vergessen.
✗ Beim Simplex den Quotienten mit negativen Elementen bilden.
Das Wichtigste
✔ Das Modell
✔ Grafische Lösung
✔ Simplexalgorithmus
George Dantzig im Jahr 1947 – es gehört zu den wichtigsten Algorithmen des 20. Jahrhunderts.
Wer hat das Simplexverfahren erfunden?
George Dantzig im Jahr 1947 – es gehört zu den wichtigsten Algorithmen des 20. Jahrhunderts.
Sehr gerne! Unsere Lehrkräfte erklären dir das Thema persönlich – in Wien oder online. Jetzt Nachhilfe anfragen →
Persönliche Nachhilfe
Das Modell
- Zielfunktion: (oder min)
- Nebenbedingungen: lineare Ungleichungen (Ressourcen)
- Nichtnegativität: ,
Grafische Lösung
Das Optimum liegt immer in einer Ecke des Lösungsbereichs. Man verschiebt die Zielgerade parallel, bis sie den Bereich gerade noch berührt.
Simplexalgorithmus
Für mehr als zwei Variablen: Schlupfvariablen einführen, Simplextableau aufstellen, Pivotspalte (negativster Wert in der Zielzeile) und Pivotzeile (kleinster Quotient) wählen und so lange umformen, bis die Zielzeile keine negativen Werte mehr hat.
Probier es aus: Zielfunktion testen
Lösungsbereich wie in der Grafik: , , x,
Beispiele
Beispiel
, , : Ecken (0|0) → 0, (4|0) → 12, (2|4) → 22, (0|5) → 20 → Optimum (2|4)
Übungsaufgaben
Rechne selbst und klappe danach die Lösung auf.
Aufgabe 1
, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?
Lösungsweg:
- Gegeben ist der Lösungsbereich durch seine vier Ecken (0|0), (3|0), (2|2) und (0|3); gesucht ist das Maximum von .
- Grundidee: Weil Z linear ist, liegt das Optimum immer in einer Ecke des Lösungsbereichs – wir müssen also nur die Ecken prüfen.
- Ecke (0|0): .
- Ecke (3|0): .
- Ecke (2|2): .
- Ecke (0|3): .
- Vergleich: Der größte Wert ist 4. Kontrolle in der Grafik: Die Gerade berührt den Bereich nur noch im Punkt (2|2).
- Ergebnis: Das Maximum wird im Punkt (2 | 2) erreicht.
Lösung: 4 bei (2|2)
Aufgabe 2
Wo liegt das Optimum immer?
Lösungsweg:
- Die Zielfunktion ist linear. Für einen festen Wert von Z ist das eine Gerade – die Zielgerade.
- Verschiedene Werte von Z ergeben parallele Geraden: Sie haben alle dieselbe Steigung .
- Je weiter wir die Zielgerade (beim Maximieren) nach außen schieben, desto größer wird Z.
- Wir dürfen aber nur Punkte im Lösungsbereich nehmen. Also schieben wir, bis die Gerade den Bereich gerade noch berührt.
- Der Lösungsbereich ist ein Vieleck mit geraden Rändern – die letzte Berührung passiert an einer Ecke (oder entlang einer ganzen Kante, dann sind beide Ecken optimal).
- Ergebnis: Das Optimum liegt immer in einer Ecke des Lösungsbereichs.
Lösung: in einer Ecke
Aufgabe 3
Was sind Schlupfvariablen?
Lösungsweg:
- Ausgangspunkt ist eine Nebenbedingung als Ungleichung, zum Beispiel x + y ≤ 10 (10 Stunden Maschinenzeit).
- Der Simplexalgorithmus rechnet aber mit Gleichungen. Deshalb fügen wir eine neue Variable s hinzu: .
- s gleicht den Unterschied aus: Werden nur 7 Stunden verbraucht , dann ist .
- Weil man nicht mehr als die Ressource verbrauchen darf, gilt .
- Jede ≤-Bedingung bekommt ihre eigene Schlupfvariable s₁, s₂, … – im Starttableau sind sie die Basisvariablen.
- Ergebnis: Schlupfvariablen geben an, wie viel einer Ressource ungenutzt bleibt.
Lösung: nicht genutzte Ressourcen
Aufgabe 4
mit Ecken wie im Beispiel: Optimum?
Lösungsweg:
- Gegeben: mit dem Lösungsbereich aus dem Beispiel, Ecken (0|0), (4|0), (2|4), (0|5).
- Wieder gilt: Das Maximum liegt in einer Ecke, also setzen wir alle Ecken ein.
- (0|0): .
- (4|0): .
- (2|4): .
- (0|5): .
- Vergleich: 20 ist der größte Wert. Weil x hier viel mehr bringt (5 statt 2), lohnt es sich, nur x zu produzieren.
- Ergebnis: Optimum bei (4 | 0) mit .
Lösung: (4|0),
Typische Fehler
- Die Nichtnegativitätsbedingungen vergessen.
- Beim Simplex den Quotienten mit negativen Elementen bilden.
Häufige Fragen zu Lineare Optimierung - Simplexalgorithmus
Wer hat das Simplexverfahren erfunden?
George Dantzig im Jahr 1947 – es gehört zu den wichtigsten Algorithmen des 20. Jahrhunderts.
Ich brauche echte Nachhilfe.
Sehr gerne! Unsere Lehrkräfte erklären dir das Thema persönlich – in Wien oder online. Jetzt Nachhilfe anfragen →
