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).
Wenn Variablen ganzzahlig sein müssen, wird LP zum IP — und plötzlich ist das Problem NP-schwer. 8/8 OR-Klausuren behandeln das Thema.
Klausur-Tipp: Bei "Lösen Sie das IP" IMMER LP-Relaxation als obere/untere Schranke berechnen. Dann zeigen, dass naive Rundung fehlschlägt + nächstes Gitterpunkt-Argument. So sichert man Teilpunkte selbst ohne Branch & Bound durchgerechnet zu haben.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Wenn Variablen ganzzahlig sein müssen, wird LP zum IP — und plötzlich ist das Problem NP-schwer. 8/8 OR-Klausuren behandeln das Thema.
Ganzzahlige Programmierung (Integer Programming, IP): Eine lineare Optimierung, bei der die Variablen ganzzahlig sein müssen (statt beliebig reell).
| Typ | Variablen | Beispiel |
|---|---|---|
| Reines IP | Alle x_i ∈ ℤ | Anzahl Maschinen, Anzahl Mitarbeiter |
| Gemischt-ganzzahliges IP (MIP) | Manche x_i ∈ ℤ, andere reell | Mengen-Variablen + Setup-Kosten |
| 0-1-IP (binär) | x_i ∈ \0, 1\ | Ja/Nein-Entscheidungen, Zuordnung |
0-1-IP ist der wichtigste Spezialfall — Klausur-Klassiker.
LP-Relaxation: Lass die Ganzzahligkeits-Bedingung weg, löse das LP. Dann hast du eine kontinuierliche Lösung x_i^* — oft NICHT ganzzahlig (z.B. x₁^* = 3.75).
Naive Idee: Runde die LP-Lösung auf nächsten ganzen Wert.
Problem: Das funktioniert SELTEN. Drei Fallen:
(3.75, 1.25) → aufrunden auf (4, 2) verletzt vielleicht Restriktionen.2ⁿ Rundungs-Möglichkeiten. Bei 30 Variablen schon 1 Mrd Kombinationen.Daher: Eigene Algorithmen für IP. Standard: Branch & Bound (siehe eigenes Topic).
Integrality Gap: Differenz zwischen LP-Relaxation-Optimum und IP-Optimum.
Gap = z_(LP)^* - z_(IP)^* (bei max)
Eigenschaften:
z_(LP)^* ≥ z_(IP)^* (LP ist immer mindestens so gut)LP-Relaxation liefert immer eine obere Schranke für IP (bei max) → wichtig für Branch & Bound.
Anzahl Maschinen, Mitarbeiter, Fahrzeuge — alles ganze Zahlen.
"Soll Projekt
jdurchgeführt werden?" →x_j ∈ \0, 1\"Wird Standortieröffnet?" →y_i ∈ \0, 1\"Bekommt PersoniAufgabej?" →x_(ij) ∈ \0, 1\
"Wenn Maschine läuft, MUSS Setup-Kosten anfallen" "Wenn Bestellung > 0, dann mindestens 10 Stück"
Formulierung mit binärer Variable y ∈ \0, 1\ und großer Konstante M:
x ≤ M · y
→ Wenn y = 0, dann x ≤ 0 (also x = 0). Wenn y = 1, dann x ≤ M (frei).
"Entweder Restriktion A oder Restriktion B muss erfüllt sein."
Formulierung:
a_A^T x ≤ b_A + M(1 - y) und a_B^T x ≤ b_B + My mit y ∈ \0, 1\
Wähle Gegenstände mit max. Wert, ohne Gewichts-Grenze zu überschreiten.
max Σ_j v_j x_j s.t. Σ_j w_j x_j ≤ W, x_j ∈ \0, 1\
NP-schwer, aber gut studiert. Greedy-Approximation: nach Wert/Gewicht sortieren.
Wähle eine Menge von Standorten, die jede Region mindestens 1× abdecken.
Anwendung: Feuerwehr-Standorte, WLAN-Hotspots, Lager-Standorte.
Finde die kürzeste Rundreise durch
nStädte.
min Σ_(ij) c_(ij) x_(ij), x_(ij) ∈ \0, 1\
Mit zusätzlichen Subtour-Eliminations-Restriktionen. Klassisches NP-schweres Problem.
Ordne
nPersonennAufgaben zu, jede Person genau eine, minimiere Gesamtkosten.
min Σ_(ij) c_(ij) x_(ij), x_(ij) ∈ \0, 1\
mit Σ_j x_(ij) = 1 ∀ i und Σ_i x_(ij) = 1 ∀ j.
Spezialfall: LP-Relaxation ist hier exakt — Lösung ist automatisch ganzzahlig. Lösbar mit Hungarian Algorithm in O(n³).
| Problem | Komplexität |
|---|---|
| LP (kontinuierlich) | polynomial (Simplex praktisch schnell, Karmarkar's Algorithmus theoretisch polynomial) |
| Allgemeines IP | NP-schwer |
| 0-1-IP | NP-schwer (sogar das Knapsack-Entscheidungs-Problem ist NP-vollständig) |
| Assignment-Problem | polynomial (O(n³) via Hungarian) |
| TSP | NP-schwer |
| Verfahren | Wann? |
|---|---|
| Branch & Bound | Allgemeines IP, exakte Lösung |
| Branch & Cut | Kombination mit Schnittebenen (Gomory-Cuts) |
| Heuristiken | Schnelle Näherungs-Lösung (Greedy, lokale Suche, Genetic) |
| Spezial-Algorithmen | Assignment (Hungarian), Matching, MinCost-Flow |
| MIP-Solver | CPLEX, Gurobi, GLPK (Open Source) |
1. IP-Relaxation gibt OBERE Schranke (bei max). Wichtig für Branch & Bound und Bounds-Argumente.
2. Rundung der LP-Lösung ist KEIN gültiger IP-Algorithmus. Resultat kann unzulässig oder weit vom Optimum entfernt sein.
3. 0-1-IP ist wichtigster Spezialfall. Klausur-Beispiele: Knapsack, Assignment, Set Cover, Standort-Auswahl.
4. Big-M-Methode für logische Verknüpfungen. x ≤ M · y koppelt x an binäre Entscheidung y.
5. NP-Schwere bedeutet exponentielle Worst-Case-Laufzeit. In der Praxis lösen MIP-Solver (Gurobi, CPLEX) erstaunlich große Instanzen.
6. Assignment ist Spezialfall: LP-Relaxation ist exakt — kein Branch & Bound nötig.
1. LP-Lösung einfach runden. Falsch. Ergebnis kann unzulässig (zu viel Material) oder suboptimal sein. IMMER mit Branch & Bound oder spezial-Algorithmus.
2. 'IP-Optimum ≤ LP-Optimum' bei min vergessen. Bei MIN-Problemen gilt z_(LP)^* ≤ z_(IP)^*. Bei MAX gilt z_(LP)^* ≥ z_(IP)^*. Klausur-Falle.
3. Big-M zu klein wählen. Wenn M zu klein gewählt wird, ist die Restriktion x ≤ M · y aktiv selbst wenn y = 1 — verzerrt das LP. M muss > obere Schranke von x sein.
4. Assignment-Problem mit Branch & Bound lösen. Unnötig kompliziert — LP-Relaxation reicht (oder Hungarian Algorithm).
5. NP-schwer ≠ unlösbar. Real-world MIP-Solver lösen Instanzen mit Mio Variablen. NP-Schwere ist eine Worst-Case-Aussage.
6. Ganzzahlig vs. nichtnegativ verwechseln. x ∈ ℤ₊ heißt: ganzzahlig UND nichtnegativ. x ∈ ℤ ohne Index heißt: nur ganzzahlig, kann negativ sein.
3 Beispiel-Probleme (Rucksack / Produktions-Mix / Binäre Projekt-Auswahl) zeigen den Unterschied zwischen LP-Relaxation (kontinuierliche Lösung) und IP-Optimum (Gitterpunkt).
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Bei "Lösen Sie das IP" IMMER LP-Relaxation als obere/untere Schranke berechnen. Dann zeigen, dass naive Rundung fehlschlägt + nächstes Gitterpunkt-Argument. So sichert man Teilpunkte selbst ohne Branch & Bound durchgerechnet zu haben.
6 Aufgaben zu IP-Typen, LP-Relaxation, Big-M und Komplexität.
Klausurfragen mit Lösungen (6)
Antwort: IP-Variablen müssen ganzzahlig sein, LP-Variablen sind reell
Erklärung: Beim IP müssen einige (oder alle) Variablen ganzzahlig sein (x ∈ ℤ). Beim LP sind alle Variablen reell (x ∈ ℝ). Diese scheinbar kleine Änderung macht IP NP-schwer, während LP polynomial lösbar ist. Beides sind lineare Probleme (Zielfunktion + Restriktionen linear).
Antwort: x ∈ {0, 1}
Erklärung: 0-1-IP: x ∈ {0, 1}. Modelliert Ja/Nein-Entscheidungen. Klausur-Klassiker: x_ij = 1 wenn Person i Aufgabe j zugeordnet, sonst 0. Wichtigster IP-Spezialfall.
Zuordnungen:
Erklärung: Klassische 0-1-IP-Probleme: Knapsack (max Wert), TSP (min Strecke), Set Cover (min Standorte), Assignment (min Kosten 1:1). Alle bis auf Assignment sind NP-schwer. Assignment ist polynomial (Hungarian Algorithm, O(n³)) — LP-Relaxation ist hier sogar exakt.
Typ: Zuordnung
Antwort: Differenz zwischen IP-Optimum und LP-Relaxations-Optimum
Erklärung: Integrality Gap = z*_LP − z*_IP (bei max). Misst, wie gut die LP-Relaxation das IP approximiert. Kleine Gap → LP-Schätzung ist gut → Branch & Bound terminiert schnell. Große Gap → IP ist 'schwer'. Wichtig: bei min ist Gap = z*_IP − z*_LP (umgekehrt).
Antwort: Falsch
Erklärung: FALSCH. Aufrunden kann (1) UNZULÄSSIG sein (Restriktionen verletzt) oder (2) suboptimal (IP-Optimum ist nicht der gerundete LP-Punkt, sondern ein anderer Gitterpunkt). Beispiel: LP gibt (3.75, 1.25), aufrunden auf (4, 2) verletzt Gewichts-Restriktion → tatsächliches IP-Optimum ist (3, 2). Daher: eigene IP-Algorithmen (Branch & Bound).
Typ: Wahr/Falsch
Antwort: z*_LP ≥ z*_IP
Erklärung: Bei max: z*_LP ≥ z*_IP. Begründung: LP ist 'lockerer' (mehr Lösungen erlaubt — auch nicht-ganzzahlige). Also kann das LP höchstens besser sein als IP. LP-Optimum ist OBERE SCHRANKE für IP. Bei min umgekehrt: z*_LP ≤ z*_IP, LP ist UNTERE Schranke. Wichtig für Branch & Bound!
6 typische Klausurfragen zu IP-Modellierung, Big-M, NP-Schwere und Algorithmen.
Klausurfragen mit Lösungen (6)
Antwort: Assignment-Problem (n×n)
Erklärung: Assignment-Problem ist POLYNOMIAL — der Hungarian Algorithm (Kuhn 1955) löst es in O(n³). Andere drei sind klassische NP-schwere Probleme. Assignment ist Spezialfall, weil die LP-Relaxation automatisch ganzzahlige Lösungen liefert (Eckpunkte des LP-Polyeders sind ganzzahlig).
Antwort: Branch & Bound
Erklärung: Branch & Bound ist Standard-IP-Algorithmus: Problem in Subprobleme zerlegen (Branch), LP-Relaxation als Schranke (Bound), suboptimale Äste abschneiden (Pruning). Simplex löst nur LPs (kontinuierlich). Gradient Descent ist für nichtlineare Optimierung. Dijkstra für kürzeste Pfade.
Lösungen pro Lücke:
Erklärung: 0-1-Variable: x ∈ {0, 1}. Modelliert Ja/Nein-Entscheidungen (Projekt ja/nein, Standort öffnen ja/nein). Big-M-Methode: x ≤ M · y koppelt kontinuierliche Variable x an binäre y. Wenn y=0, dann x=0. Wenn y=1, dann x ≤ M (frei). M muss obere Schranke von x sein.
Typ: Lückentext
Richtige Reihenfolge:
Erklärung: Branch & Bound: 1) LP-Relaxation lösen → Lösung x* meist nicht ganzzahlig. 2) Branch: für eine fraktionale Variable xi = 1.7 zwei Sub-Probleme: xi ≤ 1 und xi ≥ 2. 3) Bound: jedes Subproblem LP-relaxieren. 4) Prune: wenn Bound schlechter als beste bekannte ganzzahlige Lösung → Ast verwerfen. Wiederholen bis alle Äste durchgegangen.
Typ: Reihenfolge
Antwort: x ≤ 0, also bei x ≥ 0: x = 0 erzwungen
Erklärung: Wenn y = 0: x ≤ M · 0 = 0. Bei der Nichtnegativitäts-Bedingung x ≥ 0 wird also x = 0 erzwungen. Wenn y = 1: x ≤ M (effektiv frei). So koppelt Big-M die kontinuierliche Variable x an die binäre Entscheidung y. Wichtig: M muss > obere Schranke von x sein, sonst verzerrt es das Optimum.
Antwort: Wahr
Erklärung: RICHTIG. NP-Schwere ist eine Worst-Case-Aussage. In der Praxis nutzen moderne MIP-Solver (Gurobi, CPLEX, GLPK) Branch & Cut + Heuristiken + clever vor-verarbeiten. Real-world MIPs mit Tausenden Variablen sind oft in Sekunden bis Minuten lösbar. Klausur-Klassiker: 'NP-schwer ≠ unlösbar in der Praxis'.
Typ: Wahr/Falsch