Über 1,6 Millionen Schüler*innen nutzen sofatutor!
  • 93%

    haben mit sofatutor ihre Noten in mindestens einem Fach verbessert

  • 94%

    verstehen den Schulstoff mit sofatutor besser

  • 92%

    können sich mit sofatutor besser auf Schularbeiten vorbereiten

Lineares Optimieren – Einführung

Inhaltsverzeichnis zum Thema Lineares Optimieren – Einführung
Du möchtest schneller & einfacher lernen?

Dann nutze doch Erklärvideos & übe mit Lernspielen für die Schule.

Kostenlos testen
Du willst ganz einfach ein neues Thema lernen
in nur 12 Minuten?
Du willst ganz einfach ein neues
Thema lernen in nur 12 Minuten?
  • Das Mädchen lernt 5 Minuten mit dem Computer 5 Minuten verstehen

    Unsere Videos erklären Ihrem Kind Themen anschaulich und verständlich.

    92%
    der Schüler*innen hilft sofatutor beim selbstständigen Lernen.
  • Das Mädchen übt 5 Minuten auf dem Tablet 5 Minuten üben

    Mit Übungen und Lernspielen festigt Ihr Kind das neue Wissen spielerisch.

    93%
    der Schüler*innen haben ihre Noten in mindestens einem Fach verbessert.
  • Das Mädchen stellt fragen und nutzt dafür ein Tablet 2 Minuten Fragen stellen

    Hat Ihr Kind Fragen, kann es diese im Chat oder in der Fragenbox stellen.

    94%
    der Schüler*innen hilft sofatutor beim Verstehen von Unterrichtsinhalten.
Bewertung

Ø 3.6 / 9 Bewertungen
Die Autor*innen
Avatar
Mathe-Team
Lineares Optimieren – Einführung
lernst du in der 7. Klasse - 8. Klasse - 9. Klasse - 10. Klasse

Grundlagen zum Thema Lineares Optimieren – Einführung

Was ist lineare Optimierung?

Bei der linearen Optimierung suchen wir für eine Aufgabe mit verschiedenen Bedingungen eine optimale Lösung. Für lineare Optimierungen gibt es vielfältige Anwendungen, zum Beispiel die Produktionsprogrammplanung in einem Unternehmen, bei der es darum geht, die ideale Produktionsmenge von verschiedenen Produkten (z. B. verschiedene Smartphones) oder die Zusammensetzung von bestimmten Zutaten in einem Produkt zu planen, zum Beispiel von Zucker und Mehl in einem Kuchen – und vieles mehr.
Im Folgenden betrachten wir, wie du eine solche optimale Lösung findest und worauf du dabei achten musst.

Beispiel zur linearen Optimierung

Zur Erklärung der linearen Optimierung schauen wir uns zunächst ein Beispiel an. Stell dir vor, wir befinden uns in einer Großbäckerei, in der sämtliche angebotenen Brötchen entweder aus Roggenmehl oder aus Weizenmehl gebacken werden. Täglich wird die Bäckerei mit Mehlsäcken beliefert. Bei der Lieferung gibt es ein paar Einschränkungen zu beachten:

  • Die Lieferung erfolgt in 50-kg-Weizenmehlsäcken und 30-kg-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 $1 500\,\pu{kg}$ nicht überschreiten.
  • Die Bäckerei braucht mindestens halb so viele und höchstens doppelt so viele Roggenmehlsäcke wie Weizenmehlsäcke.

Unsere Aufgabe ist nun, die maximale Anzahl an Mehlsäcken, die unter diesen Voraussetzungen pro Lkw geliefert werden können, zu bestimmen. Dafür nutzen wir das Verfahren der linearen Optimierung.

  • Bei der linearen Optimierung geht es darum, die bestmögliche, also die optimale, Lösung für eine Fragestellung unter vorgegebenen Bedingungen zu finden.

Dieses mathematische Verfahren lässt sich anwenden, wenn alle Bedingungen durch lineare Zusammenhänge darstellbar sind.

Gesucht ist die maximale Anzahl der Mehlsäcke. Da es zwei verschiedene Sorten gibt, legen wir die folgenden Variablen fest:

  • $x$: Anzahl der Weizenmehlsäcke
  • $y$: Anzahl der Roggenmehlsäcke

Wir können nun die maximale Anzahl an Säcken, die pro Lkw-Ladung geliefert werden können, mathematisch schreiben als:

$x+y = \text{maximal}$

Dieser Zusammenhang wird Zielfunktion genannt. Zu Beginn jeder linearen Optimierung steht die Definition der Zielfunktion.

Für die Ladung gibt es bestimmte Vorgaben, die wir oben schon gesehen haben. Diese Bedingungen drücken wir nun durch mathematische Ungleichungen aus:

  • Das Gesamtgewicht der Säcke darf $1 500\,\pu{kg}$ nicht überschreiten:

$\qquad x\cdot 30\,\pu{kg}+y\cdot 50\,\pu{kg} \leq 1 500\,\pu{kg}$

Die Einheit $\pu{kg}$ lassen wir der Einfachheit halber weg und erhalten:

$\qquad 30x+50y\leq 1 500$

  • Die Bäckerei benötigt mindestens halb so viele Roggenmehlsäcke wie Weizenmehlsäcke:

$\qquad y\geq\dfrac{1}{2} x$

  • Die Bäckerei benötigt höchstens doppelt so viele Roggenmehlsäcke wie Weizenmehlsäcke:

$\qquad y\leq 2x$

