Lineare Programmierung — Simplex-Verfahren & grafische Lösung

Lineare Programmierung ist eine Methode, um den besten Wert einer linearen Zielfunktion zu finden, zum Beispiel den maximalen Gewinn oder die minimalen Kosten, unter linearen Nebenbedingungen. Bei einem Problem mit zwei Variablen bestimmt die grafische Lösung den zulässigen Bereich und prüft seine Eckpunkte. Bei größeren Problemen nutzt das Simplex-Verfahren dieselbe Eckpunkt-Idee auf algebraische Weise.

Verwende lineare Programmierung nur dann, wenn sowohl die Zielfunktion als auch die Nebenbedingungen linear sind. Wenn die Beziehung gekrümmt ist, Kurven enthält oder von Produkten wie $xy$ abhängt, ist das Modell kein lineares Programm.

Definition der linearen Programmierung

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

unter Nebenbedingungen wie

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

sowie ähnlichen linearen Ungleichungen, zusammen mit Bedingungen wie $x_i \ge 0$, wenn negative Werte keinen Sinn ergeben.

Die Menge aller Punkte, die jede Nebenbedingung erfüllen, heißt zulässiger Bereich. Die lineare Programmierung fragt: Welcher dieser zulässigen Punkte liefert den besten Wert der Zielfunktion?

So funktioniert die grafische Methode

Wenn es nur zwei Entscheidungsvariablen gibt, kannst du jede Nebenbedingung in der $xy$-Ebene einzeichnen. Die Überlappung aller erlaubten Bereiche ist der zulässige Bereich.

Jeder Punkt in diesem Bereich ist eine gültige Lösung. Die Zielfunktion ordnet jedem davon einen Wert zu.

Für lineare Programme gilt eine wichtige Tatsache: Wenn eine optimale Lösung existiert, dann liegt mindestens eine optimale Lösung an einem Eckpunkt des zulässigen Bereichs. Deshalb konzentriert sich die grafische Methode auf die Eckpunkte, statt jeden Punkt in der schraffierten Fläche zu prüfen.

Durchgerechnetes Beispiel: Ein lineares Programm grafisch lösen

Angenommen, ein Betrieb stellt zwei Produkte her, $A$ und $B$.

• Gewinn pro Einheit von $A$: $3$
• Gewinn pro Einheit von $B$: $5$
• Maschinenzeit-Grenze: Jede Einheit von $A$ benötigt $1$ Stunde, jede Einheit von $B$ benötigt $2$ Stunden, und es stehen höchstens $8$ Stunden zur Verfügung
• Montage-Grenze: Jede Einheit von $A$ benötigt $1$ Stunde, jede Einheit von $B$ benötigt $1$ Stunde, und es stehen höchstens $5$ Stunden zur Verfügung

Sei $x$ die Stückzahl von $A$ und $y$ die Stückzahl von $B$.

Maximiere

$$P = 3x + 5y$$

unter den Nebenbedingungen

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Bestimme die Eckpunkte

Aus den Achsen und den Geraden der Nebenbedingungen ergeben sich die zulässigen Eckpunkte

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Der Punkt $(2,3)$ entsteht durch das Lösen der Randgleichungen

$$x + 2y = 8,\quad x + y = 5$$

Durch Subtraktion erhält man $y = 3$, und dann $x = 2$.

Prüfe die Zielfunktion an jedem Eckpunkt

Berechne den Gewinn an jedem Eckpunkt:

• Bei $(0,0)$ ist $P = 0$
• Bei $(5,0)$ ist $P = 15$
• Bei $(0,4)$ ist $P = 20$
• Bei $(2,3)$ ist $P = 21$

Der maximale Gewinn ist also

$$P = 21$$

bei

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

Das ist die grafische Methode in einem Satz: Zeichne den zulässigen Bereich, bestimme die Eckpunkte und werte dort die Zielfunktion aus.

Intuition zum Simplex-Verfahren

Die grafische Methode ist nur dann praktisch, wenn es zwei Variablen gibt, und manchmal noch bei drei, wenn du bereit bist, dir einen 3D-Bereich vorzustellen. Reale Optimierungsprobleme haben oft viele Variablen, sodass das Zeichnen des zulässigen Bereichs nicht mehr realistisch ist.

