Lineare Programmierung
Lineare Programmierung
Definition
Die Lineare Programmierung (engl. Linear Programming, LP) ist ein mathematisches Optimierungsverfahren zur Maximierung oder Minimierung einer linearen Zielfunktion unter linearen Nebenbedingungen.
---
Grundlagen
Zielfunktion
Die Zielfunktion ist eine lineare Funktion der Entscheidungsvariablen:
- max / min z = c₁x₁ + c₂x₂ + ... + cₙxₙ
Beispiel:
- Maximierung des Gewinns
---
Entscheidungsvariablen
Variablen, deren Werte gesucht werden:
- x₁, x₂, ..., xₙ ≥ 0
---
Nebenbedingungen
Lineare Gleichungen oder Ungleichungen:
- a₁₁x₁ + a₁₂x₂ + ... ≤ b₁
- a₂₁x₁ + a₂₂x₂ + ... ≥ b₂
---
Lösungsraum
Die Menge aller zulässigen Lösungen wird als zulässiger Bereich (feasible region) bezeichnet.
Eigenschaften:
- konvex
- durch lineare Ungleichungen begrenzt
---
Mathematische Formulierung
Allgemeine Form:
Maximiere oder minimiere:
- z = cᵀx
unter den Nebenbedingungen:
- Ax ≤ b
- x ≥ 0
---
Geometrische Interpretation
Bei zwei Variablen lässt sich das Problem grafisch darstellen:
- Nebenbedingungen bilden einen Bereich
- Zielfunktion wird als Gerade verschoben
- Optimum liegt an einer Ecke (Extrempunkt)
---
Beispiel
Maximiere:
- z = 3x + 2y
Nebenbedingungen:
- x + y ≤ 4
- x ≤ 2
- y ≤ 3
- x, y ≥ 0
Lösung:
- Optimum liegt an einem Eckpunkt des zulässigen Bereichs
---
Lösungsverfahren
Simplex-Verfahren
- Klassisches Verfahren
- Durchläuft systematisch die Eckpunkte
- Sehr effizient in der Praxis
---
Innere-Punkte-Verfahren
- Arbeiten im Inneren des Lösungsraums
- Gut für große Probleme geeignet
---
Graphische Methode
- Nur für 2 Variablen praktikabel
- Veranschaulichung des Problems
---
Eigenschaften
- Konvexe Optimierungsprobleme
- Lokales Optimum = globales Optimum
- Lösungen liegen an Randpunkten
---
Dualität
Zu jedem linearen Problem existiert ein duales Problem.
Eigenschaften:
- Zusammenhang zwischen primalem und dualem Problem
- Wirtschaftliche Interpretation (z. B. Schattenpreise)
---
Sensitivitätsanalyse
Untersuchung, wie sich Änderungen der Parameter auswirken:
- Änderung der Koeffizienten
- Änderung der Nebenbedingungen
- Stabilität der Lösung
---
Anwendungen
- Produktionsplanung
- Transportprobleme
- Ressourcenallokation
- Finanzoptimierung
- Netzflussprobleme
- Landwirtschaft (z. B. optimale Düngemittelverteilung)
---
Vorteile
- Mathematisch gut untersucht
- Effiziente Algorithmen verfügbar
- Eindeutige Lösungen
---
Nachteile
- Nur lineare Zusammenhänge modellierbar
- Vereinfachung realer Probleme notwendig
---
Erweiterungen
- Ganzzahlige Programmierung (Integer Programming)
- Gemischt-ganzzahlige Programmierung (MILP)
- Nichtlineare Programmierung (NLP)
---
Vergleich zu anderen Verfahren
| Verfahren | Eigenschaften |
|---|---|
| Lineare Programmierung | Exakt, effizient, linear |
| Nichtlineare Optimierung | Komplex, nicht-konvex möglich |
| Heuristiken | Schnell, aber nicht exakt |
---
Begriffe
- Zielfunktion
- Nebenbedingungen
- Lösungsraum
- Simplex
- Dualität
---
Literatur
- Dantzig, G.: Linear Programming and Extensions
- Nocedal, J.: Numerical Optimization
---