Lineare Programmierung

Lineare Optimierung (auch Linear Program oder kurz LP) ist ein Spezialfall der Optimierung, bei der alle Funktionen linear sind.

Klassische Formulierung

Jedes beliebige LP-Problem lässt sich wie folgt notieren:

Unter den Nebenbedingungen:

Nichtnegativitätsbedingungen:

Normalform

Um das Problem in Normalform umzuformen, wird das Problem als Gleichungssystem dargestellt. Dafür werden zu jeder Nebenbedingung sogenannte Schlupfvariablen (nichtnegative Variablen) ergänzt und das kleiner-gleich-Zeichen durch ein Gleichzeichen ersetzt. In der Zielfunktion werden diese mit dem Koeffizienten bewertet.

Formale Definition

Maximiere die

unter den Nebenbedingungen

mit Nichtnegativitätsbedingung

Insgesamt ergeben sich Strukturvariablen und Schlupfvariablen (aufgrund der Nebenbedingungen).

Matrixschreibweise

Maximiere

unter den Nebenbedingungen

• sind die Entscheidungsvariablen (Dimension ) (Die gilt es zu finden)
• ist der Zielfunktionsvektor (Dimension ) (Diese Funktion gilt es zu maximieren)
• ist eine Matrix und heißt Koeffizientenmatrix
• ist der Restriktionsvektor (Dimension ) (Die rechte Seite der Nebenbedingungen)

Beispiel zu den Notationen