Lineares Optimieren – Einführung

Hallo. Ich möchte Dich herzlich zur Einführung in das lineare Optimieren willkommen heißen. Dazu möchte ich mit Dir folgendes Problem betrachten: Stell Dir vor, wir befinden uns in einer Großbäckerei. Sämtliche angebotene Brötchen werden entweder aus einem Teig mit Roggen- oder Weizenmehl gemacht. Damit die Bäckerei immer genügend der beiden Mehlsorten vorrätig hat, lässt sie das Mehl täglich anliefern. Die Lieferung erfolgt in 50kg-Weizenmehlsäcken und 30kg-Roggenmehlsäcken. Der LKW, der die Bäckerei beliefert, kann höchstens 1,5 Tonnen laden. Das heißt, das Gesamtgewicht der verladenen Weizen- und Roggenmehlsäcke darf 1500 kg nicht überschreiten. Die Bäckerei braucht mindestens halb und höchstens doppelt so viele Roggenmehlsäcke wie Weizenmehlsäcke. Unsere Aufgabe soll es nun sein, die maximale Anzahl an Mehlsäcken zu bestimmen, die unter diesen Umständen pro LKW geliefert werden können. Hierbei handelt es sich um eine typische Aufgabe zum linearen Optimieren. Vielleicht fragst Du Dich, was sich hinter dem Begriff lineares Optimieren verbirgt. Es ist nichts weiter als die Suche nach der bestmöglichen Lösung bei vorgegebenen Bedingungen. Heute möchte ich mit Dir die Frage klären, wie man zu dieser optimalen Lösung kommt und was dabei alles beachtet werden muss. Um das Problem von Anlieferung von Mehl für die Großbäckerei mathematisch zu fassen, beschreiben wir die Anzahl der Weizenmehlsäcke mit der Variablen x und die der Roggenmehlsäcke mit der Variablen y. Gesucht ist die maximale Anzahl an Säcken, die pro LKW-Lieferung geliefert werden können. Mathematisch ausgedrückt, soll also die Summe von x + y maximal sein. Allerdings haben wir für die LKW-Lieferung verschiedene Vorgaben. Das Gesamtgewicht der 50kg schweren Weizenmehlsäcke und der 30kg schweren Roggenmehlsäcke darf die 1500kg-Grenze nicht überschreiten. Denn mehr kann der LKW nicht transportieren. Daraus erhalten wir unsere erste Ungleichung. x * 50kg + y * 30kg ≤ 1,5 Tonnen, also 1500kg sein. Für die weitere Berechnung verzichten wir auf die Einheit kg und schreiben: 50x + 30y ≤ 1500. Weitere Informationen entnehmen wir der Vorgabe, dass die Bäckerei mindestens halb so viele Roggenmehlsäcke wie Weizenmehlsäcke braucht. y  ≥ 1/2x. Es besteht gleichzeitig aber auch die Einschränkung, dass die Bäckerei höchstens doppelt so viele Roggenmehlsäcke wie Weizenmehlsäcke benötigt. y ≤ 2x. Damit haben wir sämtliche relevante Informationen in Ungleichungen ausgedrückt. Damit wir sie grafisch darstellen können, müssen wir sie gleich einer Funktionsgleichung nach einer Variable auflösen. Wir entscheiden uns im Video für y. Das ist bequemer, denn die letzten beiden Ungleichungen sind bereits nach y aufgelöst. Wir nehmen also die Ungleichung der ersten Nebenbedingung 50x + 30y ≤ 1500 und lösen sie nach y auf. Dazu subtrahieren wir auf beiden Seiten der Gleichung 50x und erhalten: 30y ≤ 1500 - 50x. Als nächstes teilen wir durch 30 und erhalten y ≤ 50 - (5/3)x. Wenn wir die Summanden noch ordnen, erhalten wir also für y: y ≤ -(5/3)x + 50. Damit haben wir nun ein lineares Ungleichungssystem, bestehend aus drei Ungleichungen, die nach y aufgelöst sind. Deshalb lassen sie sich im nächsten Schritt nun grafisch darstellen. Im Koordinatensystem ergibt sich damit folgendes Schaubild: Der x-Wert stellt die Anzahl der Weizenmehlsäcke dar und der y-Wert die Anzahl der Roggenmehlsäcke. Hier siehst Du nun die erste Ungleichung y ≤ -(5/3)x + 50. Alle Funktionswerte, die im ersten Quadranten durch den Graphen und der x- und y-Achse eingegrenzt werden, erfüllen die erste Nebenbedingung. Die zweite Ungleichung y ≥ (1/2)x sieht eingezeichnet so aus. Und die dritte Ungleichung y ≤ 2x so. Auch hier gilt, wie bei der ersten Nebenbedingung, dass sämtliche Funktionswerte, die im ersten Quadranten durch den Graphen und der x- und y-Achse eingegrenzt werden, Lösungen der Ungleichungen bilden. Zusammen bilden die drei Geraden ein Dreieck. Dieses Dreieck heißt Planungsvieleck. Es muss nicht zwangsläufig ein Dreieck sein. Je nach Anzahl der Bedingungen, die sich, wie Du schon gesehen hast, zeichnerisch als Geraden darstellen lassen, kannst Du auch ein Viereck, ein Fünfeck und so weiter, also ein Vieleck erhalten. Alle Punkte in diesem Planungsvieleck erfüllen alle drei Ungleichungen. Alle diese Punkte stellen also Lösungen dar, wie der LKW mit den Säcken beladen werden kann. Aber welche ist denn jetzt unsere optimale Lösung? Es kommt ganz auf die Fragestellung an, welches unsere optimale Lösung ist. Zur besseren Verdeutlichung schauen wir uns einfach mal ein Beispiel an. Unsere Aufgabe war es, die maximale Anzahl an Mehlsäcken zu bestimmen, die der LKW liefern kann. Die Summe der Weizen- und Roggenmehlsäcke x + y soll also maximal sein. Die Summe stellt den optimalen Wert dar und damit die Lösung der Aufgabe. Wir bezeichnen c als optimalen Wert und stellen anschließend die Gleichung nach y um. Aus x + y = c erhalten wir y = -x + c. Damit haben wir eine neue Geradengleichung erhalten. Nur wo liegt sie im Schaubild? Wir können ablesen, dass sie die Steigung -1 hat. Die y-Achsenverschiebung ist uns nicht bekannt. Gesucht ist allerdings das größtmögliche c. Damit suchen wir einen Wert c, so dass die Gerade y = -x + c aber noch das Planungsvieleck schneidet. Zeichnen wir einmal die Gerade für ein beliebiges c, zum Beispiel c = 50, ein. Wie Du siehst, ist der Wert zu groß gewählt, denn die Gerade schneidet das Planungsvieleck nicht. Für den Wert c = 20 erhalten wir eine Gerade, die das Planungsvieleck zwar schneidet. Du siehst aber, dass da noch Platz nach oben wäre. Der höchste Punkt des Planungsvielecks, der von der geraden geschnitten werden sollte, ist der Schnittpunkt der Ungleichungen y ≤ -(5/3)x + 50 und y ≤ 2x. Um diesen Schnittpunkt zu bestimmen, setzen wir die beiden Ungleichungen gleich. -(5/3)x + 50 = 2x. Wir addieren (5/3)x und erhalten 50 = (11/3)x. Zuletzt dividieren wir durch 11/3 und erhalten für x den Wert gerundet 13,64. Hast Du schon einmal 13,64 Säcke Mehl gegessen? Bestimmt nicht. Es werden nur ganze Säcke geliefert. Das heißt, das Ergebnis muss auch eine ganze Zahl sein. Wir haben daher zwei Möglichkeiten. Entweder wir runden auf oder wir runden ab. Das kommt ganz darauf an, in welche Ungleichung man den gerundeten x-Wert einsetzt, um den y-Wert zu erhalten. In y ≤ -5/3x + 50 oder y ≥ 2x. Ich veranschauliche Dir das kurz an dieser Skizze. Hier siehst Du die Graphen der beiden Ungleichungen. S ist der Schnittpunkt der beiden Geraden und die markierte Fläche ist unser Planungsdreieck. Der Schnittpunkt S liegt bei 13,64. Nun müssen wir uns entscheiden, ob wir aufrunden oder abrunden. Angenommen, wir runden auf 14 auf, dann müssen wir den x-Wert in die Ungleichung y ≤ -5/3x + 50 einsetzen, um den y-Wert zu berechnen. Denn der y-Wert der Ungleichung y ≥ 2x wäre außerhalb des Planungsdreiecks. Würden wir auf 13 abrunden, dann wäre es genau andersherum. Dann dürften wir den gerundeten x-Wert nur in die Ungleichung y ≥ 2x einsetzen, um den y-Wert zu berechnen. Denn der y-Wert der Ungleichung y ≤ -5/3x + 50 wäre dann außerhalb des Planungsdreiecks. Du siehst, ein Blick auf das Planungsdreieck lohnt sich. Der Einfachheit halber runden wir nun unser Ergebnis 13,64 auf 13 ab und setzen den gerundeten x-Wert in die einfachere Ungleichung y ≤ 2x, y ≤ 2 * 13. y ≤ 26. Nachdem wir den Schnittpunkt bestimmt haben, kennen wir einen entscheidenden Punkt, der auf unserer Zielgeraden liegen soll. Setzen wir diesen Punkt in die Gleichung y = -x + c, 26 = -13 + c. Wenn wir nun 13 addieren, erhalten wir für c den Wert 39. Das ist die höchste Anzahl an Mehlsäcken, die verladen werden können. Da aber nur ganze Mehlsäcke verladen werden dürfen, erhalten wir als optimale Lösung 39 Säcke. Des weiteren können wir nun auch auf die Anzahl der Weizen- und Roggenmehlsäcke schließen. Denn x stellt ja die Anzahl der Weizenmehlsäcke und y die Anzahl der Roggenmehlsäcke dar. Der LKW wird also optimaler Weise mit insgesamt 39 Säcken beladen, worunter sich 13 Weizenmehlsäcke und 26 Roggenmehlsäcke befinden. Wie Du gesehen hast, ist das lineare Optimieren ein mehrstufiges Verfahren. Als erstes haben wir das gegebene Problem mathematisch erfasst, indem wir Variablen festgelegt und eine Zielgleichung aufgestellt haben. Dann haben wir die Randbedingungen durch ein lineares Ungleichungssystem beschrieben und das Planungsvieleck gezeichnet. Anschließend konnten wir durch Parallelverschiebung die optimale Zielgerade bestimmen. Zuletzt mussten wir also nur noch den optimalen Eckpunkt ablesen und den Zielwert berechnen. Hier muss hinzugefügt werden, dass nicht immer der optimale Wert ein Eckpunkt im Planungsvieleck ist. Je nach Aufgabenstellung kann beispielsweise auch einer der Randpunkte der Zielwert sein. Na, hast Du Dir eine Übersicht zu diesem mehrstufigen Verfahren zum linearen Optimieren verschaffen können? Vielleicht kannst Du es jetzt wie ein Rezept für weitere Aufgaben benutzen. Was meinst Du? Ich hoffe, die Berechnungen haben Dir Spaß gemacht. Tschüss.