Lineare Programmierung: Modellierung als Zielfunktion + Restriktionen, 2D-grafische Lösung über Polygon-Ecken, Simplex-Algorithmus, Spezialfälle (unbeschränkt, mehrfach optimal) und Sensitivitäts-/Schattenpreis-Analyse.
Lineare Optimierung (LP) sucht das Maximum oder Minimum einer linearen Zielfunktion unter linearen Nebenbedingungen. Pflichtthema in Wirtschaftsmathe (BWL/WI/WiIng) und Operations Research. Klausur-Klassiker: 2D-grafische Lösung, Simplex-Algorithmus.
Was du in der Klausur können musst:
In Klausuren oft gefragt: "Maximiere unter den Restriktionen ...", "Welche Ecke ist optimal?", "Eine Simplex-Iteration" — Pflicht-Aufgaben.
Allgemein:
unter den Nebenbedingungen:
Klausur-Beispiel — Produktions-Aufgabe:
Eine Firma produziert Stuhl () und Tisch (). Stuhl bringt 3 € Gewinn, Tisch 5 €. Restriktionen: Holz (), Arbeitszeit (). Maximiere Gewinn.
Modellierung:
Bei nur zwei Variablen ist die grafische Lösung in der Klausur Pflicht-Methode:
Fundamentalsatz der LP: Wenn ein zulässiges LP ein endliches Optimum besitzt, existiert mindestens eine optimale Ecke des zulässigen Polygons. Bei mehreren Optima kann auch eine ganze Kante optimal sein. Bei unbeschränkten oder unzulässigen LPs gibt es kein endliches Optimum.
Beispiel — Stuhl-Tisch-Aufgabe oben: vier Ecken-Kandidaten:
Optimum bei mit €.
Bei mehr als 2 Variablen ist grafisch unmöglich. Simplex (George Dantzig, 1947) ist der Standard-Algorithmus.
Idee: Starte in einer Ecke, wandere von Ecke zu Ecke entlang von Kanten — immer in Richtung Verbesserung. Stoppe, wenn keine Verbesserung mehr möglich ist.
| Basis | RHS | ||||
|---|---|---|---|---|---|
| 4 | 6 | 1 | 0 | 240 | |
| 3 | 2 | 0 | 1 | 120 | |
| −3 | −5 | 0 | 0 | 0 |
Pivot wählen: negativste Zahl in der -Zeile bestimmt die Pivot-Spalte (hier: mit ). Min-Quotient RHS / Pivot-Spalten-Wert bestimmt die Pivot-Zeile (hier: in Zeile ).
Pivot-Operation: Pivot-Element auf 1 normieren, Rest der Spalte auf 0.
Wiederholen bis alle Werte in der -Zeile sind → Optimum erreicht.
| Basis | RHS | ||||
|---|---|---|---|---|---|
| 2/3 | 1 | 1/6 | 0 | 40 | |
| 5/3 | 0 | −1/3 | 1 | 40 | |
| 1/3 | 0 | 5/6 | 0 | 200 |
→ alle -Werte → Optimum: , , . Hinweis: hier hätte man auch zur Ecke pivotieren können — die Variante mit höherem -Beitrag wird gewählt.
Wenn die Pivot-Spalte nur -Werte hat → keine Pivot-Zeile möglich → Zielfunktion wächst ins Unendliche. Bedeutung: Modell ist falsch (vergessene Restriktion).
Wenn das Polygon leer ist → kein zulässiger Punkt. Beispiel: und .
Wenn die Zielfunktions-Gerade parallel zu einer Polygon-Kante ist → die ganze Kante ist optimal. Im Tableau: ein -Wert ist 0 in einer Nicht-Basis-Spalte.
Schattenpreis einer Restriktion: wie viel zusätzlicher Gewinn pro zusätzlicher Einheit der RHS? Im optimalen Tableau in der -Zeile unter der -Spalte ablesbar (das Vorzeichen hängt von der Tableau-Konvention ab — in einigen Lehrbüchern , in anderen ). Schattenpreise gelten lokal im Sensitivitätsbereich und sollten bei Degeneration / mehrfach optimalen Lösungen vorsichtig interpretiert werden.
Zielfunktions-Bereiche: Wie weit kann schwanken, ohne dass sich die optimale Ecke ändert? Klausur-erweitert in OR-Vertiefung.
- 2 Variablen → immer grafisch lösen (Polygon + Ziel-Gerade verschieben).
- Mehr Variablen → Simplex-Tableau. Schlupfvariablen einführen, dann Pivot-Iterationen.
- Optimum in Ecke — Fundamentalsatz, mehrere Optima nur bei Parallelität.
- Pivot-Wahl: negativste in -Zeile (Spalte), min-Quotient (Zeile).
- Schattenpreise ablesen aus -Spalten der finalen -Zeile.
Faustregel zum Mitnehmen: LP-Modellierung in 3 Schritten — Zielfunktion, Restriktionen, Nicht-Negativität. 2D grafisch, n-D Simplex. Optimum immer in Ecke des Polygons. Mehr als alle anderen Mathematik-Themen lebt LP von der Modellierung der Wort-Aufgabe — geübtes Übersetzen ist der Klausur-Schlüssel.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur — und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Pflichtthema in Wirtschaftsmathe (BWL/WI/WiIng) und Operations Research. Klausur-Klassiker: 2D-grafische Lösung, Simplex-Algorithmus.
f(x) = ax² + bx + c. Parabeln verstehen, Scheitelpunkt finden, Nullstellen berechnen mit pq- und abc-Formel. Drei Darstellungsformen und wann welche.
Vom Differenzenquotienten zum Differentialquotienten: Tangentensteigung als Grenzwert der Sekantensteigungen. Grundregeln (Potenz, Faktor, Summe, Differenz) und erweiterte Regeln (Produkt, Quotient, Kette). Extremwerte über die notwendige Bedingung f'(x) = 0 und hinreichende Bedingung mit f''.
Was du in der Klausur können musst:
In Klausuren oft gefragt: "Maximiere z unter den Restriktionen ...", "Welche Ecke ist optimal?", "Eine Simplex-Iteration" — Pflicht-Aufgaben.
Allgemein:
max z = c₁ x₁ + c₂ x₂ + ... + c_n x_n
unter den Nebenbedingungen:
a_(11) x₁ + ... + a_(1n) x_n ≤ b₁
a_(21) x₁ + ... + a_(2n) x_n ≤ b₂
⋮
x_i ≥ 0 (Nicht-Negativität)
Klausur-Beispiel — Produktions-Aufgabe:
Eine Firma produziert Stuhl (
x₁) und Tisch (x₂). Stuhl bringt 3 € Gewinn, Tisch 5 €. Restriktionen: Holz (4x₁ + 6x₂ ≤ 240), Arbeitszeit (3x₁ + 2x₂ ≤ 120). Maximiere Gewinn.
Modellierung:
max z = 3x₁ + 5x₂
u.d.N. 4x₁ + 6x₂ ≤ 240, 3x₁ + 2x₂ ≤ 120, x₁, x₂ ≥ 0
Bei nur zwei Variablen ist die grafische Lösung in der Klausur Pflicht-Methode:
x₁, x₂ ≥ 0)c₁ x₁ + c₂ x₂ = z verschiebenFundamentalsatz der LP: Wenn ein zulässiges LP ein endliches Optimum besitzt, existiert mindestens eine optimale Ecke des zulässigen Polygons. Bei mehreren Optima kann auch eine ganze Kante optimal sein. Bei unbeschränkten oder unzulässigen LPs gibt es kein endliches Optimum.
Beispiel — Stuhl-Tisch-Aufgabe oben: vier Ecken-Kandidaten:
(0, 0) → z = 0(40, 0) aus 3x₁ + 2x₂ = 120 bei x₂ = 0 → z = 120(0, 40) aus 4x₁ + 6x₂ = 240 bei x₁ = 0 → z = 2004x₁ + 6x₂ = 240 und 3x₁ + 2x₂ = 120 → Lösung (24, 24) → z = 3 · 24 + 5 · 24 = 192Optimum bei (0, 40) mit z = 200 €.
Bei mehr als 2 Variablen ist grafisch unmöglich. Simplex (George Dantzig, 1947) ist der Standard-Algorithmus.
Idee: Starte in einer Ecke, wandere von Ecke zu Ecke entlang von Kanten — immer in Richtung Verbesserung. Stoppe, wenn keine Verbesserung mehr möglich ist.
≤-Ungleichungen → Gleichungen mit s_i ≥ 0:4x₁ + 6x₂ + s₁ = 240, 3x₁ + 2x₂ + s₂ = 120
| Basis | x₁ | x₂ | s₁ | s₂ | RHS |
|---|---|---|---|---|---|
s₁ | 4 | 6 | 1 | 0 | 240 |
s₂ | 3 | 2 | 0 | 1 | 120 |
z | −3 | −5 | 0 | 0 | 0 |
Pivot wählen: negativste Zahl in der z-Zeile bestimmt die Pivot-Spalte (hier: x₂ mit -5). Min-Quotient RHS / Pivot-Spalten-Wert bestimmt die Pivot-Zeile (hier: min(240/6, 120/2) = min(40, 60) = 40 in Zeile s₁).
Pivot-Operation: Pivot-Element auf 1 normieren, Rest der Spalte auf 0.
Wiederholen bis alle Werte in der z-Zeile ≥ 0 sind → Optimum erreicht.
| Basis | x₁ | x₂ | s₁ | s₂ | RHS |
|---|---|---|---|---|---|
x₂ | 2/3 | 1 | 1/6 | 0 | 40 |
s₂ | 5/3 | 0 | −1/3 | 1 | 40 |
z | 1/3 | 0 | 5/6 | 0 | 200 |
→ alle z-Werte ≥ 0 → Optimum: x₁ = 0, x₂ = 40, z = 200. Hinweis: hier hätte man auch zur Ecke (24, 24) pivotieren können — die Variante mit höherem z-Beitrag wird gewählt.
Wenn die Pivot-Spalte nur ≤ 0-Werte hat → keine Pivot-Zeile möglich → Zielfunktion wächst ins Unendliche. Bedeutung: Modell ist falsch (vergessene Restriktion).
Wenn das Polygon leer ist → kein zulässiger Punkt. Beispiel: x₁ ≥ 5 und x₁ ≤ 3.
Wenn die Zielfunktions-Gerade parallel zu einer Polygon-Kante ist → die ganze Kante ist optimal. Im Tableau: ein z-Wert ist 0 in einer Nicht-Basis-Spalte.
Schattenpreis einer Restriktion: wie viel zusätzlicher Gewinn pro zusätzlicher Einheit der RHS? Im optimalen Tableau in der z-Zeile unter der s_i-Spalte ablesbar (das Vorzeichen hängt von der Tableau-Konvention ab — in einigen Lehrbüchern z_j - c_j, in anderen c_j - z_j). Schattenpreise gelten lokal im Sensitivitätsbereich und sollten bei Degeneration / mehrfach optimalen Lösungen vorsichtig interpretiert werden.
Zielfunktions-Bereiche: Wie weit kann c_i schwanken, ohne dass sich die optimale Ecke ändert? Klausur-erweitert in OR-Vertiefung.
- 2 Variablen → immer grafisch lösen (Polygon + Ziel-Gerade verschieben).
- Mehr Variablen → Simplex-Tableau. Schlupfvariablen einführen, dann Pivot-Iterationen.
- Optimum in Ecke — Fundamentalsatz, mehrere Optima nur bei Parallelität.
- Pivot-Wahl: negativste in
z-Zeile (Spalte), min-Quotient (Zeile).- Schattenpreise ablesen aus
s_i-Spalten der finalenz-Zeile.
Faustregel zum Mitnehmen: LP-Modellierung in 3 Schritten — Zielfunktion, Restriktionen, Nicht-Negativität. 2D grafisch, n-D Simplex. Optimum immer in Ecke des Polygons. Mehr als alle anderen Mathematik-Themen lebt LP von der Modellierung der Wort-Aufgabe — geübtes Übersetzen ist der Klausur-Schlüssel.
Verstelle die Zielfunktions-Koeffizienten c₁, c₂ und die Restriktions-Parameter — das zulässige Polygon wird live gezeichnet, die Ziel-Gerade verschiebt sich entsprechend, der optimale Eckpunkt wird hervorgehoben.
Probier folgendes:
c₁=3, c₂=5, Holz 4x₁+6x₂ ≤ 240, Arbeit 2x₁+3x₂ ≤ 120) → Optimum bei (0, 40) mit z = 200c₁=10, c₂=2 → Optimum verschiebt sich zu (60, 0)Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Faustregel zum Mitnehmen: Bei 2 Variablen ist die grafische Lösung in der Klausur Standard — Polygon zeichnen, Ziel-Gerade als Schar paralleler Geraden verschieben, das Polygon "von außen" anschmiegen lassen. Die letzte berührte Ecke ist die Lösung. Bei Parallelität zur Restriktionskante: ganze Kante optimal (mehrfache Lösung).
Klausur-typische LP-Aufgaben: Modellierung, grafische Lösung, Simplex-Schritte.
Klausurfragen mit Lösungen (6)
Antwort: Zielfunktion, Nebenbedingungen, Nicht-Negativitäts-Bedingungen
Erklärung: LP-Modell: (1) lineare Zielfunktion (Max/Min), (2) lineare Nebenbedingungen (Ungleichungen), (3) Nicht-Negativität x_i ≥ 0. Die NNB ist Pflicht — sonst ist es kein Standard-LP.
Antwort: 200
Erklärung: z = 3·0 + 5·40 = 200. Beide Restriktionen sind in (0, 40) bindend (4·0+6·40=240, 2·0+3·40=120). Eckpunkt liegt auf Schnitt zweier Restriktionen → klassische LP-Lösung.
Typ: Zahlen-Eingabe
Antwort: Die optimale Lösung liegt immer in einer Ecke des zulässigen Polygons (oder auf einer ganzen Kante)
Erklärung: Fundamentalsatz: Optimum liegt in einer Ecke (Vertex) — Begründung: Niveaulinien der Zielfunktion sind parallel, die letzte berührte Stelle ist eine Ecke. Bei Parallelität zur Polygon-Kante ist die ganze Kante optimal (unendlich viele Lösungen, alle gleichwertig).
Antwort: Die Spalte mit dem negativsten Wert in der z-Zeile
Erklärung: Standardregel (Dantzig): negativste z-Zeilen-Eintrag → Pivot-Spalte. Begründung: gibt die größte Verbesserung pro Schritt. Wenn alle z-Einträge ≥ 0 → Optimum erreicht. Pivot-Zeile dann via Min-Quotient RHS / Pivot-Spalten-Wert (positiv).
Antwort: Wahr
Erklärung: Korrekt. Beispiel: x_1 ≥ 5 und x_1 ≤ 3 gleichzeitig — Schnittmenge leer → unzulässiges Modell (Infeasible). Im Simplex erkennt man das durch eine negative RHS, die nicht behoben werden kann (Big-M oder Zwei-Phasen-Methode für formale Diagnose).
Typ: Wahr/Falsch
Antwort: Den marginalen Zielfunktions-Zuwachs pro zusätzlicher Einheit einer Restriktion-RHS
Erklärung: Schattenpreis (= Dual-Variable, = Marginalwert): wie viel mehr ist die Zielfunktion wert, wenn die rechte Seite einer Restriktion um 1 erhöht wird? Ablesen im optimalen Simplex-Tableau in der z-Zeile unter den Schlupfvariablen-Spalten. Klausur-Anwendung in Sensitivitätsanalyse.
Sechs Aufgaben zur LP-Modellierung, Simplex-Mechanik und Spezialfällen.
Klausurfragen mit Lösungen (6)
Antwort: 36
Erklärung: Schnittpunkt: x_1 + x_2 = 10 und 2x_1 + x_2 = 16 → Subtraktion ergibt x_1 = 6, dann x_2 = 4. z = 4·6 + 3·4 = 24 + 12 = 36. Plausibilitäts-Check: andere Ecken (0,0)=0, (8,0)=32, (0,10)=30 — alle kleiner als 36 → Optimum bestätigt.
Typ: Zahlen-Eingabe
Antwort: Ungleichungen werden in Gleichungen umgewandelt
Erklärung: Schlupfvariablen s_i ≥ 0 wandeln a·x ≤ b in a·x + s = b um — Gleichungssystem statt Ungleichungssystem. Im Start-Tableau bilden die Schlupfvariablen die Anfangs-Basis (alles auf 0 + s_i = b_i). Klausur-Pflicht-Schritt vor jeder Simplex-Iteration.
Antwort: Tritt auf, wenn die Zielfunktions-Gerade parallel zu einer Polygon-Kante ist — dann ist die ganze Kante optimal
Erklärung: Mehrere Optima: Zielfunktions-Gerade ist parallel zu einer Polygon-Kante → unendlich viele optimale Punkte entlang dieser Kante (alle mit gleichem z-Wert). Im Tableau erkennt man das an einem 0-Wert in der z-Zeile bei einer Nicht-Basis-Variable. Häufig in Praxis-Modellen, z.B. wenn zwei Produkte gleich profitabel pro Engpass-Einheit sind.
Antwort: Eine Erhöhung der RHS von Restriktion 1 um 1 erhöht `z` um 2 (Schattenpreis = 2)
Erklärung: Schattenpreis = Wert von s_i in z-Zeile am Optimum. Schattenpreis 2 bedeutet: 1 zusätzliche Einheit der Restriktion-RHS bringt 2 zusätzliche Zielfunktion-Einheiten. Klausur-Pflicht in Sensitivitätsanalyse. Wenn Schattenpreis = 0, ist die Restriktion nicht bindend (Slack > 0).
Lösungen pro Lücke:
Erklärung: Pivot-Spalte: negativste z-Zeile. Pivot-Zeile: min-Quotient RHS/Spalten-Wert (positiv). Stopp: alle z-Einträge ≥ 0 → keine Verbesserung mehr möglich → Optimum erreicht.
Typ: Lückentext
Antwort: ... die Zielfunktion in eine Richtung beliebig wachsen kann (Polygon offen in Verbesserungsrichtung)
Erklärung: Unbeschränkt = das Polygon ist offen in der Richtung, in der die Zielfunktion wächst → z → ∞. Im Simplex erkennbar: Pivot-Spalte hat keine positiven Einträge → keine Pivot-Zeile möglich. Praktische Bedeutung: Modellierungsfehler, eine Ressourcen-Restriktion fehlt.
Fläche unter der Kurve: Riemann-Summen, Stammfunktion und Hauptsatz. Bestimmtes vs. unbestimmtes Integral, Potenzregel rückwärts. Die zweite Säule der Analysis.