📞 01/503 94 10✉ office@team-plus.at
Mo–Fr 10–22 Uhr

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.

Max – dein virtueller, kostenloser Mathe-Coach. Ich erkläre dir das Thema Lineare Optimierung – Simplexalgorithmus Schritt für Schritt.
Mit Sprachausgabe – Ton kannst du jederzeit abschalten.

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.

Das Modell

  • Zielfunktion: Z=c1x+c2y  →  max⁡Z = c_{1} x + c_{2} y \;\rightarrow\; \max (oder min)
  • Nebenbedingungen: lineare Ungleichungen (Ressourcen)
  • Nichtnegativität: x≥0x \geq 0, y≥0y \geq 0

Grafische Lösung

xy12345612345678Optimum
2x + y ≤ 8, x + 2y ≤ 10: Optimum in einer Ecke

Das Optimum liegt immer in einer Ecke des Lösungsbereichs. Man verschiebt die Zielgerade parallel, bis sie den Bereich gerade noch berührt.

xy123456123452x + y = 8x + 2y = 10erlaubt(0|0)(4|0)(2|4)(0|5)
Jede Nebenbedingung ist eine Gerade; erlaubt ist die Seite zum Ursprung hin. Der grüne Bereich erfüllt alle Bedingungen.
xy12345612345Optimum (2|4): Z = 22Z = 6Z = 26: außerhalb
Zielgeraden Z = 3x + 4y: Je weiter außen, desto größer Z. Die letzte Gerade, die den Bereich noch berührt, liefert das Optimum.

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.

Ungleichungen mit Schlupfvariablen zu GleichungenStarttableau aufstellenPivotspalte: negativster Wert in der Z-ZeilePivotzeile: kleinster Quotient RS / SpaltePivotelement auf 1, Rest der Spalte auf 0Noch negative Werte in Z-Zeile?janein:fertig
Ablauf: Schlupfvariablen, Starttableau, Pivotspalte, Pivotzeile, umformen – bis die Zielzeile keine negativen Werte mehr hat.
BVxys₁s₂RSQuotients₁211088 : 1 = 8s₂12011010 : 2 = 5 ✓Z−3−4000−4 am kleinsten
Starttableau für Z = 3x + 4y → max: Pivotspalte y (−4), Pivotzeile s₂ (kleinster Quotient 5), Pivotelement 2.
BVxys₁s₂RSQuotients₁1,501−0,533 : 1,5 = 2 ✓y0,5100,555 : 0,5 = 10Z−100220noch −1
Nach dem 1. Schritt: y ist Basisvariable (y = 5), Z = 20. In der Zielzeile steht noch −1 → weiter mit Pivotspalte x.
BVxys₁s₂RSx10⅔−⅓2x = 2y01−⅓⅔4y = 4Z00⅔⁵⁄₃22keine negativen Werte
Endtableau: keine negativen Werte mehr in der Zielzeile → Optimum x = 2, y = 4, Z = 22 (wie grafisch).

Probier es aus: Zielfunktion testen

Z in (0|0), (4|0), (2|4), (0|5)
Optimum

Lösungsbereich wie in der Grafik: 2x+y≤82 x + y \leq 8, x+2y≤10x + 2 y \leq 10, x, y≥0y \geq 0

Beispiele

Beispiel

Z=3x+4y  →  max⁡Z = 3 x + 4 y \;\rightarrow\; \max, 2x+y≤82 x + y \leq 8, x+2y≤10x + 2 y \leq 10: 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

Z=x+yZ = x + y, Ecken (0|0), (3|0), (2|2), (0|3): Maximum?

xy12341234(0|0) → 0(3|0) → 3(2|2) → 4(0|3) → 3Z = 4

Lösungsweg:

  1. Gegeben ist der Lösungsbereich durch seine vier Ecken (0|0), (3|0), (2|2) und (0|3); gesucht ist das Maximum von Z=x+yZ = x + y.
  2. Grundidee: Weil Z linear ist, liegt das Optimum immer in einer Ecke des Lösungsbereichs – wir müssen also nur die Ecken prüfen.
  3. Ecke (0|0): Z=0+0=0Z = 0 + 0 = 0.
  4. Ecke (3|0): Z=3+0=3Z = 3 + 0 = 3.
  5. Ecke (2|2): Z=2+2=4Z = 2 + 2 = 4.
  6. Ecke (0|3): Z=0+3=3Z = 0 + 3 = 3.
  7. Vergleich: Der größte Wert ist 4. Kontrolle in der Grafik: Die Gerade x+y=4x + y = 4 berührt den Bereich nur noch im Punkt (2|2).
  8. Ergebnis: Das Maximum Z=4Z = 4 wird im Punkt (2 | 2) erreicht.

