Grundlagen zur linearen Optimierung

Die lineare Optimierung ist auch unter der Bezeichnung lineare Programmierung bekannt. Sie beschäftigt sich, wie der Name schon sagt, „mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist“1. Dabei wird die (Ziel-) Funktion minimiert oder maximiert, unter Beachtung der linearen Nebenbedingungen, die man auch Restriktionen nennt. Die Variablen (x1, x2, ... , xn) hingegen in der (Ziel-)funktion nennt man Entscheidungsvariablen.

Nachfolgend der allgemeine Aufbau eines linearen Optimierungsproblems.

Den Anfang macht die allgemeine Form einer linearen Zielfunktion von n Variablen:
f(x) = c1x1 + c2x2 + ... + cnxn

Anschließend die allgemeine Form der linearen Nebenbedingungen:
ai1x1 + ai2x2 + ... ainxn ≥ bj
ai1x1 + ai2x2 + ... ainxn ≤ bj
ai1x1 + ai2x2 + ... ainxn = bj

Zu guter Letzt noch die Nichtnegativitätsbedingungen:
x1, x2 ... xn ≥ 0

Die allgemeine Form eines linearen Optimierungsproblems setzt sich nun einfach aus den vorangegangen Teilen zusammen:

P: max/min f(x) = c1x1 + c2x2 + ... + cnxn
s.t. ai1x1 + ai2x2 + ... ainxn bj
ai1x1 + ai2x2 + ... ainxn bj
ai1x1 + ai2x2 + ... ainxn = bj
x1, x2 ... xn 0

Betrachtet wird also immer ein Minimierungs- oder Maximierungsproblem. Das s.t. Ist die Abkürzung für subject to und bedeutet unter den Nebenbedingung. Dementsprechend werden danach auch alle Nebenbedingungen aufgelistet, den Abschluss bilde die Nichtnegativitätsbedingung.


Quellen:
1 - Wikipedia Lineare Optimierung
Operations Research von Nickel, Stein, Waldmann