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).
Aus Worten Modelle machen. Das ist die wahre Klausur-Schwierigkeit bei Operations Research — der Simplex-Algorithmus folgt mechanisch, aber die Übersetzung Wortproblem → Mathematisches Modell musst du WIRKLICH können. Pflicht in 8/8 OR-Klausuren.
Klausur-Tipp: Bei "Modellieren Sie als LP" IMMER 4-Schritt-Schema einhalten: 1) Variablen mit Einheiten, 2) Restriktionen (inkl. Nichtnegativität!), 3) Zielfunktion mit Richtung, 4) Modell zusammensetzen. Punkte werden pro Schritt vergeben — nicht nur für das fertige Modell.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Aus Worten Modelle machen. Das ist die wahre Klausur-Schwierigkeit bei Operations Research — der Simplex-Algorithmus folgt mechanisch, aber die Übersetzung Wortproblem → Mathematisches Modell musst du WIRKLICH können. Pflicht in 8/8 OR-Klausuren.
Lineare Optimierung (LP): Eine Zielfunktion (linear in Variablen) wird unter linearen Ungleichungs-Restriktionen maximiert oder minimiert.
Allgemein:
max (oder min) z = c₁ x₁ + c₂ x₂ + ... + c_n x_n
unter:
a_(11) x₁ + a_(12) x₂ + ... + a_(1n) x_n ≤ b₁; a_(21) x₁ + ... + a_(2n) x_n ≤ b₂; ⋮; a_(m1) x₁ + ... + a_(mn) x_n ≤ b_m; x₁, x₂, ..., x_n ≥ 0
Komponenten:
x₁, ..., x_n = Entscheidungs-Variablenc_j = Zielfunktions-Koeffizienten (Wert pro Einheit)a_(ij) = Technologie-Koeffizienten (Ressourcenverbrauch pro Variable)b_i = Ressourcen-Vorgaben (Right-Hand-Side, RHS)Frage: Über welche GRÖSSEN entscheidet das Management?
Pflicht: Jede Variable hat eine EINHEIT (Stück, kg, Personen, €). Ohne Einheit ist die Modellierung nicht eindeutig.
Frage: Welche Begrenzungen oder Anforderungen gibt es?
| Wort im Text | Operator |
|---|---|
| "höchstens", "verfügbar", "Kapazität" | ≤ |
| "mindestens", "Anforderung", "Bedarf" | ≥ |
| "genau", "Bilanz", "muss gleich sein" | = |
Pflicht: Nichtnegativität x_i ≥ 0 nicht vergessen! Wird in Klausur oft als eigene Restriktion erwartet.
| Wort im Text | Richtung |
|---|---|
| Gewinn, Umsatz, Output, Deckungsbeitrag | max |
| Kosten, Zeit, Verschnitt, Verbrauch | min |
Koeffizienten: Wert pro Einheit der Variable. z.B. "40 € pro Tisch" → 40 x₁.
Setze alles zusammen:
Erst dann an Lösung denken (Simplex / Graphisch / Software).
"Welche Mengen produzieren, um Gewinn zu maximieren bei beschränkten Ressourcen?"
x₁, x₂, ..."Welche Anteile von Rohstoffen mischen, um Anforderungen zu erfüllen bei minimalen Kosten?"
Diet-Problem (Stigler 1939) ist der Urvater — was sollte ein Mensch essen, um Nährstoff-Anforderungen bei minimalen Kosten zu erfüllen?
"Wieviel von Quelle i an Senke j liefern, um Transportkosten zu minimieren?"
x_(ij) = Liefermenge von i nach j"Welche Person auf welche Aufgabe, um Gesamtnutzen zu maximieren?"
x_(ij) ∈ \0, 1\ — ist binär! (ganzzahlig)"Wieviele Mitarbeiter pro Schicht, um Personalbedarf bei minimalen Kosten zu decken?"
Der Simplex-Algorithmus erwartet eine Standardform:
=)Umformungen:
| Ausgangsform | Standardform |
|---|---|
a₁ x₁ + a₂ x₂ ≤ b | a₁ x₁ + a₂ x₂ + s₁ = b, wobei s₁ ≥ 0 Schlupfvariable |
a₁ x₁ + a₂ x₂ ≥ b | a₁ x₁ + a₂ x₂ - s₁ = b, wobei s₁ ≥ 0 Überschussvariable |
x_i frei | x_i = x_i⁺ - x_i⁻, wobei x_i⁺, x_i⁻ ≥ 0 |
Schlupfvariablen interpretiert man als nicht-genutzte Ressource. z.B. wenn 60 h Schreinerei verfügbar sind, aber nur 50 h verbraucht werden, dann ist s₁ = 10 (10 h ungenutzte Schreinerei-Kapazität).
1. Reihenfolge IMMER: Variablen → Restriktionen → Zielfunktion. Nie mit Zielfunktion anfangen (du kennst die Variablen noch nicht).
2. Variablen haben Einheiten. Notiere immer "x₁ = Anzahl Tische pro Woche [Stück]". Ohne Einheit halbe Punkte.
3. Nichtnegativität ist eine Pflicht-Restriktion. x_i ≥ 0. Wird in Klausuren oft vergessen — 1 Punkt Abzug.
4. Operator-Mapping: "höchstens" → ≤, "mindestens" → ≥, "genau" → =. Im Zweifel auf Kontext achten.
5. Schlupfvariablen = ungenutzte Ressource. In der Klausur wirst du gefragt, was s₁ = 10 bedeutet — Antwort: "10 Einheiten Ressource 1 sind nicht genutzt".
6. Lineare Optimierung ≠ Nichtlineare Optimierung. LP setzt LINEAR voraus — keine Quadrate, keine Produkte x₁ · x₂, keine Bruchterme.
1. Variablen falsch definiert. Statt "Anzahl Tische" → "Tischproduktion" (zu vage). Statt "kg Material A" → "Material A" (Einheit fehlt). Klausur erwartet PRÄZISE Definition.
2. Restriktion vs. Zielfunktion verwechseln. "Gewinn" ist Zielfunktion (Wert, der maximiert wird), nicht Restriktion. Aber "Mindest-Gewinn von 1000 €" wäre Restriktion (z ≥ 1000).
3. Nichtlineare Terme einbauen. "Quadratisch wachsende Kosten" → KEIN LP. Falls Klausur das verlangt: stoppen und fragen oder ausdrücklich vermerken "linearisiert mit Annahme X".
4. Nichtnegativität bei freien Variablen. Falsche Annahme dass alle Variablen ≥ 0 sind. Z.B. "Lager-Bestand kann positiv (Lager) oder negativ (Backorder) sein" → Variable frei, mit x = x⁺ - x⁻ ersetzen.
5. Restriktionen nicht auf Einheiten prüfen. Linke Seite Stunden, rechte Seite Euro? → Modellierungs-Fehler. Beide Seiten immer in gleicher Einheit.
6. Schlupf- vs. Überschussvariable verwechseln. Bei ≤ wird PLUS Schlupf zu Gleichung. Bei ≥ wird MINUS Überschuss. Klausur-Klassiker.
3 klassische LP-Probleme als Schritt-für-Schritt-Workshop: Wortproblem → Variablen → Restriktionen → Zielfunktion → fertiges Modell.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Modellieren Sie als LP" IMMER 4-Schritt-Schema einhalten: 1) Variablen mit Einheiten, 2) Restriktionen (inkl. Nichtnegativität!), 3) Zielfunktion mit Richtung, 4) Modell zusammensetzen. Punkte werden pro Schritt vergeben — nicht nur für das fertige Modell.
6 Aufgaben zu Modellierungs-Schritten, Restriktions-Typen und Standardform.
Klausurfragen mit Lösungen (6)
Antwort: Variablen → Restriktionen → Zielfunktion
Erklärung: Reihenfolge IMMER: 1) Variablen identifizieren (mit Einheiten!), 2) Restriktionen aufstellen (inkl. Nichtnegativität), 3) Zielfunktion formulieren. Mit Zielfunktion anfangen geht nicht — du kennst die Variablen noch nicht. Klausur erwartet diesen 3-Schritt-Aufbau.
Antwort: ≤
Erklärung: 'Höchstens' / 'verfügbar' / 'Kapazität' → ≤ (kleiner-gleich). Beispiel: 3x₁ + 2x₂ ≤ 60. Andere Stichworte: 'mindestens' → ≥, 'genau' → =. Operator-Mapping ist Klausur-Grundlage.
Zuordnungen:
Erklärung: Standard-LP-Patterns mit ihren typischen Variablen: Produktion (Mengen), Mischung (Anteile), Transport (Doppelindex für Quelle×Senke), Zuordnung (binär 0/1). Zuordnungs-Problem ist genaugenommen ganzzahlige Programmierung wegen 0/1-Variablen.
Typ: Zuordnung
Antwort: 3x₁ + 2x₂ + s₁ = 60, s₁ ≥ 0 (Schlupfvariable)
Erklärung: ≤-Restriktion wird zur Gleichung durch PLUS Schlupfvariable s₁ ≥ 0. Bei ≥-Restriktion wäre es MINUS Überschussvariable. Schlupfvariable hat Bedeutung: 's₁ = 10' heißt 10 h Schreinerei ungenutzt. Klausur-Klassiker beim Aufstellen der Simplex-Tabelle.
Antwort: Wahr
Erklärung: RICHTIG. Nichtnegativität (x_i ≥ 0) ist Standard-Annahme für LP — wird in Klausuren EXPLIZIT erwartet. Vergessen kostet 1 Punkt. Ausnahmen: 'freie Variablen' (z.B. Lagerbestand kann negativ = Backorder) — dann mit x = x⁺ − x⁻ ersetzen, beide ≥ 0.
Typ: Wahr/Falsch
Antwort: x = x⁺ − x⁻ mit x⁺ ≥ 0 und x⁻ ≥ 0
Erklärung: Freie Variable x wird ersetzt durch x = x⁺ − x⁻, wobei x⁺, x⁻ ≥ 0. Wenn x positiv ist, ist x⁺ > 0 und x⁻ = 0. Wenn x negativ ist, ist x⁻ > 0 und x⁺ = 0. So bleibt das LP in Standardform (alle Variablen ≥ 0). Antwort 1 (frei lassen) zerstört Simplex-Struktur. |x| wäre nichtlinear → kein LP.
6 typische Klausurfragen zu Modellierung, Standardform und LP-Theorie.
Klausurfragen mit Lösungen (6)
Antwort: Zielfunktion + Restriktionen sind beide LINEAR in den Variablen
Erklärung: LP = Linear Programming. Sowohl Zielfunktion ALS AUCH Restriktionen müssen linear in den Variablen sein. Keine Quadrate (x²), keine Produkte (x₁·x₂), keine Brüche (1/x). Bei Quadraten → quadratisches Programm (QP). Bei beliebigen nichtlinearen Termen → nichtlineare Optimierung (NLP).
Antwort: 10 Einheiten der Ressource sind UNGENUTZT (Schlupf)
Erklärung: Schlupfvariable s₁ in der Umformung 3x₁ + 2x₂ + s₁ = 60 misst NICHT-GENUTZTE Ressource. s₁ = 10 → 10 h verbleibende Kapazität. s₁ = 0 → Ressource voll ausgelastet (Restriktion 'aktiv'). Klausur-Klassiker: Schlupf wirtschaftlich interpretieren.
Lösungen pro Lücke:
Erklärung: Standard-Umformungen für Simplex: 1) a·x ≤ b wird zu a·x + s = b mit Schlupfvariable s ≥ 0. 2) a·x ≥ b wird zu a·x − s = b mit Überschussvariable s ≥ 0. Beide neuen Variablen müssen ≥ 0 sein, damit das LP in Standardform vorliegt.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Reihenfolge: 1) Variablen (mit Einheiten — sonst sind Restriktionen nicht prüfbar), 2) Restriktionen (alle Begrenzungen + Pflicht-Nichtnegativität), 3) Zielfunktion (max für Gewinn, min für Kosten), 4) Modell zusammensetzen + auf Konsistenz prüfen. Mit Zielfunktion anfangen geht nicht — du kennst die Variablen noch nicht.
Typ: Reihenfolge
Antwort: x₁ + 2 x₂ ≤ 12
Erklärung: Schneiderei: 1 h pro Hemd · x₁ + 2 h pro Hose · x₂ ≤ 12 h Kapazität. Operator ist ≤ weil 'zur Verfügung' eine Obergrenze ist. = wäre falsch (man muss die Kapazität nicht ausnutzen). Antwort 4 wäre nichtlinear (Produkt zweier Variablen).
Antwort: Wahr
Erklärung: RICHTIG. George Stigler stellte 1939 das Diet-Problem: was muss ein US-Soldat essen, um alle Nährstoff-Anforderungen zu erfüllen bei minimalen Kosten? 77 Lebensmittel, 9 Nährstoff-Restriktionen (Protein, Calcium, Eisen, etc.). Vor dem Simplex (Dantzig 1947) löste Stigler es per Hand — moderne Lösung 39 $/Jahr, ungenießbar. Klassischer LP-Anwendungsfall.
Typ: Wahr/Falsch