L1 Lineare Optimierungsprobleme
Mathematische Einführung der Linearen Optimierung
Achtung, hier kommt die sehr kompakte und abstrakte mathematische Vorstellung des Problems der Linearen Optimierung. Diese wird nach und nach aber etwas mit Leben gefüllt.
Vereinfachtes Lineares Optimierungsproblem in Matrixschreibweise
| max | z= cT·x | Zielfunktion |
| u.d.N. | A·x ≤ b | Nebenbedingungen |
| x≥0 | Nichtnegativitätsbedingungen |
In Worten: Eine Zielgröße z soll maximiert werden, diese Zielgröße ist das Produkt aus einem Zeilenvektor mit Koeffizienten c und einem Variablenvektor x. Das heißt, es sollen die Werte von x bestimmt werden, sodass z den höchsten möglichen Wert erreicht.
Dabei sind aber Nebenbedingungen zu beachten, man sagt „unter den Nebenbedingungen“ oder kurz u.d.N. Das Produkt einer Koeffizientenmatrix A mit dem Variablenvektor x ist kleiner-gleich einem Beschränkungsvektor b. Für das vereinfachte Problem wird ferner angenommen, dass in b keine negativen Werte enthalten sind.
Zudem ist der Variablenvektor x≥0, d.h. keine Variable darf einen negativen Wert annehmen.
Vereinfachtes Lineares Optimierungsproblem in ausführlicher Schreibweise
Die vorstehende, sehr platzsparende Schreibweise nun noch einmal ausführlicher. Dafür werden die Bestandteile von Matrizen und Vektoren einzeln ausgeschrieben.
Zielfunktion
Zielwert
Zielfunktion
max z= c1·x1+ c2·x2+ c3·x3+…+ cn·xn
Der Ausdruck „max z“ bedeutet so viel wie: „Die folgende Aufgabe ist ein Optimierungsproblem, bei dem der Zielwert z einen möglichst großen Wert annehmen soll.“
Der Zielwert z errechnet sich als Summe von mit Koeffizienten cj multiplizierten Variablen xj. Es handelt sich somit um eine lineare Gleichung.
Allein mit der Zielfunktion wäre die Aufgabe recht langweilig. Einfach alle Variablen mit positiven Koeffizienten auf unendlich setzen! Deswegen erfolgt die Maximierung unter Nebenbedingungen.
Nebenbedingungen
kleiner-gleich
Restriktionen
Nebenbedingungen
| a11·x1 | + a12·x2 | + a13·x2 | + … | + a1n·xn | ≤ | b1 |
| a21·x1 | + a22·x2 | + a23·x2 | + … | + a2n·xn | ≤ | b2 |
| … | ||||||
| am1·x1 | + am2·x2 | + am3·x2 | + … | + amn·xn | ≤ | bm |
Bei der Wahl der Werte für die Variablen sind Nebenbedingungen zu beachten. Diese liegen in Form von linearen Ungleichungen vor. Die Werte für die Variablen müssen so gewählt werden, dass alle Ungleichungen erfüllt sind. Für den Anfang werden hier nur Ungleichungen vom Typ „kleiner-gleich“ betrachtet. Ferner wird angenommen, dass die Werte auf der rechten Seite positiv sind.
Nebenbedingungen werden häufig auch als Restriktionen bezeichnet.
Nichtnegativitätsbedingungen
x1≥0; x2≥0; x3≥0; … ; xn≥0;
Letzter unauffälliger aber sehr wichtiger Bestandteil eines Linearen Optimierungsproblems sind die Nichtnegativitätsbedingungen. Alle Variablen müssen null oder größer sein. Das scheint auf den ersten Blick vielleicht eine willkürliche Festlegung zu sein. Aber ohne sie funktioniert der Simplexalgorithmus nicht und oftmals sind bei realen Problemen tatsächlich nur positive Werte sachlich sinnvoll.
