Lineare Programmierung in 20 Minuten

Lineare Programmierung (LP) klingt nach schwerem mathematischem Gerät, ist aber im Kern eine der zugänglichsten Ideen der Optimierung. Wer eine Zielgröße maximieren oder minimieren will und dabei ein paar lineare Beschränkungen einhalten muss, arbeitet bereits mit einem LP, oft ohne es so zu nennen. Dieser Beitrag ist ein Schnelleinstieg für Studierende und Entwickler:innen ohne Vorwissen in Operations Research: Definition, ein durchgerechnetes Beispiel, die geometrische Anschauung und ein Wort dazu, wie man solche Probleme in der Praxis löst.

Was ist ein LP, in einem Satz

Ein lineares Programm besteht aus drei Zutaten: kontinuierlichen Entscheidungsvariablen, einer linearen Zielfunktion (die man minimiert oder maximiert) und linearen Nebenbedingungen. Entscheidend ist das Wort linear: Sowohl die Zielfunktion als auch alle Restriktionen sind gewichtete Summen der Variablen, ohne Produkte wie $x_1 x_2$, ohne Potenzen wie $x_1^2$ und ohne Beträge wie $|x_1|$. Und die Variablen dürfen beliebige reelle Werte annehmen, also auch Brüche.

Sobald man Variablen miteinander multipliziert, potenziert oder verlangt, dass sie ganzzahlig sind, verlässt man die Klasse der LPs und landet in schwierigeren Gefilden. Gerade weil die Klasse so eng definiert ist, lässt sie sich effizient und zuverlässig lösen. Und trotz dieser Einfachheit modelliert LP viele praktische Fragen: Produktion, Logistik, Finanzen, Energie, Telekommunikation.

Die drei Zutaten und eine kompakte Schreibweise

Formal schreibt man ein LP gern in einer kompakten, häufig genutzten Form:

$\max \; c^T x \quad \text{u.d.N.} \quad A x \leq b, \quad x \geq 0.$

Dabei ist $x \in \mathbb{R}^n$ der Vektor der Entscheidungsvariablen, $c \in \mathbb{R}^n$ der Zielfunktionsvektor, $A \in \mathbb{R}^{m \times n}$ die Koeffizientenmatrix der Restriktionen und $b \in \mathbb{R}^m$ die rechte Seite. „u.d.N.“ heißt „unter den Nebenbedingungen“. Ein Hinweis zur Terminologie: Die Bezeichnungen schwanken in der Literatur. Manche Lehrbücher nennen diese Ungleichungsform „kanonische Form“ und reservieren „Standardform“ für die Gleichungsform ($A x = b$, $x \geq 0$), wie sie der Simplex-Algorithmus intern nutzt. Auf den Namen kommt es weniger an als darauf, dass sich alles ineinander übersetzen lässt.

Denn diese Form wirkt speziell, ist es aber nicht: Sie ist ohne Einschränkung allgemein. Minimieren ist dasselbe wie Maximieren von $-c^T x$. Eine Gleichung $a^T x = b$ ersetzt man durch die zwei Ungleichungen $a^T x \leq b$ und $a^T x \geq b$. Eine $\geq$-Ungleichung wird durch Multiplikation mit $-1$ zu einer $\leq$-Ungleichung. Und eine freie, vorzeichenlose Variable schreibt man als Differenz zweier nichtnegativer Variablen.

Vom Text zum Modell: die Möbelwerkstatt

Der eigentliche Handwerksschritt ist das Modellieren, also der Weg von einer Textaufgabe zum LP. Ein Beispiel: Eine Möbelwerkstatt fertigt Tische und Stühle. Pro Tisch bleiben 40 Euro Deckungsbeitrag, pro Stuhl 30 Euro. Ein Tisch braucht 2 Stunden Maschinenzeit, ein Stuhl 1 Stunde, und pro Woche stehen 100 Maschinenstunden zur Verfügung. In der Montage kostet jedes Stück 1 Stunde, hier sind 80 Stunden verfügbar. Wie viele Tische und Stühle sollte die Werkstatt bauen, um den Deckungsbeitrag zu maximieren?

Wir führen zwei Variablen ein: $x_1$ für die Zahl der Tische, $x_2$ für die Zahl der Stühle. Der Deckungsbeitrag ist $40 x_1 + 30 x_2$, das ist die Zielfunktion. Die Maschinenzeit liefert $2 x_1 + x_2 \leq 100$, die Montagezeit $x_1 + x_2 \leq 80$. Negative Stückzahlen ergeben keinen Sinn, also $x_1, x_2 \geq 0$. Das vollständige Modell:

