Lineare Ungleichungssysteme und lineare Optimierung

Kompetenzcode: AG 2.6

Bereich: Algebra und Geometrie

Viele Planungsfragen haben dieselbe Struktur:

• Zwei veränderliche Größen sollen gewählt werden.
• Mehrere Bedingungen schränken die möglichen Werte ein.
• Eine Zielgröße soll möglichst groß oder möglichst klein werden.

Beispiele sind die Produktionsplanung, das Mischen von Rohstoffen, die Einteilung von Arbeitszeit oder die Minimierung von Kosten.

Lineare Optimierung bedeutet: Unter allen Punkten, die sämtliche linearen Nebenbedingungen erfüllen, den Punkt mit dem besten Wert einer linearen Zielfunktion finden.

1. Eine lineare Ungleichung beschreibt eine Halbebene

Eine lineare Ungleichung in zwei Variablen hat zum Beispiel die Form

$$ax+by\le c.$$

Die zugehörige Gleichung

$$ax+by=c$$

ist die Grenzgerade. Sie teilt die Zeichenebene in zwei Halbebenen. Genau eine dieser Halbebenen erfüllt die Ungleichung.

• Bei $\le$ oder $\ge$ gehört die Grenzgerade zum Lösungsbereich und wird durchgezogen gezeichnet.
• Bei $<$ oder $>$ gehört die Grenzgerade nicht dazu und wird gestrichelt gezeichnet.

Welche Seite richtig ist, lässt sich mit einem Testpunkt entscheiden. Wenn die Gerade nicht durch den Ursprung verläuft, ist $(0,0)$ meist besonders bequem.

Beispiel 1: Eine Halbebene schrittweise bestimmen

Stelle den Lösungsbereich von

$$2x+y\le6$$

dar.

Schritt 1: Grenzgerade bilden.

$$2x+y=6.$$

Schritt 2: Zwei Punkte der Grenzgeraden berechnen.

Für $x=0$ gilt

$$y=6,$$

also liegt $(0,6)$ auf der Geraden. Für $y=0$ gilt

$$2x=6\quad\Longrightarrow\quad x=3,$$

also liegt auch $(3,0)$ darauf.

Schritt 3: Grenzgerade zeichnen.

Die Punkte $(0,6)$ und $(3,0)$ werden verbunden. Wegen $\le$ wird die Gerade durchgezogen.

Schritt 4: Testpunkt einsetzen.

Mit $(0,0)$ erhält man

$$2\cdot0+0\le6 \quad\Longleftrightarrow\quad 0\le6.$$

Die Aussage ist wahr. Daher ist die Halbebene auf der Seite des Ursprungs die Lösung.

Schritt 5: Mit einem zweiten Punkt kontrollieren.

Für $(2,3)$ gilt

$$2\cdot2+3=7>6.$$

Dieser Punkt liegt außerhalb des Lösungsbereichs.

2. Mehrere Ungleichungen: Nur die Schnittmenge zählt

Ein lineares Ungleichungssystem besteht aus mehreren Ungleichungen, die gleichzeitig erfüllt sein müssen. Jede Ungleichung liefert eine Halbebene. Der gemeinsame Teil aller Halbebenen ist der Lösungsbereich.

Die Bedingungen

$$x\ge0 \qquad\text{und}\qquad y\ge0$$

heißen Nichtnegativitätsbedingungen. Sie beschränken die Lösung auf den ersten Quadranten.

Beispiel 2: Gemeinsamen Lösungsbereich bestimmen

Gegeben ist

$$\begin{aligned} x&\ge0,\\ y&\ge0,\\ x+y&\le6,\\ 2x+y&\le8. \end{aligned}$$

Schritt 1: Grenzgeraden zeichnen.

Zu den beiden schrägen Grenzen gehören

$$x+y=6 \qquad\text{und}\qquad 2x+y=8.$$

Beide Ungleichungen enthalten den Ursprung, denn $0\le6$ und $0\le8$.

Schritt 2: Schnittpunkt der schrägen Geraden berechnen.

$$\begin{aligned} x+y&=6,\\ 2x+y&=8. \end{aligned}$$

Die zweite Gleichung minus die erste ergibt

$$x=2.$$

Einsetzen in $x+y=6$ liefert

$$2+y=6 \quad\Longrightarrow\quad y=4.$$

Der Schnittpunkt ist $(2,4)$.

Schritt 3: Achsenecken bestimmen.

Auf der $y$-Achse ist $(0,6)$ die äußerste zulässige Ecke. Auf der $x$-Achse ist $(4,0)$ die äußerste zulässige Ecke.

Schritt 4: Zulässiges Vieleck notieren.