Das Simplex-Verfahren behält dieselbe Eckpunkt-Logik bei, führt sie aber algebraisch aus. Grob gesagt bewegt es sich von einem zulässigen Eckpunkt zu einem anderen, der die Zielfunktion verbessert, und stoppt, wenn kein benachbarter Schritt mehr einen besseren Wert liefert.

Ein gutes mentales Modell ist also:

• Grafische Methode: die Eckpunkte sehen
• Simplex-Verfahren: die Eckpunkte ohne Zeichnung durchlaufen

Diese Beschreibung ist die Intuition, nicht der vollständige Algorithmus. Das eigentliche Simplex-Verfahren verwendet ein Tableau oder eine äquivalente algebraische Form, um in jedem Schritt zu entscheiden, welche Variable in die Basis aufgenommen wird und welche sie verlässt.

Warum Eckpunkte wichtig sind

Lineare Zielfunktionen erzeugen Niveaugeraden wie

$$3x + 5y = k$$

für verschiedene Werte von $k$. Wenn du diese Gerade in Richtung größeren Gewinns verschiebst, ist der letzte Punkt, an dem sie den zulässigen Bereich noch berührt, der Ort des Maximums.

In vielen Zeichnungen liegt dieser letzte Berührpunkt an genau einem Eckpunkt. Wenn die Zielfunktionsgerade parallel zu einer Randkante ist, können mehrere Punkte auf dieser Kante optimal sein. Auch dann gibt es mindestens einen optimalen Eckpunkt.

Häufige Fehler

Zulässig mit optimal verwechseln

Ein Punkt kann alle Nebenbedingungen erfüllen und trotzdem die Zielfunktion nicht maximieren oder minimieren. Zulässig bedeutet nur erlaubt.

Nichtnegativitätsbedingungen vergessen

Wenn $x$ und $y$ Mengen darstellen, die du produzierst oder transportierst, ergeben negative Werte meist keinen Sinn. Wenn man $x \ge 0$ oder $y \ge 0$ weglässt, kann sich das Problem verändern.

Annehmen, dass jede Antwort eine ganze Zahl sein muss

Die gewöhnliche lineare Programmierung erlaubt gebrochene Werte. Wenn die Variablen ganze Zahlen sein müssen, etwa die Anzahl von Lastwagen oder Arbeitskräften, brauchst du ein Modell der ganzzahligen Programmierung oder eine zusätzliche Ganzzahligkeitsbedingung.

Annehmen, dass jedes Problem eine beste Lösung hat

Manche linearen Programme sind unzulässig, das heißt, kein Punkt erfüllt alle Nebenbedingungen. Andere sind unbeschränkt, das heißt, die Zielfunktion kann sich ohne Grenze verbessern. Ein endliches Optimum gibt es nur dann, wenn die Nebenbedingungen das Problem tatsächlich ausreichend begrenzen.

Die grafische Methode bei zu vielen Variablen verwenden

Sobald es viele Variablen gibt, ist Zeichnen nicht mehr das richtige Werkzeug. Dann werden das Simplex-Verfahren oder andere Optimierungsmethoden notwendig.

Wann lineare Programmierung eingesetzt wird

Lineare Programmierung wird verwendet, wenn Entscheidungen um begrenzte Ressourcen konkurrieren und sowohl das Ziel als auch die Einschränkungen linear modelliert werden können. Typische Beispiele sind Produktionsplanung, Transport, Personaleinsatz, Mischungsprobleme, Terminplanung und Budgetverteilung.

Ein Modell ist nur so gut wie seine Annahmen. Wenn die reale Beziehung nicht annähernd linear ist oder wenn die Variablen ganzzahlig sein müssen, ist ein gewöhnliches lineares Programm möglicherweise nur ein Ausgangspunkt.

Probiere ein ähnliches Problem

Nimm eine kleine Textaufgabe mit zwei Produkten, zwei Ressourcenbeschränkungen und einer Gewinnfunktion. Definiere die Variablen, zeichne die Nebenbedingungen und prüfe die Eckpunkte selbst. Wenn diese Idee sitzt, wird das Simplex-Verfahren viel leichter verständlich, weil es dieselbe Logik auf höhere Dimensionen erweitert.