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).
Erklärung
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.
Die Idee in einem Satz
Lineare Optimierung (LP): Eine Zielfunktion (linear in Variablen) wird unter linearen Ungleichungs-Restriktionen maximiert oder minimiert.
Die LP-Standardform
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)
Die 4 Modellierungs-Schritte
Schritt 1, Entscheidungs-Variablen identifizieren
Frage: Über welche GRÖSSEN entscheidet das Management?
- Bei Produktions-Problem: Mengen jedes Produkts
- Bei Mischungs-Problem: Anteile jedes Bestandteils
- Bei Schicht-Problem: Anzahl Mitarbeiter pro Schicht
- Bei Transport-Problem: Lieferung von Quelle i zu Senke j
Pflicht: Jede Variable hat eine EINHEIT (Stück, kg, Personen, €). Ohne Einheit ist die Modellierung nicht eindeutig.
Schritt 2, Restriktionen aufstellen
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.
Schritt 3, Zielfunktion formulieren
| 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₁.
Schritt 4, LP-Modell fertigstellen
Setze alles zusammen:
- Zielfunktion (max oder min)
- Restriktionen (≤, ≥, =)
- Nichtnegativität
Erst dann an Lösung denken (Simplex / Graphisch / Software).
Klassische LP-Typen
Produktions-Problem
"Welche Mengen produzieren, um Gewinn zu maximieren bei beschränkten Ressourcen?"
- Variablen: Produkt-Mengen
x₁, x₂, ... - Restriktionen: Ressourcen-Limits (≤)
- Zielfunktion: Gewinn (max)
Mischungs-Problem
"Welche Anteile von Rohstoffen mischen, um Anforderungen zu erfüllen bei minimalen Kosten?"
- Variablen: Rohstoff-Mengen
- Restriktionen: Anforderungen (≥), Mischungs-Summen (=)
- Zielfunktion: Kosten (min)
Diet-Problem (Stigler 1939) ist der Urvater, was sollte ein Mensch essen, um Nährstoff-Anforderungen bei minimalen Kosten zu erfüllen?
Transport-Problem
"Wieviel von Quelle i an Senke j liefern, um Transportkosten zu minimieren?"
- Variablen:
x_(ij)= Liefermenge voninachj - Restriktionen: Angebot-Limits, Nachfrage-Mindestmengen
- Zielfunktion: Σ Transportkosten (min)
Zuordnungs-Problem (Assignment)
"Welche Person auf welche Aufgabe, um Gesamtnutzen zu maximieren?"
- Variablen:
x_(ij) ∈ \0, 1\, ist binär! (ganzzahlig) - Restriktionen: Jede Person genau einer Aufgabe
- Zielfunktion: Σ Nutzen (max)
Schicht-Planung
"Wieviele Mitarbeiter pro Schicht, um Personalbedarf bei minimalen Kosten zu decken?"
- Variablen: Anzahl pro Schicht
- Restriktionen: Deckung des Bedarfs pro Stunde
- Zielfunktion: Personalkosten (min)
Standardform-Konventionen (für Simplex)
Der Simplex-Algorithmus erwartet eine Standardform:
- Alle Restriktionen sind Gleichungen (
=) - Alle Variablen sind nichtnegativ
- Rechte Seite ist nichtnegativ
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).
Klausur-Faustregeln
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.
Häufige Stolpersteine
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.
Interaktiv verstehen
LP-Modellierungs-Workshop
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.
Praxis-Übung
LP-Modellierung, Praxis-Übung
6 Aufgaben zu Modellierungs-Schritten, Restriktions-Typen und Standardform.
Klausurfragen mit Lösungen (6)
- F1.In welcher Reihenfolge solltest du beim Modellieren eines LP vorgehen?
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.
- F2.Welcher Operator passt zu 'Wir können HÖCHSTENS 60 Stunden Schreinerei einsetzen'?
Antwort: ≤
Erklärung: 'Höchstens' / 'verfügbar' / 'Kapazität' → ≤ (kleiner-gleich). Beispiel: 3x₁ + 2x₂ ≤ 60. Andere Stichworte: 'mindestens' → ≥, 'genau' → =. Operator-Mapping ist Klausur-Grundlage.
- F3.Ordne den LP-Typ der charakteristischen Variablen-Definition zu.
Zuordnungen:
- Produktions-Problem → x_i = Menge Produkt i
- Mischungs-Problem → x_i = Anteil Rohstoff i
- Transport-Problem → x_ij = Lieferung von Quelle i nach Senke j
- Zuordnungs-Problem → x_ij ∈ {0,1} = ist Person i Aufgabe j zugeordnet?
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
- F4.Wie wird die Restriktion '3x₁ + 2x₂ ≤ 60' in Simplex-Standardform überführt?
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.
- F5.Die Nichtnegativitäts-Bedingung x_i ≥ 0 ist Pflicht-Restriktion in jedem LP und muss explizit aufgeschrieben werden.
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
- F6.Eine Variable x kann positiv oder negativ sein (frei). Wie wird sie im LP behandelt?
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.
Klausur-Quiz
LP-Modellierung, Klausur-Quiz
6 typische Klausurfragen zu Modellierung, Standardform und LP-Theorie.
Klausurfragen mit Lösungen (6)
- F1.Welche Aussage trifft auf eine lineare Optimierung (LP) zu?
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).
- F2.Was bedeutet eine Schlupfvariable s₁ = 10 in einer ≤-Restriktion?
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.
- F3.Bei einer ≤-Restriktion wird die {{1}}-Variable {{2}} addiert um eine Gleichung zu erhalten. Bei einer ≥-Restriktion wird die {{3}}-Variable {{4}}. In beiden Fällen müssen die neuen Variablen {{5}} sein.
Lösungen pro Lücke:
- {{1}}: Schlupf
- {{2}}: addiert / plus / hinzugefügt
- {{3}}: Überschuss
- {{4}}: subtrahiert / minus / abgezogen
- {{5}}: nichtnegativ / ≥ 0 / größer gleich null
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
- F4.Bringe die 4 Schritte der LP-Modellierung in die korrekte Reihenfolge.
Richtige Reihenfolge:
- Variablen definieren (mit Einheiten!)
- Restriktionen aufstellen (inkl. Nichtnegativität)
- Zielfunktion formulieren (max/min)
- LP-Modell zusammensetzen + prüfen
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
- F5.Eine Bekleidungs-Firma stellt Hemden (x₁) und Hosen (x₂) her. Pro Tag stehen 12 h Schneiderei zur Verfügung. Ein Hemd braucht 1 h, eine Hose 2 h. Wie lautet die Schneiderei-Restriktion?
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).
- F6.Im Diet-Problem (Stigler 1939) waren die Variablen Mengen einzelner Lebensmittel und die Zielfunktion war Minimierung der Gesamtkosten unter Erfüllung von Nährstoff-Anforderungen.
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
