Lineares Optimierungsproblem
Definition
Ein Lineares Optimierungsproblem ist eine mathematische Aufgabenstellung, bei der eine lineare Zielfunktion unter Berücksichtigung von linearen Nebenbedingungen (Einschränkungen) optimiert werden soll.
Ein Lineares Optimierungsproblem besteht aus drei Hauptkomponenten:
- Zielfunktion: Eine Funktion, deren Wert entweder maximiert (z. B. Gewinnfunktion oder Erlösfunktion) oder minimiert (z. B. Kostenfunktion) werden soll.
- Bedingungssystem (Nebenbedingungen): Ein System von linearen Ungleichungen, das die verfügbaren Ressourcen wie Maschinenkapazitäten, Materialvorräte oder Arbeitszeit beschreibt (siehe auch Kapazitätsgrenze).
- Nichtnegativitätsbedingungen (NNB): Da in wirtschaftlichen Kontexten keine negativen Mengen produziert werden können, muss für alle Entscheidungsvariablen gelten: \(x_i \ge 0\).
Es wird unterschieden zwischen:
- Maximierungsproblem: Ziel ist das Erreichen des höchsten Wertes (z. B. Deckungsbeitragsmaximierung).
- Minimierungsproblem: Ziel ist das Erreichen des geringsten Wertes (z. B. Kostenminimierung beim Einsatzproblem).
Modellierung ökonomischer Prozesse
Um ein reales Problem mathematisch abzubilden, werden Entscheidungsvariablen definiert (z. B. \(x_1\) für Produkt A, \(x_2\) für Produkt B). Die sprachlichen Informationen werden dann in ein mathematisches Modell übersetzt, das oft die Form eines linearen Systems annimmt, jedoch mit Ungleichungen statt Gleichungen.
Beispiel
Die Modellwerk Ruhr GmbH produziert zwei Spielzeugmodelle:
- Kran: 40 € Deckungsbeitrag (DB) pro Stück.
- Lok: 50 € DB pro Stück.
Die Produktion ist durch zwei Abteilungen begrenzt:
- Holzbearbeitung: \(2x_1 + 1x_2 \le 100\) Stunden
- Endmontage: \(1x_1 + 2x_2 \le 80\) Stunden
- NNB: \(x_1, x_2 \ge 0\)
Die Zielfunktion lautet: \(z = 40x_1 + 50x_2 \rightarrow \text{max!}\)