Die Eckpunkte lauten in Umlaufrichtung

$$(0,0),\ (0,6),\ (2,4),\ (4,0).$$

Schritt 5: Einen inneren Punkt kontrollieren.

Für $(2,2)$ gilt

$$2+2=4\le6$$

und

$$2\cdot2+2=6\le8.$$

Der Punkt erfüllt alle vier Bedingungen sogar mit echten Abständen zu den beiden schrägen Grenzgeraden und liegt im Inneren des zulässigen Bereichs.

Ein Punkt ist nur dann zulässig, wenn er jede einzelne Nebenbedingung erfüllt. Eine erfüllte Ungleichung genügt nicht.

3. Ein Sachproblem mathematisch modellieren

Vor jeder Rechnung müssen die Variablen und ihre Einheiten festgelegt werden. Danach wird jeder Satz der Aufgabenstellung einzeln übersetzt.

Beispiel 3: Produktionsplanung aufstellen

Ein Betrieb produziert zwei Produkte $A$ und $B$.

Gesucht ist die Produktionsmenge mit größtem gesamten Deckungsbeitrag.

Schritt 1: Variablen festlegen.

$$x=\text{Anzahl von Produkt }A, \qquad y=\text{Anzahl von Produkt }B.$$

Schritt 2: Maschinenzeit übersetzen.

Produkt $A$ benötigt $2$ Stunden, Produkt $B$ eine Stunde. Höchstens $100$ Stunden stehen bereit:

$$2x+y\le100.$$

Schritt 3: Materialbedingung übersetzen.

$$x+3y\le90.$$

Schritt 4: Nichtnegativität ergänzen.

$$x\ge0, \qquad y\ge0.$$

Schritt 5: Zielfunktion aufstellen.

Der gesamte Deckungsbeitrag ist

$$Z(x,y)=40x+50y.$$

Da ein größtmöglicher Wert gesucht ist, lautet das Modell:

$$\boxed{\max Z(x,y)=40x+50y}$$

unter den Nebenbedingungen

$$\boxed{ \begin{aligned} 2x+y&\le100,\\ x+3y&\le90,\\ x&\ge0,\\ y&\ge0. \end{aligned}}$$

Einheitenkontrolle: Die linke Seite der ersten Nebenbedingung wird in Stunden gemessen, die zweite in Kilogramm und die Zielfunktion in Euro.

4. Die Eckpunkte des zulässigen Bereichs berechnen

Bei einem beschränkten zulässigen Vieleck nimmt eine lineare Zielfunktion ihr Maximum und Minimum an mindestens einem Eckpunkt an. Deshalb genügt es, die relevanten Eckpunkte exakt zu bestimmen und dort die Zielfunktion auszuwerten.

Beispiel 4: Eckpunkte des Produktionsmodells bestimmen

Die Grenzgeraden sind

$$2x+y=100 \qquad\text{und}\qquad x+3y=90.$$

Schritt 1: Ursprung erfassen.

$$E_1=(0,0).$$

Schritt 2: Zulässige Ecke auf der $y$-Achse bestimmen.

Für $x=0$ liefern die beiden Bedingungen

$$y\le100 \qquad\text{und}\qquad 3y\le90\Longrightarrow y\le30.$$

Damit ist

$$E_2=(0,30).$$

Schritt 3: Schnittpunkt der Grenzgeraden berechnen.

Aus

$$2x+y=100$$

folgt

$$y=100-2x.$$

Einsetzen in $x+3y=90$ ergibt

$$x+3(100-2x)=90,$$ $$x+300-6x=90,$$ $$-5x=-210 \quad\Longrightarrow\quad x=42.$$

Damit

$$y=100-2\cdot42=16.$$

Also ist

$$E_3=(42,16).$$

Schritt 4: Zulässige Ecke auf der $x$-Achse bestimmen.

Für $y=0$ gilt

$$2x\le100\Longrightarrow x\le50$$

und

$$x\le90.$$

Die engere Bedingung liefert

$$E_4=(50,0).$$

Schritt 5: Jede Ecke in alle Nebenbedingungen einsetzen.

Zum Beispiel erfüllt $(42,16)$

$$2\cdot42+16=100$$

und

$$42+3\cdot16=90.$$

Der Punkt ist zulässig und beide Ressourcen werden vollständig ausgeschöpft.

5. Die Zielfunktion an allen Eckpunkten vergleichen

Eine Gleichung

$$40x+50y=k$$

beschreibt für jedes feste $k$ eine Gerade. Alle diese Zielfunktionsgeraden sind parallel. Beim Maximieren wird die Gerade parallel in Richtung größerer Werte verschoben. Der letzte Berührpunkt mit dem zulässigen Vieleck liefert das Maximum.

