Informatik
DE | ENContact

Optimierungsmodell

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.

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:

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

    Block Model

    Block Modell des Steinbruchs

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

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

    Steinbruchdaten

  3. Das Ziel ist die Maximierung des Profits:

    g = c1x1 + c2x2 + ...

    indem man

    x1 Tonnen vom Block B1,
    x2 Tonnen vom Block B2,
    ...

    abbaut und dabei die untenstehenden Randbedingungen erfüllt.
  4. 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:

    (r1  -  Rmin) x1 + (r2  -  Rmin) x2 + ...   ≥   0
    (r1  -  Rmax) x1 + (r2  -  Rmax) x2 + ...   ≤   0

    Entsprechende Ungleichungen werden für die anderen Chemikalien aufgestellt.
  5. Die genommenen Tonnagen müssen selbstverständlich die folgenden Bedingungen erfüllen:

    x1   ≥   0
    x2   ≥   0
    ...
    x1   ≤   B1
    x2   ≤   B2
    ...

  6. Die Firma hat nur eine beschränkte Produktionskapazität Tmax:

    x1  +  x2 + ...   ≤   Tmax

Zweidimensionaler Fall

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

g = 6x1 + 2x2 = max !

maximal wird und die Randbedingungen

-5x1 + 15x2   ≥   0
-10x1 + 10x2   ≤   0
x1   ≥   0
x2   ≥   0
x1   ≤   20
x2   ≤   10
x1  +  x2   ≤   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 (x1, x2)-Ebene lösen.
Graphische Lösung

Graphische Lösung (Bilderzeugung)

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

6x1 + 2x2 = 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

x1 = 18.75
x2 = 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.