LP-Modell

Ein LP-Modell (lineares Optimierungsmodell) liegt vor, wenn Zielfunktion und Nebenbedingungen linear sind und die n (Struktur-) Variablen x1, . . . , x n (nichtnegative) reelle Zahlenwerte annehmen dürfen. Eine allgemeine, kompakte Formulierung eines LP-Modells erhält man unter Verwendung der Vektorschreibweise. Zur Bewertung der im Lösungsvektor x =(x1, ..., x n) zusammengefassten Variablen benötigt man einen Vektor c = (c1, . . . , cn) von Zielfunktionskoeffizienten. Zur Formulierung der m Nebenbedingungen sind eine -Koeffizientenmatrix A und ein Vektor b = (b1, ..., bm) der rechten Seiten erforderlich. Mit diesen Parametern ergibt sich die allgemeine Formulierung eines linearen OM (man beachte das Transponiertzeichen, auf das wir aus Darstellungsgründen im Text verzichten, obwohl wir Vektoren stets in Zeilenform angeben): Bei (1)-(2) handelt es sich um die Normalform eines LP-Modells. Liegt ein Modell ursprünglich nicht in dieser Form vor, so kann es im Falle von Ungleichungen in den Nebenbedingungen durch Einführen von Schlupfvariablen, die in der Zielfunktion mit Koeffizient

en 0 zu gewichten sind, in Normalform überführt werden. Als Beispiel diene eine Modellinstanz mit zwei Strukturvariablen x1 und x2: Mit den Schlupfvariablen x3, x4, x5 ergibt sich die Normalform von (3)-(7): Im Rahmen von Lösungsverfahren wie z.B. dem Simplex-Algorithmus ist der Begriff Basislösung (BL) von Bedeutung. Eine bezüglich (2) zulässige Lösung x ist BL, wenn sich die Menge der n Variablen aufteilen lässt in n-m Nichtbasisvariablen (NBV) mit Wert 0 und m Basisvariablen (BV) mit nichtnegativen Werten (letztere bilden die Basis). Nummeriert man die Variablen so durch, dass x1, . . . , x n-m NBV und xn-m+1, ..., xn BV sind, und löst das Gleichungssystem nach den BV auf, so erhält man mit einer -Matrix und einer -Einheitsmatrix I. Diese BL ist zulässig, wenn gilt. Liegt eine zulässige BL vor, so befindet sich das Modell in kanonischer Form und kann unmittelbar mit dem primalen Simplex-Algorithmus gelöst werden. Ansonsten ist zunächst eine zulässige BL zu ermitteln, z.B. mit der M-Methode oder dem dualen Simplex- Algorithmus. Die Modellinstanz (3’)-(7’) hat kanonische Form; die zulässige BL ist gegeben durch die NBV x1 = x2 = 0 und die BV x3 = 100, x4 = 720, x5 = 60 mit F(x) = 0. Für dieses einfache Beispiel mit nur zwei (Struktur-)Variablen kommt neben dem Simplex-Algorithmus auch die graphische Optimierung in Frage.

<< vorhergehender Begriff

nächster Begriff >>

LP

LP-Modelle