Beispiel 5: Produktionsplan maximieren und deuten

Für

$$Z(x,y)=40x+50y$$

werden alle vier Eckpunkte geprüft.

Der größte Tabellenwert ist

$$Z_{\max}=2480.$$

Er wird bei

$$(x,y)=(42,16)$$

erreicht.

Deutung im Kontext: Der Betrieb soll $42$ Stück von Produkt $A$ und $16$ Stück von Produkt $B$ herstellen. Dann beträgt der maximale gesamte Deckungsbeitrag $2480$ Euro. Dabei werden genau $100$ Maschinenstunden und $$ Kilogramm Material verbraucht.

6. Ein Minimum in einem unbeschränkten Bereich

Ein zulässiger Bereich kann unbeschränkt sein und trotzdem ein Minimum besitzen. Entscheidend ist, in welche Richtung die Zielfunktion besser wird.

Beispiel 6: Kosten minimieren

Gesucht ist das Minimum von

$$K(x,y)=3x+2y$$

unter

$$\begin{aligned} x+y&\ge6,\\ 2x+y&\ge8,\\ x&\ge0,\\ y&\ge0. \end{aligned}$$

Schritt 1: Relevante Ecken bestimmen.

Auf der $y$-Achse müssen $y\ge6$ und $y\ge8$ gelten. Die erste Ecke ist daher

$$E_1=(0,8).$$

Der Schnittpunkt der beiden Grenzgeraden folgt aus

$$\begin{aligned} x+y&=6,\\ 2x+y&=8. \end{aligned}$$

Subtraktion ergibt $x=2$, danach $y=4$. Somit

$$E_2=(2,4).$$

Auf der $x$-Achse müssen $x\ge6$ und $2x\ge8$ gelten. Daher

$$E_3=(6,0).$$

Schritt 2: Kosten an den Ecken vergleichen.

$$K(0,8)=3\cdot0+2\cdot8=16,$$ $$K(2,4)=3\cdot2+2\cdot4=14,$$ $$K(6,0)=3\cdot6+2\cdot0=18.$$

Schritt 3: Ergebnis angeben.

$$K_{\min}=14 \quad\text{bei}\quad (x,y)=(2,4).$$

Kontrolle: Beide Ressourcenforderungen werden genau erfüllt:

$$2+4=6 \qquad\text{und}\qquad 2\cdot2+4=8.$$

Obwohl der zulässige Bereich nach rechts oben unbegrenzt ist, steigen dort wegen der positiven Koeffizienten die Kosten. Das Minimum bleibt daher endlich.

7. Warum das Eckpunktverfahren funktioniert

Zwischen zwei Punkten eines Randsegments ändert sich eine lineare Zielfunktion gleichmäßig. Ein innerer Punkt eines Segments kann daher nicht plötzlich einen besseren Wert als beide Endpunkte besitzen.

Für ein lineares Optimierungsproblem gilt deshalb:

• Gibt es bei einem beschränkten zulässigen Vieleck ein eindeutiges Optimum, liegt es an einer Ecke.
• Ist die Zielfunktionsgerade parallel zu einer optimalen Randkante, sind alle Punkte dieser Kante optimal.
• Ist der zulässige Bereich in Verbesserungsrichtung offen, kann das Optimierungsproblem unbeschränkt sein.
• Haben die Nebenbedingungen keine gemeinsame Schnittmenge, gibt es keine zulässige Lösung.

8. Besonderer Fall: Mehrere optimale Lösungen

Beispiel 7: Eine ganze Kante ist optimal

Maximiere

$$Z(x,y)=x+y$$

unter

$$x\ge0, \qquad y\ge0, \qquad x+y\le4.$$

Schritt 1: Eckpunkte bestimmen.

$$(0,0),\ (4,0),\ (0,4).$$

Schritt 2: Zielfunktion auswerten.

$$Z(0,0)=0, \qquad Z(4,0)=4, \qquad Z(0,4)=4.$$

Zwei benachbarte Ecken besitzen denselben größten Wert.

Schritt 3: Randkante prüfen.

Auf der gesamten Strecke

$$x+y=4, \qquad x\ge0, \qquad y\ge0$$

gilt automatisch

$$Z(x,y)=x+y=4.$$

Damit ist jeder Punkt

$$(t,4-t) \quad\text{mit}\quad 0\le t\le4$$

optimal. Es gibt unendlich viele optimale Lösungen.

9. Weitere Sonderfälle erkennen

Keine zulässige Lösung

Die Bedingungen

$$x+y\le2 \qquad\text{und}\qquad x+y\ge5$$