$\max \; 40 x_1 + 30 x_2$ $2 x_1 + x_2 \leq 100 \quad \text{(Maschine)},$ $x_1 + x_2 \leq 80 \quad \text{(Montage)},$ $x_1, x_2 \geq 0.$

Geometrische Intuition: der zulässige Bereich

Jede Ungleichung $a_i^T x \leq b_i$ definiert einen Halbraum, also eine Hälfte der Ebene. Der Durchschnitt aller Halbräume, zusammen mit $x \geq 0$, ist ein konvexes Polyeder, der zulässige Bereich. In unserem Beispiel ist das ein Vieleck in der $(x_1, x_2)$-Ebene, begrenzt von den beiden Achsen und den zwei Restriktionsgeraden.

Die Zielfunktion $c^T x = z$ beschreibt für festes $z$ eine Gerade, eine Niveaulinie, die senkrecht auf dem Vektor $c$ steht. Optimieren heißt anschaulich: Man schiebt diese Niveaulinie in Richtung $c$ (bei Maximierung), so weit es geht, ohne das Polyeder zu verlassen. Der letzte Berührpunkt ist optimal.

Das Optimum sitzt in einer Ecke

Der Fundamentalsatz der linearen Optimierung macht das präzise: Besitzt ein LP eine optimale Lösung, so wird sie in (mindestens) einer Ecke des Polyeders angenommen. Der Grund ist die Kombination aus konvexem Bereich und linearer Zielfunktion; sie sorgt außerdem dafür, dass jedes lokale Optimum automatisch global ist. Praktisch heißt das: Man muss nur die endlich vielen Ecken prüfen, nicht die unendlich vielen inneren Punkte.

Für die Möbelwerkstatt sind es vier Ecken, und wir setzen jede einfach in die Zielfunktion $40 x_1 + 30 x_2$ ein:

• $(0,0)$: $40 \cdot 0 + 30 \cdot 0 = 0$
• $(50,0)$: $40 \cdot 50 + 30 \cdot 0 = 2000$
• $(0,80)$: $40 \cdot 0 + 30 \cdot 80 = 2400$
• $(20,60)$: $40 \cdot 20 + 30 \cdot 60 = 800 + 1800 = 2600$

Die drei Ecken auf den Achsen liest man direkt ab. Die interessante vierte Ecke $(20,60)$ liegt im Schnittpunkt der beiden Restriktionsgeraden, dort binden also beide Restriktionen mit Gleichheit. Man löst das $2 \times 2$-Gleichungssystem

$2 x_1 + x_2 = 100 \quad \text{(Maschine)}, \qquad x_1 + x_2 = 80 \quad \text{(Montage)}.$

Subtrahiert man die zweite Gleichung von der ersten, fällt $x_2$ heraus: $2 x_1 - x_1 = 100 - 80$, also $x_1 = 20$. Einsetzen in $x_1 + x_2 = 80$ liefert $x_2 = 60$. Zur Kontrolle die Restriktionen: Maschine $2 \cdot 20 + 60 = 100$ und Montage $20 + 60 = 80$, beide exakt ausgeschöpft.

Das Optimum ist damit $x_1 = 20$, $x_2 = 60$ mit einem Deckungsbeitrag von 2600 Euro. Dass hier ganze Zahlen herauskommen, ist Zufall der gewählten Zahlen. Im Allgemeinen sind LP-Optima gebrochen, und das ist völlig in Ordnung, denn die Variablen dürfen ja reelle Werte annehmen. Ändert man etwa die Montagekapazität von 80 auf 85 Stunden, wandert das Optimum nach $x_1 = 15$, $x_2 = 70$ mit Zielwert $40 \cdot 15 + 30 \cdot 70 = 2700$: fünf Stunden mehr Montage bringen 100 Euro, ein erster Vorgeschmack auf die Schattenpreise der Dualität.

Wenn es kein eindeutiges Optimum gibt

Ein LP hat nicht immer genau eine Lösung. Es gibt vier mögliche Ausgänge. Erstens ein eindeutiges Optimum in einer Ecke, wie oben. Zweitens unendlich viele Optima: Steht $c$ senkrecht auf einer Kante (verläuft die Niveaulinie also parallel zu ihr), ist die ganze Kante optimal (eine Ecke darunter aber immer noch). Drittens unzulässig (infeasible): Die Restriktionen widersprechen sich, der zulässige Bereich ist leer. Viertens unbeschränkt (unbounded): Der Zielwert wächst über alle Grenzen, weil das Polyeder in Zielrichtung offen ist. Nebenbei: Ein beschränktes, nichtleeres Polyeder heißt Polytop, ein Polyeder darf aber durchaus unbeschränkt sein.

Simplex: intelligentes Ablaufen der Ecken

Alle Ecken durchzuprobieren funktioniert bei zwei Variablen, wird aber bei vielen Variablen schnell aussichtslos, da ihre Zahl explodiert. Genau hier setzt das Simplex-Verfahren an, das George Dantzig 1947 entwickelte. Die Idee: Man startet in einer Ecke und läuft entlang der Kanten des Polyeders von Ecke zu benachbarter Ecke, wobei sich der Zielwert in jedem Schritt verbessert (oder zumindest nicht verschlechtert). Sobald keine bessere Nachbarecke mehr existiert, ist die aktuelle Ecke optimal. Man läuft also gezielt an den Kanten entlang, statt blind alle Ecken zu testen.

Wer das an einem 2D-Fall sehen möchte, kann meinen Simplex-Visualizer ausprobieren; dort lässt sich die Eckenwanderung Schritt für Schritt nachvollziehen. Die vollständige Herleitung mit Schlupfvariablen und Tableau spare ich hier bewusst aus; für die Intuition genügt das Bild der wandernden Ecke.

In der Praxis: fertige Solver nutzen

Man implementiert Simplex heute nicht selbst. Interessant ist die Laufzeitfrage trotzdem: Simplex kann im schlimmsten Fall exponentiell viele Schritte brauchen (der Klee-Minty-Würfel von 1972 zeigt das für bestimmte Pivot-Regeln), in der Praxis ist das Verfahren aber sehr schnell und robust. Dass LP grundsätzlich in polynomieller Zeit lösbar ist, zeigten erst andere Verfahren: die Ellipsoidmethode (Khachiyan, 1979, theoretisch wichtig, praktisch langsam) und die Innere-Punkte-Verfahren (Karmarkar, 1984), die anders als Simplex quer durch das Innere des Polyeders laufen.

Für die eigene Arbeit greift man zu fertigen Solvern. Quelloffen sind etwa HiGHS (der Standard hinter SciPys linprog), GLPK und COIN-OR CLP, kommerziell Gurobi, CPLEX oder Mosek. Formuliert wird das Modell meist über eine Modellierungsschicht wie PuLP, Pyomo oder JuMP (Julia). In wenigen Zeilen Python steht die Möbelwerkstatt und der Solver liefert $(20, 60)$ in Millisekunden.

Was als Nächstes kommt: Dualität und Ganzzahligkeit

Zwei Themen schließen sich natürlich an und verdienen eigene Artikel. Zum einen die Dualität: Zu jedem LP gehört ein duales LP mit vertauschten Rollen von Zielen und Restriktionen. Bei starker Dualität stimmen die Optimalwerte beider überein, und die Dualvariablen lassen sich als Schattenpreise der Ressourcen deuten, die Grundlage jeder Sensitivitätsanalyse.

Zum anderen die Ganzzahligkeit: Verlangt man ganzzahlige Variablen (Integer bzw. Mixed-Integer Programming), wird das Problem NP-schwer, im Gegensatz zum in P liegenden LP. Das LP ohne Ganzzahligkeitsforderung heißt LP-Relaxierung und liefert eine Schranke; gelöst wird typischerweise mit Branch-and-Bound. Ein wichtiger Merksatz zum Schluss: Die LP-Lösung einfach zu runden ist im Allgemeinen weder optimal noch überhaupt zulässig.

Fazit

Ein LP ist eine lineare Zielfunktion über kontinuierlichen Variablen unter linearen Nebenbedingungen. Der zulässige Bereich ist ein konvexes Polyeder, und das Optimum sitzt, sofern es existiert, in einer seiner Ecken. Das Simplex-Verfahren findet diese Ecke durch systematisches Ablaufen der Kanten, und in der Praxis erledigt ein fertiger Solver die Arbeit in Sekundenbruchteilen. Wer das verstanden hat, hat das Fundament, auf dem Dualität und ganzzahlige Optimierung aufbauen.