Wir haben nun alle Bedingungen in Ungleichungen überführt. Dies sind die sogenannten Nebenbedingungen.

Die optimale Lösung können wir mithilfe einer grafischen Darstellung finden. Damit wir die Ungleichungen in ein Koordinatensystem eintragen können, müssen wir sie wie bei einer Funktionsgleichung nach einer Variablen auflösen. Wir lösen hier nach $y$ auf, weil die letzten beiden Ungleichungen schon nach $y$ aufgelöst vorliegen. Für die erste Ungleichung ergibt sich nach $y$ aufgelöst:

$y\leq -\dfrac{5}{3}x+50$

Die drei Ungleichungen zusammengenommen ergeben ein lineares Ungleichungssystem, das wir grafisch lösen können. Wenn du eine Schritt-für-Schritt-Anleitung dazu sehen möchtest, kannst du dir das Video Systeme linearer Ungleichungen grafisch lösen anschauen.

Wir zeichnen die Geraden und markieren die Bereiche, die sich aus den Nebenbedingungen ergeben. Zusammen bilden die drei Geraden ein Dreieck. Dieses Dreieck heißt Planungsvieleck.

Planungsvieleck der linearen Optimierung in Mathe

Alle Punkte im gelb markierten Planungsvieleck erfüllen die drei Ungleichungen. Alle diese Punkte stellen also Lösungen dar, wie der Lkw mit Säcken beladen werden kann. Aber welches ist die optimale Lösung?

Dafür brauchen wir unsere Zielfunktion. Die Summe $x+y$ soll maximal sein. Wir bezeichnen den optimalen Wert mit $c$, sodass wir die Zielfunktion schreiben können als:
$x+y=c$
Diese Gleichung stellen wir nach $y$ um:
$y = -x+c$

Damit haben wir eine neue Geradengleichung erhalten. Doch wo liegt diese im Koordinatensystem? Aus der Gleichung können wir ablesen, dass sie die Steigung $-1$ besitzt. Der Parameter $c$ bezeichnet den $y$-Achsenabschnitt. Die Gerade muss nun so verlaufen, dass $c$ möglichst groß ist und sie das Planungsvieleck schneidet.

Am Koordinatensystem können wir erkennen, dass der Parameter $c$ größtmöglich ist, wenn die Zielfunktion das Planungsvieleck im Schnittpunkt der beiden Geraden, die durch die beiden Ungleichungen $ y \leq -\dfrac{5}{3}x + 50$ und $y \leq 2x$ gegeben sind, berührt. Um diesen Schnittpunkt zu bestimmen, setzen wir die beiden Ungleichungen gleich:

$-\dfrac{5}{3}x + 50 = 2x$

und lösen nach $x$ auf:

$50 = \dfrac{11}{3}x$

$x = \dfrac{150}{11} \approx 13,64$

Da $x$ die Anzahl der Weizenmehlsäcke bezeichnet, ist nur eine ganzzahlige Lösung sinnvoll. Also müssen wir das Ergebnis runden. Hierbei müssen wir darauf achten, das Planungsvieleck durch das Runden nicht zu „verlassen“. Wir können eine der beiden Ungleichungen wählen und jeweils den aufgerundeten und den abgerundeten Wert einsetzen und daran erkennen, ob der Punkt innerhalb oder außerhalb des Planungsvielecks liegt.

Wir wählen die Ungleichung $y \leq 2\cdot x$ und müssen dafür abrunden zu $x = 13$. Durch Einsetzen in die Ungleichung, die wir für die Schnittpunktberechnung verwendet haben, erhalten wir dazu den $y$-Wert $y \leq 2\cdot 13 = 26$. Wir setzen den $x$-Wert und den zugehörigen $y$-Wert in die Zielfunktion ein und bestimmen den Parameter $c$:

$26 = -13 +c$

$c = 39$

Also ist $c=39$ die größtmögliche Anzahl an Mehlsäcken, die verladen werden können. Das heißt, der Lkw wird optimalerweise mit insgesamt 39 Säcken beladen, wobei sich darunter $13$ Weizenmehlsäcke und $26$ Roggenmehlsäcke befinden müssen.

Im Bild haben wir die Gerade mit der Gleichung $y=-x+39$ eingezeichnet, auf der der Punkt $\left(13 \vert 26 \right)$ liegt, der die optimale Lösung darstellt.

Lösung im Planungsvieleck der linearen Optimierung in Mathe

Lineares Optimieren – Zusammenfassung

Wir fassen nun noch einmal zusammen, welche Schritte wir bei der linearen Optimierung durchführen müssen:

  • Die Variablen festlegen
  • Die Zielfunktion, die zu optimieren ist, aufstellen
  • Die Nebenbedingungen in mathematische Ungleichungen übersetzen
  • Das entstandene lineare Ungleichungssystem grafisch lösen. Es ergibt sich das Planungsvieleck, in dem alle möglichen Lösungen liegen.
  • Die Zielfunktion einzeichnen und den Parameter der Zielfunktion so wählen, dass die Lösung innerhalb des Planungsvielecks liegt und gleichzeitig den optimalen Wert annimmt. Dabei beachten, dass das Ergebnis der linearen Optimierung je nach Anwendung möglicherweise ganzzahlig sein muss
  • Den optimalen Eck- oder Randpunkt ablesen. Es ist der Schnittpunkt der Zielfunktion mit dem Planungsvieleck.

Wenn du noch weiter lernen möchtest, findest du auf dieser Seite interaktive Übungen zur linearen Optimierung.

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