Lösung: 4 bei (2|2)

Aufgabe 2

Wo liegt das Optimum immer?

xy1234512345zuletzt berührtverschieben

Lösungsweg:

  1. Die Zielfunktion Z=c1x+c2yZ = c_{1} x + c_{2} y ist linear. Für einen festen Wert von Z ist das eine Gerade – die Zielgerade.
  2. Verschiedene Werte von Z ergeben parallele Geraden: Sie haben alle dieselbe Steigung −c1c2- \dfrac{c_{1}}{c_{2}}.
  3. Je weiter wir die Zielgerade (beim Maximieren) nach außen schieben, desto größer wird Z.
  4. Wir dürfen aber nur Punkte im Lösungsbereich nehmen. Also schieben wir, bis die Gerade den Bereich gerade noch berührt.
  5. 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).
  6. Ergebnis: Das Optimum liegt immer in einer Ecke des Lösungsbereichs.

Lösung: in einer Ecke

Aufgabe 3

Was sind Schlupfvariablen?

verbraucht: x + yRest sRessource gesamt = 10x + y ≤ 10 ⟶ x + y + s = 10, s ≥ 0

Lösungsweg:

  1. Ausgangspunkt ist eine Nebenbedingung als Ungleichung, zum Beispiel x + y ≤ 10 (10 Stunden Maschinenzeit).
  2. Der Simplexalgorithmus rechnet aber mit Gleichungen. Deshalb fügen wir eine neue Variable s hinzu: x+y+s=10x + y + s = 10.
  3. s gleicht den Unterschied aus: Werden nur 7 Stunden verbraucht (x+y=7)(x + y = 7), dann ist s=3s = 3.
  4. Weil man nicht mehr als die Ressource verbrauchen darf, gilt s≥0s \geq 0.
  5. Jede ≤-Bedingung bekommt ihre eigene Schlupfvariable s₁, s₂, … – im Starttableau sind sie die Basisvariablen.
  6. Ergebnis: Schlupfvariablen geben an, wie viel einer Ressource ungenutzt bleibt.

Lösung: nicht genutzte Ressourcen

Aufgabe 4

Z=5x+2yZ = 5 x + 2 y mit Ecken wie im Beispiel: Optimum?

xy1234512345(0|0) → 0(4|0) → 20(2|4) → 18(0|5) → 10

Lösungsweg:

  1. Gegeben: Z=5x+2yZ = 5 x + 2 y mit dem Lösungsbereich aus dem Beispiel, Ecken (0|0), (4|0), (2|4), (0|5).
  2. Wieder gilt: Das Maximum liegt in einer Ecke, also setzen wir alle Ecken ein.
  3. (0|0): Z=5⋅0+2⋅0=0Z = 5 \cdot 0 + 2 \cdot 0 = 0.
  4. (4|0): Z=5⋅4+2⋅0=20Z = 5 \cdot 4 + 2 \cdot 0 = 20.
  5. (2|4): Z=5⋅2+2⋅4=10+8=18Z = 5 \cdot 2 + 2 \cdot 4 = 10 + 8 = 18.
  6. (0|5): Z=5⋅0+2⋅5=10Z = 5 \cdot 0 + 2 \cdot 5 = 10.
  7. Vergleich: 20 ist der größte Wert. Weil x hier viel mehr bringt (5 statt 2), lohnt es sich, nur x zu produzieren.
  8. Ergebnis: Optimum bei (4 | 0) mit Z=20Z = 20.

Lösung: (4|0), Z=20Z = 20

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 →

Weitere Themen aus Themen Wirtschaftsmathematik (BHS)

← Zurück zur Themenübersicht

Lineare Optimierung – Simplexalgorithmus zum Mitnehmen

Zusammenfassung herunterladen PDF · kostenlos

Arbeitsblatt mit Lösungen

Arbeitsblatt herunterladen PDF · 4 Aufgaben und Kurz-Check mit ausführlichen Lösungen · kostenlos
📞