Nichtlineare Produktionsprogrammplanung - Grundlagen der nichtlinearen Programmierung

Inhaltsverzeichnis

Abkürzungsverzeichnis

Symbolverzeichnis

Abbildungsverzeichnis

1. Einleitung

2. Grundlagen der nichtlinearen Programmierung
2.1 Das Grundmodell
2.2 Durch Nichtlinearität bedingte Schwierigkeiten
2.3 Konvexität
2.4 Quadratische Programmierung

3. Nichtlineare Produktionsprogrammplanung und das Kuhn-Tucker-Theorem
3.1 Nichtlineares Modell mit linearen PAF
3.2 Allgem. Herleitung der Kuhn-Tucker-Bedingungen
3.3 Das Kuhn-Tucker-Theorem
3.4 Interpretation der Kuhn-Tucker-Bedingungen

4. Erläuterungen anhand eines Zahlenbeispiels
4.1 Ermitteln des Optimums eines nichtlinearen Produktionsprogramms
4.2 Interpretation der Ergebnisse

5. Lösungsalgorithmus von Wolfe

6. Fazit

Anlagen
Anlage 1: Graphische Darstellungen
Anlage 2: Überprüfung der Zielfunktion auf Konvexität (am Beispiel)
Anlage 3: Optimierung mit dem EXCEL-Solver
Anlage 4: Lösungsalgorithmus von Wolfe (am Beispiel)

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Symbolverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abb. 1: Mögliche Optima

Abb. 2: Graphische Darstellung einer Lösung bei nichtlinearer Zielfunktion

Abb. 3: Graphische Darstellung einer Lösung bei nichtlinearer Nebenbedingung

Abb. 4: Beispiele für nichtkonvexe und konvexe Mengen

Abb. 5: Beispiele für nichtkonvexe und konvexe Funktionen

1. Einleitung

Häufig wird in Lehrbüchern das Entscheidungsproblem der Produktionsprogrammplanung als ein Modell der linearen Optimierung präsentiert, d.h. es wird versucht, unter Berücksichtigung von Kapazitätsrestriktionen, die Summe aller Deckungsbeiträge zu maximieren, wobei unterstellt wird, dass die Preise eines Produktes unabhängig von der hergestellten Menge sind. In der Realität tritt es jedoch häufiger auf, dass diese Linearitätsannahme nicht zutrifft. Vielmehr muss sich mit nichtlinearen Produktionsprogrammen auseinandergesetzt werden.

Stellt der erzielbare Preis eine monoton abnehmende Funktion der Absatzmenge dar, wie es im Falle eines Monopolisten oder auch Oligopolisten gegeben ist, so trifft die Linearitätsannahme nicht mehr zu, sondern es entstehen nichtlineare (quadratische) Zielfunktionen.^[1]

Bisher existiert allerdings kein Algorithmus mit dem sich jedes spezifische nichtlineare Problem lösen lässt wie dies in der linearen Programmierung, z.B. für den Simplex Algorithmus, der Fall ist. Für einige wichtige Spezialfälle existieren jedoch funktionsfähige Algorithmen, z.B. für konvexe, quadratische Optimierungsmodelle.^[2]

Als erstes werden im folgenden Kapitel die Grundlagen der nichtlinearen Programmierung vorgestellt um so die Basis für die nichtlineare Produktionsprogrammplanung zu schaffen. Das dritte Kapitel wird sich mit der nichtlinearen Produktionsprogrammplanung und dem Kuhn-Tucker-Theorem beschäftigen, während im vierten Kapitel die Theorie anhand eines Beispiels angewandt wird. Der Algorithmus von Wolfe, ein Algorithmus zur Lösung nichtlinearer konvexer Optimierungsprobleme, wird im fünften Kapitel vorgestellt.

2. Grundlagen der nichtlinearen Programmierung

2.1 Das Grundmodell

Ein allgemeines nichtlineares Optimierungsmodell lässt sich folgendermaßen aufstellen:

Maximiere Abbildung in dieser Leseprobe nicht enthalten

