Operations Research
Wer vom Ziel nicht weiß, kann den Weg nicht haben.Christian Morgenstern
Prof. Dr. Martin Moog
Lehrstuhl für Forstliche Wirtschaftslehre
Gliederung
(1) Allgemeine Einführung– Literatur
– Modellbildung
(2) Logistische Prozesse– Reihenfolgeprobleme
• Rundreise
– Optimierung der Kapazitätsauslastung
– Optimierung der Maschinenbelegung
– Optimierung des Werkzeugwechsels
– Sonderfall: Ganzzahlige Optimierung
• Rundreise
• Postkutsche
– Zuordnungsprobleme• Transportproblem
• Chinese-Postman Problem
(3) Produktionsplanung und -steuerung
– Optimierung von Losgrößen
– Optimierung von Mischungen
– Sonderfall: Ganzzahlige Optimierung
(4) Standortentscheidung und Warteschlangenmodell
Prof. Dr. Martin Moog, Technische Universität München 2
(1) Allgemeine Einführung
• Literatur
• Modellbildung
Prof. Dr. Martin Moog, Technische Universität München 3
Übersetzungen von OR ins Deutsche
• Unternehmensforschung
• Operationsforschung
• Optimierungsrechnung
• Planungsforschung
• Planungsrechnung• Planungsrechnung
• Optimalplanung
• mathematische Entscheidungsvorbereitung
Prof. Dr. Martin Moog, Technische Universität München 4
haben sich nicht durchgesetzt
OR-Lehrbücher
• Domschke und Drexl (2007): Einführung in Operations Research, Springer-Lehrbuch
• Zimmermann, Werner (1992) Operations Research – Quantitative Methoden zur Entscheidungsvorbereitung, 6. Auflage, Oldenbourg
• Heinrich, Gert: Operations Research, Oldenbourg, 2007
• Werners, Brigitte (2006) Grundlagen des Operations Research. Springer
• Zimmermann, Hans-Jürgen (2008): Operations-Research. 2. Auflage, Vieweg
• Gohout, Wolfgang (2009): Operations Research. 4. Auflage, Oldenbourg
• Hillier, Frederick S. und Lieberman, Gerald J.: Operations Research, 4. Auflage, 1988, Oldenbourg(übersetzt)
• Henn, R. und Künzi, H. P.: Einführung in die Unternehmensforschung Band I und II, Springer Verlag, 1968
• Müller-Merbach, H.: Operations-Research, 2. Auflage, Vahlen, 1971 (es gibt viele neuere Auflagen)
• Gritzmann, Peter und Brandenberg, René: Das Geheimnis des kürzesten Weges, 3. Auflage, Springer Verlag, 2005
Prof. Dr. Martin Moog, Technische Universität München 5
eine kleine Auswahl
Gliederungsschemata in OR Lehrbüchern (1/2)
• Netzplantechnik• Lineare Optimierung• Transport und
Zuordnungsoptimierung• Ganzzahlige Optimierung• Kombinatorische Optimierung• Dynamische Optimierung
• Lineare Optimierung• Graphentheorie• Lineare Optimierungsprobleme mit
spezieller Struktur• Netzplantechnik• Ganzzahlige und kombinatorische
Optimierung• Dynamische Optimierung
Zimmermann, W., 1992 Domschke und Drexl 1991, 2007
• Dynamische Optimierung• Nichtlineare Optimierung• Wahrscheinlichkeitstheoretische
Grundlagen• Entscheidungstheoretische
Grundlagen• Theorie der Spiele• Simulationstechnik• Warteschlangensysteme• Optimale Lagerhaltung
• Dynamische Optimierung• Nichtlineare Optimierung• Warteschlangentheorie• Simulation
Prof. Dr. Martin Moog, Technische Universität München 6
Gliederungsschemata in OR Lehrbüchern (2/2)
• Lineare Optimierung• Spieltheorie• Transportprobleme• Ganzzahlige Optimierung• Binäre Optimierung• Graphentheorie• Netzplantechnik• Simulation
• Grundlagen linearer Optimierung• Modellerweiterungen, Dualität,
Sensitivitätsanalyse• Anwendungen linearer Optimierung• Graphentheorie• Projektplanung• Simulation und
Warteschlangensystem
Heinrich 2007 Werners 2006
• Simulation • Simulation und Warteschlangensystem
• Lösungen der Aufgaben
Prof. Dr. Martin Moog, Technische Universität München 7
Wissenschaftliche Gesellschaften und Zeitschriften
• Deutsche Gesellschaft für Operations Research DGOR• Gesellschaft für Mathematik, Ökonomie und Operations Research GMÖOR• International Federation of OR-Societies IFORS• Operations Research Society of America ORSA
Prof. Dr. Martin Moog, Technische Universität München 8
• Annals of OR• European Journal of OR• Journal of the Operational Research Society• Management Science• Mathematical Programming• Operations Research• OR Spektrum• Zeitschrift für OR
OR in forstlichen Lehrbüchern
• Kangas, Kangas, Kurttila: Decision Support for Forest Management, Springer 2008
• Bettinger, Boston, Siry, Grebner: Forest Management and Planning, Elsevier Academic Press, 2009
Prof. Dr. Martin Moog, Technische Universität München 9
nur eine Auswahl
Literatur zu OR-Anwendungen in der Forstwirtschaft
HÖFLE und SCHÖPFER (1970 und 1971) haben eine Bibliographie der Anwendung der Methoden des Operations Research in der Forst- und Holzwirtschaft zusammengestellt (Mitteilungen der Baden-Württembergischen Forstlichen Versuchs- und Forschungsanstalt, Heft 25, Freiburg/Br.). In dieser Bibliographie sind rund 500 Titel erfaßt, von denen aber viele im angelsächsischen Sprachraum erschienen sind.
Prof. Dr. Martin Moog, Technische Universität München 10
Ein Beispiel für eine Darstellung von LP-Modellen für landw. Fragestellungen
Mußhoff, Oliver u. Hirschauer, Norbert: Modernes Agrar-Management. Vahlen 2010
Ein Beispiel für eine Arbeit mit forstlichen Fragestellungen:
Rose, Dietmar: Quantitative Modelle in der strategischen Planung am Beispielder Forstwirtschaft, Hochschulverlag, Freiburg, 1992
OR-Modellbildung
OR im weiteren Sinne
Modellbildung und Lösungsfindung
Prof. Dr. Martin Moog, Technische Universität München 11
Entwicklung vonAlgorithmen
OR im engeren Sinne
Erste OR-Anwendungen
Zusammenstellung vonSchiffskonvois im WKII
Optimierung derRadarerfassung derFlugbewegungen an derenglischen Küste
Der Krieg ist Vater aller Dinge.
Prof. Dr. Martin Moog, Technische Universität München 12
kommerzielle Anwendungen nach dem 2. Weltkrieg
unzählige Rechenknechte
Computereinsatz notwendig
Museum in Hünfeld (Rhön)
Prof. Dr. Martin Moog, Technische Universität München 13
Konrad Zuse
Logo der Konrad Zuse Gesellschaft
Z1 – 1938, ein mechanischer RechnerZ2 – 1938 der erste Versuch mit ElektronikZ3 – 1941 der erste funktionsfähige RechnerZ4 – noch in Berlin gebaut, im Allgäu
wiederaufgebaut, an die ETH vermietet.Plankalkül – die erste Programmiersprache (1945)
Konrad Zuse war auch künstlerisch begabt.Bill Gates ließ sich von ihm porträtieren.
Exkurs: Museen
Hünfeld
Paderborn – Heinz Nixdorf Museums Forum
München – Deutsches Museum
Prof. Dr. Martin Moog, Technische Universität München 14
Realität(objektiv)
PerceptionBewusstsein
Anspruchsniveaus(subjektiv)
Problem(im Bewusstsein eines
Menschen)
Anpassung der An-Sprüche, Änderung
des Realitätsaus-schnitts Rechenmodell
Mathematisches Real-Modell
Verbales Modell
Formale
Sprache,Abstraktion
Algorithmus
natürliche
Sprache
Entschluss
Nicht-quantifizierterelevante Probleme
Tatbestände
Lösung des Problems
akzeptabel?
Lösung des Real-Modelles
Lösung des Rechenmodelles
Interpretation
Algorithmus
Interpretation
Zusammenhänge zwischen Problemen, Modellen und Algorithmen (Zimmermann, 1992, S. 1)
ja
Prof. Dr. Martin Moog, Technische Universität München 15
Improvisation Planung
Prof. Dr. Martin Moog, Technische Universität München 16
Improvisation Planung
Grundsätzliche Vorgehensweise des OR
reales Problem
mathematisches Modell
Abstraktion
Prof. Dr. Martin Moog, Technische Universität München 17
Modell-Lösung
Lösungsvorschlagfür das reale Problem
Rechnung
Interpretation
nach Zimmermann, W., 1992, S. 3
Die gewählte Lösung mußnicht die Modell-Lösung sein.
Berücksichtigung weitererUmstände ist sinnvoll.
Modelltypen
Modelle
Erklärungs- Entscheidungs-Beschreibungs-
modelle
Erklärungs-modelle
oderPrognosemodelle
Entscheidungs-oder
Optimierungs-modelle
Prof. Dr. Martin Moog, Technische Universität München 18
Restriktionenin Optimierungs-modellen
Schwerpunkt des OR
Optimierungsmodelle
Optimierungsmodell = Zielfunktion + Nebenbedingungen
maximiere den Deckungsbeitrag
Prof. Dr. Martin Moog, Technische Universität München 19
minimiere die Kosten beachte die zur Verfügung stehendenProduktionskapazitäten
bei vorgegebenen Produktionsmengen
Modelle zur Maximierung oder Minimierung
Charakterisierung von Optimierungsmodellen
Informationsgraddeterministische Modelle
stochastische Modelle
Typ der Zielfunktion
und der
Nebenbedingungen
lineare, nichtlineare, ganzzahlige
eine oder mehrere Zielfunktionen
Zielfunktion(en)
eine oder mehrere Zielfunktionen
bei letzteren nur „Optimierung“, wenn
Effizienzkriterien angegeben werden können
(Beurteilungsmaßstäbe für den Grad der Erreichung
der Ziele)
Prof. Dr. Martin Moog, Technische Universität München 20
Ein Unternehmen besitzt an mehreren Orten Fabrikhallen.
Es stellt sich die Frage, wie die Abteilungen auf diese Orte verteilt werden sollen.
Die Abteilungen müssen untereinander Güter austauschen. Dadurch entstehenTransportkosten.
Je mehr Güter getauscht werden müssen und je größer die Distanzen sind,desto höher sind die Transportkosten.
Nug30 – gelöst im Jahr 2000
desto höher sind die Transportkosten.
C.E. Nugent, Th.E. Vollmann und J. Ruml haben 1968 einen Satz von Beispielenformuliert für 5, 6, 7, 8, 12, 15, 20 und 30 Standorte (Nug5 bis Nug30).
An diesen Beispielen werden Optimierungsprogramme getestet.
Nug12 wurde erstmals 1978 gelöst, Nug15 1979
Nug30 hat 2,65 x 1032 Lösungen. Es wurde mit einem Algorithmus gelöst,der die Lösungen aussondert, unter denen das Optimum nicht sein kann.Gerechnet wurde mit mehr als 1.000 zusammengeschalteten Computern.
Prof. Dr. Martin Moog, Technische Universität München 21FAZ vom 25. 10. 2000
Vier wichtige Merkmale des OR
• Optimalitätsstreben
• Modellanalytische Vorgehensweise
• Problemquantifizierung
• Entscheidungsvorbereitung
Prof. Dr. Martin Moog, Technische Universität München 22
Zimmermann, W., 1992, S. 4
Einteilung der Lösungsverfahren
• analytische Verfahren
• Näherungs-Verfahren
• heuristische Verfahren
• Simulations-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 23
Teilgebiete des OR
• Lineare Optimierung• Graphentheorie und Netzplantechnik• Ganzzahlige (lineare) und kombinatorische Optimierung• Dynamische Optimierung• Nichtlineare Optimierung• Warteschlangentheorie• Warteschlangentheorie• Simulation
Prof. Dr. Martin Moog, Technische Universität München 24
nach Domschke u. Drexl, 2. Aufl. 1991
Typische Fragestellungen
• Losgrößen
• Reihenfolgeprobleme
• Rundreiseprobleme
• Zuordnungsprobleme
Prof. Dr. Martin Moog, Technische Universität München 25
(2) Logistische Prozesse
• Reihenfolgeproblem
– Rundreise
– Postkutsche
• Zuordnungsproblem
– Transportproblem– Transportproblem
– Chinese-Postman Problem
Prof. Dr. Martin Moog, Technische Universität München 26
Einfache Reihenfolgeprobleme
• Das bekannteste Lehrbuch-Reihenfolgeproblem ist das sogen. Travelling-Salesman-Problem oder Rundreiseproblem.
• Das Rundreiseproblem kann in der Forst- und Holzwirtschaft z.B. in Form einer Minimierung von Umsetzzeiten oder Umsetzkosten auftreten.Umsetzkosten auftreten.
• Die Reihenfolge der Bearbeitung von Losen kann aber auch ein Reihenfolgeproblem sein, bei dem es darum gehen kann, die Rüstzeiten oder die Rüstkosten zu minimieren.
Prof. Dr. Martin Moog, Technische Universität München 27
Start
1 2 3
Das Reihenfolgeproblem als Ereignisbaum (3 Stationen)
1
2
3
3
2
2
1
3
3
1
3
1
2
2
1
Prof. Dr. Martin Moog, Technische Universität München 28
Ein Beispiel für ein Rundreiseproblem
Die Reihenfolge, in der mit einem Bohr-Roboter Löcherin ein Werkstück gebohrt werden.
Der Bohrkopf beginnt mit dem ersten Loch, bohrt dannnacheinander die Löcher in das Werkstück und mußin die Ausgangsposition zurück, um beim nächstenWerkstück mit demselben Loch anzufangen.
Prof. Dr. Martin Moog, Technische Universität München 29
Werkstück mit demselben Loch anzufangen.
Durch Optimierung der Reihenfolge läßt sich dieProduktivität der Maschine ggf. stark steigern.
Die Geschichte der gelösten Rundreiseprobleme
Jahr Art des Problems und Größe Autor, Algorithmus
1954 49 Städte, Hauptstädte der 48
Staaten der USA + Washingtonwww.math.princeton.edu/tsp/history.html
George Dantzig, Ray Fulkerson, Selmer
Johnson,
Branching and Bounding
1962 Wettbewerb von Proctor &
Gamble
1977 120 Knoten Martin Grötschel
1987 666 Knoten (world tour) Martin Grötschel und Olaf Holland
1991 3.038 Knoten David Applegate, Robert Bixby, Vasek
Chvátal
Die 15.112 Gemeinden in
Rheinland-Pfalz
2004 24.978 Orte in Schweden
Prof. Dr. Martin Moog, Technische Universität München 30
vgl. Gritzmann und Brandenberg, 2005, S. 346 ff.
Stark symmetrische Probleme sind mit viel höherem Rechenaufwand verbunden.Ein Problem mit 225 Städten wurde erst 1995 geknackt.
Rundreise-Spiel
Internetseite von Herrn Kollegen Gritzmann, Fakultät für Mathematik
https://www-m9.ma.tum.de/Allgemeines/TravelingSalesman
Prof. Dr. Martin Moog, Technische Universität München 31
F
A
Start undZiel
B
Rundreiseproblem (1/2)
Wie findet man intuitiv eine Lösung?
E
C
D
Prof. Dr. Martin Moog, Technische Universität München 32
F
A
Start undZiel
B
Einfach zur jeweilsnächstgelegenen Station!
Algorithmus des besten
Nachfolgers
Rundreiseproblem (2/2)
E
C
D
Nachfolgers
führt tendenziell zulangen Rückwegen
Prof. Dr. Martin Moog, Technische Universität München 33
Start/Ziel A B C
Start/Ziel 11 5 9
A 11 3 4
B 5 3 12
C 9 4 12 A
Es können auch Reisezeiten oderReisekosten sein.
Rundreiseproblem - Beispiel
Prof. Dr. Martin Moog, Technische Universität München 34
Start/Ziel
B
C
11
9
5
3 4
12
Algorithmus des besten Nachfolgers (1/5)
Start/Ziel A B C
Start/Ziel 11 5 9
A 11 3 4
B 5 3 12
C 9 4 12
Prof. Dr. Martin Moog, Technische Universität München 35
Es wird eine Entfernungsmatrix benötigt,diese ist symmetrisch, wenn Hin- und Rückwege gleichlang sind;die Felder auf der Hauptdiagonalen sind leer bzw. Null.
Bei der Rundreise liegt Start/Ziel fest, die erste Zeile und die erste Spalte sind dadurch bestimmt.
Die Reihenfolge der Spalten und Zeilen gibt die Reihenfolge der Stationen an;die Summe der blauen Felder folglich die Länge der Rundreise, hier 35.
Algorithmus des besten Nachfolgers (2/5)
Start/Ziel A B C
Start/Ziel 11 5 9
A 11 3 4
B 5 3 12
C 9 4 12
Prof. Dr. Martin Moog, Technische Universität München 36
Um im Sinne des Algorithmus des besten Nachfolgers den Weg zu bestimmen,muß die Spalte A gegen die Spalte getauscht werden, in der in der ZeileStart/Ziel der kleinste Wert steht.
Es muß also Spalte B gegen Spalte A getauscht werden, dann die Zeilen entsprechend.
Start/Ziel A B C
Start/Ziel 11 5 9
A 11 3 4
B 5 3 12
C 9 4 12
Algorithmus des besten Nachfolgers (3/5)
Start/Ziel B A C
Start/Ziel 5 11 9
A 11 3 0 4
B 5 3 12
C 9 12 4
Prof. Dr. Martin Moog, Technische Universität München 37
nach Tausch derSpalten A und B
Start/Ziel B A C
Start/Ziel 5 11 9
A 11 3 0 4
B 5 3 12
C 9 12 4
nach Tausch derSpalten A und B
Algorithmus des besten Nachfolgers (4/5)
Start/Ziel B A C
Start/Ziel 5 11 9
B 5 3 12
A 11 3 4
C 9 12 4
Prof. Dr. Martin Moog, Technische Universität München 38
nach Tausch derZeilen A und B
Die Summe derDistanzen beträgtnun 21
Start/Ziel B A C
Start/Ziel 5 11 9
B 5 3 12
A 11 3 4
C 9 12 4
nach Tausch derSpalten A und Bund der Zeilen A und B
Algorithmus des besten Nachfolgers (5/5)
Prof. Dr. Martin Moog, Technische Universität München 39
Es muß jetzt in der Zeile B rechts der Spalte B der kleinste Wert gesuchtwerden. Die Spalte müßte dann an die Position rechts neben Bgetauscht werden, dann entsprechend die Zeilen.
Hier steht aber schon der kleinste Wert an der richtigen Stelle.
Die Lösung lautet also: Start - B – A – C – Ziel Bei symmetrischen Matrizenist der umgekehrte Weg eine
gleichgute Lösung.
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
Verfahren des Sukzessiven Einbaus (1/7)
Prof. Dr. Martin Moog Technische Universität München
40
E
C
D Das Rundreiseproblem
ersterWegbzw .Schleife
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
ersterUmweg
Verfahren des Sukzessiven Einbaus (2/7)
E
C
D
ersterWeg
Prof. Dr. Martin Moog, Technische Universität München 41
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
ersterUmweg
zweiter Umweg
Verfahren des Sukzessiven Einbaus (3/7)
E
C
D
ersterWeg
Prof. Dr. Martin Moog, Technische Universität München 42
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
ersterUmweg
zweiter Umweg
Verfahren des Sukzessiven Einbaus (4/7)
E
C
D
ersterWeg
dritter Umweg
Prof. Dr. Martin Moog, Technische Universität München 43
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
ersterUmweg
zweiter Umweg
vierter Umweg
Verfahren des Sukzessiven Einbaus (5/7)
E
C
D
ersterWeg
dritter Umweg
Prof. Dr. Martin Moog, Technische Universität München 44
F
AStart und
Ziel
B
Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs
erster
ersterUmweg
zweiter Umweg
vierter Umweg
Verfahren des Sukzessiven Einbaus (6/7)
E
C
D
ersterWeg
dritter Umwegfünfter Umweg
Prof. Dr. Martin Moog, Technische Universität München 45
Wenn man mit diesem Algorithmus Lösungen für jede mögliche Ausgangsschleife (Start- Station – Ziel) berechnet, erhält manje eine Lösung.Aus diesen Lösungen kann man die beste auswählen.
Verfahren des Sukzessiven Einbaus (7/7)
Prof. Dr. Martin Moog, Technische Universität München 46
Das muß zwar nicht das Optimum sein, wird aber wahrscheinlicheine relativ gute Lösung sein.
• Das Rundreiseproblem kann dadurch gelöst werden, daß alle möglichen Wege berechnet werden (vollständige Enumeration)
• Die Zahl der möglichen Wege ist sehr groß, der Rechenaufwand dadurch ggf. zu hoch.
• Rechentechnisch erfolgt eine vollständige Enumeration dadurch, daß die Entfernungsmatrix vollständig durchgetauscht wird (vollständige
Vollständige Enumeration (1/8)
• Rechentechnisch erfolgt eine vollständige Enumeration dadurch, daß die Entfernungsmatrix vollständig durchgetauscht wird (vollständige Permutation).
Dabei wird nach jedem Tausch einer Spalte/Zeile die Rundreisestrecke berechnet.
Aus allen Rundreisestrecken wird schließlich die geringste ausgesucht. Deren Stationenfolge ist optimal.
Prof. Dr. Martin Moog, Technische Universität München 47
Start/Ziel A B C
Start/Ziel
A
B
C Rückweg
Tausch Reihenfolge
Die Zeile/Spalte Start/Ziel soll an erster Position bleiben, die anderen sollen vollständig durchgetauscht werden. Also tauschen wir:
in der quadratischen Matrix
Vollständige Enumeration (2/8)
A gegen B S/Z-B-A-C
A gegen C S/Z-B-C-A
B gegen C S/Z-C-B-A
B gegen A S/Z-C-A-B
C gegen A S/Z-A-C-B
der nächste Tausch C gegen B
würde die Ausgangssituation A-B-C
wiederherstellen.
Prof. Dr. Martin Moog, Technische Universität München 48
in der quadratischen Matrixmit je 3 Zeilen und Spaltengibt es 6 mögliche Reihenfolgender Zeilen bzw. Spalten.
6 = 3!
Die Zahl der Lösungen bei einemRundreiseproblem ist also immer:Zahl der Stationen ohne Start/ZielFakultät.
Tausch Reihenfolge Länge
Ausgangssituation 21
A gegen B S/Z-B-A-C 32
A gegen C S/Z-B-C-A
B gegen C S/Z-C-B-A
B gegen A S/Z-C-A-B
C gegen A S/Z-A-C-B
erster Tausch
Vollständige Enumeration (3/8)
Start/Ziel A B C
Start/Ziel 9 11 5
A 9 4 12
B 11 4 3
C 5 12 3
Start/Ziel B A C
Start/Ziel 11 9 5
B 11 4 3
A 9 4 12
C 5 3 12
Weglänge: 21 Weglänge: 32Rückweg
Prof. Dr. Martin Moog, Technische Universität München 49
zweiter Tausch
Vollständige Enumeration (4/8)
Tausch Reihenfolge Länge
Ausgangssituation 21
A gegen B S/Z-B-A-C 32
A gegen C S/Z-B-C-A 35
B gegen C S/Z-C-B-A
B gegen A S/Z-C-A-B
C gegen A S/Z-A-C-B
Start/Ziel B C A
Start/Ziel 11 5 9
B 11 3 4
C 5 3 12
A 9 4 12
Start/Ziel B A C
Start/Ziel 11 9 5
B 11 4 3
A 9 4 12
C 5 3 12
Weglänge: 32 Weglänge: 35
Prof. Dr. Martin Moog, Technische Universität München 50
dritter Tausch
Vollständige Enumeration (5/8)
Tausch Reihenfolge Länge
Ausgangssituation 21
A gegen B S/Z-B-A-C 32
A gegen C S/Z-B-C-A 35
B gegen C S/Z-C-B-A 21
B gegen A S/Z-C-A-B
C gegen A S/Z-A-C-B
Start/Ziel B C A
Start/Ziel 11 5 9
B 11 3 4
C 5 3 12
A 9 4 12
Start/Ziel C B A
Start/Ziel 5 11 9
C 5 3 12
B 11 3 4
A 9 12 4
Weglänge: 35 Weglänge: 21
Prof. Dr. Martin Moog, Technische Universität München 51
vierter Tausch
Vollständige Enumeration (6/8)
Tausch Reihenfolge Länge
Ausgangssituation 21
A gegen B S/Z-B-A-C 32
A gegen C S/Z-B-C-A 35
B gegen C S/Z-C-B-A 21
B gegen A S/Z-C-A-B 32
C gegen A S/Z-A-C-B
Start/Ziel C A B
Start/Ziel 5 9 11
C 5 12 3
A 9 12 4
B 11 3 4
Start/Ziel C B A
Start/Ziel 5 11 9
C 5 3 12
B 11 3 4
A 9 12 4
Weglänge: 35 Weglänge: 32
Prof. Dr. Martin Moog, Technische Universität München 52
fünfter Tausch
Vollständige Enumeration (7/8)
Tausch Reihenfolge Länge
Ausgangssituation 21
A gegen B S/Z-B-A-C 32
A gegen C S/Z-B-C-A 35
B gegen C S/Z-C-B-A 21
B gegen A S/Z-C-A-B 32
C gegen A S/Z-A-C-B 35
Start/Ziel C A B
Start/Ziel 5 9 11
C 5 12 3
A 9 12 4
B 11 3 4
Start/Ziel A C B
Start/Ziel 9 5 11
A 9 12 4
C 5 12 3
B 11 4 3
Weglänge: 32 Weglänge: 35
Prof. Dr. Martin Moog, Technische Universität München 53
Start/Ziel C B A
Start/Ziel 5 11 9
C 5 3 12
Start/Ziel A B C
Start/Ziel 9 11 5
A 9 4 12
Es gibt zwei gleichwertige Lösungen:
A-B-C und C-B-A
mit je einer Rundreisestrecke von 21
Vollständige Enumeration (8/8)
C 5 3 12
B 11 3 4
A 9 12 4
A 9 4 12
B 11 4 3
C 5 12 3
Prof. Dr. Martin Moog, Technische Universität München 54
Wenn alle Wege zweiseitig befahrbar sind,(keine Einbahnstraßen und gleichlang), muß es mindestens zwei gleichgute Lösungen geben.
Reihenfolgeprobleme, bei denen die erste und/oder letzte Stationnicht festliegt, haben n! Lösungen.
Ist die Reihenfolge von 3 Losen so zu bestimmen, daß die Rüstzeitenminimiert werden, ist eine Matrix mit den Zeiten für das jeweiligeUmrüsten aufzustellen
Ereignisbaum (1/2)
Latten Dielen Balken
Latten 4 3
Dielen 2 4
Balken 5 6
Die gesamte Zeit zum Umrüsten ergibt sich aus der Summe der Felderüber der Hauptdiagonalen.
Prof. Dr. Martin Moog, Technische Universität München 55
Das Reihenfolgeproblem als Ereignisbaum
(3 Lose: Latten, Dielen, Balken)
Start
Latten Dielen Balken
4 3 2 4 6 5
Latten Dielen Balken
Latten 4 3
Dielen 2 4
Balken 5 6
Ereignisbaum (2/2)
Dielen Balken
Balken
Latten Balken Dielen Latten
Dielen Balken Latten Latten Dielen
4 3 2 4 6 5
Prof. Dr. Martin Moog, Technische Universität München 56
4 6 3 5 2 4
8 9 5 9 8 9Summe der Umrüstzeiten
Bei Müller-Merbach (1971) findet sich eine Lösung des Rundreiseproblemsmit Hilfe der Dynamischen Programmierung.
Dynamische Programmierung
Prof. Dr. Martin Moog, Technische Universität München 57
Beispiel für die Einsparung von Rechenzeit: Ein Reihenfolgeproblem
der Dimension 10x10 hat 1010
Lösungen, die bei einer vollständigen Enumeration berechnet werden
müßten. Gelingt es, dieses Problem in drei Stufen zu fassen, dann sind nur noch 103 Lösungen zu berechnen.
Ein Reisender will mit der Postkutsche vom Osten in den Westen der USA reisen. Er sucht die sicherste Strecke. Es gibt jeweils Lebensversicherungs-Policen für die Teilstrecken. Die Gesamtstrecke mit den geringsten Lebensversicherungs-Kostensei die sicherste Strecke.Der Graph teilt das Problem in Stufen und zeigt die möglichen Wegevon Stufe zu Stufe.
Das Postkutschenproblem (1/3)
Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
B E
Prof. Dr. Martin Moog, Technische Universität München 58
vgl. Hillier u. Lieberman, 1988, S. 316 ff.
Die Aufteilung in Stufen ist wichtig.Sie vermindert die Zahl möglicher Wege.
ZA C
B
D G
E
F
H
I
Das Postkutschenproblem (2/3)
Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
B C D
A 2 4 3
E F G
B 7 4 6
C 3 2 4
D 4 1 5
H I
E 1 4
F 6 3
G 3 3
Z
H 3
I 4
Prof. Dr. Martin Moog, Technische Universität München 59
Die Kosten der Lebensversicherungen von Stufe zu Stufe
Das sind unsere Daten
vgl. Hillier u. Lieberman, 1988, S. 316 ff.
D G
Das Postkutschenproblem (3/3)
Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B E
F
H
I
B C D
A 2 4 3
E F G
B 7 4 6
C 3 2 4
D 4 1 5
H I
E 1 4
F 6 3
G 3 3
Z
H 3
I 4
Prof. Dr. Martin Moog, Technische Universität München 60
Die Wahl des jeweils besten Nachfolgers führt zu
A B F I Z mit Kosten von 2+4+3+4 = 13
D G
Berechnung der Wege der Stationen der letzten Stufe
zum Ziel
Berechnung der Wege von denStationen der vorletzten Stufe
über die Stationen der letzten Stufezum Ziel
Der Ablauf ist auch vom Start aus in Richtung Zielmöglich.
Das Postkutschenproblem – dyn. Programmierung (1/8)
Prof. Dr. Martin Moog, Technische Universität München 61
Berechnung der Wege von denStationen der drittletzten Stufe
über die Stationen der vorletzten Stufezum Ziel
usw. bis zum Erreichen des Starts
Das Postkutschenproblem – dyn. Programmierung (2/8)
Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B E
F
H
I
B C D
A 2 4 3
E F G
B 7 4 6
C 3 2 4
D 4 1 5
H I
E 1 4
F 6 3
G 3 3
Z
H 3
I 4
Prof. Dr. Martin Moog, Technische Universität München 62
Wir suchen den Weg mit den geringsten Kosten1 A x1 x2 x3 x4
wobei x4 = Z
D G
I
Wir suchen den Weg mit den geringsten Kosten.Dabei suchen wir vom Ziel aus. derzeitiger Ort Kosten Zielort
Das Postkutschenproblem – dyn. Programmierung (3/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Prof. Dr. Martin Moog, Technische Universität München 63
Dabei suchen wir vom Ziel aus.Es wird auf jeder Stufe der Weg gesucht, der die Kosten für den Rest der Strecke minimiert.Von Stufe 3 nach Stufe 4 sind die Kosten 3 oder 4,die niedrigsten Kosten also 3.
derzeitiger Ort
s
Kosten
f*4(s)
Zielort
x4*
H 3 Z
I 4 Z
B C D
A 2 4 3
E F G
B 7 4 6
C 3 2 4
D 4 1 5
H I
E 1 4
F 6 3
G 3 3
Z
H 3
I 4
Wie erreiche ich die Orte der 3. Stufemit geringsten Kosten?
Wir gehen eine Stufe in Richtung Startund berechnen für die Orte E, F und Gdie günstigsten Wege. derzeitiger Ort Kosten Zielort
jeweils + 3
Das Postkutschenproblem – dyn. Programmierung (4/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Prof. Dr. Martin Moog, Technische Universität München 64
die günstigsten Wege. derzeitiger Orts
Kosten
f*4(s)
Zielort
x4*
H 3 Z
I 4 ZKosten bei nächstem Ort
derzeitiger
Ort x3s
Ort H Ort I geringste
Kosten
also über Ort
E 1+3 = 4 4 + 4 = 8 4 H
F 6+3 = 9 3 + 4 = 7 7 I
G 3 + 3 = 6 3 + 4 = 7 6 H
jeweils + 4
H I
E 1 4
F 6 3
G 3 3
Wie erreiche ich die Orteder 2. Stufe zu geringsten Kosten?
Wir gehen eine Stufe in Richtung Start und berechnen für die Orte B, C und D die günstigsten Wege.
derzeitiger
Ort x
Kosten bei dem Weg über
Das Postkutschenproblem – dyn. Programmierung (5/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Wenn ich über E nach B fahre,
derzeitiger
Ort x3s
Kosten bei nächstem Ort
Ort H Ort I geringste
Kosten
also über
Ort
E 1+3 = 4 4 + 4 = 8 4 H
F 6+3 = 9 3 + 4 = 7 7 I
G 3 + 3 = 6 3 + 4 = 7 6 H
Prof. Dr. Martin Moog, Technische Universität München 65
Ort x2s
E
je + 4
F
je + 7
G
je + 6
geringste
Kosten
also über
Ort
B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 E oder F
C 3 + 4 = 7 2 + 7 = 9 4 +6 = 10 7 E
D 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 E oder F
die zusätzlichen Kostenstehen in dieser Spalte
die Kosten der Stufe kommenaus dieser Matrix
E F G
B 7 4 6
C 3 2 4
D 4 1 5
Wenn ich über E nach B fahre,dann auf dem kürzesten Wegnach E. Andere wären ineffizient.
Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst
Das Postkutschenproblem – dyn. Programmierung (6/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Wenn ich über B nach A fahre,dann auf dem kürzesten Wegzwischen B und Z.Andere Wege wären ineffizient.
derzeitiger
Ort x2s
Kosten bei dem Weg über
E
je + 4
F
je + 7
G
je + 6
geringste
Kosten
also über
Ort
B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 E oder F
C 3 + 4 = 7 2 + 7 = 9 4 +6 = 10 7 E
D 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 E oder F
Prof. Dr. Martin Moog, Technische Universität München 66
derzeitiger
Ort x2s
Kosten bei dem Weg über
B C D geringste
Kosten
also über
Ort
A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 C oder D
die zusätzlichen Kostenstehen in dieser Spalte
die Kosten der Stufe kommenaus dieser Matrix
B C D
A 2 4 3
Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst
Das Postkutschenproblem – dyn. Programmierung (7/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Prof. Dr. Martin Moog, Technische Universität München 67
derzeitiger
Ort x2s
Kosten bei dem Weg über
B C D geringste
Kosten
also über Ort
A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 C oder D
Jetzt ergibt sich der optimale Weg bzw. die optimalen Wege, die jeweils Kosten von 11 verursachen:
Man startet über C oder über Dbei Wahl von C muß die Reise über E fortgesetzt werden und dann über H
bei Wahl von D kann auch über E und H fortgesetzt werden, oder über F und I
Jetzt ergibt sich der optimale Weg bzw. die optimalen Wege, die jeweils Kosten von 11 verursachen:
Man startet über C oder über D
Das Postkutschenproblem – dyn. Programmierung (8/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0
ZA C
B
D G
E
F
H
I
Prof. Dr. Martin Moog, Technische Universität München 68
Man startet über C oder über Dbei Wahl von C muß die Reise über E fortgesetzt werden und dann über Hbei Wahl von D kann auch über E und H fortgesetzt werden, oder über F und I
A D E H ZA C E H Z
A D F I Z
oder4 3 1 3 = 11 3 4 1 3 = 11
3 1 3 4 = 11
B C D
A 2 4 3
E F G
B 7 4 6
C 3 2 4
D 4 1 5
H I
E 1 4
F 6 3
G 3 3
Z
H 3
I 4
150
2
110
1
170
8
140
7
160
6
170
5
240
Nummer
verbleibendeGrundfläche
Durchforstungsoptimierung alsdynamische Programmierung
0 10
100
1. Durchforstung 2. DurchforstungBestandesbegründung Endnutzung
4
90
3
100
110
9
110
140
11
0
In Anhalt an Bettinger u.a. 2009, S. 117
35 Jahre 45 Jahre 55 Jahre
von der ersten zur zweiten Stufeoder die erste Durchforstung
Ernte in Festmetern diskontierter Erlös
keine Durchforstung ---- ---
schwache Durchforstung 3.378 244.96
mittlere Durchforstung 4.360 316.17
starke Durchforstung 5.352 388.11
0 1
0 2
30
starke Durchforstung 5.352 388.11
Im Lehrbuch von Bettinger sind bei der ersten Durchforstung noch die Kulturkosten abgezogen (250.00 GE). Das ist jedoch nicht nötig, da hier ja die Kulturkosten konstant sind. Die Kulturkosten ändern also am Kapitalwert oder Endwert der Durchforstungen nichts. Daher sind die Zahlen hier zur Vereinfachung leicht verändert. Die Berücksichtigung der Kulturkosten ist aber nötig, wenn auch die Umtriebszeit variabel gestaltet wird. Dann muß
der Beitrag zum Bodenertragswert berechnet werden – darin sind auch die Kulturkosten enthalten.
0 4
In Anhalt an Bettinger u.a. 2009, S. 117
von der zweiten zur dritten Stufeoder die zweite Durchforstung
Ernte in Festmetern diskontierter Erlös
keine Durchforstung --- ---
keine Durchforstung --- ---
mittlere Durchforstung 7.931 353.08
starke Durchforstung 9.343 415.94
keine Durchforstung --- ---
1 5
2 6
2 9
2 10
keine Durchforstung --- ---
schwache Durchforstung 6.188 275.48
mittlere Durchforstung 7.638 339.94
keine Durchforstung --- ---
schwache Durchforstung 4.347 193.52
mittlere Durchforstung 5.762 256.52
3 7
3 9
3 10
4 8
4 9
4 10
In Anhalt an Bettinger u.a. 2009, S. 117
von der dritten zur vierten Stufeoder die Endnutzung
Ernte in Festmetern diskontierter Erlös
Endnutzung 44.858 1,225.99
Endnutzung 36.620 1,000.85
Endnutzung 33.804 923.88
Endnutzung 31.031 848.09
5 11
6 11
7 11
Endnutzung 31.031 848.09
Endnutzung 24.500 669.60
Endnutzung 23.000 628.60
8 11
9 11
10 11
In Anhalt an Bettinger u.a. 2009, S. 117
Optimale Durchforstung mit dynamischer ProgrammierungEin Beispiel von Bettinger u.a. (2009 S. 116 ff.)
Es geht um einen Douglasienbestand, der mit gegebener Umtriebszeit undzwei Durchforstungen bewirtschaftet werden soll, wobei die Durchforstungenunterbleiben können.
Die Durchforstungen können unterschiedlich stark sein.Sie werden hinsichtlich ihrer Stärke als Absenkung der Grundfläche auf einenbestimmten Wert (Quadratfuß/Hektar) definiert.
Voraussetzung einer solchen Optimierung ist naturgemäß ein vergleichsweiseleistungsfähiges Modell zur Prognose des Wachstums
Eingriffsstärke 1. Durchforstung 2. Durchforstung
schwach Absenkung um 60 GF/ha Absenkung um 60 GF/ha
mittel Absenkung um 70 GF/ha Absenkung um 70 GF/ha
stark Absenkung um 80 GF/ha Absenkung um 80 GF/ha
In Anhalt an Bettinger u.a. 2009, S. 117
Die Durchforstungsmöglichkeiten in Baumstruktur
Kultur
ohneGF=170
ohne schwache mittlere starke
schwacheGF= 110
ohne schwache mittlere
mittlere
GF=100
ohne schwache mittlere
starke
GF= 90
ohne schwache mittlere
GF die jeweils verbleibende Grundfläche (Quadratfuß/Hektar)
ohneGF= 240
schwacheGF=170
mittlereGF=110
starkeGF=100
ohneGF=170
schwacheGF=110
mittlereGF=100
ohneGF=160
schwacheGF=110
mittlereGF=100
ohneGF=140
schwacheGF=110
mittlereGF=100
rekursive Lösung, 1. Schritt
Erlös 1. Df. Erlös 2. Df. Erlös der EN Summe
1,225.99
Wir lösen das Problem jetzt rekursiv, also von der Endnutzung her.Dazu beginnen wir mit der Tabelle, die die diskontierten Endnutzungserlöse auflistete.
Betrachtet man nur diesen Schritt, dann ist natürlich der Weg 5-11 der vorteilhafteste.Aber das berücksichtigt die Stufe vorher nicht – das wollen wir in der nächsten Folie tun.
5 11
1,000.85
923.88
848.09
669.60
628.60
Man könnte es so ausdrücken:von 5 her kommend wird man
bei der EN mit 1.225 GE belohnt.6 11
7 11
8 11
9 11
10 11
In Anhalt an Bettinger u.a. 2009, S. 117
rekursive Lösung, 2. Schritt
1. Df. 2. Df. Erlös EN Summe
--- 1,225.99 1,225.99
--- 1,000.85 1,000.85
353.08 669.60 1,022.68
415.94 628.60 1,044.54
Wir betrachten jetzt die Wege von Stufe 2 über Stufe 3 zur Endnutzung (Stufe 4)
1 5 11
1 6 11
2 9 11
2 10 11 415.94 628.60 1,044.54
--- 923.88 923.88
275.48 669.60 945.08
339.94 628.60 968.54
--- 848.09 848.09
193.52 669.60 863.12
256.52 628.60 885.12
2 10 11
3 7 11
3 9 11
3 10 11
4 8 11
4 9 11
4 10 11
In Anhalt an Bettinger u.a. 2009, S. 117
rekursive Lösung, 3. Schritt
1. Df. 2. Df. Erlös EN Summe
--- 1,225.99 1,225.99
--- 1,000.85 1,000.85
353.08 669.60 1,022.68
Wir betrachten jetzt die Wege von Stufe 1 über die Stufen 2 u. 3 zur Endnutzung (Stufe 4)
markiert jeweils den besten Weg, der für den nächsten Schritt ausgewählt wird
1 5 11
2 6 11
2 9 11
415.94 628.60 1,044.54
--- 923.88 923.88
275.48 669.60 945.08
339.94 628.60 968.54
--- 848.09 848.09
193.52 669.60 863.12
256.52 628.60 885.12
2 10 11
3 7 11
3 9 11
3 10 11
4 8 11
4 9 11
4 10 11In Anhalt an Bettinger u.a. 2009, S. 117
rekursive Lösung, 3. Schritt
1. Df. 2. Df. Erlös EN Summe
--- --- 1,225.99 1225.99
Wir betrachten jetzt die Wege von Stufe 1 über die Stufen 2 u. 3 zur Endnutzung (Stufe 4)
Wir verlängern nur die jeweils besten Wege nun nach rückwärts weiter.Das sind die mit dem Stern markierten in der vorherigen Folie.So wird das Problem eingegrenzt.Jetzt wird das Ergebnis der ersten Durchforstung hinzugefügt.
0 1 5 11 --- --- 1,225.99 1225.99
244.96 415.94 628.60 1289.50
316.17 339.94 628.60 1284.71
388.11 256.52 628.60 1273.23
Die Kulturkosten müssen, wie oben gesagt, hier nicht berücksichtigt werden.Damit kann aus den die 1. Df. einbeziehenden Lösungen nun die beste Gesamtlösungherausgesucht werden. Es ist die rechts mit dem Stern gekennzeichnete.
0 1 5 11
0 2 10 11
110 3 10
0 4 10 11
In Anhalt an Bettinger u.a. 2009, S. 117
rekursive Rechnung zusammengefaßt
rekursive Lösung
1. Schritt 2. Schritt 3. Schritt
Weg Erlös EN Weg Erlös 2. Df. Zw.-Su. Weg Erlös 1. Df. Summe
5 - 11 1.225,99
1 - 5 -11 0,00 1.225,99 *
0 - 1 - 5 - 11 0,00 1.225,99
6 - 11 1.000,85
2 - 6 -11 0,00 1.000,85
7 -11 923,88
3 - 7 - 11 0,00 923,883 - 7 - 11 0,00 923,88
8 -11 848,09
4 - 8 - 11 0,00 848,09
9 -11 669,60
2 - 9 -11 353,08 1.022,68
3 - 9 - 11 275,48 945,08
4 - 9 - 11 193,52 863,12
10 -11 628,60
2 - 10 -11 415,94 1.044,54 *
0 - 2 -10 - 11 244,96 1.289,50
3 - 10 - 11 339,94 968,54 *
0 - 3 -10 - 11 316,17 1.284,71
4 - 10 -11 256,52 885,12 *
0 - 4 - 10 - 11 388,11 1.273,23
Vorwärtsrechnung
Das Problem muß nicht rekursiv gelöst werden, es kann auch von der Kultur beginnend die günstigste Lösung gesucht werden.
In diesem Fall wird zuerst die erste Durchforstung betrachtet, dann erste und zweite zusammen.Es werden die Wege gesucht, auf dem die „Stationen“ der 3. Stufe (Nrn. 5 bis 10) mit dem jeweils höchsten Erlös erreicht werden.Dann wird zur 4. Stufe (Endnutzung) für diese Wege weitergerechnet.Dann wird zur 4. Stufe (Endnutzung) für diese Wege weitergerechnet.
Es gibt aber Konstellationen, in denen die Vorwärtsrechnung nicht zum Optimum führt.
Sensitivitätsanalysen
Eine naheliegende Erweiterung besteht darin, die zusätzlichen
Kosten zu berechnen, die dadurch entstehen, daß der Weg durch
einen bestimmten Knoten genommen wird.
Vorwärtsrechnung für dasselbe ProblemVorwärtsrechnung
1. Schritt 2. Schritt 3. Schritt
Weg Erlös 1. Df. Weg Erlös 2. Df. Zw.-Su. Weg Erlös EN Summe
0 - 1 0,00
0 - 1 - 5 0,00 0,00 *
0 - 1 - 5 - 11 1.225,99 1.225,99
0 - 2 244,96
0 - 2 - 6 0,00 244,96 *
0 - 2 - 6 - 11 1.000,85 1.245,81
0 - 2 - 9 353,08 598,04 *
0 - 2 - 9 - 11 669,60 1.267,64
0 - 2 - 10 415,94 660,90 *
0 - 2 - 10 - 11 628,60 1.289,50
0 - 3 316,17
0 - 3 - 7 0 316,17 *
0 – 3 – 7 - 11 923,88 1.240,05
0 - 3 - 9 275,48 591,65
0 - 3 - 10 339,94 656,11
0 - 4 388,11
0 - 4 - 8 0 388,11 *
0 - 4 - 8 - 11 848,09 1236,20
0 - 4 - 9 193,52 581,63
0 - 4 - 10 256,52 644,63
Übungsaufgabe: maximiere die Erntemenge über 3 Durchforstungen (nur Holzmenge)
von nach Holzmenge
0 1 0
0 2 40
1 3 0
1 4 44
2 5 28
1. Durchforstung 1, 2
2. Durchforstung 3, 4, 5
3. Durchforstung 6, 7, 8
Endnutzung 92 5 28
3 6 0
3 7 55
4 7 27
4 8 47
5 8 29
6 9 246
7 9 206
8 9 185In Anhalt an Bettinger u.a. 2009, S. 117
3 6
von nach Holzmenge
0 1 0
0 2 40
1 3 0
1 4 44
2 5 28
3 6 0
3 7 55
4 7 27
4 8 47
98520
41 7
Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5
Alter 30 Alter 40 Alter 50 Alter 60 Alter 70
5 8 29
6 9 246
7 9 206
8 9 185
3 6
Verbale Formulierung der Lösungsidee (Vorwärtsrechnung für Reisekosten):Es wird für jeden Knoten auf jeder Stufe kalkuliert, welche Kosten für die möglichen Wege von allen Knoten der vorherigen Stufe entstehen.Da die niedrigst möglichen Kosten zur Erreichung der Knoten der vorherigenStufe bereits bekannt sind, sind auch für jeden Knoten der aktuellen Stufe die niedrigsten Kosten leicht zu ermitteln.So werden sukzessive für alle Knoten
98520
3
41
6
7
Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5
So werden sukzessive für alle Knotenvon Stufe zu Stufe die Wege bestimmt,auf denen sie mit den geringstenKosten erreicht werden.Schließlich der Weg (oder dieWege), auf denen das Zielmit den geringstenKosten erreicht wird.
Transportproblem
Von den Ausgangsorten Ai sollen bestimmte Mengen zu denBestimmungsorten Bj transportiert werden.
A1 Die Kosten sind zu minimieren.
Prof. Dr. Martin Moog, Technische Universität München 85
A3
A2
Z1 Z2 Z3
als Lösungsverfahren geeignet:der Simplex-Algorithmus
aber die Rechen-zeiten erfordern
effizientereAlgorithmen
Prinzipielle Vorgehensweise der effizienteren Algorithmen
Ermittlung einer Ausgangslösung
BeispieleNordwest-Ecken-RegelVogelsches ApproximationsverfahrenSpalten-Minimum-Verfahren
zur Suche der optimalen Lösung
Prof. Dr. Martin Moog, Technische Universität München 86
Ermittlung einer optimalen Lösung durchein iteratives Verfahren
zur Suche der optimalen LösungStepping-Stone-Methode
MODI-Methode
vgl. Heinrich, S. 65 ff.
Das Transportproblem als spezielles Zuordnungsproblem
Es sind n Elemente (Mittel, Personen) so auf n Aufgaben bzw. Stellenoder Orte zu verteilen, daß die Gesamtwirksamkeit maximiert wird.
E1Ein Spezialfall ist das Stundenplanproblem.Es sind die Lehrer den Klassen und den
Prof. Dr. Martin Moog, Technische Universität München 87
E3
E2
Z1 Z2 Z3
Es sind die Lehrer den Klassen und denRäumen zuzuteilen.Ähnlich bei Dienstplänen.
Ein nicht ganz ernstgemeintes Zuordnungsproblem
Töchter Jünglinge
Jakob Joachim Jens Jan Johann Joseph
Tina
TizianaTiziana
Tirolia
Thea
Prof. Dr. Martin Moog, Technische Universität München 88
Scheich Schuleiman möchte seine Töchter so verheiraten, daß die Zahlder Kamele maximiert wird.
vgl. Zimmermann, W., 1992, S. 120
Anzahl der Lösungen beim Zuordnungsproblem
Die Anzahl der Lösungen bei einem Zuordnungsproblem von n Sachenzu n Aufgaben ist n! (n Fakultät)
Bei n = 20 sind n! = 20x19x18x17 ....x2x1 = 2.432.902.008.176.640.000 Möglichkeiten
Prof. Dr. Martin Moog, Technische Universität München 89
Ein Computer mit einer Arbeitsgeschwindigkeit von 10-6 Sekunden pro Operation(1 Mio. Operationen pro Sekunde) würde bei ununterbrochenem Einsatzfür die Berechnung aller Lösungen 80.000 Jahre benötigen.
kombinatorische Explosion
Ein einfaches Zuordnungsproblem
Ein Forstdienstleistungsunternehmen hat 5 Wartungsfahrzeuge mit denStandorten A1, ....., A5.5 Forstmaschinen an den Standorten P1, ...., P5 sind am nächsten Tagzu warten. Welcher Wartungstrupp fährt zu welchem Einsatzort?Gesucht sei die minimale Fahrtstrecke
Die Matrix enthält die Entfernungen zwischen allen Orten
Ausgangsorte Bestimmungsorte
P1 P2 P3 P4 P5
A1 8 3 11 13 16
A2 2 8 17 2 7
A3 12 9 4 4 6
A4 5 11 9 7 14
A5 6 8 9 3 13
Prof. Dr. Martin Moog, Technische Universität München 90
Zimmermann, W., 1992, S. 112
Lösung des einfachen Zuordnungsproblems
Ausgangs-
orte
Bestimmungsorte
P1 P2 P3 P4 P5
A1 8 3 11 13 16
A2 2 8 17 2 7
A3 12 9 4 4 6
A4 5 11 9 7 14
A5 6 8 9 3 13
Prof. Dr. Martin Moog, Technische Universität München 91
Fahrtstrecke 3+7+4+5+3 = 22 km
Zimmermann, W., 1992, S. 112
Lösungsmöglichkeiten für Zuordnungsprobleme
• Distributions-Methode• Stepping-Stone-Verfahren• Ungarische Methode• vollständige Enumeration
Prof. Dr. Martin Moog, Technische Universität München 92
Methoden nach Zimmermann, W., 1992, S. 112ff
Die Vorgehensweise (außer bei der vollständigen Enumeration) besteht darin, im ersten Schritt eine Ausgangslösung zu suchen, die dann im zweiten Schritt verbessert wird.Eine gute Ausgangslösung findet man z.B. mit der Vogel´schen Methode.Alternativen sind das Nordwest-Ecken-Verfahren, das Matrixminimumverfahren,die Russel´sche Approximationsmethode, das Zeilen- oder Spaltenfolgeverfahren.
Transportkostenproblem - Vogel‘sches Verfahren (1/11)
Ausgan
gs-orte
Bestimmungsorte Pro-duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100Bedarf 70 90 130 60 100
gedeckt
Rest
Prof. Dr. Martin Moog, Technische Universität München 93
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Die Felder der Matrix enthalten die Transportkosten je Mengeneinheit.
Wir suchen eine gute Ausgangslösung.
Im Beispiel entsprechen die Liefermengen genau den Bedarfsmengen.Das nennt man den Standardfall.
Ist die Summe der Liefermengen größer als der Bedarf, muß man eine Spalte für die überschüssigen Mengen einfügen.
Ausgan
gs-orte
Bestimmungsorte Pro-duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (2/11)
Bedarf 70 90 130 60 100
gedeckt
Rest
Prof. Dr. Martin Moog, Technische Universität München 94
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute Ausgangslösung
Die Lösungsidee ist, zuerst das Feld mit den niedrigsten Transportkosten zu suchen und dort möglichst viele Mengeneinheiten einzusetzen.Dann geht man zum Feld mit den zweitniedrigsten Transportkosten und setztdort möglichst viele Mengeneinheiten ein; u.s.f……..
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 x 70 35 110 90 85 100 70 30
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (3/11)
gedeckt 70
Rest 70-70 =
0
Prof. Dr. Martin Moog, Technische Universität München 95
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute Ausgangslösung
Feld 4,I ist das Feld mit den niedrigsten Transportkosten.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 x 100 150 100 50
4 20 x 70 35 110 90 85 100 70 30
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (4/11)
gedeckt 70 100
Rest 0 0
Prof. Dr. Martin Moog, Technische Universität München 96
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute Ausgangslösung
Feld 3,V ist das Feld mit den zweitniedrigsten Transportkosten.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 x 100 150 100 50
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (5/11)
gedeckt 70 30 100
Rest 0 90-30
=60
0
Prof. Dr. Martin Moog, Technische Universität München 97
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungFeld 2,I ist das Feld mit den drittniedrigsten Transportkosten, aber der Bedarf istschon gedeckt. Das Feld mit den viertniedrigsten Transportkosten ist 4,II, dort können 30 Einheiteneingeplant werden. Damit sind die Lieferungen aus Ort 4 ausgelastet.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 x 50 75 25 x 100 150 100+50 0
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (6/11)
gedeckt 70 30 50 100
Rest 0 60 130-50
=80
0
Prof. Dr. Martin Moog, Technische Universität München 98
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungFeld 3,III ist das Feld mit den fünftniedrigsten Transportkosten.Vom Ausgangsort 3 sind noch 50 Einheiten lieferbar, die werden dort eingeplant. Damit ist auch Ort 3 nicht mehr lieferfähig.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 45 x 80 80 75 120 80 40
2 25 90 50 70 60 80
3 100 60 35 x 50 75 25 x 100 150 100+50 0
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (7/11)
gedeckt 70 30 50+80
=130
100
Rest 0 60 80-80=0 0
Prof. Dr. Martin Moog, Technische Universität München 99
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungFeld 1,III ist das Feld mit den sechstniedrigsten Transportkosten.Am Bestimmungsort III werden noch 80 Einheiten benötigt, die werden dort eingeplant. Damit ist der Bedarf an Ort III gedeckt
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 x 40 45 x 80 80 75 120 80+40 0
2 25 90 50 70 60 80
3 100 60 35 x 50 75 25 x 100 150 100+50 0
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (8/11)
gedeckt 70 30+40
=70
50+80 100
Rest 0 60-40
=20
0 0
Prof. Dr. Martin Moog, Technische Universität München 100
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungFeld 1,II ist das Feld mit den siebtniedrigsten Transportkosten.Am Bestimmungsort II werden noch 60 Einheiten benötigt, von Ort 1 könnennoch 40 Einheiten geliefert werden. Die werden dort eingeplant Damit ist die Lieferfähigkeit von Ort 1 erschöpft.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 x 40 45 x 80 80 75 120 80+40 0
2 25 90 50 70 x 60 60 80 60 20
3 100 60 35 x 50 75 25 x 100 150 100+50 0
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (9/11)
gedeckt 70 30+40
=70
50+80 60 100
Rest 0 20 0 60-60=0 0
Prof. Dr. Martin Moog, Technische Universität München 101
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungFeld 2,IV ist das Feld mit den siebtniedrigsten Transportkosten.Dort können 60 Einheiten eingeplant werden. Damit ist der Bedarf an Ort IV gedeckt.
Ausgan
gs-orteBestimmungsorte Pro-
duktion
ge-
liefertRest
I II III IV V
1 30 50 x 40 45 x 80 80 75 120 80+40 0
2 25 90 x 20 50 70 x 60 60 80 60+20 0
3 100 60 35 x 50 75 25 x 100 150 100+50 0
4 20 x 70 35 x 30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem - Vogel‘sches Verfahren (10/11)
gedeckt 70 30+40 +
20=90
50+80 60 100
Rest 0 0 0 0 0
Prof. Dr. Martin Moog, Technische Universität München 102
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine gute AusgangslösungNun sind von Ort 2 noch 20 Einheiten zu liefern, und in Ort II werden noch 20 Einheitenbenötigt.Diese werden in Feld 2,II eingeplant.
Ausgangs-
orteBestimmungsorte
ProduktionI II III IV V
1 30 50 x 40 45 x 80 80 75 120
2 25 90 x 20 50 70 x 60 60 80
3 100 60 35 x 50 75 25 x 100 150
4 20 x 70 35 x 30 110 90 85 100
Bedarf 70 90 130 60 100
Kosten 2.000 3.600
Transportkostenproblem - Vogel‘sches Verfahren (11/11)
Kosten
1.400
2.000
+1.800
+1.050
= 4.850
3.600
+1.250
=4.850 4.200 2.500 17.800
Prof. Dr. Martin Moog, Technische Universität München 103
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir berechnen die Transportkosten der guten Ausgangslösung:
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (1/8)
Bedarf 70 90 130 60 100
Prof. Dr. Martin Moog, Technische Universität München 104
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Die Felder der Matrix enthalten die Transportkosten je Mengeneinheit
Wir suchen eine zulässige Ausgangslösung.Diese wird als Start einer Optimierungsrechnung benötigt.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (2/8)
Bedarf 70 90 130 60 100
Prof. Dr. Martin Moog, Technische Universität München 105
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine zulässige Ausgangslösung mit der Nord-West-Ecken-Regel
Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem Feld 2,II weitermachen und so fortfahren.
Transportkostenproblem – Nordwest-Ecken-Regel (3/8)
Quell-orte
Zielorte
I II III IV
1 Wenn 1 mehrliefern kann als Zielort I braucht
2 Wenn der Bedarfvon Zielort I größer ist als die
Start
größer ist als dieLieferfähigkeit von Quellort 1
Prof. Dr. Martin Moog, Technische Universität München 106
Man beginnt in Feld 1,I im Nordwesten und trägt soviele Einheiten wie möglich ein.Ist die Lieferfähigkeit des Quellortes 1 größer als der Bedarf des Zielortes I, trägt man in Feld 1,II soviel Einheiten wie möglich ein – u.s.f. bis Quellort 1nicht mehr lieferfähig ist. Dann geht es in Zeile 2 mit der Spalte weiter, in derder Bedarf noch nicht gedeckt ist.Ist der Bedarf von Zielort I mit der Lieferfähigkeit von Quellort 1 nicht zu decken, geht man in Zeile 2 und trägt möglichst viele Einheiten ein, u.s.f.
Ausgan
gs-orte
Bestimmungsorte Produktion
ge-
liefertRest
I II III IV V
1 30 x 70 50 x 50 45 80 75 120 70+50 0
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (4/8)
Bedarf 70 90 130 60 100
gedeckt 70 50
Rest 0 40
Prof. Dr. Martin Moog, Technische Universität München 107
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine zulässige Ausgangslösung mit der Nord-West-Ecken-Regel
Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem eine Zeile tiefer liegenden Feld weitermachen und so fortfahren.
Ausgan
gs-orte
Bestimmungsorte Produktion
ge-
liefertRest
I II III IV V
1 30 x 70 50 x 50 45 80 75 120 70+50 0
2 25 90 x 40 50 x 40 70 60 80 40+40 0
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (5/8)
Bedarf 70 90 130 60 100
gedeckt 70 50+40 40
Rest 0 0 90
Prof. Dr. Martin Moog, Technische Universität München 108
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine zulässige Ausgangslösung mit dem Nordwest-Ecken-Regel Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem eine Zeile tiefer liegenden Feld weitermachen und so fortfahren.
Ausgan
gs-orte
Bestimmungsorte Produktion
ge-
liefertRest
I II III IV V
1 30 x 70 50 x 50 45 80 75 120 70+50 0
2 25 90 x 40 50 x 40 70 60 80 40+40 0
3 100 60 35 x 90 75 x 60 25 150 90+60 0
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (6/8)
Bedarf 70 90 130 60 100
gedeckt 70 50+40 40+90 60
Rest 0 0 0 0
Prof. Dr. Martin Moog, Technische Universität München 109
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine zulässige Ausgangslösung mit der Nordwest-Ecken-Regel Wir machen mit Feld 3,III weiter. Dort setzen wir 90 ein.Dann in Feld 3,IV 60 Mengeneinheiten.
Ausgan
gs-orte
Bestimmungsorte Produktion
ge-
liefertRest
I II III IV V
1 30 x 70 50 x 50 45 80 75 120 70+50 0
2 25 90 x 40 50 x 40 70 60 80 40+40 0
3 100 60 35 x 90 75 x 60 25 150 90+60 0
4 20 35 110 90 x 0 85 x100 100 100 0
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (7/8)
gedeckt 70 50+40 40+90 60 100
Rest 0 0 0 0 0
Prof. Dr. Martin Moog, Technische Universität München 110
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir suchen eine zulässige Ausgangslösung mit dem Nord-West-Ecken-Regel Wir machen mit Feld 4,IV weiter. Dort können wir aber nichts einsetzen, weil der Bedarfan Ort IV schon gedeckt ist.Wir gehen also zu Feld 4,V weiter und setzen dort die fehlenden 100 Mengeneinheiten ein.
Ausgan
gs-orte
Bestimmungsorte Produktion
ge-
liefertRest
I II III IV V
1 30 x 70 50 x 50 45 80 75 120 70+50 0
2 25 90 x 40 50 x 40 70 60 80 40+40 0
3 100 60 35 x 90 75 x 60 25 150 90+60 0
4 20 35 110 90 x 0 85 x100 100 100 0
Bedarf 70 90 130 60 100
Transportkostenproblem – Nordwest-Ecken-Regel (8/8)
Bedarf 70 90 130 60 100
gedeckt 70 50+40 40+90 60 100
Rest 0 0 0 0 0
Kosten 2.100 2.500
+3.600
= 6.100
2.000
+3.150
=5.150 4.500 8.500 26.350
Prof. Dr. Martin Moog, Technische Universität München 111
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir berechnen die Transportkosten für die mit dem Nordwest-Ecken-Regel gefundene Ausgangslösung.
Transportkostenproblem – Spalten-Minimum-Verfahren
Man beginnt in der linken Spalte.Dort sucht man den Weg mit den geringsten Kosten. Auf diesen setzt man die größtmögliche Menge.Dann sucht man den Weg mit den zweitgeringsten Kosten.Auf diesen setzt man die größtmögliche Menge.So arbeitet man die Spalte ab, bis der Bedarf gedeckt ist.
Prof. Dr. Martin Moog, Technische Universität München 112
So arbeitet man die Spalte ab, bis der Bedarf gedeckt ist.Dann geht man eine Spalte weiter.Dort wiederholt man die Prozedur.
Transportkostenproblem – Spalten-Minimum-Verfahren
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
Prof. Dr. Martin Moog, Technische Universität München 113
4 20 35 110 90 85 100
Bedarf 70 90 130 60 100
gedeckt
Rest
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50 45 80 75 120
2 25 90 50 70 60 80
3 100 60 35 75 25 150
4 20x70 35 110 90 85 100 70 30
Transportkostenproblem – Spalten-Minimum-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 114
Bedarf 70 90 130 60 100
gedeckt 70
Rest 0
In Spalte I betragen die minimalen Transportkosten 20 GE/ME.Da der Ort 4 mehr als den Gesamtbedarf von 70 ME liefern kann,ist der Bedarf von I völlig aus 4 zu decken. Spalte I scheidet aus der weiteren Betrachtung aus.
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50x60 45 80 75 120 60 60
2 25 90 50 70 60 80
3 100 60 35 75 25 150
Transportkostenproblem – Spalten-Minimum-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 115
3 100 60 35 75 25 150
4 20x70 35x30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
gedeckt 70 30+60
Rest 0 0
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50x60 45 80 75 120 60 60
2 25 90 50 70 60 80
3 100 60 35x130 75 25 150 130 20
Transportkostenproblem – Spalten-Minimum-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 116
3 100 60 35x130 75 25 150 130 20
4 20x70 35x30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
gedeckt 70 30+60 130
Rest 0 0 0
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50x60 45 80 75 120 60 60
2 25 90 50 70x60 60 80 60 20
3 100 60 35x130 75 25 150 130 20
Transportkostenproblem – Spalten-Minimum-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 117
3 100 60 35x130 75 25 150 130 20
4 20x70 35x30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
gedeckt 70 30+60 130 60
Rest 0 0 0 0
Aus-
gangs-
orte
BestimmungsortePro-
duktion
ge-
liefertRestI II III IV V
1 30 50x60 45 80 75x60 120 60+60 0
2 25 90 50 70x60 60x20 80 60+20 0
3 100 60 35x130 75 25x20 150 130+20 0
4 20x70 35x30 110 90 85 100 70+30 0
Bedarf 70 90 130 60 100
Transportkostenproblem – Spalten-Minimum-Verfahren
Prof. Dr. Martin Moog, Technische Universität München 118
Bedarf 70 90 130 60 100
gedeckt 70 30+60 130 60 20+20+
60
Rest 0 0 0 0 0
Kosten 1.400 3.000
+1.050
= 4.050
4.550 4.200 4.500
+1.200
+ 500
= 6.200
Summe der Kosten: 20.400
Die Lösung ist weniger gut als die nach dem
Vogel´schen Verfahren, aber besser als die nach
der NW-Ecken-Regel.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 30 x 70 50 x 50 45 80 75 120
2 25 90 x 40 50 x 40 70 60 80
3 100 60 35 x 90 75 x 60 25 150
4 20 35 110 90 x 0 85 x 100 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Stepping Stone Verf. (1/15)
Bedarf 70 90 130 60 100
Kosten 2.100 6.100 5.150 4.500 8.500 26.350
Prof. Dr. Martin Moog, Technische Universität München 119
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wollen uns im Hinblick auf die Optimierung nun fragen, ob es sich lohnt,Mengeneinheiten in noch freie Felder zu verschieben.Wir demonstrieren die Überlegung an Feld 2,I
Das Stepping-Stone-Verfahren wird auch Zyklusmethode genannt, weil nach einerzyklischen Tauschmöglichkeit gesucht wird, mit der die Transportkosten vermindert
werden können.Ein Beispiel findet man auch in Wikipedia.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 30 x 69 50 x 51 45 80 75 120
2 25 x 1 90 x 39 50 x 40 70 60 80
3 100 60 35 x 90 75 x 60 25 150
4 20 35 110 90 x 0 85 x 100 100
Bedarf 70 90 130 60 100
Kosten 2.070 2.550 5.150 4.500 8.500 26.305
Transportkostenproblem – Stepping Stone Verf. (2/15)
Kosten 2.070
25
2.095
2.550
3.510
6.060
5.150 4.500 8.500 26.305
Prof. Dr. Martin Moog, Technische Universität München 120
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wollen uns im Hinblick auf die Optimierung nun fragen, ob es sich lohnt,Mengeneinheiten in noch freie Felder zu verschieben, wobei die Summen in Zeilen und Spalte n konstant bleiben müssen.Wir demonstrieren die Überlegung an Feld 2,IWenn von 2,II eine Einheit nach 2,I verschoben wird, muß von 1,I eine nach 1,IIverschoben werden. Es entstehen die folgenden Kostendifferenzen:c2,I - c2,II + c1,II - c1,I in Zahlen: 25-90+50-30=-45Wir tragen diese Kostendifferenzen nun in alle freien Felder ein.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +30 +30 120
2 -45 40 40 -20 -25 80
3 +45 -15 90 60 -45 150
4 -50 -55 +60 0 100 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Stepping Stone Verf. (3/15)
Kosten 26.350
Prof. Dr. Martin Moog, Technische Universität München 121
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Die Matrix enthält nun in allen Feldern, die nicht mit Mengen belegt sind, dieKostenwirkung bei Verschiebung einer Mengeneinheit in das bisher unbelegte Feld.
Felder, in die eine Verschiebung zu Mehrkosten führt, enthalten rote Zahlen.Felder, in die eine Verschiebung zu Einsparungen führt, enthalten grüne Zahlen.Die fetten schwarzen Zahlen sind die Mengen der Ausgangslösung.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +30 +30 120
2 -45 40 40 -20 -25 80
3 +45 -15 90 60 -45 150
4 -50 -55 +60 0 100 100
Bedarf 70 90 130 60 100
Transportkostenproblem – Stepping Stone Verf. (4/15)
Kosten 26.350
Prof. Dr. Martin Moog, Technische Universität München 122
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Die Lösungsidee besteht nun darin, mit Verschiebungen möglichst viele Mengeneinheitenauf die Felder mit den grünen negativen Zahlen zu bringen.
Man muß nicht mit dem Feld beginnen, das die höchsten Einsparungen erbringt.
Die Operation wird solange fortgesetzt, bis keine Einsparungen mehr zu erzielen sind.Dann ist das Optimum gefunden.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +30 +30 120
2 -45 40 40 -20 -25 80
3 +45 -15 90 60 -45 150
4 -50 -55 +60 0 100 100
Bedarf 70 90 130 60 100
Kosten 26.350
Wir wählen das Feld 3,V als erstes.
Transportkostenproblem – Stepping Stone Verf. (5/15)
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +30 +30 120
2 -45 40 40 -20 -25 80
3 +45 -15 90 0+45=+45 60 150
4 -50 -55 +60 0 100 100
Bedarf 70 90 130 60 100
Kosten
Prof. Dr. Martin Moog, Technische Universität München 123Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 3,V als erstes.
60
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +30+45= +75
+30+45=+75
120
2 -45 40 40 -20+45=+25
-25+45= +20
80
3 +45 -15 90 +45 60 150
4 -50-45= -95
-55-45= -100
+60-45= +15
60 40 10060
60
Transportkostenproblem – Stepping Stone Verf. (6/15)
Bedarf 70 90 130 60 100
Kosten
Prof. Dr. Martin Moog, Technische Universität München 124Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 3,V als erstes.Wenn 60 ME von 3,IV nach 3,V verschoben werden, müssen zum Ausgleich 60 MEvon 4,V nach 4,IV verschoben werden.Dadurch entstehen für die Lieferungen des Ortes 4 zwar keine Mehrkosten,aber die Rückverschiebung würde in Zeile 3 Mehrkosten von 45 GE verursachen.Deshalb müssen die Verschiebungskosten in Zeile 4 um je 45 GE gemindert werden.Das erhöht die Vorteile einer Verschiebung in diese Felder. In den Spalten IV und Verhöhen sich die Verschiebungskosten um 45 GE/ME.Wir suchen daher als nächstes das Feld 4,II aus.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +75 +75 120
2 -45 40 40 +25 +20 80
3 +45 -15 90 +45 60 150
4 -95 -100 +15 60 40 100
Bedarf 70 90 130 60 100
Kosten
Wir wählen das Feld 4,2 als nächstes. Aus Feld 4,5 lassen sich 40 ME verschieben
Transportkostenproblem – Stepping Stone Verf. (7/15)
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +75 +75 120
2 -45 40 40 +25 +20 80
3 +45 -15 90 +45 60 150
4 -95 -100 +15 60 40 100
Bedarf 70 90 130 60 100
Kosten
Prof. Dr. Martin Moog, Technische Universität München 125
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 4,2 als nächstes. Aus Feld 4,5 lassen sich 40 ME verschieben
40
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 +75-100= -25
+75 120
2 -45 40-40=0 40+40=80 +25-100=-75
+20 80
3 +45 -15 90-40=50 +45-100=-55
60+40=100 150
4 -95+100= +5
40 +15 +100= +115
60 +100 100
40
40
40
Transportkostenproblem – Stepping Stone Verf. (8/15)
= +5 = +115
Bedarf 70 90 130 60 100
Kosten 19.650
Prof. Dr. Martin Moog, Technische Universität München 126
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 4,II als nächstes. Aus Feld 4,V lassen sich 40 ME verschieben.Zum Ausgleich müssen 40 ME aus Spalte II in die Spalte V verschoben werden.Dies geschieht in zwei Schritten durch Verschiebung von Spalte II in Spalte III und dann in Vohne Mehrkosten.
In Zeile 4 sind die Verschiebungskosten jeweils um die 100 GE/ME zu vermindern.In Spalte IV sind die Verschiebungskosten um 100 GE/ME zu vermindern.
40
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35 -25 +75 120
2 -45 0 80 -75 +20 80
3 +45 -15 50 -55 100 150
4 +5 40 +115 60 +100 100
Bedarf 70 90 130 60 100
Kosten 19.650
Transportkostenproblem – Stepping Stone Verf. (9/15)
Prof. Dr. Martin Moog, Technische Universität München 127
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,I als nächstes. Die Verschiebung von 0 aus Feld 2,II nach Feld 2,I verändert allerdings die Gesamtkostennicht.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 +35-45=-10
-25 +75-45=+30
120
2 0 +45 80 -75+45=-30
+20 80
3 +45+45= 90
-15+45=30
50 -55+45=-10
100 150
4 +5 40 +115-45=+70
60 +100-45=+55
100
Transportkostenproblem – Stepping Stone Verf. (10/15)
=+70 =+55
Bedarf 70 90 130 60 100
Kosten 19.650
Prof. Dr. Martin Moog, Technische Universität München 128
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,I als nächstes. Die Verschiebung von 0 aus Feld 2,II nach Feld 2,I verändert allerdings die Gesamtkostennicht.Sie führt allerdings zu Veränderungen der Verschiebungskosten.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 70 50 -10 -25 +30 120
2 0 +45 80 -30 +20 80
3 90 30 50 -10 100 150
4 +5 40 +70 60 +55 100
Bedarf 70 90 130 60 100
Kosten
Transportkostenproblem – Stepping Stone Verf. (11/15)
Prof. Dr. Martin Moog, Technische Universität München 129
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 1,III als nächstes.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 +10 50 70 -25 +40 120
2 70 +35 10 -40 +20 80
3 90 20 50 -20 100 150
4 +15 40 +80 60 +65 100
Bedarf 70 90 130 60 100
Kosten
Transportkostenproblem – Stepping Stone Verf. (12/15)
Prof. Dr. Martin Moog, Technische Universität München 130
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,IV als nächstes.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 -30 40 80 -25 +40 120
2 70 +75 +40 10 +60 80
3 50 20 50 -20 100 150
4 -25 50 +80 50 +65 100
Bedarf 70 90 130 60 100
Kosten
Transportkostenproblem – Stepping Stone Verf. (13/15)
Kosten
Prof. Dr. Martin Moog, Technische Universität München 131
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 1,I als nächstes.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 40 +30 80 +5 +40 120
2 30 +75 +10 50 +30 80
3 80 50 50 +10 100 150
4 -25 90 +50 10 +35 100
Bedarf 70 90 130 60 100
Kosten
Transportkostenproblem – Stepping Stone Verf. (14/15)
Kosten
Prof. Dr. Martin Moog, Technische Universität München 132
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 4,I als nächstes, das als einziges eine Kostenminderung ermöglicht.
Ausgangs-
orte
BestimmungsorteProduktion
I II III IV V
1 40 +5 80 +5 +40 120
2 20 +50 +10 60 +30 80
3 +80 +25 50 +10 100 150
4 10 90 +75 +25 +60 100
Bedarf 70 90 130 60 100
Kosten 17.100
Transportkostenproblem – Stepping Stone Verf. (15/15)
Prof. Dr. Martin Moog, Technische Universität München 133
vgl. Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Nun weist kein Feld mehr negative Verschiebungskosten auf, so daß eine optimaleLösung erreicht sein muß.
Transportkostenproblem
Mit dem Excel-Solver läßt sich das Transportkosten-Beispiel aus dem Buch von Henn&Künzi auch lösen.
Prof. Dr. Martin Moog, Technische Universität München 134
Die Lösung des Transportkostenproblems
mit dem Excel-Solver
Besonders beeindruckende logistische Leistungen
Umzug des Flughafens München in der Nacht vom 16./17. Mai 1992von Riem nach Erding.
Austausch aller Schilder auf dem Flugfeld des Rhein-Main-Flughafensin einer Nacht (FAZ vom 12.6. 2010).
Prof. Dr. Martin Moog, Technische Universität München 136
Umzug der Ministerien von Bonn nach Berlin
Das Problem des Postboten unterscheidet sich vom Problem desHandlungsreisenden dadurch, daß es nicht darum geht, eine Reihe vonOrten zu besuchen, sondern ein Netz auf einem möglichst kurzen Wegvollständig abzulaufen.
Im Graphen kommt es also darauf an, alle Kanten zu durchlaufen, wobeimöglichst wenige (nur kurze) unproduktive Strecken vorkommen sollen.
Das Chinese Postman Problem
eigenes Foto
Prof. Dr. Martin Moog, Technische Universität München 137
Praktische Anwendungen könnten z.B. sein:
• eine optimierte Strecken für die Schneeräumung auf den Waldwegen• eine optimierte Strecke für die Begutachtung der Randbäume an Wegen• eine optimierte Strecke für die Prüfung der Wege nach einem Sturm
(3) Produktionsplanung und -steuerung
• Optimierung von Losgrößen
• Optimierung von Mischungen
• Optimierung der Kapazitätsauslastung
• Optimierung der Maschinenbelegung
• Optimierung des Werkzeugwechsels• Optimierung des Werkzeugwechsels
• Sonderfall: Ganzzahlige Optimierung
Prof. Dr. Martin Moog, Technische Universität München 138
Optimierung der Bearbeitungsreihenfolge von Losen
• Reihenfolgeprobleme ergeben sich in der industriellen Produktion besonders dann, wenn zur Bearbeitung von Losen mehrere Kapazitätseinheiten nacheinander in Anspruch genommen werden müssen und die Bearbeitung der Lose jeweils unterschiedliche Zeit in Anspruch nimmt. Die Optimierung der Reihenfolge der Bearbeitung führt dann zur Minimierung der Leerzeiten der Kapazitätseinheiten.
• In der Sägeindustrie ist z.B. vorstellbar, daß Einschnitt und Trocknung hintereinandergeschaltet sind. Durch Optimierung der Reihenfolge könnten dann Leerzeiten der Trocknungsanlage vermieden werden.
• Ein solches Reihenfolgeproblem läßt sich mit Johnson´s-Algorithmus elegant lösen.
Prof. Dr. Martin Moog, Technische Universität München 139
Es sei ein Reihenfolgeproblem aus 8 Losen betrachtet.
Die Zahl der möglichen Lösungen ist 8! = 40.320
Es liegt eine zweistufige Bearbeitungsfolge vor, wie sie in der Holzindustriebeispielsweise beim Sägen und Trocknen vorkommen könnte, oder bei einemBearbeitungs- und einem Verleimungsprozeß.
Johnson‘s Algorithmus (1/13)
Prof. Dr. Martin Moog, Technische Universität München 140
Dabei soll es Ziel der Optimierung sein, die Leerzeiten des zweiten Prozesseszu minimieren (Zielfunktion). Bei einem Trockner, einem Brennofen, einer beheizten Presse etc. ist der Zweck offensichtlich (Energieeinsparung).
Es kann aber auch darum gehen, die Arbeitszeit der zweiten Bearbeitungs-stufe zu minimieren, weil diese noch für einen anderen Produktionsprozeßbenötigt wird und daher ein Engpaßfaktor ist.
der vorgestellte Algorithmusfunktioniert auch bei 3 Maschinen
(OR Handbook, in unserem Bestand)
Ein Beispiel (fahrende Künstler) findetman bei Kaufmann u. Faure, Methoden
des OR, Walter de Gruyter, S 231 ff.
Los 1 2 3 4 5 6 7 8
Stufe 1 20 10 14 12 12 18 25 15
Stufe 2 25 8 11 10 15 12 20 20
Die Tabelle zeigt die Zeiteinheiten, die für die Bearbeitung der Lose nötig sind.
grafische Darstellung der Leerzeiten, zufällige Reihenfolge
Johnson‘s Algorithmus (2/13)
Prof. Dr. Martin Moog, Technische Universität München 141
grafische Darstellung der Leerzeiten, zufällige Reihenfolge
Stufe 1
2 6 3 8 7 1 4 5
Stufe 2 8 12 11 20 20 25
10 18 14 15 25 20 12 12
10 10 2 4 5
Leerzeiten
Los 1 2 3 4 5 6 7 8
Stufe 1 20 10 14 12 12 18 25 15
Stufe 2 25 8 11 10 15 12 20 20
Nun suchen wir uns das Los mit der kürzesten Bearbeitungszeit.
Das ist Los 2, mit 8 Minuten in Stufe 2.
Johnson‘s Algorithmus (3/13)
Prof. Dr. Martin Moog, Technische Universität München 142
Das ist Los 2, mit 8 Minuten in Stufe 2.
Wenn diese kürzeste Bearbeitungszeit auf Stufe 1 fällt, reihen wir dieses Losan den Anfang.
Wenn die kürzeste Bearbeitungszeit auf die Stufe 2 fällt, reihen wir dieses Losan das Ende.
Wir wiederholen diesen Schritt und tragen das Ergebnis in eine Matrix ein, die in der Waagerechten die Reihenfolge zeigt und in der Senkrechten dieAuswahlschritte (Iterationen).
also an das Ende
Los 1 2 3 4 5 6 7 8
Stufe 1 20 10 14 12 12 18 25 15
Stufe 2 25 8 11 10 15 12 20 20
Position in der Reihenfolge
Johnson‘s Algorithmus – 1. Auswahlschritt (4/13)
1. 2. 3. 4. 5. 6. 7. 8.
Ausw
ahls
chritt
1 2
2
3
4
5
6
7
8
Prof. Dr. Martin Moog, Technische Universität München 143
Los 1 2 3 4 5