Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · 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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · 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).
Für 2-Variablen-LPs geht's am Papier. Die graphische Methode visualisiert die LP-Theorie perfekt — Klausur-Klassiker.
Klausur-Tipp: Bei "Lösen Sie das LP graphisch" IMMER 4-Schritt-Methode anwenden: 1) Achsen + Nichtnegativität, 2) Restriktionen als Geraden mit 2 Punkten, 3) Zulässigen Bereich schraffieren (Test mit Ursprung), 4) Zielgerade verschieben + alle Ecken-Werte berechnen. Optimum in Ecke + Wert nennen.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Für 2-Variablen-LPs geht's am Papier. Die graphische Methode visualisiert die LP-Theorie perfekt — Klausur-Klassiker.
Graphische LP-Lösung: Bei 2 Variablen kann das LP durch Zeichnen gelöst werden — Restriktionen als Geraden, zulässiger Bereich als Polygon, Optimum in einer Ecke.
Achsen x₁ (horizontal) und x₂ (vertikal). Nichtnegativitäts-Restriktion erlaubt nur 1. Quadrant.
Jede Restriktion a₁ x₁ + a₂ x₂ ≤ b wird als Grenz-Gerade gezeichnet.
Konstruktion einer Geraden: 2 Punkte reichen.
x₁ = 0: x₂ = b / a₂x₂ = 0: x₁ = b / a₁Beispiel: 2 x₁ + 3 x₂ ≤ 12:
x₁ = 0 ⇒ x₂ = 4 → Punkt (0, 4)x₂ = 0 ⇒ x₁ = 6 → Punkt (6, 0)Verbinde mit Gerade.
Die zulässige Seite jeder Restriktion ist:
≤: Seite des Ursprungs (wenn RHS positiv) — darunter≥: andere Seite — darüber=: nur die Gerade selbstSchnitt aller Halbebenen + x₁ ≥ 0, x₂ ≥ 0 = zulässiger Bereich.
Diese Region ist immer ein konvexes Polygon (Polytop).
Zielfunktion c₁ x₁ + c₂ x₂ = z ist auch eine Gerade — für verschiedene z parallele Geraden.
Bei MAX: Verschiebe die Zielgerade in Richtung steigender z (in Gradient-Richtung), bis sie den zulässigen Bereich nur in einer Ecke berührt.
Bei MIN: Umgekehrt — in Richtung sinkender z.
Die berührende Ecke = Optimum.
Fundamentalsatz der linearen Optimierung: Wenn ein LP eine optimale Lösung hat, dann existiert (mindestens) eine optimale Ecke des zulässigen Polytops.
Konsequenz: Statt unendlich viele Punkte zu prüfen, reicht es, alle Ecken durchzugehen.
Anzahl Ecken eines m × n-LP: Höchstens C(m+n,m) — kann exponentiell viele werden, aber praktisch oft handhabbar.
Wenn die Zielgerade PARALLEL zu einer aktiven Restriktion ist, dann liegt das Optimum auf einer ganzen KANTE des Polytops.
Diagnose: c ist Vielfaches eines a_i (Restriktions-Normalen-Vektor).
Wenn der zulässige Bereich unbeschränkt ist UND die Zielgerade in unbeschränkter Richtung verschoben werden kann → z → ∞ (max) bzw. -∞ (min).
Beispiel: max x₁ + x₂ mit nur x₁, x₂ ≥ 0 → unbeschränkt.
Wenn keine Punkte alle Restriktionen erfüllen → keine Lösung.
Beispiel: x₁ ≤ 1 und x₁ ≥ 3 → leer.
Wenn mehr als 2 Restriktionen durch eine Ecke gehen → entartet. Kommt bei kleinen Problemen selten vor, kann bei Simplex Probleme verursachen.
z = c₁ x₁ + c₂ x₂ pro Ecke.z (bei max).z-Wert (z.B. z = 0) und zeichne Zielgerade.Klausur-Praxis: Schieben ist schneller bei einfachen Problemen, Ecken-Methode systematischer.
Simplex-Algorithmus ist im Kern die Ecken-Methode systematisiert für höhere Dimensionen:
2D ist Special-Case — bei 3+ Dimensionen ist Simplex die einzige praktikable Methode (oder Innere-Punkte-Methoden).
max z = 3 x₁ + 5 x₂
unter:
2 x₁ + 1 x₂ ≤ 8; 1 x₁ + 3 x₂ ≤ 9; x₁, x₂ ≥ 0
Schritt 1: Achsen + Nichtnegativität → 1. Quadrant.
Schritt 2: Restriktion 1: (0, 8) und (4, 0). Restriktion 2: (0, 3) und (9, 0).
Schritt 3: Schnitt der ≤-Halbebenen ist ein 5-Eck mit Ecken (0, 0), (4, 0), (3, 2), (0, 3).
Schritt 4: Werte berechnen:
(0, 0): z = 0(4, 0): z = 12(3, 2): z = 9 + 10 = 19(0, 3): z = 15→ Optimum bei (3, 2) mit z^* = 19.
1. Restriktionen Gerade durch 2 Punkte: (0, b/a₂) und (b/a₁, 0).
2. Zulässige Seite: Bei ≤ → Ursprung-Seite (für b > 0), bei ≥ → andere Seite.
3. Optimum immer in einer Ecke (Fundamentalsatz der LP).
4. Schieben in Gradient-Richtung: Zielgerade verschieben bis sie nur Ecke berührt.
5. Spezialfälle erkennen: Multipel-Optimum (Kante), Unbeschränkt, Leer, Entartet.
6. Graphisch nur 2D, sonst Simplex. 3D-LP visuell schwer, ≥4D unmöglich → Simplex.
1. Restriktion auf falscher Seite schraffiert. Bei ≤ mit b > 0: Ursprung-Seite. Bei ≥ mit b > 0: Gegen-Seite. Test: Setze (0, 0) ein → ist Restriktion erfüllt? Wenn ja → diese Seite ist zulässig.
2. Nichtnegativität vergessen einzuzeichnen. x₁, x₂ ≥ 0 bedeutet: NUR 1. Quadrant. Wichtig bei Beispielen, wo Restriktionen-Geraden in andere Quadranten gehen.
3. Zielgerade nur einmal zeichnen. Falsch — Zielgerade muss VERSCHOBEN werden in Richtung steigender (max) / sinkender (min) z-Werte. Mehrere parallele Geraden zeichnen.
4. Optimum auf einer Kante. Wenn Zielgerade parallel zu einer Restriktion: GANZE Kante optimal. Antwort dann: 2 Ecken + alle Konvex-Kombinationen.
5. Schnittpunkt zweier Restriktionen falsch berechnen. a₁ x₁ + a₂ x₂ = b₁ und a₁' x₁ + a₂' x₂ = b₂ → Cramer-Regel oder Substitution.
6. Innere Punkte als Optimum vorschlagen. Falsch. Bei linearer Zielfunktion liegt Optimum IMMER auf dem Rand (Ecken oder Kanten). Innere Punkte sind nie optimal.
2-Variablen-LP visualisiert: Restriktionen, zulässiger Bereich, Eckpunkte + verschiebbare Zielgerade. Slider verändert z, du siehst wie das Optimum gesucht wird.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das LP graphisch" IMMER 4-Schritt-Methode anwenden: 1) Achsen + Nichtnegativität, 2) Restriktionen als Geraden mit 2 Punkten, 3) Zulässigen Bereich schraffieren (Test mit Ursprung), 4) Zielgerade verschieben + alle Ecken-Werte berechnen. Optimum in Ecke + Wert nennen.
6 Aufgaben zur Methodik, Spezialfällen und Eckpunkt-Berechnung.
Klausurfragen mit Lösungen (6)
Antwort: Gerade durch (0, 4) und (6, 0), schraffiere darunter (Ursprung-Seite)
Erklärung: Standard-Methode: 2 Punkte über Achsen-Schnittpunkte. Bei x₁ = 0: x₂ = 12/2 = 6. Bei x₂ = 0: x₁ = 12/3 = 4. Also Gerade durch (0, 6) und (4, 0). Bei ≤ schraffiere Ursprung-Seite (Test: Setze (0,0) ein → 0 ≤ 12 ✓). Antwort A hat die Punkte vertauscht.
Antwort: In einer Ecke (oder auf einer Kante bei Multipel-Optimum)
Erklärung: Fundamentalsatz der linearen Optimierung: bei linearer Zielfunktion + linearen Restriktionen liegt das Optimum IMMER in einer Ecke des zulässigen Polytops. Spezialfall: wenn Zielgerade parallel zu einer Restriktion ist, kann das Optimum auf einer ganzen Kante liegen (Multipel-Optimum). Innere Punkte sind nie optimal.
Zuordnungen:
Erklärung: 4 Spezialfälle der LP-Theorie: Multipel-Optimum (Optimum auf Kante), Unbeschränkt (z → ∞), Leer (keine zulässige Lösung), Entartung (Simplex kann zykeln). Klausur-Klassiker: Diagnose anhand graphischer Lösung beschreiben.
Typ: Zuordnung
Antwort: Gegen-Seite des Ursprungs
Erklärung: Test: Setze (0, 0) ein → 0 ≥ 4 ist FALSCH → Ursprung erfüllt Restriktion NICHT → andere Seite ist zulässig. Bei ≤ mit positiver RHS ist Ursprung typisch zulässig (Ursprung-Seite), bei ≥ umgekehrt. Klausur-Tipp: IMMER mit (0,0) testen — schnellster Check.
Antwort: Wahr
Erklärung: RICHTIG. Graphisch geht nur 2D (Papier-Ebene) — bei 3D-LP visuell schwer (mit Müh möglich), ≥4D unmöglich für Menschen. Daher: Simplex-Algorithmus als algorithmische Version der Ecken-Methode für n Dimensionen. Wichtig: graphische Methode lehrt aber die LP-INTUITION (zulässiger Bereich, Eckpunkte, Verschieben der Zielgerade) — Grundlage für Simplex-Verständnis.
Typ: Wahr/Falsch
Antwort: Auf der Kante zwischen (4, 0) und (0, 4), z* = 8 — Multipel-Optimum
Erklärung: Zielgerade 2x₁ + 2x₂ = z ist PARALLEL zur Restriktion x₁ + x₂ = 4 (gleicher Normalen-Vektor (1, 1)). Daher liegt das Optimum auf der ganzen Kante zwischen (4, 0) und (0, 4) — Multipel-Optimum. z* = 8 auf der ganzen Kante. Beispiele: (4, 0), (0, 4), (2, 2), (3, 1) — alle mit z = 8. Klausur-Klassiker.
6 typische Klausurfragen zur Methodik und Theorie.
Klausurfragen mit Lösungen (6)
Antwort: Konvexes Polygon (Polytop)
Erklärung: Der zulässige Bereich eines LP ist IMMER ein konvexes Polygon (in 2D) bzw. Polytop (in höheren Dimensionen). Konvexität folgt aus dem Schnitt von Halbebenen (jede ist konvex). Daher: Eckpunkte sind endlich viele. Klausur-Theorie: Lineare Optimierung über konvexen Polytopen.
Antwort: Wenn die Zielfunktion in unbeschränkte Richtung verschiebbar ist und der zulässige Bereich unbeschränkt ist
Erklärung: Unbeschränktes LP: zulässiger Bereich ist unbeschränkt UND Zielgerade kann in dieser Richtung verschoben werden, ohne den zulässigen Bereich zu verlassen. Beispiel: max x₁ + x₂ s.t. x₁ ≥ 0, x₂ ≥ 0 (kein Limit oben). z → ∞. In Praxis: Modellierungsfehler — fehlende Restriktion.
Lösungen pro Lücke:
Erklärung: Standard-Konstruktion: Restriktions-Gerade über 2 Achsen-Schnittpunkte (x₁ = 0 → x₂ = b/a₂; x₂ = 0 → x₁ = b/a₁). Zulässige Seite: Test mit Ursprung (0, 0). Fundamentalsatz: Optimum in Ecke des Polytops. Diese 4 Fakten sind LP-Klausur-Standard.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: 4-Schritt-Methode: 1) Koordinatensystem (Achsen) + Nichtnegativität durch 1. Quadrant. 2) Restriktionen als Geraden über Achsen-Schnittpunkte. 3) Zulässigen Bereich = Schnitt aller Halbebenen markieren. 4) Zielfunktions-Gerade verschieben — Optimum in letzter Ecke, die berührt wird. Werte berechnen.
Typ: Reihenfolge
Antwort: Optimum ist mehrdeutig (mehrere optimale Lösungen)
Erklärung: Multipel-Optimum: das LP hat mehrere optimale Lösungen mit gleichem z*-Wert. Tritt auf, wenn Zielfunktions-Gerade parallel zu einer aktiven Restriktion ist. Lösung: das Optimum liegt auf einer ganzen KANTE — alle Punkte auf der Kante sind optimal (Konvex-Kombination zweier Ecken). Klausur-Klassiker: 'Zeichnen Sie alle optimalen Lösungen ein'.
Antwort: Wahr
Erklärung: RICHTIG. Bei linearer Zielfunktion (Gradient zeigt in feste Richtung) liegt das Optimum immer auf dem RAND des zulässigen Bereichs. Konvexitäts-Argument: wenn ein innerer Punkt optimal wäre, könnte man in Gradient-Richtung weitergehen und höheren z-Wert erreichen — also war es nicht optimal. Daher: Optimum auf Rand, und auf Rand wieder in Ecken (es sei denn parallele Zielgerade → Kanten).
Typ: Wahr/Falsch