Lineare Optimierung und Scheduling verständlich erklärt

Auf einen Blick

1. Ein Optimierungsmodell besteht aus Entscheidungsvariablen, Zielfunktion und Nebenbedingungen. Die meisten Fehler entstehen beim Modellieren, nicht beim Rechnen.
2. Lineare Programme lassen sich sehr effizient lösen. Ihr Optimum liegt in einer Ecke des zulässigen Bereichs, und Schattenpreise zeigen, was eine zusätzliche Einheit einer knappen Ressource wert ist.
3. Ganzzahligkeit und Reihenfolgen machen Probleme deutlich schwerer. Runden reicht nicht; Branch-and-Bound, Constraint Programming und Heuristiken schließen die Lücke.

Die Entscheidungstheorie vergleicht eine überschaubare Zahl von Optionen. In vielen betrieblichen Fragen ist die Zahl der Möglichkeiten aber riesig: Wie viel von welchem Produkt fertigen wir diese Woche? In welcher Reihenfolge laufen die Aufträge über die Maschine? Welche Fahrzeuge beliefern welche Kunden? Mathematische Optimierung sucht in solchen Räumen systematisch die beste zulässige Lösung. Sie ist der Kern des Operations Research, und ihre bekannteste Form – die lineare Programmierung – ist seit George B. Dantzigs Arbeiten der späten 1940er-Jahre ein Standardwerkzeug der Planung (Dantzig 1963).

Ein Optimierungsmodell in drei Teilen

Jedes Optimierungsmodell besteht aus denselben Bausteinen:

1. Entscheidungsvariablen – die Größen, die wir festlegen dürfen, etwa Produktionsmengen oder Startzeiten.
2. Zielfunktion – die Größe, die maximiert oder minimiert wird, etwa Deckungsbeitrag, Kosten oder Verspätung.
3. Nebenbedingungen – die Grenzen, die jede Lösung einhalten muss: Kapazitäten, Budgets, Mindestmengen, Regeln.

Sind Zielfunktion und Nebenbedingungen linear, spricht man von linearer Optimierung oder einem linearen Programm (LP). In Matrixschreibweise lautet die Standardform $\max\ c^\top x$ unter $Ax \le b$ und $x \ge 0$. „Programm“ meint hier übrigens keinen Code, sondern – im älteren Sprachgebrauch – einen Plan.

Beispiel: Produktionsplanung als lineares Programm

Ein Betrieb fertigt zwei Produkte. Ein Stück „Standard“ bringt 30 € Deckungsbeitrag und braucht eine Stunde in der Fertigung und drei Stunden in der Montage. Ein Stück „Premium“ bringt 40 € und braucht je zwei Stunden in Fertigung und Montage. Pro Woche stehen 40 Fertigungs- und 72 Montagestunden zur Verfügung, und vom Premium-Produkt lassen sich höchstens 16 Stück absetzen. Die Zahlen sind konstruiert; sie zeigen das Prinzip.

Mit $x_1$ Stück Standard und $x_2$ Stück Premium pro Woche lautet das Modell:

Alle Punkte, die sämtliche Nebenbedingungen erfüllen, bilden den zulässigen Bereich – hier ein Fünfeck. Die Abbildung zeigt ihn zusammen mit zwei Linien gleichen Deckungsbeitrags.

Die Ecken des Fünfecks und ihr Deckungsbeitrag:

Optimal sind also 16 Stück Standard und 12 Stück Premium mit 960 € Deckungsbeitrag pro Woche. Fertigung und Montage sind dann voll ausgelastet; beim Premium-Absatz bleiben 4 Stück Luft.

Warum das Optimum in einer Ecke liegt

Alle Pläne mit gleichem Deckungsbeitrag $30\,x_1 + 40\,x_2 = z$ liegen auf einer Geraden, und für verschiedene $z$ sind diese Geraden parallel. Verschiebt man sie in Richtung höherer Werte, verlässt die letzte Gerade den zulässigen Bereich in einer Ecke – oder, wenn sie zufällig parallel zu einer Kante liegt, entlang einer ganzen Kante mit lauter gleich guten Lösungen. Dieses Bild trägt in beliebig viele Dimensionen: Hat ein lineares Programm eine Optimallösung und besitzt der zulässige Bereich überhaupt Ecken, dann ist auch eine Ecke optimal (Bertsimas & Tsitsiklis 1997). Man muss also nicht unendlich viele Punkte durchsuchen, sondern nur endlich viele Ecken – allerdings können das in großen Modellen astronomisch viele sein.

Wie Solver lineare Programme lösen

Das Simplex-Verfahren nutzt die Ecken-Eigenschaft direkt: Es startet in einer zulässigen Ecke und wandert entlang der Kanten zu benachbarten Ecken, solange sich der Zielwert verbessert (Dantzig 1963). Im Beispiel kann es von (0 | 0) über (24 | 0) nach (16 | 12) gehen – je nach Auswahlregel auch über (0 | 16) und (8 | 16). Victor Klee und George Minty haben 1972 Beispiele konstruiert, in denen das Verfahren exponentiell viele Schritte braucht; in der Praxis ist es trotzdem meist sehr schnell (Bertsimas & Tsitsiklis 1997).

Einen anderen Weg gehen Innere-Punkte-Verfahren. Sie bewegen sich durch das Innere des zulässigen Bereichs auf das Optimum zu. Narendra Karmarkar stellte 1984 ein solches Verfahren mit polynomieller Laufzeit vor, das auch praktisch konkurrenzfähig war (Karmarkar 1984). Moderne Solver kombinieren beide Ansätze. Der Simplex-Löser des frei verfügbaren Solvers HiGHS etwa beruht auf einer parallelisierten Variante des dualen Simplex-Verfahrens (Huangfu & Hall 2018); daneben gibt es freie Werkzeuge wie SCIP und Google OR-Tools sowie kommerzielle Solver.

Schattenpreise: was eine Stunde mehr wert ist

Zu jedem linearen Programm gehört ein zweites, das duale Programm. Seine Variablen lassen sich als Preise der knappen Ressourcen lesen – deshalb spricht man von Dualität. Für das Beispiel lautet es:

Die Optimallösung ist $y_1 = 15$, $y_2 = 5$, $y_3 = 0$ mit dem Wert $40 \cdot 15 + 72 \cdot 5 = 960$ – genau der optimale Deckungsbeitrag des ursprünglichen Problems. Diese Übereinstimmung heißt starke Dualität.

Die Dualwerte sind die Schattenpreise der Ressourcen:

• Eine zusätzliche Fertigungsstunde erhöht den optimalen Deckungsbeitrag um 15 €, eine zusätzliche Montagestunde um 5 €.
• Die Absatzgrenze hat den Schattenpreis 0 €: Sie ist nicht ausgeschöpft, eine Lockerung bringt nichts.
• Die Preise „erklären“ die Lösung: Ein Stück Standard verbraucht eine Fertigungs- und drei Montagestunden, bewertet $1 \cdot 15 + 3 \cdot 5 = 30$ € – genau sein Deckungsbeitrag. Für Premium gilt $2 \cdot 15 + 2 \cdot 5 = 40$ €. Beide Produkte decken also exakt den Wert der Ressourcen, die sie binden.

Ganzzahlige Optimierung: wenn man nicht runden darf

Viele Entscheidungen sind unteilbar: eine Maschine kauft man ganz oder gar nicht, ein Fahrzeug fährt eine Tour oder nicht. Müssen Variablen ganzzahlig sein, spricht man von ganzzahliger Optimierung (MIP, mixed-integer programming). Naheliegend wäre, das lineare Programm zu lösen und das Ergebnis zu runden. Ein kleines Beispiel zeigt, warum das scheitert:

Ohne Ganzzahligkeit liegt das Optimum bei $x_1 = 2{,}25$ und $x_2 = 3{,}75$ mit der Leistung 41,25. Rundet man auf (2 | 4), sprengt man das Budget, denn $5 \cdot 2 + 9 \cdot 4 = 46$. Abrunden auf (2 | 3) ergibt nur 34, der Nachbar (3 | 3) immerhin 39. Das tatsächliche ganzzahlige Optimum ist aber (0 | 5) mit der Leistung 40 – nur große Maschinen, weit entfernt von der gerundeten Lösung.

Das Standardverfahren für solche Probleme ist Branch-and-Bound, von Ailsa Land und Alison Doig 1960 eingeführt (Land & Doig 1960). Es löst zuerst das lineare Programm ohne Ganzzahligkeit. Ist eine Variable gebrochen, teilt es das Problem in zwei Teilprobleme (etwa $x_2 \le 3$ und $x_2 \ge 4$). Jede LP-Lösung liefert eine obere Schranke für ihren Teilbaum; liegt diese unter der besten bekannten ganzzahligen Lösung, wird der Teilbaum verworfen. Für das Beispiel genügen sieben Knoten:

Moderne Solver ergänzen das Verfahren um Schnittebenen, Vorverarbeitung und Heuristiken; ganzzahlige Modelle mit Ja-nein-Entscheidungen, Fixkosten oder Logikbedingungen sind damit in der Praxis oft gut lösbar (Wolsey 2020). Im Allgemeinen sind sie aber NP-schwer: Es ist kein Verfahren bekannt, das jede Instanz in polynomieller Zeit löst.

Scheduling: Reihenfolgen optimieren

Beim Scheduling geht es darum, Aufträge zeitlich auf Ressourcen zu verteilen. Schon der einfachste Fall – eine Maschine, vier Aufträge – zeigt, dass „optimal“ vom Ziel abhängt (Pinedo 2016):

Die Regel SPT (shortest processing time) minimiert die Summe der Fertigstellungszeiten – und damit die mittlere Wartezeit. Der Beweis ist ein Tauschargument: Steht ein längerer Auftrag $i$ direkt vor einem kürzeren Auftrag $j$, und beginnt das Paar zur Zeit $t$, dann verringert ein Tausch die Summe der beiden Fertigstellungszeiten um

während alle anderen Aufträge unverändert bleiben. Die Regel EDD (earliest due date) minimiert dagegen die größte Verspätung. Im Beispiel liefert sie mit einer Stunde Verspätung das beste Ergebnis für die Termintreue – und zugleich die schlechteste Summe der Fertigstellungszeiten aller 24 möglichen Reihenfolgen.

Realistische Probleme sind viel schwerer. Beim Job-Shop-Problem durchlaufen Aufträge mehrere Maschinen in unterschiedlicher Reihenfolge; es ist NP-schwer, und schon mittelgroße Instanzen lassen sich nicht mehr durch Ausprobieren lösen (Pinedo 2016). Eingesetzt werden dann ganzzahlige Modelle, Constraint Programming – das Zeitfenster, Reihenfolgen und Ressourcen direkt als logische Bedingungen formuliert – sowie Heuristiken und Metaheuristiken wie lokale Suche oder Simulated Annealing. Heuristiken liefern schnell gute Pläne, aber keine Optimalitätsgarantie; Schranken aus exakten Verfahren zeigen, wie viel im schlechtesten Fall noch zu holen wäre.

Optimieren unter Unsicherheit

Das Produktionsbeispiel tut so, als wären Kapazitäten, Deckungsbeiträge und Absatz sicher bekannt. Das sind sie selten. Ein Plan, der für die durchschnittliche Nachfrage optimal ist, kann bei realer Schwankung teuer oder sogar undurchführbar werden. Zwei Ansätze berücksichtigen das ausdrücklich:

• Stochastische Optimierung beschreibt die Unsicherheit durch Szenarien mit Wahrscheinlichkeiten. Typisch sind zweistufige Modelle: Heute wird entschieden, was vor dem Eintreten der Unsicherheit festgelegt werden muss; später wird mit Korrekturmaßnahmen reagiert. Optimiert wird der Erwartungswert über alle Szenarien (Birge & Louveaux 2011). Die Szenarien stammen oft aus einer Monte-Carlo-Simulation.
• Robuste Optimierung verlangt, dass eine Lösung für alle Werte aus einer Unsicherheitsmenge zulässig bleibt, und optimiert den ungünstigsten Fall. Sie ist vorsichtiger, braucht dafür aber keine Wahrscheinlichkeiten (Ben-Tal et al. 2009).

In der Praxis kommt ein drittes Mittel hinzu: regelmäßig neu optimieren, sobald neue Daten vorliegen – und dabei darauf achten, dass Pläne nicht bei jeder kleinen Änderung umgeworfen werden.

Typische Fehler in der Praxis

1. Das falsche Ziel. Wer nur die Auslastung maximiert, erzeugt oft lange Warteschlangen. Die Zielfunktion muss abbilden, was dem Betrieb tatsächlich wichtig ist – inklusive der Rangfolge zwischen Zielen.
2. Fehlende Nebenbedingungen. Rüstzeiten, Schichtregeln oder Qualitätsfreigaben, die nicht im Modell stehen, machen den optimalen Plan unbrauchbar.
3. Unzulässig oder unbeschränkt. Meldet der Solver „unzulässig“, widersprechen sich Nebenbedingungen; viele Solver können eine minimale widersprüchliche Teilmenge bestimmen. „Unbeschränkt“ deutet fast immer auf eine vergessene Grenze hin.
4. Scheingenauigkeit. Wenn die Eingangsdaten auf zehn Prozent genau sind, sind sieben Nachkommastellen im Ergebnis bedeutungslos. Sensitivitätsanalysen zeigen, welche Daten wirklich zählen.
5. Die Lösung nicht erklären können. Schattenpreise, bindende Nebenbedingungen und der Vergleich mit einfachen Alternativplänen machen eine Empfehlung nachvollziehbar – und damit überhaupt erst freigabefähig.

Fazit

Optimierung übersetzt eine Planungsfrage in Variablen, Ziel und Grenzen – und findet dann zuverlässig die beste zulässige Lösung dieses Modells. Lineare Programme sind dabei der gut verstandene Kern: effizient lösbar, geometrisch anschaulich und mit Schattenpreisen, die erklären, was knapp ist. Ganzzahligkeit und Reihenfolgen machen Probleme schwerer, aber mit Branch-and-Bound, Constraint Programming und Heuristiken beherrschbar. Wer tiefer einsteigen will, findet bei Williams die Kunst des Modellierens (Williams 2013), bei Bertsimas und Tsitsiklis die Theorie der linearen Optimierung (Bertsimas & Tsitsiklis 1997) und bei Pinedo das Handwerkszeug für Scheduling (Pinedo 2016).

Häufige Fragen

Was ist lineare Optimierung?

Lineare Optimierung – auch lineare Programmierung – sucht Werte für Entscheidungsvariablen, die eine lineare Zielfunktion maximieren oder minimieren und dabei lineare Nebenbedingungen einhalten. Ein typisches Beispiel sind Produktionsmengen, die den Deckungsbeitrag maximieren, ohne Maschinenkapazitäten zu überschreiten.

Was ist ein Schattenpreis?

Der Schattenpreis einer Nebenbedingung gibt an, um wie viel sich der optimale Zielwert verbessert, wenn die zugehörige Ressource um eine Einheit wächst. Im Beispiel dieses Artikels ist eine zusätzliche Fertigungsstunde 15 € wert, eine Montagestunde 5 €. Der Wert gilt nur in einem Bereich, in dem die optimale Lösung ihre Struktur behält.

Warum darf man die Lösung eines linearen Programms nicht einfach runden?

Weil gerundete Werte unzulässig oder deutlich schlechter als das ganzzahlige Optimum sein können. Im Beispiel dieses Artikels verletzt die gerundete Lösung das Budget, und das ganzzahlige Optimum liegt an einer ganz anderen Stelle. Ganzzahlige Probleme löst man mit Verfahren wie Branch-and-Bound.

Welche Software löst Optimierungsprobleme?

Es gibt frei verfügbare Solver wie HiGHS und SCIP, Werkzeugsammlungen wie Google OR-Tools und kommerzielle Solver wie Gurobi oder CPLEX. Wichtiger als die Wahl des Solvers ist meist ein sauberes Modell mit geprüften Daten.

Quellen und weiterführende Literatur

1. BuchDantzig, G. B. (1963): Linear Programming and Extensions. Princeton University Press.
2. BuchBertsimas, D. und Tsitsiklis, J. N. (1997): Introduction to Linear Optimization. Athena Scientific.Gründliches Lehrbuch zu Geometrie, Simplex-Verfahren, Dualität und Innere-Punkte-Methoden.
3. BuchWilliams, H. P. (2013): Model Building in Mathematical Programming (5. Auflage). Wiley.Klassiker zur Frage, wie man reale Probleme in lineare und ganzzahlige Modelle übersetzt.
4. PaperKarmarkar, N. (1984): A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395.
5. PaperLand, A. H. und Doig, A. G. (1960): An Automatic Method of Solving Discrete Programming Problems. Econometrica 28(3), 497–520.
6. BuchWolsey, L. A. (2020): Integer Programming (2. Auflage). Wiley.
7. BuchPinedo, M. L. (2016): Scheduling: Theory, Algorithms, and Systems (5. Auflage). Springer.Standardwerk zu Prioritätsregeln, Komplexität und Algorithmen für Reihenfolgeprobleme.
8. PaperHuangfu, Q. und Hall, J. A. J. (2018): Parallelizing the dual revised simplex method. Mathematical Programming Computation 10(1), 119–142.Grundlage des Simplex-Lösers im freien Solver HiGHS.
9. BuchBirge, J. R. und Louveaux, F. (2011): Introduction to Stochastic Programming (2. Auflage). Springer.
10. BuchBen-Tal, A., El Ghaoui, L. und Nemirovski, A. (2009): Robust Optimization. Princeton University Press.

Zuletzt fachlich geprüft am 25. September 2026. Hinweise auf Fehler nehmen wir gern entgegen: impressum@nyxai.com.

Weiterlesen

Entscheiden & Optimieren

Entscheidungstheorie und Entscheidungsbäume

Von der Ergebnismatrix über Erwartungswert und Erwartungsnutzen bis zum Entscheidungsbaum: wie man Optionen unter Unsicherheit vergleicht – und was zusätzliche Information wert ist.

10 Min. Lesezeit

Simulation & Unsicherheit

Monte-Carlo-Simulation einfach erklärt

Wie aus Zufallszahlen belastbare Zahlen werden: π schätzen, eine Projektdauer tausendfach durchspielen und den Simulationsfehler sauber abschätzen.

10 Min. Lesezeit· mit interaktivem Explainer

Decision Intelligence

Was ist Decision Intelligence?

Wie aus Daten überprüfbare Entscheidungen werden: Definition, Abgrenzung zu BI und Predictive Analytics, die methodischen Bausteine und ein durchgerechnetes Beispiel.

13 Min. Lesezeit