können nie gleichzeitig erfüllt sein. Die Halbebenen schneiden einander nicht; das Modell ist unzulässig.

Unbeschränktes Maximum

Unter lediglich

$$x\ge0 \qquad\text{und}\qquad y\ge0$$

besitzt $Z=x+y$ kein Maximum. Für jeden zulässigen Punkt kann durch Vergrößern von $x$ oder $y$ ein besserer Wert erzeugt werden.

Ganzzahlige Stückzahlen

Das grafische Eckpunktverfahren behandelt zunächst reelle Variablen. Müssen $x$ und $y$ ganze Stückzahlen sein und ist die optimale Ecke nicht ganzzahlig, darf nicht blind gerundet werden. Die benachbarten zulässigen Gitterpunkte müssen einzeln geprüft werden.

10. Technologie sinnvoll verwenden

Ein Grafikprogramm oder CAS kann

• alle Ungleichungen gleichzeitig darstellen,
• Schnittpunkte der Grenzgeraden berechnen,
• den zulässigen Bereich sichtbar machen,
• Zielfunktionsgeraden verschieben,
• und Werte an Eckpunkten kontrollieren.

Ein sinnvoller Ablauf lautet:

1. Variablen und Modell selbst festlegen.
2. Jede Nebenbedingung einzeln eingeben.
3. Grafisch prüfen, ob die erwartete Halbebene markiert ist.
4. Grenzgeraden schneiden und Eckpunkte notieren.
5. Jeden Eckpunkt auf Zulässigkeit prüfen.
6. Zielfunktion an allen relevanten Ecken auswerten.
7. Ergebnis mit Einheit und Sachbedeutung angeben.

Technologie ersetzt weder die Übersetzung des Textes noch die Deutung des Ergebnisses.

11. Typische Fehler

Fehler 1: Ungleichungszeichen beim Modellieren vertauschen

„Höchstens“ führt zu $\le$, „mindestens“ zu $\ge$.

Fehler 2: Die falsche Halbebene markieren

Nach dem Zeichnen der Grenzgeraden immer einen Testpunkt einsetzen.

Fehler 3: Nur zwei Grenzgeraden betrachten

Auch $x\ge0$ und $y\ge0$ sind Nebenbedingungen und erzeugen oft Eckpunkte.

Fehler 4: Jeden Geradenschnitt als Ecke übernehmen

Ein Schnittpunkt ist nur relevant, wenn er alle Nebenbedingungen erfüllt.

Fehler 5: Nur eine scheinbar beste Ecke testen

Die Zielfunktion muss an allen relevanten Ecken ausgewertet werden.

Fehler 6: Nur den Zielfunktionswert nennen

Zur vollständigen Lösung gehören die optimale Variablenbelegung, der optimale Zielwert, die Einheiten und ein Antwortsatz.

Fehler 7: Reelle Lösung unzulässig runden

Bei ganzzahligen Variablen müssen nach dem Runden die Nebenbedingungen erneut geprüft werden.

12. Allgemeiner Arbeitsplan

1. Variablen mit Bedeutung und Einheit festlegen.
2. Jede Textbedingung einzeln in eine lineare Ungleichung übersetzen.
3. Nichtnegativitätsbedingungen ergänzen.
4. Zielfunktion aufstellen und Maximum oder Minimum festlegen.
5. Grenzgeraden zeichnen und richtige Halbebenen mit Testpunkten bestimmen.
6. Gemeinsame Schnittmenge als zulässigen Bereich markieren.
7. Relevante Eckpunkte rechnerisch bestimmen.
8. Jeden Kandidaten in alle Nebenbedingungen einsetzen.
9. Zielfunktion an allen zulässigen Ecken auswerten.
10. Besten Wert auswählen und Sonderfälle prüfen.
11. Variablenbelegung und Zielwert im Kontext deuten.
12. Einheiten, Ganzzahligkeit und Plausibilität kontrollieren.

Merksätze

• Eine lineare Ungleichung in zwei Variablen beschreibt eine Halbebene.
• Der Lösungsbereich eines Ungleichungssystems ist die Schnittmenge aller Halbebenen.
• Nebenbedingungen bestimmen, was zulässig ist; die Zielfunktion bestimmt, was gut ist.
• Relevante Eckpunkte müssen alle Nebenbedingungen erfüllen.
• Eine lineare Zielfunktion erreicht ein endliches Optimum an mindestens einer Ecke des zulässigen Bereichs.
• Gleiche optimale Werte an benachbarten Ecken bedeuten: Die ganze Verbindungskante ist optimal.
• Eine vollständige Lösung nennt Variablenbelegung, Zielwert, Einheiten und Sachdeutung.