u. d. N.: Abbildung in dieser Leseprobe nicht enthalten für i = 1, …, I

Abbildung in dieser Leseprobe nicht enthalten für j = 1, …, J.

Wobei nichtlineare Optimierungsprobleme im Gegensatz zu linearen Problemen eine nichtlineare Zielfunktion und/oder mindestens eine nichtlineare Nebenbedingung besitzen.^[3]

2.2 Durch Nichtlinearität bedingte Schwierigkeiten

Im Falle der Linearität geht man davon aus, dass sowohl die Zielfunktion als auch die Nebenbedingungen linear sind. Für diesen Fall bildet die Menge der zulässigen Lösungen eine konvexe Menge, i.d.R. einen konvexen Polyeder und die optimale Lösung befindet sich in einem Eckpunkt der Menge der zulässigen Lösungen. Liegt jedoch ein Optimierungsproblem mit nichtlinearer Zielfunktion vor, so ist es möglich, dass sich die optimale Lösung nicht etwa in einem Eckpunkt befindet, sondern sich innerhalb des zulässigen Lösungsraums befindet (siehe Abb. 2).

Ein weiterer Vorteil der Linearität besteht darin, dass ein lokales Optimum gleichzeitig auch ein globales Optimum darstellt. Auch diese Eigenschaft ist im Falle der Nichtlinearität nicht mehr zwingend gegeben, so dass der Simplex-Algorithmus für die nichtlineare Produktionsprogrammplanung nicht ohne weiteres heran gezogen werden kann.

Für den Fall, dass die Nebenbedingungen nichtlinear sind bildet die Menge der zulässigen Lösungen keinen konvexen Polyeder mehr (siehe Abb. 3). Daher kann sogar bei linearer Zielfunktion das lokale Optimum ungleich dem Globalen sein.^[4]

Um zu garantieren, dass es sich bei dem aufgefundenen Optimum um ein globales und nicht nur ein lokales Optimum handelt, liegt es nahe nichtlineare Probleme auf Modelle mit konvexem Lösungsraum und, je nach Zielsetzung, konvexer oder konkaver Zielfunktion (konvexe Optimierungsmodelle) einzugrenzen.^[5] In diesem Fall ist stets gewährleistet, dass ein lokales Optimum gleichzeitig auch ein Globales ist.

2.3 Konvexität

Eine Menge wird als konvex bezeichnet, wenn für je zwei Punkte aus dieser Menge auch die Verbindungsstrecken zwischen diesen beiden Punkten vollständig in der Menge liegen (siehe Abb. 4). Von einer konvexen Funktion hingegen spricht man, wenn die Punktmenge oberhalb des Graphen der Funktion konvex ist. D.h. die Punkte der Verbindungsstrecke zweier Kurvenpunkte liegen stets oberhalb oder auf der Kurve (siehe Abb. 5).^[6] Zur Überprüfung einer Funktion auf Konvexität müssen zunächst die zweiten partiellen Ableitungen gebildet werden. Für eine Funktion mit zwei Variablen müssen folgende Bedingungen erfüllt sein:

Abbildung in dieser Leseprobe nicht enthalten

Für den Fall, dass die Funktion konkav ist, kann das [Abbildung in dieser Leseprobe nicht enthalten]-Zeichen in den Bedingungen (2) und (3) durch ein [Abbildung in dieser Leseprobe nicht enthalten]-Zeichen ersetzt werden.^[7]

[...]

^[1] Vgl. Domschke WISU, S. 1649.

^[2] Vgl. Hillier/ Liebermann (2002), S.415 f.

^[3] Vgl. Domschke/ Drexl (1998), S.164 f.

^[4] Vgl. Luptácik (1981), S. 6 ff.

^[5] Konvexe Optimierungsmodelle werden in Punkt 2.3 näher erläutert.

^[6] Vgl. Ellinger/ Baumann/ Leisten (2003), S.195 f.

^[7] Vgl. Hillier/ Liebermann (2002), S. 813 f.