Lineares Optimierungsproblem

Definition

Ein lineares Optimierungsproblem besteht aus einer Zielfunktion und einem System von einschränkenden Bedingungen (Nebenbedingungen), die alle linear sind.

Man unterscheidet:

• Maximierungsprobleme (z. B. Maximierung von Gewinn oder Deckungsbeitrag)
• Minimierungsprobleme (z. B. Minimierung von Kosten oder Transportaufwand)

Maximiere bzw. minimiere die Zielfunktion

[math]\displaystyle{ Z = c_1x_1 + c_2x_2 + \dots + c_nx_n }[/math]

unter den Nebenbedingungen

[math]\displaystyle{ \begin{aligned} a_{11}x_1 + a_{12}x_2 &\le b_1\\ a_{21}x_1 + a_{22}x_2 &\le b_2\\ \vdots \end{aligned} }[/math]

sowie den Nichtnegativitätsbedingungen

[math]\displaystyle{ x_1 \ge 0,\; x_2 \ge 0,\; \dots }[/math]

Die Menge aller zulässigen Lösungen heißt zulässiger Bereich.

Ökonomische Interpretation

• Zielfunktion: Gewinnfunktion oder Erlösfunktion
• Nebenbedingungen: Kapazitätsgrenzen (vgl. Kapazitätsgrenze)
• Variablen: Produktionsmengen

Grafische Lösung

Bei zwei Entscheidungsvariablen kann das Problem grafisch gelöst werden:

• Zeichnen der Nebenbedingungen als Geraden (vgl. Lineare Funktion)
• Bestimmung des zulässigen Bereichs
• Untersuchung der Eckpunkte (vgl. Eckpunktberechnungsmethode)

Beispiel

Ein Unternehmen produziert zwei Produkte:

• Gewinn pro Stück A: 3 GE
• Gewinn pro Stück B: 5 GE

Nebenbedingungen:

[math]\displaystyle{ \begin{aligned} 2x + y &\le 8\\ x + 2y &\le 8\\ x,y &\ge 0 \end{aligned} }[/math]

Zielfunktion:

[math]\displaystyle{ Z = 3x + 5y \rightarrow \max }[/math]

Zusammenhang zu anderen Themen

• Lösung von Gleichungssystemen: Lineares Gleichungssystem
• Darstellung in Tabellenform: Matrix