lineare Programmierung

Lineare Programmierung (LP) (auch lineare Planungsrechnung, lineare Optimierung) ist die Minimierung oder Maximierung einer Zielfunktion unter Beachtung verschiedener Nebenbedingungen (Restriktionen), wobei die Variablen in Zielfunktion und Nebenbedingungen nur in der ersten Potenz auftreten. Die lineare Programmierung gehört zu den Verfahren des Operations Research.

Zur Bestimmung der gewinnoptimalen Menge wird eine Abteilungsleiter-Konferenz einberufen. Dabei erklärt der Leiter der Verkaufsabteilung, daß aus absatz- und sortimentspolitischen Gründen von Produkt A mindestens 20 und höchstens 80 Einheiten pro Monat hergestellt werden sollen.

Die entsprechenden Werte für Produkt B belaufen sich auf 10 (Mindestmenge) und 50 (Höchstmenge). Der Leiter der Einkaufsabteilung berichtet von einer Lieferstockung hinsichtlich eines zur Erzeugung von A notwendigen Rohstoffs. Danach können im kommenden Monat lediglich 150 Rohstoffeinheiten beschafft werden. Zur Erstellung einer Einheit A sind 2 Rohstoffeinheiten erforderlich. Die monatlichen Fixkosten belaufen sich auf 8 000 EUR.

Gesucht ist das gewinnmaximierende Programm. Dazu sind die verfügbaren Informationen in Nebenbedingungen, Zielfunktion und Nichtnegativitätsbedingungen umzuformen.

Zur Lösung des so formulierten Problems wird im allgemeinen die Simplex-Methode verwendet. Der gegebene Fall zweier Güter läßt aber auch eine grafische Lösung zu. Diese hat den Vorzug der Anschaulichkeit.

Betrachtet man die gestrichelte Isogewinnlinie mit der Steigerung, dann erkennt man, daß die Ecke E3 gewinnoptimal ist.

Demnach sind im kommenden Monat zu fertigen:
xa = 60 Einheiten und xb = 40 Einheiten.

Dabei wird ein Nettogewinn von
Gne = 60 ? 90 + 40 ? 120 ? 8 000 = 2 200 EUR pro Monat

erzielt.

Anwendung:
(1) Die Anwendungsbreite der LP ist beträchtlich. Neben der Bestimmung des gewinnmaximalen Programms (Programmoptimierung) läßt sich dieses Verfahren einsetzen zur Verschnittminimierung, z. B. bei der Bearbeitung von Blechen, Mischungsoptimierung, z. B. bei der Herstellung von Tierfuttermittel, Wahl des optimalen Produktionsverfahrens (Verfahrenswahl), Problemlösung bei Eigenfertigung oder Fremdbezug, Transportoptimierung (kostenminimierende Tourenpläne für Reisende), Ermittlung optimaler Bestellmengen und Losgrößen.

(2) LP kann auch außerhalb der Kostenrechnung angewendet werden,
etwa zur Ermittlung optimaler Investitions- und Finanzierungsprogramme, zur Produktionssteuerung und zur Erstellung von Stundenplänen.

(3) Zur Lösung eines LP-Problems ist im praktischen Fall ein Computer-Einsatz notwendig; eine manuelle Lösung kommt meist schon aus Zeitgründen nicht in Frage. Für Großrechner existiert mittlerweile ein breites Angebot an Standardsoftware, die manches über die Optimierungsrechnung hinaus anbietet, etwa Sensibilitätsanalyse. Die Entwicklung von LP-Programmen für den PC ist noch in vollem Gange. Für kleinere und mittlere Betriebe dürften die PC-Lösungen ausreichen.

englisch: Linear programming Lineare Programmierung oder lineare Planungsrechnung ist ein Verfahren des – Operations Research zur Lösung komplexer Entscheidungsprobleme. Die Anwendung dieser Methode führt zur Bestimmung einer hinsichtlich eines Ziels optimalen Alternative unter gleichzeitiger Berücksichtigung einer oder mehrerer Restriktionen. Für die Bewertung der Lösungen muß ein objektiver Maßstab wie Kosten, Erlöse oder Mengen gefunden werden. Die Modellkomponenten müssen quantifizierbar sein. Die Problemstellung muß sich durch ein System linearer Gleichungen und Ungleichungen ausdrücken lassen.

Es gibt verschiedene Lösungsverfahren:

1. Distributions-Methode: Gilt insbesondere für die Lösung von Transportproblemen. Kann nur für solche Aufgaben herangezogen werden, die durch Beschränkungsgleichungen mit den Koeffizienten »eins für die Variablen und Hilfsvariablen beschrieben sind.

2. Simplex-Methode: Die Gleichungen werden, nachdem die Ungleichungen durch Schlupfvariable in Gleichungen verwandelt worden sind, in einer Matrix zusammengestellt, die Schritt für Schritt nach bestimmten Regeln in neue Matrizen umgewandelt werden, bis in einer Matrix die optimale Lösung gefunden ist. Da das Maximum oder Minimum einer linearen Funktion unter gewissen Nebenbedingungen zu suchen ist, kommen als Anwendungsgebiete betriebswirtschaftliche Entscheidungsprobleme z.B. folgender Art in Frage:

1. Bestimmung der optimalen Zusammensetzung des Fertigungsprogramms (Fertigungsprogrammplanung)

2. Bestimmung eines optimalen Investitionsbudgets

3. Bestimmung der Optimalkapazität des Betriebes

4. Bestimmung der optimalen Losgröße bzw. der optimalen Bestellmenge.

Die lineare Programmierung, auch lineare Optimierung genannt, ist die wohl am meisten angewandte Methode des Operations Research, um optimale Entscheidungen zu treffen. Sie dient der Bestimmung einer optimalen Verteilung bei Verwendung begrenzter Kapazitäten, um ein bestimmtes Ziel zu erreichen. Das Entscheidungsmodell der linearen Programmierung besteht aus der Zielfunktion und den Nebenbedingungen sowie den Nicht-Negativitätsbedingungen und Ganzzahligkeitsbedingungen. Grundlage der linearen Programmierung sind lineare Beziehungen sowohl bei der Zielfunktion als auch bei den Nebenbedingungen. Lineare Programmierungsprobleme können Maximierungs- und Minimierungsprobleme sein. Die Universalmethode der linearen Programmierung ist die Simplexmethode.

lineare Optimierung

Die Lineare Programmierung ist eine Technik zur Optimierung von Problemstellungen unter Zuhilfenahme mathematischer Algorithmen. Dabei müssen sich die Probleme darstellen lassen als ein System von linearen Ungleichungen (auch Nebenbedingungen genannt) und einer linearen Zielsetzung (auch Zielfunktion genannt). Synonyme Begriffe zur Linearen Programmierung sind lineare Planungsrechnung oder lineare Optimierung. Das Grund modell der LP hat die folgende Struktur Zielfunktion: n max Z L c, x, j1 Nebenbedingungen: n Z a“ x, = bj für 1,. . . . x, S 0 für1,. . ., n Die Xj stehen für die vom Algorithmus zu ermittelnden Entscheidungsvariablen. Die Zielfunktionsbeiträge der Variablen werden durch Cj dargestellt, ajj charakterisieren die Auswirkungen von Variablenwerten in bezug auf die Nebenbedingungen, die durch den konstanten Wen b, begrenzt werden. Alle Probleme, die in solchen Modellen dargestellt werden können, lassen sich mit Hilfe der SimplexMethode lösen. Diese Methode wurde von Dantzig entwickelt und in dem wohl bedeutendsten Werk der Linearen Programmierung dargelegt (G. B. Dantzig, Lineare Programmierung und Erweiterungen, deutsche Übersetzung von A. Jaeger, BerlinHeidelbergNew York 1966). Die Nebenbedingungen des LPs bilden, mathematisch gesehen, ein konvexes Polyeder, d. h. einen zusammenhängenden Bereich, in dem alle zulässigen Variablenkombinationen liegen. Dieser Bereich wird Zulässigkeitsbereich genannt. Die Schnittpunkte der Nebenbedingungen werden Ecken oder Basislösungen genannt. Die Zielfunktion, die über den Zulässigkeitsbereich maximiert oder minimiert wird, kann nur in einer Ecke ( oder in mehreren) ihren Extremwert annehmen. Diese Ecke heißt Basislösung. Die SimplexMethode geht von einer zulässigen Basislösung aus, wandert systematisch unter Berücksichtigung der Zielfunktion von einer Ecke zur anderen, bis sie durch einen weiteren Eckentausch oder Basiswechsel nicht mehr verbessert werden kann. Somit ist nach endlich vielen Basiswechseln die optimale Lösung, falls eine existiert, gef und en. Da praktische LPModelle mehrere tausend Variablen und Nebenbedingungen aufweisen können, ist es für die Zwecke der Lösbarkeit mittels EDVAnlage innerhalb vertretbarer Zeiten notwendig, die SimplexMethode abzuwandeln bzw. zu erweitern. Die Abwandlung führt zur revidierten SimplexMethode, die nicht mehr die gesamte Matrix der Koeffizienten während der Berechnung mitführt, sondern nur die zum Basiswechsel erforderlichen Koeffizienten. Erweiterungen bestehen z. B. in einer Prozedur, die eine erste zulässige Basislösung ermittelt (CrashProzedur). Außerdem besitzen die meisten Soft702 warepakete eine Reinversionsprozedur, die versucht, Rechenungenauigkeiten auszugleichen, die bei häufigem Basiswechsel auftreten. Die meisten auf dem Markt existierenden Softwaresysteme zur linearen Optimierung (MPSX von IBM, LP5000 von Siemens, FMPS von Sperry Univac) benutzen einheitlich zur Dateneingabe das MPSFormat (mathematical programming System format), bei dem Variablen und Nebenbedingungen durch ihre Namen (8 Stellen) identifiziert werden. Auch die Ausgabe der Lösung ist standardisiert. Die Lineare Programmierung kann als die wichtigste Methode innerhalb des» Operations Research angesehen werden, da viele andere Optimierungsmethoden wie nichtlineare Optimierung, ganzzahlige Optimierung, Transportproblematik, Netzplantechnik, Zuteilungsproblematik als Spezialfälle aus der Linearen Programmierung hervorgegangen sind.

In der Praxis ist die Lineare Programmierung am stärksten im Produktionsbereich vertreten. Die Anwendungen reichen von der Produktionsprogrammplanung über die Verfahrensplanung bis zur optimalen Mischungs und KuppelprozeßplanungBei der Produktionsprogrammplanung geht es darum, die zu produzierenden und abzusetzenden Mengen von Produkten zu bestimmen. Die Nebenbedingungen bestehen in den Kapazitätsrestriktionen, den Absatzgrenzen und gegebenenfalls, bei mehrperiodigen Modellen, in Lager bedingungen, bei mehrstufigen Modellen über mehrere Produktionsstufen in Mengenflußbedingungen. Die Verfahrensplanung entscheidet im Falle von mehreren alternativen Arbeitsplänen oder Arbeitsgängen über das optimale Produktionsverfahren. In vielen Fällen ist dieses Entscheidungsproblem integriert in die Produktionsprogrammplanung. Mischungsprobleme zeichnen sich dadurch aus, daß die Mengen der Input und Outputstoffe als Variablen definiert werden. Somit müssen die Nebenbedingungen sämtliche Mengenbeziehungen erfassen und als »Mengenbilanzen« darstellen. Die Anwendungen aus dem Produktionsbereich setzen meist konstante Kapazitäten voraus. Läßt man diese Voraussetzung fallen, so gelangt man zu Investitionsplanungsmodellen oder integrierten Investitions, Finanz und Produktionsplanungsmodellen. Theoretisch sind solche Modelle sehr interessant, insbesondere deswegen, weil sie der Forderung nach Integration der betrieblichen Teilbereiche nachkommen. In der Praxis werden sie jedoch kaum angewandt, da Modellerstellung, Datenerhebung und nicht zuletzt die Optimierungsrechnung einen hohen Aufwand bedingen. weitere Anwendungsgebiete der Linearen Programmierung liegen im MarketingBereich mit Modellen zur Absatz und Absatzförderungsplanung, im Finanzbereich mit Capital Budgeting und im Transportwesen. Diese Aufzählung kann weiter fortgesetzt werden, da sich die meisten Detriebswirtschaftlichen Planungsprobleme als Lineares Programm darstellen lassen. Im Einzelfall ist dann zu prüfen, ob das Problem wirtschaftlich mit dieser Methode zu lösen ist oder ob es Methoden gibt, die der Problemstellung eher entsprechen (z. B. Netzplantechnik, Simulation).

Vorhergehender Fachbegriff: lineare Planungsrechnung | Nächster Fachbegriff: Lineare Programmierung (LP)

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : Versicherungsgesellschaft(en) | Käuferland | internationale Nachfrage

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