sofatutor 30 Tage
kostenlos ausprobieren

Videos & Übungen für alle Fächer & Klassenstufen

Lineares Optimieren – Einführung 15:25 min

Textversion des Videos

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

Lineares Optimieren – Einführung Übung

Du möchtest dein gelerntes Wissen anwenden? Mit den Aufgaben zum Video Lineares Optimieren – Einführung kannst du es wiederholen und üben.

  • Stelle die Bedingungen für die Anzahl der Weizenmehl- und Roggenmehlsäcke auf.

    Tipps

    Mache dir jeweils die Relationen an Beispielen klar.

    Die Gesamtzahl von zwei Größen erhältst du, indem du die Größen addierst.

    Beachte: In einen Weizenmehlsack passen $50~kg$ und einen Roggenmehlsack $30~kg$.

    Es ist wichtig, die Ungleichheitszeichen zu kennen:

    • mindestens so groß: $\ge$ und
    • höchstens so groß: $\le$
    Lösung

    Um ein lineares Optimierungsproblem zu lösen, muss man dieses mathematisch formulieren. Das bedeutet, man übersetzt das Ziel und auch jede Bedingung in mathematische Terme und Relationen.

    Hierfür werden den unbekannten Größen Variablen zugewiesen:

    • $x$ sei die Anzahl der Weizenmehlsäcke und
    • $y$ die Anzahl der Roggenmehlsäcke.
    Die Gesamtzahl $x+y$ der Mehlsäcke soll möglichst groß werden. Dies führt zu dem Ziel: $x+y~\rightarrow$ maximal.

    Nun kommen die Bedingungen:

    • Die Zahl der Roggenmehlsäcke soll mindestens so groß sein wie die Hälfte der Weizenmehlsäcke: $y\ge \frac12$.
    • Die Zahl der Roggenmehlsäcke soll höchstens doppelt so groß sein wie die Anzahl der Weizenmehlsäcke: $y\le 2$.
    • Auch das maximale Gewicht, welches der LKW transportieren kann, führt zu einer Bedingung. Da jeder Weizenmehlsack $50~kg$ enthält, enthalten die $x$ Weizenmehlsäcke $50x$ (in kg) Mehl. Ebenso kann das Gewicht der Roggenmehlsäcke verwendet werden. Dies führt zu der letzten Nebenbedingung: $50x+30y\le 1500$.
  • Bestimme den Bereich graphisch, in welchem sich die Lösungen befinden.

    Tipps

    Forme jede der Relationen so um, dass sie eine dieser Forme erfüllt:

    • $y \le mx+b$
    • $y \ge mx+b$

    Die Gerade zu der Gleichung $y=mx+b$ ist die Gerade, welche den Lösungsbereich der jeweiligen Bedingung begrenzt.

    Mache dir an Beispielen klar, auf welcher Seite der Geraden die Lösungen liegen.

    Die Zielfunktion $x+y=c$ wird nun so lange parallel verschoben, bis sie den Rand des Lösungsbereiches erreicht.

    Je weiter die Gerade von dem Koordinatenursprung entfernt ist, desto größer ist $c$.

    Lösung

    Um ein lineares Optimierungsproblem grafisch zu lösen, müssen die jeweiligen Bedingungen in einem Koordinatensystem erfasst werden. Hierfür werden bei Relationen jeweils die Geraden gezeichnet, die zu der Relation gehören. Diese Geraden begrenzen die Lösungsmenge:

    • Die rote Gerade gehört zu der Gleichung $50x+30y=1500$. Diese kann umgeformt werden zu $y=-\frac53x+50$. Alle Punkte im ersten Quadranten unterhalb dieser Geraden erfüllen die Ungleichung $50x+40y\le 1500$.
    • Die blaue Gerade gehört zu der Gleichung $y=2x$. Alle Punkte unterhalb dieser Geraden erfüllen die Ungleichung $y\le 2x$.
    • Die grüne Gerade gehört zu der Gleichung $y\ge \frac12x$. Alle Punkte oberhalb der Geraden erfüllen die Ungleichung $y\ge \frac12x$.
    • Wenn man alle Lösungsmengen kombiniert, erhält man das gelbe Dreieck. Dieses wird als Planungsdreieck bezeichnet. Da nicht immer ein Dreieck vorliegt, spricht man im Allgemeinen auch von einem Planungsvieleck.
    Rosa eingezeichnet sind hier die Funktion $x+y=c$ für verschiedene $c$. Je größer $c$ ist, desto weiter entfernt vom Koordinatenursprung liegt die Gerade: Die untere der beiden gehört zu $x+y=20$ und die obere zu $x+y=50$.

  • Leite die Zielfunktion sowie die Bedingungen her.

    Tipps

    Beachte, dass $\le$ eine Beziehung beschreibt, die durch höchstens angegeben ist.

    Formuliere die Relationen als Gleichungen und überlege dann, wie das Relationszeichen gewählt werden muss.

    Das Schlüsselwort zusammen weist auf eine Addition hin.

    Lösung

    Das Erste, was man tun muss, ist: Man weist den unbekannten Größen Variablen zu:

    • $x$ sei die Anzahl der Riesenlutscher und
    • $y$ sei die Anzahl der Donuts.
    Damit ist die Gesamtzahl der Süßigkeiten $x+y$. Diese soll möglichst groß werden.

    Nun kann man sich die einzelnen Bedingungen anschauen:

    • Paul möchte höchstens $64~€$ ausgeben. Das bedeutet, es muss die folgende Relation $1,2x+2y\le 64$ erfüllt sein.
    • Die Zahl der Donuts soll mindestens so groß sein wie die Zahl der Lutscher. Dies führt zu $y\ge x$.
    • Die Zahl der Donuts soll höchstens so groß sein wie das Dreifache der Zahl der Lutscher. So erhält man die dritte Ungleichung $y\le 3x$.
  • Ermittle die optimale Anzahl an Lutschern und Donuts.

    Tipps

    Es muss $x+y$ möglichst groß werden.

    Betrachten wir einmal $y\ge x$ genauer. Dann steht die Gerade $y=x$ für die Begrenzung der Lösungsmenge dieser Ungleichung.

    Der Schnitt aller Lösungsmengen ist das Planungsvieleck, hier ein Planungsdreieck.

    Verschiebe die Zielfunktion (dies ist in dem Bild zu erkennen) zu einem Eckpunkt des Planungsdreiecks. Dieser Punkt liefert die gesuchte Lösung.

    Hierfür musst du zwei Gleichungen lösen.

    Lösung

    Hier sind die Zielfunktion $x+y$ in violett sowie die verschiedenen Bedingungen zu sehen.

    Dabei steht

    • $x$ für die Anzahl der Lutscher und
    • $y$ für die Anzahl der Donuts.
    Das markierte Dreieck ist das Planungsdreieck.

    Schauen wir uns einmal die Bedingungen an:

    • $y\ge x$. Dies ist die blaue Gerade. Die Lösungen dieser Ungleichung liegen oberhalb der Geraden.
    • $y\le 3x$. Dies ist die grüne Gerade. Unterhalb dieser liegen die Lösung der Ungleichung.
    • $1,2x+2y\le 64$. Dies ist die rote Gerade. Unterhalb dieser liegen die entsprechenden Lösungen.
    An dem Bild kann man erkennen, dass die Verschiebung der Zielfunktion zu einem Eckpunkt des Planungsdreiecks führt. Dieser ist gegeben als Schnittpunkt der Geraden $y=x$ sowie $1,2x+2y=64$.

    Nun kann man $y=x$ in die zweite Gerade einsetzen und erhält

    $1,2x+2x=64$, also $3,2x=64$.

    Division durch $3,2$ führt zu $x=20$ und somit auch $y=20$.

    Die maximale Anzahl an Lutschern wie an Donuts beträgt also jeweils $20$ und die Gesamtzahl ist $20+20=40$.

  • Beschreibe, was unter linearer Optimierung zu verstehen ist.

    Tipps

    Manche Bedingungen setzen eine Obergrenze, manche eine Untergrenze.

    Das optimum ist im Lateinischen das Höchste, das Größte.

    Lösung

    Was bedeutet eigentlich lineares Optimieren?

    Man kann sich jedes einzelne Wort anschauen:

    • linear: Das bedeutet, dass alle Größen linear vorliegen, also mit dem höchsten Exponenten $1$.
    • Optimierung: Irgendetwas soll möglichst groß oder möglichst klein werden.
    Bei linearen Optimierungsproblemen werden oft noch Bedingungen aufgestellt, welche die unbekannten (gesuchten!) Größen erfüllen sollen.

    Zusammenfassend kann man sagen: Lineares Optimieren ist die Suche nach der bestmöglichen Lösung bei vorgegebenen Bedingungen.

  • Bestimme die optimale Lösung.

    Tipps

    Bei den ersten beiden Beispielen kannst du die Lösungen ablesen.

    Bei dem dritten Beispiel musst du zwei Gleichungen gleichsetzen.

    Du kannst in dem Bild zu dem dritten Beispiel erkennen, welche Gleichungen du gleichsetzen musst.

    Löse die Gleichung $-5x+100=-0,6x+30$.

    Die Lösung ist nicht ganzzahlig.

    Lösung

    Bei den oberen beiden Beispielen geht es darum, wie die Lösungen abgelesen werden können. Dies ist jedoch nur bei solch übersichtlichen Beispielen möglich.

    In dem ersten Beispiel ist das optimale $x=30$ und $y=10$, in dem unteren umgekehrt $x=10$ und $y=30$. Der Zielfunktionswert ist jeweils $30+10=40$.

    Hier ist das dritte Beispiel zu sehen. Die optimale Lösung liegt in dem Punkt, in welchem sich die rote und die orange Gerade schneiden. Es muss also die Gleichung $-5x+100=-0,6x+30$ gelöst werden:

    $\begin{array}{rclll} -5x+100&=&-0,6x+30&|&+0,6x\\ -4,4x+100&=&30&|&-100\\ -4,4x&=&-70&|&:(-4,4)\\ x&=&\frac{175}{11}\\ &=&15,\overline{90}\approx15,9 \end{array}$

    Damit kann $y$ berechnet werden: $y=-0,6\cdot \frac{175}{11}+30=\frac{225}{11}=20,\overline{45}\approx20,5$. Der Zielfunktionswert ist $15,9+20,5=36,4$.