Optimierung

Ziel

Die Optimierung beantwortet eine Frage der Dosierung: welche Mengen zu produzieren sind, welche Ressourcen welchem Zweck zugeteilt werden, welche Mischung gewählt wird, wenn die zulässigen Kombinationen zu zahlreich sind, um sie einzeln zu vergleichen.

Das Ergebnis besteht aus zwei Teilen. Der optimale Plan gibt jeder Entscheidungsvariablen einen Wert: so viele Einheiten davon und so viele davon. Die Lesart der Nebenbedingungen sagt, welche der Grenzen das Ergebnis zurückhält und was ihre Lockerung um eine Einheit wert wäre. Der zweite Teil eröffnet das Gespräch mit dem Entscheidungsträger: eine bindende Nebenbedingung samt ihrem Schattenpreis macht aus "uns fehlt Kapazität" einen Betrag, den man den Kosten ihrer Beschaffung gegenüberstellt.

Einsatz

Wann einsetzen

• Geteilte Ressource: eine Werkstatt, ein Budget, ein Team, das auf Verwendungen mit ungleichem Ertrag zu verteilen ist.
• Bezifferbares Ziel und bezifferbare Grenzen: eine Marge, Gesamtkosten, eine Abweichung von einer Zielgrösse; gemessene Kapazitäten, vertragliche Zusagen, regulatorische Obergrenzen.
• Zu viele Kombinationen, um sie aufzuzählen: ab drei oder vier Variablen führt der Vergleich der Pläne von Hand nicht mehr zum Ziel.
• Wiederkehrende Entscheidung: ein monatlicher Produktionsplan, eine tägliche Tour, ein Dienstplan; das Modell amortisiert sich mit jedem Durchlauf.
• Umstrittene Abwägung zwischen Abteilungen: die Diskussion verschiebt sich von den Präferenzen auf die Nebenbedingungen und das Ziel.

Wann nicht einsetzen

• Mehrere Kriterien ohne gemeinsames Mass: Kosten, Risiko und Image gegeneinander zu gewichten verlangt die multikriterielle Entscheidungsanalyse.
• Unsicherheit, die in den Daten steckt statt in der Wahl: die Entscheidungssimulation liefert eine Verteilung, wo die Optimierung einen Punkt liefert.
• Eine Handvoll bereits aufgelisteter Optionen: vier Lieferantenvarianten entscheidet man in einer Entscheidungsmatrix.

Beschreibung

Die drei Elemente und das Modell

Die Entscheidungsvariablen sind die Grössen, die der Entscheidungsträger steuert: die Stückzahl je Artikel, die Stunden je Baustelle, der Anteil jedes Titels in einem Portfolio. Jede trägt einen Typ, der den Rechenaufwand bestimmt: stetig für eine Grösse, die jeden Wert eines Intervalls annimmt, Liter oder Stunden; ganzzahlig für Objekte, die in Stück gezählt werden; binär für eine Alles-oder-nichts-Entscheidung, einen Standort eröffnen oder nicht. Beim Training eines Modells des maschinellen Lernens übernehmen die Gewichte der erklärenden Variablen diese Rolle.

Die Zielfunktion drückt in einer Formel aus, was maximiert oder minimiert werden soll. Ein Modell trägt genau eine davon. Je nach Anwendungsgebiet heisst sie Entscheidungsfunktion, Kostenfunktion oder Fehlerfunktion. Ein Ziel wie "die Marge maximieren und die Fristen minimieren" lässt sich so nicht lösen: eines von beiden wird zur Nebenbedingung, oder beide gehen in eine gewichtete Summe ein, deren Gewichte selbst eine Entscheidung sind.

Die Nebenbedingungen begrenzen das Machbare. Jede wird als Ungleichung oder Gleichung über den Entscheidungsvariablen geschrieben: eine Kapazität, die eine Obergrenze setzt, eine Lieferzusage, die eine Untergrenze setzt, eine Zusammensetzung, die genau aufgehen muss. Der IIBA-Leitfaden verortet den Beitrag des Analysten bei den Nebenbedingungen: Sie werden durch Elizitation und in den Geschäftsregeln entdeckt, die die Geschäftsregelanalyse dokumentiert.

Das Optimierungsmodell ist eine Zeile für die Zielfunktion, eine Liste von Ungleichungen, eine Typdeklaration je Variable. Dieser Text ist das, was der Solver verarbeitet. Für die meisten Planungsprobleme eines Unternehmens passt er auf eine Seite.

Die Nebenbedingungen schreiben

Eine brauchbare Nebenbedingung trägt vier Angaben: die begrenzte Grösse, den Verbrauch je Einheit jeder Variablen, die Schranke und die Herkunft dieser Schranke. Die ersten drei sind Messwerte. Die vierte ist ein Personen- oder Dokumentenname, andernfalls ist die Nebenbedingung von einer in einer Sitzung genannten Zahl nicht zu unterscheiden.

Die Schranken stammen von unterschiedlichen Ansprechpartnern: die Maschinenkapazität aus der Werkstatt, die Einkaufsobergrenze aus dem Einkauf, die gesetzliche Pflicht vom Juristen. Die Verbrauchskoeffizienten werden an vergangenen Fertigungsläufen gemessen: Ein Fehler verschiebt dort die Gerade der Nebenbedingung und damit die Koordinaten des optimalen Eckpunkts. Ein Koeffizient der Zielfunktion ist toleranter: Er lässt oft eine Abweichung von einem Viertel und mehr zu, bevor der Plan den Eckpunkt wechselt. Implizite Nebenbedingungen zu vergessen kostet am meisten: eine Rüstzeit zwischen zwei Artikeln, eine Mindestbesetzung je Schicht, eine Exklusivklausel, die eine Mischung von Lieferanten verbietet.

Zwei Antworten des Solvers zeigen eher eine fehlerhafte Formulierung an als eine schlechte Nachricht. Unzulässig heisst, dass keine Kombination alle Nebenbedingungen zugleich erfüllt, weil sich zwei Grenzen widersprechen oder ein vorgeschriebenes Minimum eine Kapazität übersteigt. Unbeschränkt heisst, dass das Ziel ohne Ende wächst, ein Zeichen für eine fehlende Nebenbedingung, meist für jene, die die Nachfrage oder die Beschaffung deckelt.

Die entscheidende Prüfung ist menschlich. Man zeigt den optimalen Plan den Personen, die ihn einhalten müssten, und fragt sie, ob sie das könnten. Was sie einwenden, ist die fehlende Nebenbedingung, in ihren Worten.

Zwei Familien unter einem Namen

Der IIBA-Leitfaden trennt die Probleme nach dem Grad der Unsicherheit, den sie tragen.

Sind Zielfunktion und Nebenbedingungen linear, gehört das Problem in die lineare Optimierung: eine lineare Funktion über dem konvexen Bereich maximieren oder minimieren, den lineare Ungleichungen ausschneiden. George Dantzig entwarf das Lösungsverfahren dazu, das Simplexverfahren, 1947 an Planungsproblemen der US-Luftwaffe; der Name "lineare Programmierung" geht auf Tjalling Koopmans im Jahr 1948 zurück. Es folgten Algorithmen mit polynomialer Laufzeit: 1979 die Ellipsoidmethode von Khachiyan, 1984 das Innere-Punkte-Verfahren von Karmarkar. Der IIBA-Leitfaden hält ihren breiten Einsatz in Logistik, Produktion und Projektmanagement fest.

Sobald die Beziehung nicht mehr linear ist, wird das Optimum Schritt für Schritt gesucht. Ein Modell des maschinellen Lernens passt seine Gewichte an, um eine Fehlerfunktion durch Gradientenabstieg zu verkleinern, und folgt dabei in jeder Iteration der Richtung der stärksten Abnahme. Für die Volatilität eines Portfolios gilt dasselbe: Sie hängt nicht proportional von dessen Zusammensetzung ab. Der IIBA-Leitfaden leitet daraus eine Grenze ab: Die optimierte Lösung ist nicht zwingend die beste vorhandene Lösung. Er ergänzt, dass diese Berechnungen bei grossen Datenbeständen Rechenzeit verbrauchen.

Warum das Optimum auf einem Eckpunkt liegt

Bei zwei Variablen lässt sich die Geometrie zeichnen. Jede lineare Nebenbedingung teilt die Ebene in zwei Hälften und behält davon eine. Der Schnitt all dieser Halbebenen ist der zulässige Bereich, ein konvexes Polygon, das alle ausführbaren Pläne versammelt. Die Zielfunktion zeichnet darin eine Schar paralleler Geraden, eine je Ergebnisniveau. Diese Schar verschiebt man zu den wachsenden Werten hin bis zur letzten Berührung mit dem Polygon. Diese letzte Berührung ist ein Eckpunkt.

Ein Eckpunkt ist der Punkt, an dem sich mehrere Nebenbedingungen kreuzen, eine optimale Lösung macht also so viele Nebenbedingungen bindend, wie es Variablen gibt, die Nichtnegativitätsbedingungen eingeschlossen; das macht optimale Pläne so kompromisslos, mit Produktlinien auf null dort, wo die Intuition von allem etwas erwartet hätte. Das Simplexverfahren nutzt dieselbe Eigenschaft: Es geht von einem Eckpunkt zum benachbarten, bis keiner mehr besser ist, was ihm die Erkundung des Bereichsinneren erspart.

Die Lösung lesen

Ein Solver liefert mehr als nur einen Plan. Der Wert jeder Variablen ist der Plan selbst. Die bindenden Nebenbedingungen sind jene, die die Lösung bis zur Schranke ausschöpft; die übrigen behalten Schlupf, eine ungenutzte Reserve, die zu vergrössern nichts bringt. Der Schattenpreis einer bindenden Nebenbedingung beziffert den Zielgewinn, den eine zusätzliche Einheit der Ressource brächte, und ist dem Kaufpreis dieser Einheit gegenüberzustellen. Die Optimalitätsbereiche sagen, wie weit sich ein Margen- oder Kostenkoeffizient bewegen darf, bevor der optimale Plan den Eckpunkt wechselt. Die Differenz zum geltenden Plan ist die einzige Zahl, die das Gremium behalten wird.

Die Fallen

Die implizite Nebenbedingung

Der IIBA-Leitfaden zählt die exakte Formulierung der Nebenbedingungen zu den Anforderungen der Technik. Eine Grenze, an deren Nennung niemand dachte, weil sie im Betrieb selbstverständlich ist, ergibt einen Plan, der mathematisch optimal und betrieblich unmöglich ist. Der Plan wird dann verworfen, und mit ihm die Methode.

Das Ersatzziel

Die Marge des Monats zu maximieren ist leicht geschrieben und selten das, was das Unternehmen will. Das Modell gehorcht aufs Wort: Es gibt einen Kunden mit geringer Marge auf, von dem ein Volumen an Servicearbeiten abhängt, oder lastet eine Maschine aus, deren Wartung geplant ist. Was das Ziel nicht sagt, muss in die Nebenbedingungen, als Mindestleistungen oder Mindestanteile.

Das Runden der ganzen Zahlen

Stetig lösen und dann runden ist die häufigste Abkürzung. Sie verlässt den zulässigen Bereich, sobald die Nebenbedingungen eng sind: 80,4 auf 81 aufgerundete Einheiten überschreiten die Kapazität. Solver behandeln ganzzahlige Variablen von Haus aus, zu höheren Rechenkosten, die bei Modellen dieser Grösse bescheiden bleiben.

Die Genauigkeit des Solvers für die der Daten gehalten

Ein Solver zeigt CHF 43'200 an, berechnet aus Margenkoeffizienten, die auf 10% genau geschätzt sind. Die Zahl der Nachkommastellen gehört der Maschine, die Verlässlichkeit gehört den Eingangsdaten. Das Gegenmittel ist, das Modell mit den Koeffizienten an den Rändern ihres Bereichs erneut zu rechnen und zu prüfen, ob der Plan hält; dieses Vorgehen gehört zur Sensitivitätsanalyse.

Das lokale Optimum für das Optimum gehalten

Bei einem nichtlinearen Problem hält ein Gradientenabstieg am Grund der Mulde an, die er gefunden hat, ohne zu wissen, ob anderswo eine tiefere liegt. Von mehreren Startpunkten aus neu zu rechnen und die Ergebnisse zu vergleichen ist die übliche Prüfung. Diese Vorsicht entfällt in der linearen Optimierung, wo die Konvexität des Bereichs garantiert, dass das gefundene Optimum das globale ist.

Das Modell, das niemand erklären kann

Der IIBA-Leitfaden führt das unter den Grenzen: Komplexe Formulierungen sind den Stakeholdern schwer zu erklären. Ein Entscheidungsträger unterschreibt keinen Plan, dessen Herkunft er nicht kennt. Die Gegenmassnahme ist, das Modell über seine Nebenbedingungen zu präsentieren, die jeder wiedererkennt, bevor man auf die Mechanik kommt.

KI-Überlegungen

Der erste nützliche Einsatz ist die Übersetzung in eine Formulierung. Ein Sprachmodell macht aus "wir können 640 Werkstattstunden im Monat nicht überschreiten" eine Ungleichung über den deklarierten Variablen und schreibt die wenigen Codezeilen, die einen Solver aufrufen. Das Ergebnis lässt sich prüfen, denn ein Optimierungsmodell ist ein kurzer Text, dessen Zeilen sich einzeln gegen die Nebenbedingung lesen lassen, die sie abzubilden vorgeben.

Der zweite ist die Schätzung der Koeffizienten aus vergangenen Läufen, die tatsächliche Montagezeit je Artikel oder der Materialverbrauch je Einheit: eine statistische Anpassung an Daten, die das Unternehmen bereits besitzt. Der dritte ist die Erzeugung von Varianten: das Ziel umformulieren, eine zweite Schicht ergänzen, eine Obergrenze lockern, die Reihe der Szenarien rechnen und die Abweichungen zeigen. Der vierte ist, das Ergebnis in Worte zu fassen, ausgehend von den bindenden Nebenbedingungen und den Schattenpreisen, wobei die Zahlen geliefert werden und nichts erfunden wird.

Zwei Grenzen bleiben. Die Nebenbedingungen gehören der Organisation: eine Vertragsklausel, die Kapazität eines Prüfstands, eine Obergrenze aus einer kantonalen Bewilligung. Ein Sprachmodell schlägt plausible vor, was die erste Liste beschleunigt und die Freigabe durch die Person, die für jede Zahl geradesteht, nicht ersetzt. Auf die Frage "wie lautet der optimale Plan" verfasst ein Sprachmodell einen plausiblen Plan, ohne etwas gelöst zu haben: Keine Nebenbedingung ist garantiert erfüllt. Dass das Training eines solchen Modells selbst auf einer Optimierung beruht, macht es nicht fähig, die des Lesers zu lösen.

Beispiele

Eine Elektronikwerkstatt im Jura montiert zwei Messgeräte. Montage und Kalibrierung laufen über dieselben Ressourcen und ein Funkmodul steckt nur im vernetzten Modell.

Entscheidend ist die Lesart der beiden ausgelasteten Ressourcen. Eine zusätzliche Montagestunde ist CHF 45 wert, eine zusätzliche Prüfstandsstunde CHF 60, in einer Werkstatt mit vier Personen in der Montage und einem einzigen Prüfstand im Zweischichtbetrieb. Der Schattenpreis wird dem Kaufpreis der Einheit gegenübergestellt, und die beiden Einheiten kauft man nicht auf dieselbe Weise.

Eine Montagestunde kauft man stundenweise, als Überstunde oder über Temporärarbeit, zu einem bekannten Ansatz, den man den CHF 45 gegenüberstellt. Eine Prüfstandsstunde kauft man nicht: Der Prüfstand läuft bereits elf Stunden je Arbeitstag, und die kleinste am Markt erhältliche Menge ist ein ganzer zweiter Prüfstand, eine über mehrere Jahre abzuschreibende Investition. Zuerst zu lockern ist deshalb die Montage, trotz ihres tieferen Betrags; der Prüfstand ist ein Investitionsentscheid. Ein grösseres Kontingent an Funkmodulen auszuhandeln brächte nichts, da diese Nebenbedingung nicht bindend ist.

Die Stückmargen bleiben Schätzungen. Der Bereich CHF 75 bis CHF 150 gilt für den Margenkoeffizienten des Standard, heute CHF 120. Da die Marge der Verkaufspreis abzüglich der variablen Stückkosten ist, verschiebt eine Revision dieser Kosten die Marge um denselben Betrag in die Gegenrichtung: Solange die Marge innerhalb dieser Grenzen bleibt, wird das Modell nicht neu aufgerollt.

Visualisierungen

Nur eines verlangt eine Zeichnung: der Schritt von den Nebenbedingungen zur Lösung. Die Ungleichungen stehen in Zeilen und die Lösung in Spalten, doch warum das Optimum auf einem Eckpunkt landet und nicht in der Mitte des Bereichs, lässt sich nur an einer Ebene ablesen. Die Formulierung und die Lesart des Ergebnisses bleiben Tabellen, jede mit ihrer Herkunft oder ihrer Deutung daneben.

Aufwand

Werkzeuge

Die Tabellenkalkulation mit Solver ist der Einstieg. Der Solver von Excel, entwickelt von Frontline Systems, behandelt lineare, ganzzahlig lineare, quadratische und nichtlineare Probleme. Der IIBA-Leitfaden nennt ihn als Werkzeug zur Demonstration: Ein Modell mit zwei Variablen in der Arbeitsmappe, die das Controlling ohnehin liest, schafft mehr Vertrauen als ein Methodenvortrag. LibreOffice Calc bringt einen vergleichbaren Solver mit.

Programmierbibliotheken übernehmen, sobald das Modell versioniert, erneut gerechnet oder an ein System angebunden werden muss. PuLP und Pyomo in Python schreiben das Modell in einer Syntax, die seiner algebraischen Form nahekommt, scipy.optimize.linprog deckt den einfachen linearen Fall ab, Googles OR-Tools kommt für Touren- und Reihenfolgeprobleme hinzu, lpSolve leistet dasselbe in R. Die Codedatei wird zur Dokumentation des Modells.

Spezialisierte Solver stehen hinter diesen Bibliotheken, wenn die Grösse es verlangt: Gurobi, IBM CPLEX und FICO Xpress auf der kommerziellen Seite, HiGHS, CBC und GLPK auf der freien. In der industriellen Fertigung tragen die auf ein ERP aufgesetzten Advanced-Planning-Module das Modell von Haus aus, wobei die Kapazitäts- und Stücklistendaten bereits vorliegen. Auf der iterativen Seite bringen Bibliotheken des maschinellen Lernens wie scikit-learn, PyTorch und TensorFlow den Gradientenabstieg und seine Varianten mit.

Quellen

• IIBA, Guide to Business Data Analytics, §3.14 Optimization: die Definition, die drei Elemente und ihr Zusammenbau zu einem Modell, die Trennung zwischen geringer und hoher Unsicherheit, die Rolle des Analysten beim Aufdecken der Nebenbedingungen, die Stärken und die Grenzen.
• MacTutor History of Mathematics, George Dantzig, University of St Andrews: die Konzeption des Simplexverfahrens 1947 an militärischen Planungsproblemen und die Zuschreibung des Namens "lineare Programmierung" an Tjalling Koopmans im Jahr 1948.
• Wolfram MathWorld, Linear Programming: die Standardform des Problems, der durch die Ungleichungen definierte konvexe Bereich, das Simplexverfahren, die Ellipsoidmethode von Khachiyan und das Innere-Punkte-Verfahren von Karmarkar, beide mit polynomialer Laufzeit.
• Frontline Systems, Linear Programming in Excel: die Dokumentation der Entwickler des Excel-Solvers und der Umfang der Probleme, die seine Engines behandeln.