Wikipedia · einfach zusammengefasst · Stand
Lineare Optimierung
Wie in dem obigen Beispiel kann ein Unternehmen eine Reihe von Produkten mit bekanntem Deckungsbeitrag herstellen. Die Herstellung einer Einheit jedes …
Inhalt5 Abschnitte
Grundidee und mathematische Form
Die lineare Optimierung (auch lineare Programmierung) ist ein Hauptverfahren des Operations Research. Sie sucht den größten oder kleinsten Wert einer linearen Zielfunktion, während lineare Gleichungen und Ungleichungen eingehalten werden müssen. Sie ist ein Spezialfall der konvexen Optimierung und wird unter anderem in der Produktionsplanung sowie bei Verkehrs- und Telekommunikationsnetzen eingesetzt. „Programmierung“ bedeutet hier Planung, nicht das Schreiben eines Computerprogramms.
In der Standard- oder Ungleichungsform sind eine Matrix A ∈ R^{m,n}, ein Vektor b ∈ R^{m,1} und ein Zielfunktionsvektor c ∈ R^{1,n} gegeben. Gesucht wird ein Vektor x ∈ R^n mit nichtnegativen Einträgen, der alle Nebenbedingungen erfüllt und den Zielfunktionswert maximiert:
max {cx | Ax ≤ b, x ≥ 0}.
Dabei ist cx = c₁x₁ + … + cₙxₙ; die Ungleichungen gelten komponentenweise. Eine zulässige Lösung erfüllt sämtliche Nebenbedingungen. Ein Maximum kann auch als Minimum formuliert werden, indem c mit −1 multipliziert wird. Bedingungen der Form ≥ lassen sich durch Multiplikation mit −1 umformen. Eine Gleichung aᵢx = bᵢ entspricht den zwei Ungleichungen aᵢx ≤ bᵢ und −aᵢx ≤ −bᵢ. Eine Variable ohne Vorzeichenbeschränkung wird durch x' − x'' mit x', x'' ≥ 0 ersetzt.
Lineare Optimierung erlaubt reellwertige Variablen. Ganzzahlige oder gemischt-ganzzahlige lineare Programme, bei denen einige Variablen nur ganze Werte haben dürfen, sind eine Verallgemeinerung und im Allgemeinen NP-äquivalent, also vermutlich nicht effizient lösbar.
Geometrische Bedeutung und Produktionsbeispiel
Jede Nebenbedingung aᵢx ≤ bᵢ begrenzt geometrisch einen Halbraum: Die Gleichung aᵢx = bᵢ beschreibt eine Hyperebene, und zulässig ist eine ihrer Seiten einschließlich der Hyperebene. Der Schnitt aller Halbräume und der Bedingung x ≥ 0 ist die zulässige Menge P = {x | Ax ≤ b, x ≥ 0}. Sie bildet ein konvexes Polyeder. Konvex bedeutet: Die Verbindungslinie zwischen zwei Punkten von P liegt vollständig in P.
Die Zielfunktion cᵀx wird maximiert, indem man die Hyperebene cᵀx = 0 in Richtung des Vektors c verschiebt, bis sie das Polyeder gerade noch berührt. Alle Berührungspunkte sind Optimallösungen. Im zweidimensionalen Fall sind Hyperebenen Geraden und das Polyeder ein Vieleck.
Im Produktionsbeispiel werden zwei Produkte auf den Maschinen A, B und C gefertigt. Die monatlichen Kapazitäten betragen 170 Stunden für A, 150 Stunden für B und 180 Stunden für C. Produkt 1 bringt pro Mengeneinheit (ME) 300 Euro Deckungsbeitrag und benötigt je eine Stunde auf A und B. Produkt 2 bringt 500 Euro und benötigt zwei Stunden auf A, eine Stunde auf B und drei Stunden auf C. Für Produktionsmengen x₁ und x₂ lautet die Zielfunktion G(x₁,x₂) = 300x₁ + 500x₂.
Die Nebenbedingungen sind x₁ + 2x₂ ≤ 170, x₁ + x₂ ≤ 150, 3x₂ ≤ 180 sowie x₁, x₂ ≥ 0. Fixkosten können zunächst ignoriert und später addiert werden, weil sie unabhängig von den Produktionsmengen sind. Die eindeutige optimale Ecke ist (130,20); der optimale Zielfunktionswert beträgt 49.000 Euro. Optimallösungen müssen jedoch nicht eindeutig oder ganzzahlig sein: Bei gleichem Deckungsbeitrag beider Produkte wäre jeder Punkt der Strecke zwischen (130,20) und (150,0) optimal.
Anwendungen, Lösbarkeit und Methoden
In der Produktionsplanung bestimmt lineare Optimierung ein Produktionsprogramm: Es legt fest, wie viel von jedem Produkt hergestellt wird, um den Gewinn bei begrenzten Ressourcen wie Kapazität, Rohmaterial oder Arbeitszeit zu maximieren. Zu den Anwendungen gehören auch Zuschnittsprobleme.
Bei Mischungsproblemen werden Zutaten so kombiniert, dass Kosten minimal bleiben und Mindest- oder Höchstgrenzen eingehalten werden. Beim von George Dantzig 1947 untersuchten Diät-Problem sind etwa Rohmaterialien, Nährwertgehalte und Preise pro Kilogramm gegeben; gesucht ist eine möglichst günstige Mischung mit vorgegebenen Nährwertgrenzen. Ähnliche Probleme entstehen etwa bei Schmelzvorgängen in der Stahlherstellung. In Verkehrs- oder Telekommunikationsnetzen werden Verkehrsflüsse so geroutet, dass Anforderungen erfüllt und Kapazitäten nicht überschritten werden. Diese Mehrgüterflüsse (multicommodity flow) sind mit LP gut lösbar. In Zwei-Personen-Nullsummenspielen können optimale Wahrscheinlichkeitsverteilungen über Strategien berechnet werden.
Ein LP kann unzulässig sein, wenn sich Bedingungen widersprechen, etwa x ≤ 1 und x ≥ 2. Es kann unbeschränkt sein, wenn zulässige Lösungen beliebig hohe Zielfunktionswerte erreichen, etwa bei max {x | x ≥ 0}. Oder es besitzt mindestens eine Optimallösung; dies gilt beispielsweise bei einem nichtleeren, beschränkten Polyeder, also einem Polytop. Die Menge der Optimallösungen ist eine Seitenfläche des Polyeders. Es gibt daher keine, genau eine oder unendlich viele Optimallösungen. Ist ein LP lösbar und beschränkt, gibt es immer mindestens eine optimale Ecke.
Innere-Punkte-Verfahren und die Ellipsoidmethode finden eine Optimallösung oder erkennen Unzulässigkeit in Polynomialzeit. Ob ein streng polynomialer Algorithmus für allgemeine LPs existiert, ist unbekannt. Praktisch ist das Simplex-Verfahren oft schneller, obwohl seine schlechteste Laufzeit exponentiell ist. Es geht von Ecke zu benachbarter Ecke mit besserem Zielfunktionswert; wegen der Konvexität ist eine lokal optimale Ecke auch global optimal. Bei entarteten LPs kann eine Ecke durch mehr Ungleichungen als nötig definiert sein; dann können Wiederholungen auftreten. Implementierungen behandeln dies etwa durch eine spätere rückgängig gemachte leichte Perturbation.
Innere-Punkte- oder Barrier-Verfahren nähern sich der Lösung durch das Innere des Polyeders und sind für große dünnbesetzte Probleme häufig überlegen. Sie lassen sich aber schlechter warmstarten, wenn sich Bedingungen oder Variablen ändern. Das Simplex-Verfahren kann dann von einer früheren Ecke starten und ist deshalb bei Branch-and-Cut und Schnittebenenverfahren wichtig. Die Ellipsoidmethode prüft nacheinander kleinere Ellipsoide, die das Polyeder enthalten müssen; sie ist theoretisch polynomial, aber für praktische Zwecke nicht geeignet.
Duales Problem und Schranken
Zu einem primalen Maximierungsproblem max {cᵀx : Ax ≤ b, x ≥ 0} gehört das duale Minimierungsproblem
min {yᵀb : yᵀA ≥ cᵀ, y ≥ 0}.
Die Einträge von y heißen Multiplikatoren oder Dualvariablen. Sie liefern obere Schranken für den Wert des primalen Problems. Für jede zulässige primale Lösung x und jede zulässige duale Lösung y gilt der schwache Dualitätssatz:
cᵀx ≤ yᵀAx ≤ yᵀb.
Im Produktionsbeispiel folgt aus x₁ + x₂ ≤ 150 zunächst G(x₁,x₂) ≤ 75.000. Eine bessere Schranke entsteht durch 300-mal die zweite und 100-mal die dritte Ungleichung: G(x₁,x₂) ≤ 63.000. Das duale Problem sucht die beste solche obere Schranke.
Bei der Dualisierung entsprechen nichtnegative Variablen Ungleichungen und nicht vorzeichenbeschränkte Variablen Gleichungen. Umgekehrt entsprechen Ungleichungen nichtnegativen Variablen und Gleichungen nicht vorzeichenbeschränkten Variablen. Für Maximierungsprobleme werden Nebenbedingungen in der Form Ax ≤ b, für Minimierungsprobleme in der Form Ax ≥ b geschrieben. Das Dual des dualen LPs ist wieder das primale LP.
Starke Dualität und komplementärer Schlupf
Der starke Dualitätssatz besagt: Besitzt eines der beiden LPs eine beschränkte Optimallösung, dann besitzt auch das andere eine solche, und ihre optimalen Zielfunktionswerte sind gleich. Für optimale Lösungen x* und y* gilt daher cᵀx* = (y*)ᵀb. Hat das primale Problem keine zulässige Lösung, ist das duale unbeschränkt oder ebenfalls unzulässig. Ist das primale Problem unbeschränkt, hat das duale keine zulässige Lösung. Diese Zusammenhänge sind Grundlage für Verfahren mit primalen und dualen Schranken, etwa Branch-and-Cut und Schnittebenenverfahren.
Der Satz vom komplementären Schlupf präzisiert die Beziehung. Haben primales und duales Problem zulässige Lösungen, existiert ein Paar x*, y* mit
yᵢ* · (bᵢ − (Ax*)ᵢ) = 0 für alle i = 1,…,m.
Ist also yᵢ* > 0, dann ist die zugehörige primale Nebenbedingung bindend: (Ax*)ᵢ = bᵢ. Hat eine Nebenbedingung dagegen Schlupf, also (Ax*)ᵢ < bᵢ, dann gilt yᵢ* = 0. Solche Paare sind optimal, weil cᵀx* = (y*)ᵀAx* = (y*)ᵀb. Primal-duale Algorithmen nutzen dies zur Überprüfung der Optimalität.
Optimierungs- und Zulässigkeitsprobleme von Polyedern sind bezüglich ihrer Zeitkomplexität äquivalent. Statt direkt zu maximieren, kann man ein zulässiges Paar x, y suchen, das Ax ≤ b, x ≥ 0, yᵀA ≥ cᵀ, y ≥ 0 und cᵀx ≥ yᵀb erfüllt. Die ersten Bedingungen machen x primal und y dual zulässig; zusammen mit dem schwachen Dualitätssatz erzwingt die letzte Bedingung gleiche Zielfunktionswerte und damit Optimalität.