Lineare Optimierung

Die lineare Optimierung ist ein zentraler Bestandteil der Wirtschaftsmathematik und beschäftigt sich mit dem Problem, optimale Lösungen in Situationen zu finden, in denen die Ziele durch lineare Abhängigkeiten beschränkt sind. Es geht darum, eine oder mehrere lineare Funktionen zu maximieren oder zu minimieren. Diese Methode findet Anwendung in vielen Bereichen, wie z.B. in der Produktionsplanung, bei der Allokation von Ressourcen und in finanziellen Entscheidungen.

Lineare Optimierung – einfach erklärt

Lineare Optimierung, manchmal auch "lineare Programmierung" genannt, ist ein wichtiger Bestandteil der Wirtschaftsmathematik. Sie wird unter anderem in der Produktion und der Logistik eingesetzt. Die lineare Optimierung beschäftigt sich im Grunde mit der Maximierung oder Minimierung einer linearen Funktion (Zielfunktion) unter Nebenbedingungen.

Die lineare Optimierung hat dabei drei wichtige Bestandteile:

• die Zielfunktion
• die Nebenbedingung
• die Nichtnegativitätsbedingung

Die Zielfunktion kann beispielsweise ein maximaler Erlös sein.

Die Nebenbedingungen sind Grenzen, die zum Beispiel durch eine maximale Maschinenkapazität gegeben sind.

Die Nichtnegativitätsbedingung gibt an, dass die Entscheidungsvariablen der linearen Optimierung nur größer oder gleich null sein dürfen. (Negative Mengen eines Produkts können nicht produziert werden.)

Die lineare Optimierung hilft im besten Fall eine oder sogar mehrere Verbesserungen in der Produktion vorzunehmen. Es kann aber auch vorkommen, dass es keine optimale Lösung existiert.

Lineare Optimierung – Anwendung

Die lineare Optimierung ist eine der Hauptverfahren in der Operations Research und Unternehmensplanung. Diese Abteilungen eines Unternehmens beschäftigt sich mit der Planung der Tätigkeiten und trägt so zur Erreichung der Unternehmensziele bei.

Lineare Optimierung – Minimierung

Obwohl das folgende Beispiel eine Aufgabe zur Maximierung mittels der linearen Optimierung darstellt, ist es auch möglich, mit der linearen Optimierung eine Minimierung durchzuführen. Hierbei würde man also nicht den höchsten Wert suchen, sondern den geringsten. Das Verfahren funktioniert also "in beide Richtungen".

Lineare Optimierung Beispiel – Produktionsplanung

Wie Du gerade gelesen hast, wird die lineare Optimierung in der Unternehmensplanung, insbesondere in der Produktion angewendet. Das Prinzip hinter der linearen Optimierung versteht man am besten mit einem Beispiel aus der Praxis.

Lineare Optimierung – Zielfunktion aufstellen

Die zu maximierende (oder minimierende) lineare Funktion heißt Zielfunktion.Die in der Zielfunktion auftretende Variablen (x, y) heißen Entscheidungsvariablen.

Um eine Zielfunktion aufzustellen, benötigst Du für das obige Beispiel jeweils eine Variable pro Produkt. Das kann zum Beispiel x für Pullover und y für Jacken sein.

Nimm an, der Produzent erzielt pro verkauftem Pullover einen Gewinn von sieben Geldeinheiten (GE) und für jede verkaufte Jacke einen Gewinn von vier Geldeinheiten. Mit diesen Eckdaten kannst Du nun die lineare Zielfunktion aufstellen:

Nebenbedingungen

Da der Produzent aus dem Beispiel aber nicht unendlich viele Pullover und Jacken produzieren kann – weil zum einen, die Kapazitäten der Produktion beschränkt sind, aber auch weil die Nachfrage am Markt begrenzt ist – musst Du mehrere Nebenbedingungen beachten.

Nimm an, innerhalb des Planungszeitraums können maximal 10 Pullover und sieben Jacken verkauft werden. Diese Restriktion ergibt Deine erste Nebenbedingung:

Die Maschine, die für die Produktion der Waren genutzt wird, ist in ihrer Kapazität begrenzt. Angenommen innerhalb des Planungszeitraums beträgt diese 15 Zeiteinheiten (ZE). Du weißt, dass die Produktion eines Pullovers drei ZE benötigt und die Herstellung einer Jacke dauert zwei ZE.

Auch die Mitarbeiter in der Produktion haben eine zeitliche Beschränkung, diese musst Du auch berücksichtigen. Angenommen das Personal hat eine Kapazität von 20 ZE zur Verfügung. Die Produktion eines Pullovers kostet die Mitarbeiter sechs ZE, eine Jacke dauert zwei Zeiteinheiten.

Nichtnegativitätsbedingung

Jetzt fehlt nur noch die Nichtnegativitätsbedingung! Wie oben schon erwähnt, bedeuten diesen beiden Nebenbedingungen nichts anderes, als dass die Anzahl der produzierten Pullover und Jacken nicht negativ sein darf.

Lineare Optimierung – graphisch

Um die Zielfunktion zu optimieren, hast Du jetzt zwei Optionen, die rechnerische und die graphische. Um besser zu visualisieren, was genau maximiert wird, kann es sinnvoll sein, erst die graphische Lösung anzugehen.

Lineares Gleichungssystem – Nebenbedingungen

Neben der Zielfunktion hast Du nun sechs Nebenbedingungen, die die Produktion beschränken. Hier siehst Du sie noch einmal auf einen Blick:

1. x≤ 10
2. y≤ 20
3. 3x + 2y≤ 15
4. 6x + 2y≤ 20
5. x≥ 0
6. y≥ 0

Lösungsmenge graphisch bestimmen

Nachdem Du die dritte und die vierte Nebenbedingung nach y auflöst, und anschließend die Ungleichungen als Geradengleichungen interpretierst, kannst Du jetzt Deine Nebenbedingungen im Koordinatensystem eintragen.

Die fünfte und die sechste Nebenbedingung, also die Nichtnegativitätsbedingung werden durch die x- und y-Achse visualisiert, da keine negativen Produktionsmengen erzeugt werden können.

Du siehst in der Grafik, dass es zu vier Schnittpunkten kommt. A, B, C und D begrenzen also die Lösungsmenge. Die sich daraus ergebende Fläche beinhaltet alle möglichen Lösungen.

Maximierung Zielfunktion

Im letzten Schritt gilt es herauszufinden, welcher der Schnittpunkte die optimale Produktionsmenge angibt.

Dafür musst Du zu guter Letzt die Zielfunktion im Koordinatensystem eintragen. Um die Funktion einzutragen, löst Du sie nach y auf.

Du siehst, die Zielfunktion ist noch variabel, um jetzt ihren Wert zu maximieren, verschiebst Du die Gerade so weit nach rechts, bis sie die äußerste Ecke Deiner zu optimierenden Fläche schneidet.

Um die optimale Produktionsmenge zu finden, liest Du noch die Koordinaten, des Punktes D, in dem sich die drei Geraden schneiden, ab: D (1,7 | 5)

Lineare Optimierung – rechnerisch

Deine graphische Lösung kannst Du überprüfen, indem Du die Zielfunktionswerte jeder Ecke berechnet. Der Zielfunktionswert gibt den Gewinn an. Um den Output zu optimieren, wählst Du anschließend den höchsten Wert.

Als Erstes musst Du die Koordinaten der Eckpunkte ablesen:

A (0|0) , B(0|7,5) , C (3,33|0) , D (1,67|4,99)

Jetzt setzt Du die Punkte in die Zielfunktion ein und bestimmst das Maximum.

Für die Punkte A und B sind die Koordinaten sehr eindeutig, diese kannst Du ablesen. Du erhältst für A den Zielfunktionswert 0 und für B den Zielfunktionswert 30.

Um für C und D den genauen Schnittpunkt, samt der korrekten Nachkommastelle zu bestimmen, musst Du rechnerisch vorgehen.

In Punkt C schneiden sich die Gerade der vierten Nebenbedingung und die x-Achse. Du setzt also in die Geradengleichung für y den Wert 0 ein und erhältst für x ungefähr 3,33.

Auch für Punkt D kannst Du über das Einsetzen die Koordinaten ermitteln.In Punkt D schneiden sich die Geraden der vierten und der dritten Nebenbedingen.

Daher setzt Du die beiden Geraden miteinander gleich.

Löst Du nach x auf, erhältst Du etwa 1,67. Löst Du im Anschluss nach y auf, erhältst Du 4,99.Diese beiden Punkte kannst Du nun in der Zielfunktion einsetzen.

Vergleichst Du jetzt alle Werte miteinander, erkennst Du, dass die Ecke D mit 31,65 den höchsten Wert besitzt. Dieses Ergebnis stimmt also mit der graphischen Lösung überein. Die rechnerische Lösung ist jedoch ein kleines bisschen genauer.

Lineare Optimierung – Simplex

Das Simplexverfahren ist eine Methode, um lineare Optimierungsprobleme zu lösen. Das Simplexverfahren wurde bereits in den 1940ern von George Dantzig einem US-amerikanischen Mathematiker entwickelt. Seitdem gab es jedoch zahlreiche Verbesserungen. Das Simplexverfahren gehört zu den Pivotverfahren.

Lineare Optimierung – Excel

Excel ist ein weitverbreitetes Tool, das zur Lösung von mathematischen Problemen verwendet wird. Es bietet eine Vielzahl von Funktionen und Tools, die es einfach machen, auch lineare Optimierungsprobleme zu lösen, ohne dass ein tiefes Verständnis der Mathematik erforderlich ist. Wenn Du die lineare Optimierung mit Excel vornehmen möchtest, musst Du das Add-in mit dem Titel "Solver" nutzen. Dieser nutzt ebenfalls das Simplexverfahren.