Lineare Programmierung — Optimierung linearer Zielfunktionen unter linearen Nebenbedingungen
- Eingeführt von
- George B. Dantzig
- Jahr
- 1947
- Typ
- Mathematical programming / continuous optimization
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die Lineare Programmierung (LP), deren Pionier George B. Dantzig 1947 war, ist eine mathematische Methode zur Ermittlung des besten Werts einer linearen Zielfunktion — wie z.
B. minimaler Kosten oder maximaler Gewinne — unter einer Reihe von linearen Ungleichungs- und Gleichungsnebenbedingungen. Sie ist die grundlegende Technik der Unternehmensforschung und bildet die Basis für Produktionsplanung, Ressourcenallokation, Logistik, Ernährungsprobleme und unzählige andere Entscheidungsszenarien in Ingenieurwesen, Wirtschaft und Naturwissenschaften.
Die Intuition hinter der Methode
Stellen Sie sich vor, Sie betreiben eine kleine Fabrik, die zwei Produkte herstellt. Jedes Produkt erzielt einen bestimmten Gewinn, aber seine Herstellung verbraucht begrenzte Rohstoffe und Maschinenzeit. Die Lineare Programmierung ermittelt die exakte Produktmischung, die den höchsten Gewinn aus Ihren festen Ressourcen herauskitzelt — ohne Verletzung irgendeiner physischen oder vertraglichen Grenze. Der Begriff „linear“ bedeutet, dass der Gewinn und der Ressourcenverbrauch in einem geradlinigen Verhältnis zur produzierten Menge stehen. Die zulässigen Entscheidungen bilden ein Polygon (in zwei Dimensionen) oder ein Polyeder (in höheren Dimensionen), und die optimale Antwort liegt immer an einem seiner Eckpunkte.
Geschichte
Die systematische Entwicklung der Linearen Programmierung begann 1947, als George B. Dantzig, der für die US Air Force arbeitete, den Simplex-Algorithmus erfand, um die militärische Logistikplanung zu automatisieren. Dantzig veröffentlichte die grundlegende Theorie in seiner Monografie von 1963, die bis heute als kanonische Referenz gilt. Unabhängige und parallele Arbeiten von Leonid Kantorovich in der Sowjetunion (1939) befassten sich mit der Produktionsplanung unter Verwendung ähnlicher mathematischer Ideen, und Kantorovich erhielt 1975 teilweise für diesen Beitrag den Nobelpreis für Wirtschaftswissenschaften. Die theoretische Frage der polynomialen Lösbarkeit wurde durch Khachians Ellipsoidmethode (1979) und später durch Karmarkars Interior-Point-Methode (1984) geklärt, die sich für großskalige Probleme als praktisch schnell erwiesen. Heute sind kommerzielle und Open-Source-LP-Solver weltweit in Enterprise-Resource-Planning-, Flugplanungs- und Energiesystemen eingebettet.
Wann wird sie eingesetzt?
Die Lineare Programmierung ist immer dann geeignet, wenn Sie eine Größe optimieren müssen, die linear von einer Reihe von Entscheidungsvariablen abhängt und alle Nebenbedingungen ebenfalls linear sind. Sie erfordert keine Verteilungsannahmen und keine minimale Stichprobengröße — sie ist ein deterministisches mathematisches Modell, kein statistischer Schätzer. Die Methode ist anwendbar, wenn Entscheidungsvariablen kontinuierlich sind (ganzzahlige Werte sind sinnvoll); wenn Variablen ganze Zahlen oder binär sein müssen, ist stattdessen die Ganzzahlige Programmierung erforderlich. LP wird häufig in der Produktionsplanung, der Lieferkettenlogistik, bei Ernährungs- und Mischungsproblemen, der Optimierung von Finanzportfolios, Transport- und Zuordnungsproblemen sowie der Energieverteilung eingesetzt.
Grenzen und Hinweise
- Linearitätsanforderung: Wenn das Ziel oder eine Nebenbedingung nicht-linear ist, ist das LP-Modell falsch spezifiziert und die Lösung kann falsch oder unzulässiger sein.
- Nur kontinuierliche Variablen: Wenn Entscheidungsvariablen ganzzahlige oder binäre Werte annehmen müssen, liefert die LP-Relaxierung eine untere Schranke, aber keine gültige Lösung; stattdessen muss die Ganzzahlige Programmierung verwendet werden.
- Deterministisch: LP modelliert keine Unsicherheit in den Parametern; stochastische Programmierung oder robuste Optimierung ist erforderlich, wenn Daten unsicher sind.
- Degeneration und Zyklierung: In seltenen Fällen kann der Simplex-Algorithmus zwischen degenerierten Basen zyklieren, ohne zu konvergieren, obwohl Anti-Zyklierungsregeln (z. B. Bland's Regel) dies beheben.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Garantiertes globales Optimum: Da der zulässige Bereich ein konvexes Polyeder ist, ist jedes lokale Optimum auch ein globales Optimum, ohne Risiko, in einer sub-optimalen Lösung stecken zu bleiben.
- Hohe Skalierbarkeit: Moderne Solver (HiGHS, Gurobi, CPLEX) bewältigen Modelle mit Millionen von Variablen und Nebenbedingungen in Sekundenschnelle.
- Umfangreiche Nach-Lösungs-Informationen: Schattenpreise und Sensitivitätsbereiche liefern umsetzbare Einblicke in den Ressourcenwert und die Robustheit der Lösung ohne zusätzliche Durchläufe.
- Keine Verteilungsannahmen: LP ist ein rein algebraisches Modell, daher erfordert es keine Normalität oder andere statistische Eigenschaften der Daten.
Anwendungen
- Produktionsplanung: Ermittlung der optimalen Produktmischung, die den Gewinn maximiert und gleichzeitig Maschinenkapazitäten und Rohstofflimits berücksichtigt.
- Lieferketten- und Transportlogistik: Minimierung der Versandkosten über ein Netzwerk von Lagern und Kunden.
- Ernährungs- und Mischungsprobleme: Auswahl von Zutatenmengen, die die Ernährungsanforderungen zu minimalen Kosten erfüllen.
- Optimierung von Finanzportfolios: Allokation von Kapital über verschiedene Anlagen, um die erwartete Rendite unter Berücksichtigung von Risiko- und regulatorischen Nebenbedingungen zu maximieren.
- Energieverteilung und Stromnetzplanung: Minimierung der Brennstoffkosten bei gleichzeitiger Erfüllung der Stromnachfrage und der Generatorleistungsgrenzen.
- Personal- und Personaleinsatzplanung: Zuweisung von Schichten an Mitarbeiter, um die Nachfrage zu minimalen Arbeitskosten zu decken.
So funktioniert es
So funktioniert es
Das reale Entscheidungsproblem wird in mathematische Symbole übersetzt. Sie identifizieren die Entscheidungsvariablen (die Mengen, die Sie kontrollieren können), schreiben die Zielfunktion (was Sie maximieren oder minimieren möchten) als lineare Kombination dieser Variablen und schreiben jede Nebenbedingung — Ressourcenlimits, Kapazitätsgrenzen, Nachfrageanforderungen — als lineare Ungleichung oder Gleichung. Eine gut formulierte LP hat ein klares Ziel, explizite Variablengrenzen und jede strukturelle Nebenbedingung, die linear ausgedrückt wird.
Das Modell wird in eine kanonische oder Standardform gebracht, die ein Solver verarbeiten kann. Ungleichungen werden durch Einführung nicht-negativer Schlupf- oder Überschussvariablen in Gleichungen umgewandelt, und jede unbeschränkte Variable wird durch die Differenz zweier nicht-negativer Variablen ersetzt. Dieser mechanische Schritt erzeugt die Tableau- oder Matrixdarstellung, auf die der Algorithmus wirkt, und verändert das Problem nicht — er formt es nur für die Berechnung um.
Ein Solver durchsucht das zulässige Polyeder nach der optimalen Ecke. Der klassische Simplex-Algorithmus springt von Scheitelpunkt zu Scheitelpunkt entlang der Kanten des Polyeders und verbessert (oder erhält) immer das Ziel, bis kein verbessernder Nachbar mehr existiert. Interior-Point-Methoden (Barrier-Methoden) bewegen sich stattdessen durch das Innere des zulässigen Bereichs entlang eines zentralen Pfades, was besonders effizient für sehr große Modelle ist. Beide Algorithmenfamilien finden garantiert ein globales Optimum, wenn eines existiert, da der zulässige Bereich konvex ist.
Der Solver gibt die optimalen Werte der Entscheidungsvariablen und den optimalen Zielfunktionswert zusammen mit den dualen Variablen (Schattenpreisen) und Sensitivitätsbereichen zurück. Schattenpreise quantifizieren, wie stark sich das Ziel verbessern würde, wenn eine bindende Nebenbedingung um eine Einheit gelockert würde — sie sagen einem Entscheidungsträger direkt, wo zusätzliche Ressourcen am wertvollsten wären. Die Sensitivitätsanalyse identifiziert, wie stark sich ein Kostenkoeffizient oder ein Wert auf der rechten Seite ändern kann, bevor die aktuelle Basis nicht mehr optimal ist.
Häufige Fallstricke
- Anwendung von LP, wenn Nebenbedingungen oder das Ziel nicht-linear sind — die Lösung wird falsch sein oder der Solver wird das Modell ablehnen.
- Ignorieren von Ganzzahligkeitsanforderungen: Das Runden einer kontinuierlichen LP-Lösung auf ganze Zahlen ergibt im Allgemeinen keine zulässige oder optimale ganzzahlige Lösung; verwenden Sie stattdessen die Ganzzahlige Programmierung.
- Unzulässige oder unbeschränkte Modelle: Wenn der zulässige Bereich leer ist (widersprüchliche Nebenbedingungen) oder das Ziel unbeschränkt ist (fehlende Grenzbedingungen), meldet der Solver einen Fehler — überprüfen Sie immer die Modellstruktur, bevor Sie es ausführen.
- Behandlung von LP-Ausgaben als Empfehlung ohne Sensitivitätsanalyse: Eine Lösung, die technisch optimal ist, kann sich auf einer Messers Schneide befinden, wo eine kleine Datenänderung die Empfehlung umkehrt — Sensitivitätsbereiche sollten immer geprüft werden.
Häufig gestellte Fragen
Was macht ein Problem für die LP „linear“?
Sowohl die Zielfunktion als auch jede Nebenbedingung müssen linear sein — das bedeutet, jeder Term ist eine Konstante multipliziert mit einer einzelnen Entscheidungsvariablen, ohne Produkte von Variablen, ohne Exponenten und ohne nicht-lineare Funktionen. Wenn auch nur eine Nebenbedingung oder das Ziel z. B. x mal y oder x Quadrat beinhaltet, ist die Standard-LP nicht mehr anwendbar und ein Solver für nicht-lineare oder quadratische Programmierung wird benötigt.
Warum liegt die optimale Lösung immer an einer Ecke des zulässigen Bereichs?
Der durch lineare Nebenbedingungen definierte zulässige Bereich ist ein konvexes Polyeder (oder Polytop). Eine lineare Zielfunktion ist selbst linear, daher kann sie nicht zum Inneren einer konvexen Menge „gezogen“ werden — sie erreicht ihren Extremwert immer an der Grenze, und zwar speziell an einem Eckpunkt. Dies ist die geometrische Einsicht, die der Strategie des Simplex-Algorithmus von Ecke zu Ecke zugrunde liegt.
Wann sollte ich stattdessen Ganzzahlige Programmierung anstelle von LP verwenden?
Immer dann, wenn eine oder mehrere Entscheidungsvariablen ganzzahlige oder binäre (0/1) Werte annehmen müssen — zum Beispiel, ob eine Anlage geöffnet werden soll (ja/nein), wie viele Lkw eingesetzt werden sollen (ganze Zahlen) oder welche Artikel in eine Auswahl aufgenommen werden sollen. Das einfache Lösen der LP und das Runden der kontinuierlichen Lösung ist nicht zuverlässig: gerundete Lösungen können unzulässig oder weit vom Optimum entfernt sein. Die Ganzzahlige Programmierung behandelt Ganzzahligkeit korrekt, allerdings mit höheren Rechenkosten.
Was sagen mir Schattenpreise?
Ein Schattenpreis (duale Variable) für eine bindende Nebenbedingung gibt an, um wie viel sich der optimale Zielfunktionswert verbessern würde, wenn die rechte Seite dieser Nebenbedingung um eine Einheit gelockert würde, während alles andere konstant bleibt. Zum Beispiel bedeutet ein Schattenpreis von 3 für eine Arbeitsstunden-Nebenbedingung, dass die Hinzufügung einer zusätzlichen Arbeitsstunde das Ziel um 3 Einheiten verbessern würde. Nicht bindende Nebenbedingungen haben einen Schattenpreis von Null — sie schränken das aktuelle Optimum nicht ein.
Verwandte Methoden
Quellen
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Kopiert.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
DOI-Referenz öffnenKopiert.