Kurs
Google Sheets: Fortgeschrittene Funktionen
4 Std.
57.7K
Als Managerin oder Manager eines Unternehmens arbeitest du immer mit endlichen bzw. begrenzten Ressourcen – und die Erwartung des Top-Managements ist, dass du das Maximum daraus herausholst. Von Zeitproduktivität bis Kapitalnutzung, von Fläche bis Arbeit, von Lieferkette bis Produktion – fast alles dreht sich darum, die Produktivität zu optimieren.
Die meisten Fluggesellschaften optimieren ihre Flugpläne, um den Umsatz zu steigern und die Kosten zu senken. Diese Pläne beinhalten zahlreiche Situationen und Einschränkungen, etwa die Anzahl der Flugzeuge an einem Standort, Treibstoff, Crew und Streckentyp (beliebte und rentable Routen). Diese Situationen und Einschränkungen sind die Nebenbedingungen für Flüge auf den profitabelsten Routen. Lineare Optimierung hilft dabei, für ein solches Problem mit Nebenbedingungen eine optimale Lösung zu finden.
In diesem Tutorial lernst du die lineare Optimierung kennen. Wir behandeln folgende Themen:
- Einführung in die lineare Optimierung
- Grundbegriffe der LOP
- Entscheidungsvariablen
- Nebenbedingungen
- Ziel- bzw. Zielfunktion
- Optimale Lösung
- Zulässige Lösung
- Unzulässige Lösung
- Zulässiger Bereich
- Nichtnegativitätsbedingungen
- Formulierung eines LOP-Problems (mit Beispiel)
- Grafische Methode zur Lösung einer LOP in der Tabellenkalkulation
- Anwendungsfälle der LOP
- Fazit
Einführung in die lineare Optimierung
Mathematisch gesehen optimiert die lineare Programmierung (minimiert oder maximiert) eine lineare Zielfunktion mehrerer Variablen unter gegebenen Bedingungen/Nebenbedingungen, die durch lineare Ungleichungen beschrieben sind. Sie kommt in der Planung wirtschaftlicher Aktivitäten zum Einsatz, z. B. beim Transport von Gütern und Dienstleistungen, in der Produktion, bei der Optimierung elektrischer Energiesysteme und von Netzwerkflüssen. LP-Probleme lassen sich mit verschiedenen Verfahren lösen, etwa grafisch, mit dem Simplex-Verfahren oder Karmarkars Algorithmus.
Grundbegriffe der LOP
Schauen wir uns die wichtigsten Begriffe der linearen Optimierung an:
-
Entscheidungsvariablen sind die Variablen, aus denen die Zielfunktion gebildet wird. Sie bestimmen dein Ergebnis. Über die Entscheidungsvariablen steuert die entscheidende Person den Wert der Zielfunktion. Bei jedem LP-Problem identifizierst du zunächst die Entscheidungsvariablen.
-
Nebenbedingungen sind Einschränkungen oder Rahmenbedingungen. Sie können als Gleichungen oder Ungleichungen formuliert sein und begrenzen die Werte der Entscheidungsvariablen.
-
Die Zielfunktion ist eine Gewinn- oder Kostenfunktion, die maximiert oder minimiert werden soll. Sie ist das zentrale Ziel der Entscheidung.
-
Die optimale Lösung ist eine der zulässigen Lösungen, bei der die Zielfunktion entweder maximal oder minimal ist, z. B. maximaler Gewinn oder minimale Kosten. Sie liefert den besten Wert der Zielfunktion.
-
Eine zulässige Lösung ist die Menge aller möglichen Werte der Entscheidungsvariablen, die sämtliche Nebenbedingungen erfüllen. Ein LP-Problem ist zulässig, wenn es mindestens eine solche Lösung gibt.
-
Die unzulässige Lösung ist eine Menge möglicher Werte der Entscheidungsvariablen, die nicht alle Nebenbedingungen erfüllt – es existiert also keine optimale Lösung. Ein LP-Problem ist unzulässig, wenn keine Lösung existiert, die alle Bedingungen erfüllt.
-
Der zulässige Bereich ist der Bereich aller Werte, die die Nebenbedingungen erfüllen, bzw. der Schnitt aller Nebenbedingungen. Er umfasst Ungleichungen, Gleichungen und ganzzahlige Bedingungen.
-
Nichtnegativitätsbedingungen erzwingen, dass Entscheidungsvariablen nur nichtnegative Werte annehmen. Solche Bedingungen sind größer oder gleich null.
Formulierung eines LOP-Problems (mit Beispiel)
Die Modellierung eines linearen Optimierungsproblems umfasst folgende Schritte:
- Entscheidungsvariablen identifizieren
- Zielfunktion festlegen
- Nebenbedingungen bestimmen
- Nichtnegativitätsbedingungen definieren
In einem LP-Problem müssen Entscheidungsvariablen, Zielfunktion und Nebenbedingungen jeweils linear sein.
Problemstellung: Ein Möbelhändler handelt nur mit zwei Artikeln – Tischen und Stühlen. Er verfügt über 50.000 Rs zum Investieren und hat Lagerplatz für höchstens 60 Stück. Ein Tisch kostet 2.500 Rs, ein Stuhl 500 Rs. Er schätzt, dass er mit dem Verkauf eines Tisches 250 Rs Gewinn erzielt und mit dem Verkauf eines Stuhls 75 Rs. Er möchte wissen, wie viele Tische und Stühle er mit dem verfügbaren Geld kaufen soll, um seinen Gesamtgewinn zu maximieren – unter der Annahme, dass er alle gekauften Artikel verkaufen kann. (Quelle)
In diesem Beispiel gilt –
- Der Händler kann sein Geld in Tische, Stühle oder eine Kombination aus beidem investieren. Je nach Investitionsstrategie fällt der Gewinn unterschiedlich aus. (Quelle)
- Seine Investition ist auf maximal 50.000 Rs begrenzt, ebenso der Lagerplatz auf maximal 60 Stück. (Quelle)
Mathematische Formulierung:
Angenommen, er kauft nur Tische und keine Stühle. Dann kann er 50.000/2.500 = 20 Tische kaufen. In diesem Fall beträgt der Gewinn 250 × 20 = 5.000 Rs. Oder er kauft nur Stühle und keine Tische. Dann kann er 50.000/500 = 100 Stühle kaufen.
In diesem Fall beträgt der Gewinn 75 × 60 = 4.500 Rs.
Es gibt viele mögliche Kombinationen aus Tischen und Stühlen.
Angenommen, er kauft X Tische und Y Stühle. Dann müssen X und Y nichtnegativ sein.
-
Der Händler hat höchstens 50.000 Rs für den Einkauf von Tischen und Stühlen, daher gilt –
2500 X + 500 Y <= 50000 (Investitionsbedingung) bzw. 5 * X + Y <= 100 ............................................. Gl.1
-
Er kann höchstens 60 Einheiten einlagern.
X + Y <= 60 ............................................. Gl.2
-
Der Händler möchte die Mengen so wählen, dass er seinen Gewinn Z maximiert. Also lautet die Gleichung –
Max Z : 250 X + 75 Y
Zielfunktion: Max Z: 250 X + 75 Y
Unter den Nebenbedingungen:
5 * X + Y <= 100,
X + Y <= 60 and
X,Y >= 0
Quelle: http://ncert.nic.in/ncerts/l/lemh206.pdf
Grafische Methode zur Lösung einer LOP in der Tabellenkalkulation
Beispiel zur linearen Optimierung
Zielfunktion: Max Z: 250 X + 75 Y
Unter den Nebenbedingungen:
5 * X + Y <= 100,
X + Y <= 60 and
Where X,Y >= 0
Schritt 1: Trage die Funktionen in Excel ein, wie unten gezeigt.
Schritt 2: Nachdem du die Zielfunktion und die Nebenbedingungen im Spreadsheet erfasst hast, berechne die Werte für die Bedingungen C1 und C2. Setze jeweils die andere Variable auf null. Für C1 gilt: Bei X = 0 ist Y = 100, und bei Y = 0 ist X = 20. Analog verfährst du für die Nebenbedingung C2.
Schritt 3: Nach der Berechnung der Werte zeichnest du das Diagramm. Markiere die Werte der Nebenbedingung C1, gehe zu Einfügen und wähle ein Punktdiagramm mit geglätteten Linien. Dein Diagramm könnte so aussehen:
Falls es so aussieht, keine Sorge – folge diesen Schritten, um es anzupassen. Klicke mit der rechten Maustaste auf das Diagramm, wähle Daten auswählen. Du siehst zwei Reihen; entferne Reihe 2 und bearbeite Reihe 1.
Benenne die Reihe in C1 um und setze als X-Werte die Spalte A von C1 und als Y-Werte die Spalte B von C1. Klicke auf OK. Dein Diagramm sollte nun so aussehen:
Schritt 4: Gehe erneut über einen Rechtsklick auf Daten auswählen und füge eine weitere Reihe hinzu. Nenne sie C2. Wähle bei den X-Werten die X-Spalte der Nebenbedingung C2 und bei den Y-Werten die Y-Spalte von C2. Dein Diagramm sollte nun so aussehen:
Schritt 5: Jetzt ist das Diagramm erstellt, und du markierst den zulässigen Bereich:
Im zulässigen Bereich liegen nun vier Punkte (O, A, B, C). Berechne die Zielfunktionswerte an allen Punkten, um zu sehen, wo sie maximal ist.
Schritt 6: So berechnest du die Werte der Zielfunktion:
Berechne die Zielfunktion für jeden Punkt:
- Am Punkt O sind die Koordinaten (X, Y) = (0, 0). Der Zielfunktionswert ist daher = (2500+750) = 0
- Am Punkt A sind die Koordinaten (X, Y) = (0, 60). Der Zielfunktionswert ist daher = (2500+753) = 4500
- Am Punkt B sind die Koordinaten (X, Y) = (20, 0). Der Zielfunktionswert ist daher = (2503+750) = 5000
-
Am Punkt C: Um die Koordinaten dieses Punkts zu finden, musst du den Schnittpunkt der Geraden C1 und C2 bestimmen. Verwende dafür die Funktionen MMULT() und MINVERSE(), um den Schnittpunkt zweier Gleichungen zu berechnen.
-
MMULT(MINVERSE(array),array) # Liefert die Lösung der Gleichungen mit zwei Variablen. Oder: =MMULT(MINVERSE(AB17:AC18), AE17:AE18). Markiere vor der Eingabe die gelb markierten Zellen für X und Y, wende die Funktion an, um den Schnittpunkt der beiden Gleichungen zu berechnen, und drücke STRG+UMSCHALT+EINGABE.
Die finalen Werte für Z:
Wie du siehst, liegt der maximale Wert von Z in diesem Maximierungsproblem am Punkt B und beträgt 6.250 Rs. Um den Gewinn zu maximieren, sollte der Händler daher 10 Tische und 50 Stühle kaufen.
Anwendungsfälle der LOP
Lineare Optimierung wird eingesetzt, um optimale Lösungen in der Operations Research zu finden. Unter gegebenen Nebenbedingungen ermittelt LP die beste Lösung. Sie ist in vielen Bereichen anwendbar, z. B. in der Landwirtschaft, im Ingenieurwesen, in der Fertigung, im Energiesektor, in der Logistik und in der Lieferkette.
-
Ingenieurinnen und Ingenieure nutzen lineare Optimierung in der Fertigungs- und Produktionsindustrie, um vorhandene Ressourcen optimal einzusetzen und so den Gewinn zu steigern.
-
Die Logistik- und Transportbranche nutzt lineare Optimierung, um kürzeste Wege/Routen, Reisezeiten und Preisstrategien zu bestimmen.
-
Im Energiesektor wird die lineare Optimierung angewandt, um Lastflüsse zu optimieren, kürzeste Verteilnetze zu planen und das Design von Stromnetzen zu verbessern.
-
In der Landwirtschaft kann lineare Optimierung helfen, die Sorten- und Mengenwahl bei Feldfrüchten so zu planen, dass der Erlös effizient steigt.
-
In der Lebensmittelbranche unterstützt sie Gesundheitsmanager und Ernährungsberaterinnen dabei, Ernährungspläne und kostengünstige Lebensmittelsets zu entwickeln, um nichtübertragbaren Krankheiten vorzubeugen.
Fazit
Glückwunsch, du hast das Ende dieses Tutorials erreicht!
Du hast eine Menge über lineare Optimierung gelernt: was sie ist, grundlegende Konzepte und Begriffe, die Formulierung von LP-Problemen, die grafische Lösungsmethode sowie typische Anwendungsfälle.
Idealerweise kannst du die Konzepte der linearen Optimierung jetzt nutzen, um in deiner Organisation bessere Entscheidungen zu treffen oder Ergebnisse für Entscheider zu optimieren. Danke fürs Lesen!
Sieh dir auch unser Tutorial zu Diagrammen in Tabellenkalkulationen an.
Wenn du mehr über Tabellenkalkulationen lernen möchtest, empfehlen wir dir diese DataCamp-Kurse:
Themen