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 Koeffizienten 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.

Modell i. R. des Operations Research (OR) , die mathematisch oder graphisch zu Optimallösungen beitragen sollen, indem eine lineare Zielfunktion unter einer Vielzahl von Nebenbedingungen extremiert ( Optimal ) wird. Anwendung finden solche Modelle bei der Fertigungsplanung (Minimierung des Verschnittes von Textilien, optimale Mischungen von Rohstoffen, Optimierung eines Finanzportefeuilles). Mathematisch lassen sich derartige Probleme mit der Simplex-Methode lösen. Graphisch können die Nebenbedingungen in einem Koordinatensystem dargestellt werden (Polyeder) und die Zielfunktion entsprechend der Extremierungsvorschrift an die optimale Stelle im Rahmen des Zulässigen Bereiches (Lösungsbereiches) verschoben werden.

(lineare Optimierungsmodelle), siehe LP-Preprocessing von LP-/IP-Modellen.

Vorhergehender Fachbegriff: LP | Nächster Fachbegriff: LP-Modelle

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Geldhandel | Produktionsverflechtung | Compilation

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer