Lineare Optimierung

Viele quantitative Entscheidungsaufgaben in der Ökonomie und Industrie lassen sich auf Optimierungsprobleme zurückführen. In der Praxis wird vor allem die lineare Optimierung eingesetzt, bei der die Zielfunktion und die Nebenbedingungen linear von den Entscheidungsvariablen abhängen. Ich werde die lineare Optimierung (auch lineare Programmierung genannt) an einem Beispiel aus der Bergbauindustrie illustrieren.

Optimierungsmodell

Eine Bergbaugesellschaft baut Rohstoffe durch Abgraben im Tagebau ab (zum Beispiel im Steinbruch), mischt sie zur Erreichung der erforderlichen Qualität und verkauft das Gemisch auf dem Markt. Die Firma will natürlich den maximalen Profit erreichen unter Berücksichtigung der Lagerstätte, der Gemischqualität, der Produktionskosten und Kapazitäten. Das Problem wird mathematisch folgendermassen modelliert:

Diskretisierung

Die Lagerstätte wird in mehr oder weniger homogene Blöcke unterteilt:

Daten

Die Konzentration der Mineralien, das Gewicht, die Produktionskosten und andere Eigenschaften der Blöcke werden gemessen oder geschätzt:

Block	Ton­nage	Profit c/ton	R %	S %
B1	20	6	15	..
B2	10	2	35	..
B3	..	..	..	..

Steinbruchdaten

Maximierungsfunktion

Das Ziel ist die Maximierung des Profits:

g = c₁x₁ + c₂x₂ + ...

indem man

x₁ Tonnen vom Block B₁,
x₂ Tonnen vom Block B₂,
...

abbaut und dabei die untenstehenden Randbedingungen erfüllt.

Anforderungen an die Mischung

Die Konzentration der chemischen Stoffe in der Mischung muss zwischen vorgegebenen Grenzwerten liegen:

Chemikalie	Min %	Max %
R	20	25
S	..	..
..	..	..

Chemische Anforderungen an das Gemisch

Für die Chemikalie R bedeutet das:

Rmin   ≤	r1x1 + r2x2 + ...	≤   Rmax
	x1 + x2 + ...

Dies wird als zwei Ungleichungen umformuliert:

(r₁  -  R_min) x₁ + (r₂  -  R_min) x₂ + ...   ≥   0
(r₁  -  R_max) x₁ + (r₂  -  R_max) x₂ + ...   ≤   0

Entsprechende Ungleichungen werden für die anderen Chemikalien aufgestellt.

Natürliche Bedingungen an die Tonnage

Die genommenen Tonnagen müssen selbstverständlich die folgenden Bedingungen erfüllen:

x₁   ≥   0
x₂   ≥   0
...
x₁   ≤   B₁
x₂   ≤   B₂
...

Beschränkte Produktionskapazität

Die Firma hat nur eine beschränkte Produktionskapazität T_max:

x₁  +  x₂ + ...   ≤   T_max

Zweidimensionaler Fall

Wir werden nun das vereinfachte Problem mit nur 2 Blöcken lösen. Wir nehmen an, dass die maximale Produktionskapazität T_max 25 Tonnen beträgt. Die Aufgabe heisst jetzt: finde die Variablen x₁, x₂, sodass der Gewinn

g = 6x₁ + 2x₂ = max !

maximal wird und die Randbedingungen

-5x₁ + 15x₂   ≥   0
-10x₁ + 10x₂   ≤   0
x₁   ≥   0
x₂   ≥   0
x₁   ≤   20
x₂   ≤   10
x₁  +  x₂   ≤   25

erfüllt werden. Dies ist ein lineares Optimierungsproblem, da sowohl die zu optimierende Zielfunktion als auch alle Randbedingungen lineare Funktionen der Variablen x sind. Das Gebiet der linearen Optimierung heisst aus historischen Gründen auch lineare Programmierung.

Graphische Lösung

Im Fall von 2 Variablen lässt sich das Problem graphisch in der (x₁, x₂)-Ebene lösen. Die Ungleichungen entsprechen Halbebenen, die durch die korrespondierende Gleichung begrenzt sind. Die Schnittmenge der Halbebenen ist ein konvexes Polygon genannt "das zulässige Gebiet". Die Punkte des zulässigen Gebiets erfüllen alle Randbedingungen. Die Zielfunktion entspricht einer Familie von parallelen Geraden

6x₁ + 2x₂ = m

die durch den Wert von m parametrisiert werden. Wenn eine solche Gerade parallel nach rechts verschoben wird, so wird der Zielwert m erhöht und er erreicht das Maximum 125 an der äussersten rechten Ecke des zulässigen Gebiets. Somit ist die optimale Lösung

x₁ = 18.75
x₂ = 6.25
Profit = 125

Die graphische Lösungsmethode bietet einen ausgezeichneten Einblick in die Struktur linearer Optimierungsprobleme. Auch wenn wir sie nicht in höheren Dimensionen nicht anwenden können, so können wir uns doch vorstellen, wie sie funktionieren würde. Die Randbedingungen entsprechen Halbräumen, die durch Hyperebenen begrenzt sind. Die Schnittmenge der Halbräume ist das zulässige Gebiet. Es ist ein konvexes Polyeder. Die Zielfunktion ist eine Hyperebene, die zu dem Vertex des Polyeders bewegt werden muss, wo ihr Wert am grössten ist.

Lösung mit Microsoft Excel

Microsoft Excel bietet die Zusatzkomponente "Solver" zur numerischen Lösung von Optimierungsproblemen an. Die Verwendung von Excel Solver zur Lösung unseres zweidimensionalen Beispiel ist einfach. Der Einsatz von Solver zur Lösung von praktischen Problemen mit sehr vielen Variablen wird leider unhandlich und fehleranfällig.

Simplex Algorithmus

Die Methode der Wahl zur Lösung von praktischen Problemen mit sehr vielen Variablen ist der Simplex Algorithmus (PDF). Dieser Algorithmus wurde bereits im Jahr 1947 von G. B. Dantzig entwickelt. Meine Implementierung des Simplex Algorithmus in C++ kann Tausende von Variablen und Randbedingungen behandeln, ist numerisch stabil und berechnet die Lösung sehr effizient.