1
OR-Anwendungen in Forst-
und Holzwirtschaft
2
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
• 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
eine kleine Auswahl
3
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
nur eine Auswahl
4
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.
5
Übersetzungen von OR ins Deutsche
• Unternehmensforschung
• Operationsforschung
• Optimierungsrechnung
• Planungsforschung
• Planungsrechnung
• Optimalplanung
• mathematische Entscheidungsvorbereitung
haben sich nicht durchgesetzt
6
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
• 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
7
OR-Modellbildung
Entwicklung von
Algorithmen
OR im engeren Sinne
OR im weiteren Sinne
Modellbildung und Lösungsfindung
8
erste OR-Anwendungen
Zusammenstellung von
Schiffskonvois im WKII
Optimierung der
Radarerfassung der
Flugbewegungen an der
englischen Küste
kommerzielle Anwendungen nach dem 2. Weltkrieg
unzählige Rechenknechte
9
Modelltypen
Modelle
Beschreibungs-
modelle
Erklärungs-
modelle
oder
Prognosemodelle
Entscheidungs-
oder
Optimierungs-
modelle
Restriktionen
in Optimierungs-
modellen
Schwerpunkt des OR
10
Optimierungsmodelle
Optimierungsmodell = Zielfunktion + Nebenbedingungen
maximiere den Deckungsbeitrag
minimiere die Kosten beachte die zur Verfügung stehenden
Produktionskapazitäten
bei vorgegebenen Produktionsmengen
Modelle zur Maximierung oder Minimierung
11
Charakterisierung von Optimierungsmodellen
Informationsgrad deterministische Modelle
stochastische Modelle
Typ der Zielfunktion
und der
Nebenbedingungen
lineare, nichtlineare, ganzzahlige
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)
12
Computereinsatz notwendig
Konrad Zuse
Museum in Hünfeld (Rhön)
Logo der Konrad Zuse Gesellschaft
13
Nug30 – gelöst im Jahr 2000
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 entstehen
Transportkosten.
Je mehr Güter getauscht werden müssen und je größer die Distanzen sind,
desto höher sind die Transportkosten.
C.E. Nugent, Th.E. Vollmann und J. Ruml haben 1968 einen Satz von Beispielen
formuliert 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.FAZ vom 25. 10. 2000
14
Teilgebiete des OR
• Lineare Optimierung
• Graphentheorie und Netzplantechnik
• Ganzzahlige (lineare) und kombinatorische Optimierung
• Dynamische Optimierung
• Nichtlineare Optimierung
• Warteschlangentheorie
• Simulation
nach Domschke u. Drexl, 2. Aufl. 1991
15
grundsätzliche Vorgehensweise des OR
reales Problem
mathematisches Modell
Modell-Lösung
Lösungsvorschlag
für das reale Problem
Abstraktion
Rechnung
Interpretation
nach Zimmermann, W., 1992, S. 3
Die gewählte Lösung muß
nicht die Modell-Lösung sein.
Berücksichtigung weiterer
Umstände ist sinnvoll.
16
Improvisation Planung
17
Vier wichtige Merkmale des OR
• Optimalitätsstreben
• Modellanalytische Vorgehensweise
• Problemquantifizierung
• Entscheidungsvorbereitung
Zimmermann, W., 1992, S. 4
18
Einteilung der Lösungsverfahren
• analytische Verfahren
• Näherungs-Verfahren
• Heuristische Verfahren
• Simulations-Verfahren
19
Gliederungsschemata in OR Lehrbüchern
• Netzplantechnik
• Lineare Optimierung
• Transport und Zuordnungsoptimierung
• Ganzzahlige Optimierung
• Kombinatorische Optimierung
• Dynamische Optimierung
• Nichtlineare Optimierung
• Wahrscheinlichkeitstheoretische Grundlagen
• Entscheidungstheoretische Grundlagen
• Theorie der Spiele
• Simulationstechnik
• Warteschlangensysteme
• Optimale Lagerhaltung
• Lineare Optimierung
• Graphentheorie
• Lineare Optimierungsprobleme mit spezieller Struktur
• Netzplantechnik
• Ganzzahlige und kombinatorische Optimierung
• Dynamische Optimierung
• Nichtlineare Optimierung
• Warteschlangentheorie
• Simulation
Zimmermann, W., 1992 Domschke und Drexl 1991, 2007
20
Gliederungsschemata in OR Lehrbüchern
• 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
• Lösungen der Aufgaben
Heinrich 2007 Werners 2006
21
Transportproblem
Von den Ausgangsorten Ai sollen bestimmte Mengen zu den
Bestimmungsorten Bj transportiert werden.
A1
A3
A2
Z1 Z1 Z1
Die Kosten sind zu minimieren.
als Lösungsverfahren geeignet:
der Simplex-Algorithmus
aber die Rechen-
zeiten erfordern
effizientere
Algorithmen
22
prinzipielle Vorgehensweise der effizienteren Algorithmen
Ermittlung einer
Ausgangslösung
Ermittlung einer
optimalen Lösung durch
ein iteratives Verfahren
Beispiele
Nordwest-Ecken-Regel
Vogelsches Approximationsverfahren
zur Suche der optimalen Lösung
Stepping-Stone-Methode
MODI-Methode
vgl. Heinrich, S. 65 ff.
23
Das Zuordnungsproblem als spezielles
Transportproblem
Es sind n Elemente (Mittel, Personen) so auf n Aufgaben bzw. Stellen
oder Orte zu verteilen, daß die Gesamtwirksamkeit maximiert wird.
E1
E3
E2
Z1 Z1 Z1
Ein Spezialfall ist das Stundenplanproblem.
Es sind die Lehrer den Klassen und den
Räumen zuzuteilen.
Ähnlich bei Dienstplänen.
24
ein nicht ganz ernstgemeintes Zuordnungsproblem
Töchter Jünglinge
Jakob Joachim Jens Jan Johann Joseph
Tina
Tiziana
Tirolia
Thea
Scheich Schuleiman möchte seine Töchter so verheiraten, daß die Zahl
der Kamele maximiert wird.
vgl. Zimmermann, W., 1992, S. 120
25
Anzahl der Lösungen beim Zuordnungsproblem
Die Anzahl der Lösungen bei einem Zuordnungsproblem von n Sachen
zu n Aufgaben ist n! (n Fakultät)
Bei n = 20 sind n! = 20x19x18x17 ....x2x1
= 2.432.902.008.176.640.000 Möglichkeiten
Ein Computer mit einer Arbeitsgeschwindigkeit von 10-6 Sekunden pro Operation
(1 Mio. Operationen pro Sekunde) würde bei ununterbrochenem Einsatz
für die Berechnung aller Lösungen 80.000 Jahre benötigen.
kombinatorische Explosion
26
Ein einfaches Zuordnungsproblem
Ein Forstdienstleistungsunternehmen hat 5 Wartungsfahrzeuge mit den
Standorten A1, ....., A5.
5 Forstmaschinen an den Standorten P1, ...., P5 sind am nächsten Tag
zu warten. Welcher Wartungstrupp fährt zu welchem Einsatzort?
Gesucht sei die minimale Fahrtstrecke
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
Die Matrix enthält die Entfernungen zwischen allen Orten
Zimmermann, W., 1992, S. 112
27
Lösung des einfachen Zuordnungsproblems
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
Fahrtstrecke 3+7+4+5+3 = 22 km
Zimmermann, W., 1992, S. 112
28
Lösungsmöglichkeiten für Zuordnungsprobleme
• Distributions-Methode
• Stepping-Stone-Verfahren
• Ungarische Methode
• vollständige Enumeration
Methoden nach Zimmermann, W., 1992, S. 112ff
29
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Die Felder der Matrix enthalten die Transportkosten je Mengeneinheit
Wir suchen eine gute Ausgangslösung
30
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
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 setzt
dort möglichst viele Mengeneinheiten ein; u.s.f……..
31
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0
Wir suchen eine gute Ausgangslösung
Feld 4,1 ist das Feld mit den niedrigsten Transportkosten.
32
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 100-100=0
Wir suchen eine gute Ausgangslösung
Feld 3,5 ist das Feld mit den zweitniedrigsten Transportkosten.
33
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30=60 100-100=0
Wir suchen eine gute Ausgangslösung
Feld 2,1 ist das Feld mit den drittniedrigsten Transportkosten, aber der Bedarf ist
schon gedeckt.
Das Feld mit den viertniedrigsten Transportkosten ist 4,2, dort können 30 Einheiten
eingeplant werden. Damit sind die Lieferungen aus Ort 4 ausgelastet.
34
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30=60 130-50=80 100-100=0
Wir suchen eine gute Ausgangslösung
Feld 3,3 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.
35
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30=60 130-50-
80=0
100-100=0
Wir suchen eine gute Ausgangslösung
Feld 1,3 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
36
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30-
40=20
130-50-
80=0
100-100=0
Wir suchen eine gute Ausgangslösung
Feld 1,2 ist das Feld mit den siebtniedrigsten Transportkosten.
Am Bestimmungsort II werden noch 60 Einheiten benötigt, von Ort 1 können
noch 40 Einheiten geliefert werden. Die werden dort eingeplant
Damit ist die Lieferfähigkeit von Ort 1 erschöpft.
37
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30-
40=20
130-50-
80=0
60 – 60 = 0 100-100=0
Wir suchen eine gute Ausgangslösung
Feld 2,4 ist das Feld mit den siebtniedrigsten Transportkosten.
Dort können 60 Einheiten eingeplant werden. Damit ist der Bedarf an Ort IV gedeckt.
38
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orteBestimmungsorte
ProduktionI 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
-70 = 0 90-30-40 -
20=0
130-50-
80=0
60 – 60 = 0 100-100=0
Wir suchen eine gute Ausgangslösung
Nun sind von Ort 2 noch 20 Einheiten zu liefern, und in Ort II werden noch 20 Einheiten
benötigt.
Diese werden in Feld 2,2 eingeplant.
39
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
1.400
2.000
1.800
1.050
= 4.850
3.600
1.250
=4.850 4.200 2.500 17.800
Wir berechnen die Transportkosten der guten Ausgangslösung:
40
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Die Felder der Matrix enthalten die Transportkosten je Mengeneinheit
Wir suchen eine zulässige Ausgangslösung.
Diese wird als Start einer Optimierungsrechnung benötigt.
41
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Wir suchen eine zulässige Ausgangslösung mit dem Diagonalverfahren
Die Lösungsidee ist, im Feld 1,1 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,2 weitermachen und so fortfahren.
42
Prinzip des Diagonalverfahrens zur Suche einer
zulässigen Lösung des Transportproblems
Quell-
orte
Zielorte
I II III IV
1
2
3
1 2 3 4
5 6 7
8 9
43
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Ausgangs-
orte
BestimmungsorteProduktion
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-70=0 90-50=40 130 60 100
Wir suchen eine zulässige Ausgangslösung mit dem Diagonalverfahren
Die Lösungsidee ist, im Feld 1,1 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,2 weitermachen und so fortfahren.
44
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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-40-40=0
3 100 60 35 75 25 150
4 20 35 110 90 85 100
Bedarf 70 – 70
=0
90 – 50 =
40 -40 =0
130-40
=90
60 100
Wir suchen eine zulässige Ausgangslösung mit dem Diagonalverfahren
Die Lösungsidee ist, im Feld 1,1 anzufangen und dort möglichst viele
Mengeneinheiten einzusetzen.
Dann nach rechts fortzuschreiten, bis Ort 1 nicht menr lieferfähig ist.
Dann kann man mit dem Feld 2,2 weitermachen und so fortfahren.
45
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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-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 – 70
=0
90 – 50 =
40 -40 =0
130-40 -90
=0
60 100
Wir suchen eine zulässige Ausgangslösung mit dem Diagonalverfahren
Wir machen mit Feld 3,3 weiter. Dort setzen wir 90 ein.
Dann in Feld 3,4 60 Mengeneinheiten.
46
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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-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 x 100 100-0-100=0
Bedarf 70 – 70
=0
90 – 50 =
40 -40 =0
130-40 -90
=0
60-60=0 100-100=0
Wir suchen eine zulässige Ausgangslösung mit dem Diagonalverfahren
Wir machen mit Feld 4,4 weiter. Dort können wir aber nichts einsetzen, weil der Bedarf
an Ort IV schon gedeckt ist.
Wir gehen also zu Feld 4,5 weiter und setzen dort die fehlenden 100 Mengeneinheiten ein.
47
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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-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 x 100 100-0-100=0
Bedarf 70 – 70
=0
90 – 50 =
40 -40 =0
130-40 -90
=0
60-60=0 100-100=0
Kosten 2.100 2.500
3.600
= 6.100
2.000
3.150
=5.150 4.500 8.500 26.350
Wir berechnen die Transportkosten für die mit dem Diagonalverfahren gefundene
Ausgangslösung.
48
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Kosten 2.100 6.100 5.150 4.500 8.500 26.350
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,1
49
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
25
2.095
2.550
3.510
6.060
5.150 4.500 8.500 26.305
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,1
Wenn von 2,2 eine Einheit nach 2,1 verschoben wird, muß von 1,1 eine nach 1,2
verschoben werden. Es entstehen die folgenden Kostendifferenzen:
c2,1-c2,2+c1,2-c1,1 in Zahlen: 25-90+50-30=-45
Wir tragen diese Kostendifferenzen nun in alle freien Felder ein.
50
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Die Matrix enthält nun in allen Feldern, die nicht mit Mengen belegt sind, die
Kostenwirkung 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.
51
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
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
Die Lösungsidee besteht nun darin, mit Verschiebungen möglichst viele Mengeneinheiten
auf die Felder mit den grünen negativen Zahlen zu bringen.
Man muß nicht mit dem Feld beginnen, daß die höchsten Einsparungen erbringt.
Die Operation wird solange fortgesetzt, bis keine Einsparungen mehr zu erzielen sind.
Dann ist das Optimum gefunden.
52
Beispiel für das Transportkostenproblem
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
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 3,5 als erstes.
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
60
53
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 3,5 als erstes.
Wenn 60 ME von 3,4 nach 3,5 verschoben werden, müssen zum Ausgleich 60 ME
von 4,5 nach 4,4 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 V
erhöhen sich die Verschiebungskosten um 45 GE/ME.
Wir suchen daher als nächstes das Feld 4,2 aus.
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 100
Bedarf 70 90 130 60 100
Kosten
60
60
54
Beispiel für das Transportkostenproblem
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
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
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
40
55
Beispiel für das Transportkostenproblem
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.
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 V
ohne 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.
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
Bedarf 70 90 130 60 100
Kosten 19.650
40
40
40
56
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,1 als nächstes.
Die Verschiebung von 0 aus Feld 2,2 nach Feld 2,1 verändert allerdings die Gesamtkosten
nicht.
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
57
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,1 als nächstes.
Die Verschiebung von 0 aus Feld 2,2 nach Feld 2,1 verändert allerdings die Gesamtkosten
nicht.
Sie führt allerdings zu Veränderungen der Verschiebungskosten.
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
Bedarf 70 90 130 60 100
Kosten 19.650
58
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 1,3 als nächstes.
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
59
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 2,4 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
60
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 1,1 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
61
Beispiel für das Transportkostenproblem
Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968
Wir wählen das Feld 4,1 als nächstes, das als einziges eine Kostenminderung ermöglicht.
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
62
Beispiel für das Transportkostenproblem
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 optimale
Lösung erreicht sein muß.
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
63
Eine besonders beeindruckende logistische Leistung
Umzug des Flughafens München in der Nacht vom 16./17. Mai 1992
von Riem nach Erding.
64
Das Postkutschen-Problem
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-Kosten
sei die sicherste Strecke.
Der Graph teilt das Problem in Stufen und zeigt die möglichen Wege
von Stufe zu Stufe.
Z
I
H
G
F
E
D
C
B
A
vgl. Hillier u. Lieberman, 1988, S. 316 ff.
Die Aufteilung in Stufen ist wichtig.
Sie vermindert die Zahl möglicher Wege.
65
Das Postkutschen-Problem
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
Die Kosten der Lebensversicherungen von Stufe zu Stufe
Z
H 3
I 4
Z
I
H
G
F
E
D
C
B
A
Das sind unsere Daten
vgl. Hillier u. Lieberman, 1988, S. 316 ff.
66
Das Postkutschen-Problem
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
Z
I
H
G
F
E
D
C
B
A
Die Wahl des jeweils besten Nachfolgers führt zu
A B F I Z mit Kosten von 2+4+3+4 = 13
67
Das Postkutschen-Problem – dynamische Programmierung
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir suchen den Weg mit den geringsten Kosten1
A x1 x2 x3 x4
wobei x4 = Z
Z
I
H
G
F
E
D
C
B
A
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
68
Das Postkutschen-Problem – dynamische Programmierung
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir suchen den Weg mit den geringsten Kosten.
Dabei suchen wir vom Ziel aus.
Es wird auf jeder Stufe der Weg gesucht,
der die Kosten für den Rest der Strecke
minimiert.
Auf der Stufe 4 sind die Kosten 3 oder 4
derzeitiger Ort
s
Kosten
f*4(s)
Zielort
x4*
H 3 Z
I 4 Z
Z
I
H
G
F
E
D
C
B
A
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
69
Das Postkutschen-Problem – dynamische Programmierung
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir gehen eine Stufe in Richtung Start
und berechnen für die Orte E, F und G
die günstigsten Wege. derzeitiger Orts
Kosten
f*4(s)
Zielort
x4*
H 3 Z
I 4 Z
Z
I
H
G
F
E
D
C
B
A
Kosten bei nächstem Ort
derzeitiger
Ort x3s
Ort H Ort I geringste
Kosten
nächster
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
H I
E 1 4
F 6 3
G 3 3
jeweils + 3
jeweils + 4
70
Das Postkutschen-Problem – dynamische Programmierung
E F G
B 7 4 6
C 3 2 4
D 4 1 5
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir gehen eine Stufe in Richtung Start und berechnen für die Orte B, C und D die günstigsten Wege.
Z
I
H
G
F
E
D
C
B
A
derzeitiger
Ort x2s
Kosten bei dem Weg über
E
je + 4
F
je + 7
G
je + 6
geringste
Kosten
nächster 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
derzeitiger
Ort x3s
Kosten bei nächstem Ort
Ort H Ort I geringste
Kosten
nächster
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
die zusätzlichen Kosten
stehen in dieser Spalte
die Kosten der Stufe kommen
aus dieser Matrix
71
Das Postkutschen-Problem – dynamische Programmierung
B C D
A 2 4 3
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst
Z
I
H
G
F
E
D
C
B
A
derzeitiger
Ort x2s
Kosten bei dem Weg über
B C D geringste
Kosten
nächster Ort
A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 C oder D
derzeitiger
Ort x2s
Kosten bei dem Weg über
E
je + 4
F
je + 7
G
je + 6
geringste
Kosten
nächster
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 Kosten
stehen in dieser Spalte
die Kosten der Stufe kommen
aus dieser Matrix
72
Das Postkutschen-Problem – dynamische Programmierung
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst
Z
I
H
G
F
E
D
C
B
A
derzeitiger
Ort x2s
Kosten bei dem Weg über
B C D geringste
Kosten
nächster 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 D
bei 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
73
Das Postkutschen-Problem – dynamische Programmierung
Stufe 1 Stufe 2 Stufe 3 Stufe 4
Z
I
H
G
F
E
D
C
B
A
Jetzt ergibt sich der optimale Weg bzw. die optimalen Wege, die jeweils Kosten von 11 verursachen:
Man startet über C oder über D
bei 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
A D E H ZA C E H Z
A D F I Z
oder
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
4 3 1 3 = 11 3 4 1 3 = 11
3 1 3 4 = 11
74
dynamische Programmierung
Berechnung der Wege
der Stationen der letzten Stufe
zum Ziel
Berechnung der Wege von den
Stationen der vorletzten Stufe
über die Stationen der letzten Stufe
zum Ziel
Berechnung der Wege von den
Stationen der drittletzten Stufe
über die Stationen der vorletzten Stufe
zum Ziel
usw. bis zum Erreichen des Starts
Der Ablauf ist auch vom
Start aus in Richtung Ziel
möglich.
75
Ganzzahlige lineare Optimierung
Es gibt Probleme, bei denen die Variablen nur Werte aus der Menge
der natürlichen Zahlen (einschließlich 0) annehmen können.
Diese Probleme lassen sich mit dem Simplex-Algorithmus i.d.R. nicht lösen.
Bei grafischer Darstellung bedeutet die Beschränkung auf die Menge
natürlicher Zahlen, daß der Lösungsraum aus einer Menge von
Gitternetzpunkten besteht, statt im zweidimensionalen Fall aus einer Fläche.
76
Ganzzahlige lineare Optimierung
Einige ganzzahlige Probleme:
Aus den 30 Mitarbeitern der Forstdirektion sind 2 Teams zu je 5
Mitarbeitern als Nothilfe-Teams zur Unterstützung einer befreundeten
Forstverwaltung auszuwählen.
Das Jagdgatter „Hubertushohn“ will 7 Erntehirsche so an drei Weidmänner
verkaufen, daß der Deckungsbeitrag maximiert wird.
Ein neu ausgewiesenes Stück Bauland ist so in Grundstücke zu 400 m2
und 700 m2 aufzuteilen, daß der Erlös maximiert wird.
Bei einer Organisationsänderung ist das Personal auf die neu gebildeten
Organisationseinheiten zu verteilen.
Zuschnitt-Optimierungen
Bestimmung optimaler Investitionsprogramme
77
Ganzzahlige lineare Optimierung – einfache Aufgabe
Ein Fertighaus-Unternehmen fertigt zwei Produkte, Haus Thea und Haus Theo.
Es gelten folgende Restriktionen
Haus Thea Haus Theo zusammen
maximale Anzahl 5 keine Restriktion 7
Fertigungszeit (Tage) 4 20
Deckungsbeitrag 7.000 GE 22.000 GE
Der Deckungsbeitrag soll maximiert werden.
78
Ganzzahlige lineare Optimierung – einfache Aufgabe
Wir formulieren das lineare Ungleichungssystem
Haus Thea Haus Theo zusammen
maximale Anzahl 5 keine Restriktion 7
Fertigungszeit (Tage) 4 20
Deckungsbeitrag 7.000 GE 22.000 GE
Thea + Theo
79
Ganzzahlige lineare Optimierung – einfache Aufgabe
Schaubild wie Heinrich S. 101
Anzahl der Häuser Typ Thea
Anzahl der Häuser Typ Theo
Durch Verschieben einer Gerade mit der Steigung -7/22 von oben an den
Bereich der Gitternetzpunkte erhält man als Lösung den Punkt 1 Thea, 4 Theo
80
7
7
1
2
1 2
P (1,4)
vgl. Heinrich S. 101
81
Ganzzahlige lineare Optimierung – einfache Aufgabe
Zielfunktion
7000 x Thea + 22000 x Theo = max wir lösen die Ungleichungen
nach Theo auf
nach Theo Aufgelöst
Thea + Theo
82
binäre lineare Optimierung
Die binäre lineare Optimierung zeichnet sich dadurch aus,
daß alleVariablen nur die Werte 0 und 1 annehmen dürfen.
Probleme mit dieser Struktur sind beispielweise:
Das Rucksachproblem des Wanderers:
Der Wanderer hat die Wahl, welche Gegenstände er jeweils einmal in
den Rucksack packen soll, wobei das Gewicht nicht über 10 kg erreichen darf.
Welche Gegenstände müssen eingepackt werden, um den Nutzen zu maximieren?
Der Manager darf sich ein Dienstfahrzeug mit Extras aussuchen, der
Preis darf aber € 50.000 nicht überschreiten. Er will den Nutzen maximieren.
Der Waldbesitzer kann jeweils nur ganze Bestände durchforsten.
Es gelten Restriktionen hinsichtlich der Durchforstungsflächen.
Der Deckungsbeitrag soll maximiert werden.
Zur Aufforstung großer Sturmflächen stehen nicht genügend Pflanzen zur
Verfügung. Welche Flächen werden aufgeforstet, welche bleiben liegen?
Bool´sche Probleme
83
Entscheidungsbaumverfahren - Grundgedanke
Es sollen nicht alle möglichen Lösungen berechnet werden.
Dadurch sind die Verfahren relativ effizient.
84
Entscheidungsbaumverfahren
Banching and Bounding - Vorgehen
Bei Maximierungsaufgaben wird versucht, für den Wert der Zielfunktion
eine Zahl festzulegen, die mit Sicherheit von keiner Lösung überschritten wird
(obere Schranke). Bei einer Minimierungsaufgabe sucht man eine untere
Schranke.
Als Branching wird das Zuweisen von Werten für die Variablen bezeichnet.
Bei Bool´schen Problemen sind das nur 0 und 1, wodurch die grafische
Darstellung erleichtert wird.
Wichtig ist, daß man eine gute Priorisierung vornimmt.
Wenn bei einem 0-1-Problem von Anfang an einigen Variablen die richtigen
Werte zugewiesen werden, sinkt die Zahl der insgesamt zu berechnenden
Lösungen stark.
Das liegt daran, daß man dadurch bei einem Maximierungsproblem gleich
über eine relativ hohe untere Schranke verfügt, die als Kriterium für den
Abbruch der Berechnung eines Astes verwendet wird.
85
Beispiel für Branching und Bounding
Zimmermann, W. 1992, S. 134 ff.
Standorte Baukosten Produktionskapazitäten
Produkt 1 Produkt 2
1 7 15 10
2 8 20 12
3 3 10 8
4 6 18 10
5 2 6 4
Mindestmengen der Produktion 30 24
Ein Unternehmen kann an 5 Standorten eine Fabrik bauen.
In den zu bauenden Fabriken sollen 2 Güter parallel hergestellt werden.
Es sind die Standorte zu bestimmen, an denen kostenminimal gebaut werden
kann, wobei die Mindestmengen produziert werden können.
Da an jedem Standort entweder gebaut oder nicht gebaut werden kann,
ist es ein 1-0-Problem
86
Koeffizientenmatrix und Festlegung der Priorität
Standorte s1 s2 s3 s4 s5 Summe Restriktion
Baukosten 7 8 3 6 2 26
Kapazität
Produkt 115 20 10 18 6 69 >=30
Kapazität
Produkt 210 12 8 10 4 44 >=24
Summe
Kapazität25 32 18 28 10
Kosten
pro
K.-Einheit
.28 .25 .17 .22 .20
Proirität 1 2 5 3 4
87
mathematische Formulierung des Modells
Zielfunktion 7s1 + 8s2 + 3s3 + 6s4 + 2s5 = min
Restriktion für Produkt 1 15s1 + 20s2 + 10s3 + 18s4 + 6s5 >= 30
Restriktion für Produkt 2 10s1 + 12s2 + 8s3 + 10s4 + 4s5 >= 24
0
si =
1
Die Variablenwerte für die Standorte sind
entweder 0 oder 1
bei gleichem Wert der Zielfunktion
ist eine Variante mit höherer Kapazität besser
88
Berechnung des Baumes
Bei der Berechnung des Baumes
werden erst alle Variablen =1
gesetzt.
Die erste Verzweigung besteht dann
aus der Variation s1=0 und s1=1,
weil s1 mit hoher Wahrscheinlichkeit
= 0 ist (Standort 1 nicht gebaut wird).
Start
s1=0
z=19
RP1= 54
RP2=34
s1=1
z=26
RP1= 69
RP2=44
89
Berechnung des Baumes
Start
s1=0
z=19
RP1= 54
RP2=34
s1=1
z=26
RP1= 69
RP2=44
erste Ebene
s1 = 0 oder =1
zweite Ebene
s2 = 0 oder = 1s2=0
z=11
RP1= 34
RP2=22
s2=1
z=19
RP1= 54
RP2=34
s2=0
z=19
RP1= 49
RP2=32
s1=1
z=19
RP1= 54
RP2=34
da RP2 < 24
ist die Variante
unzulässig
90
Berechnung 1. Ebene
Erste Ebene - von links
s1=0 Konstanten Variablen Wert
s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 1 1 19
Restriktion Produkt 1 15 20 10 18 6 0 1 1 1 1 54
Restriktion Produkt 2 10 12 8 10 4 0 1 1 1 1 34
Konstanten Variablen Wert
s1=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 1 1 1 1 26
Restriktion Produkt 1 15 20 10 18 6 1 1 1 1 1 69
Restriktion Produkt 2 10 12 8 10 4 1 1 1 1 1 44
kleinster zulässiger Zielwert = 19
91
Berechnung, 2. Ebenezweite Ebene von links
Konstanten Variablen Wert
s1=0, s2=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 0 1 1 1 11
Restriktion Produkt 1 15 20 10 18 6 0 0 1 1 1 34
Restriktion Produkt 2 10 12 8 10 4 0 0 1 1 1 22
unzulässig wegen Verletzung von RP2
s1=1,s2=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 1 18
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 1 49
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 1 32
zulässig
s1=1, s2=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 1 18
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 1 49
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 1 32
zulässig
s1=1,s2=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 1 1 1 1 26
Restriktion Produkt 1 15 20 10 18 6 1 1 1 1 1 69
Restriktion Produkt 2 10 12 8 10 4 1 1 1 1 1 44
unzweckmäßig, schon bessere Lösung
kleinster zulässiger Zielwert = 18
92
Berechnung 3. Ebenedritte Ebene
Konstanten Variablen Wert
s1=0, s2=1, s4=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 0 1 13
Restriktion Produkt 1 15 20 10 18 6 0 1 1 0 1 36
Restriktion Produkt 2 10 12 8 10 4 0 1 1 0 1 24
unzulässig wegen Verletzung von RP2
s1=0,s2=1,s4=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 1 1 19
Restriktion Produkt 1 15 20 10 18 6 0 1 1 1 1 54
Restriktion Produkt 2 10 12 8 10 4 0 1 1 1 1 34
unzweckmäßig, schon bessere Lösung
s1=1, s2=0,s4=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 0 1 12
Restriktion Produkt 1 15 20 10 18 6 1 0 1 0 1 31
Restriktion Produkt 2 10 12 8 10 4 1 0 1 0 1 22
unzulässig wegen Verletzung von RP2
s1=1,s2=0,s4=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 1 18
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 1 49
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 1 32
kleinster zulässiger Zielwert = 13
93
Berechnung 4. Ebene
vierte Ebene
Konstanten Variablen Wert
s1=0, s2=1, s4=0,s5=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 0 0 11
Restriktion Produkt 1 15 20 10 18 6 0 1 1 0 0 30
Restriktion Produkt 2 10 12 8 10 4 0 1 1 0 0 20
unzulässig wegen Verletzung von RP2
s1=0, s2=1, s4=0,s5=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 0 1 13
Restriktion Produkt 1 15 20 10 18 6 0 1 1 0 1 36
Restriktion Produkt 2 10 12 8 10 4 0 1 1 0 1 24
zulässig, aber keine Verbesserung
s1=1, s2=0,s4=1,s5=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 0 16
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 0 43
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 0 28
zulässig, aber keine Verbesserung
s1=1,s2=0,s4=1,s5=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 1 18
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 1 49
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 1 32
unzweckmäßig
kleinster zulässiger Zielwert = 13
94
Berechnung 5. Ebene
fünfte Ebene – von links
Konstanten Variablen Wert
s1=0, s2=1, s4=0,s5=1,s3=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 0 0 0 8
Restriktion Produkt 1 15 20 10 18 6 0 1 0 0 0 20
Restriktion Produkt 2 10 12 8 10 4 0 1 0 0 0 12
unzulässig wegen Verletzung von RP2 und RP1
s1=0, s2=1, s4=0,s5=1,s3=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 0 1 1 0 1 13
Restriktion Produkt 1 15 20 10 18 6 0 1 1 0 1 36
Restriktion Produkt 2 10 12 8 10 4 0 1 1 0 1 24
zulässig
s1=1, s2=0,s4=1,s5=0,s3=0 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 0 1 0 13
Restriktion Produkt 1 15 20 10 18 6 1 0 0 1 0 33
Restriktion Produkt 2 10 12 8 10 4 1 0 0 1 0 20
unzulässig wegen Verletzung von RP2
s1=1, s2=0,s4=1,s5=0,s3=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5
Zielfunktion 7 8 3 6 2 1 0 1 1 0 16
Restriktion Produkt 1 15 20 10 18 6 1 0 1 1 0 43
Restriktion Produkt 2 10 12 8 10 4 1 0 1 1 0 28
unzweckmäßig
95
Entscheidungsbaum
1-0-Problem
Start
erste Ebene
hier wird die Variable 1
variiert (=0 oder = 1)
zweite Ebene
hier wird zusätzlich
die Variable 2 variiert
dritte Ebene
hier wird zusätzlich
die Variable 3 variiert
96
Entscheidungsbaum Beispiel
Start
1 10
11 182 3
4 9 12 13
5 6 1 14 17
7 8 15 16
unzulässig
Variation von s1
Variation von s2
Variation von s4
Variation von s5
Variation von s3
Variation nach
Priorität
zulässig
unzweckmäßig
97
Entscheidungsbaum
Start
Sobald sich eine Variante
entweder als unzulässig
(nicht mit den Restriktionen
verträglich) oder als
unwirtschaftlich (schlechter
als eine schon berechnete)
erweist, braucht der Ast
des Baumes nicht
weiterverfolgt zu werden.
unzulässig oder
unwirtschaftlich
Ast kann „abgeschnitten“
werden
müssen nicht
berechnet werden
98
Standortwahl mit LP-Modellen
• Wahl der Standorte für Feuerlöschteiche
• Wahl der Standorte für Feuerwachttürme
• Wahl der Standorte für Holzlagerplätze
99
Standortwahl für Feuerlöchteiche
das Set Covering Location Problem
Das Waldgebiet wird in Teilbereiche eingeteilt, die durch ihre Mittelpunkte
repräsentiert werden.
Die Fahrtzeiten (oder Distanzen) zwischen den Knoten werden ermittelt.
Manche Bereiche können dabei herausgenommen werden, z.B. vom
Wald umschlossene landwirtschaftliche Flächen.
Die Feuerlöschteiche können an jedem Knoten positioniert werden.
Das Problem ist damit als 1-0-Problem formuliert. Die Knoten werden
durch die Variablen FT1 .... FTn repräsentiert. Diese können jeweils
den Wert 1 oder 0 annehmen.
Für jeden Knoten gibt es eine Menge benachbarter Knoten, die
in 10 Minuten erreicht werden können. Die Menge dieser Knoten sei
mit N1 ... Nn bezeichnet.
vgl. Werners, 2006, S. 129 ff.
100
Standortwahl für Feuerlöchteiche
Nummer des
Knotens
Nummern der innerhalb
von 10 Min erreichbaren
Knoten
1 1, 2
2 1, 2, 4, 5
3 3, 6
4 2, 4, 5, 7, 8
5 2, 4, 5, 6, 7, 8
6 3, 5, 6
7 4, 5, 7, 8
8 4, 5, 7, 8
n
jjxz
1
Die Anzahl der Löschteiche
soll minimal gehalten werden.
Die Restriktion gewährleistet,
daß jeder Standort in höchstens
10 Minuten von mind. einem Teich
erreicht werden kann.
n
Njij
i
Ix 1
min
vgl. Werners, 2006, S. 129 ff.
101
Standortwahl für Feuerlöchteiche
Die Lösung ist:
an den Knoten 2, 3 und 5 sind Löschteiche zu bauen.
Werners gibt den Lösungsweg nicht an, sondern verweist auf Standardsoftware
102
Standortwahl für Feuerlöchteiche
F1 F2 F3 F4 F5 F6 F7 F8 Summe
F1 x1 x2
F2 x1 x2 x4 x5
F3 x3 x6
F4 x2 x4 x5 x7 x8
F5 x2 x4 x5 x6 x7 x8
F6 x3 x5 x6
F7 x4 x5 x7 x8
F8 x4 x5 x7 x8
alle Variablen sind entweder 0 oder 1
vgl. Werners, 2006, S. 129 ff.
103
Anwendung von Warteschlangen-Modellen
Die Warteschlangen-Theorie ist recht alt.
Die Anwendungen sind vielfältig.
Warteschlangen sind ein wichtiges Anwendungsgebiet für Simulationen.
In der Forst- und Holzwirtschaft liegt es besonders nahe, den
Aufbau und Abbau von Lagerbeständen und Pufferbeständen zu simulieren.
Bedienstation
104
Beispiele für Warteschlangen
in der Forst- und Holzwirtschaft
Der Auftragsbestand eines Holzernte-Unternehmens. Der Auftragseingang
erfolgt unregelmäßig. Die Aufträge sind unterschiedlich groß. Die Abarbeitung
unterliegt zufälligen Unterbrechungen.
Das Holzlager im Hafen. Der Beitransport des Holzes schwankt merklich. Das
Schiff kommt fast regelmäßig (diskontinuierlich). Die Beladungszeit ist
konstant.
Das Holzlager eines Sägewerkes. Der Beitransport schwankt etwas. Der
Einschnitt erfolgt ziemlich kontinuierlich. Das Lager soll insgesamt gering
gehalten werden, aber Betriebsunterbrechungen sind zu vermeiden.
Das Schnittholz-Lager eines Eichenparkett-Werkes. Eine Mindest-Lagerzeit
von x Monaten soll eingehalten werden.
Bearbeitung von Anträgen auf Aufforstungs-Subventionen in einem
zweistufigen Verfahren.
Aus den umliegenden Wäldern wird Holz zu einem Zwischenlager transportiert
und dort stark diskontinuierlich abgefahren (Zug, Schiff). Wie groß muß der
Lagerplatz sein?
105
Fragestellungen für Warteschlangen-Modelle
Wie hoch ist die
Auslastung der
Bedienstation?
Wieviele Stationen
werden gebraucht,
damit die Schlange
nicht länger wird als ..?
Wie lang ist die
Warteschlange?
maximale Wartezeit
minimale Wartezeit
mittlere Wartezeit
Mit welcher Wahrschein-
lichkeit kommt es zu einer
Warteschlange länger als ...?
Bedienstation
Wie verteilt
sich der
Output über
die Zeit?
Ankunft Warteschlange Bedienung Abgang
Wie verteilen
sich die Ankünfte
über die Zeit?
Reicht der Platz
für die Wartenden?
106
Der Klassiker: Postschalter
Kunde
Nr.
Ankunft
zufällig
Abstand zw.
den Kunden
Zeitpunkt,
zu dem
der
Kunde
das
System
betritt
Bediendauer
zufällig
Summe
Bedienzeit
Zeitpunkt,
zu dem der
Kunde das
System
verläßt
Wartezeit
des Kunden
i ai ti bi Summe bj fi wi
Beispiel bei Werners, S. 268
107
„normierte“ Beschreibung von einstufigen
Warteschlangen-Systemen
Warteschlangen-Systeme lassen sich durch drei bzw. fünf Eigenschaften
beschreiben:
Bedien-
stationWarteschlange
Ankunftsprozeß x
Bedienprozeß y
Zahl der Kanäle zSchlangenkapazität a
Anzahl der relevanten
endlich vielen Input-Elemente boft als
unendlich
angenommen
können dann
vernachlässigt werden
die drei
zur Analyse
notwendigen
Eigenschaften
Angabe von 3 oder fünf Kenngrößen
x / y / z / a / b
wobei für die Verteilungen Kennungen
verwendet werden.
108
Verteilungen für den Ankunfts- und Abfertigungsprozeß
• Markov-Verteilung (M)
• Erlang-Verteilung (E)
• beliebige Verteilung (G)
• deterministisch (D)
Warteschlangen können nicht nur simuliert, sondern auch analytisch
behandelt werden.
Bei einfachen Warteschlangen können so Kennzahlen recht einfach
berechnet werden.
Das einfache System M / M / 1 behandelt Zimmermann, H.-J. S. 415 ff.
ausführlich.
Etwas kürzer, aber mit Beispiel findet man es bei Werners, S. 285 ff.
behandelt.
109
Analytische Analyse einfacher Warteschlangen-Systeme
Für ein einfaches Warteschlangen-System
(M,M,1, Markov, Markov, 1 Bedieneinheit)
gibt Werners (S. 286 ff.) die Formeln an und stellt ein Zahlenbeispiel vor.
Formeln für mehrere Systeme auch bei Zimmermann, W. 1992, S. 366 ff.
110
das Warteschlangensystem M / M / 1
durchschnitliche Verkehrsdichte,
durchschnittlich Auslastung der
Bedieneinheit
durchschnittliche Leerzeit einer
Bedieneinheit je Zeiteinheit
mittlere Zahl der Elemente im System
durchschnittliche Länge der Warteschlange
(ohne Bedienung)
111
das Warteschlangensystem M / M / s
durchschnittliche Anzahl der in Bedienung
befindlichen Einheiten
die mittlere Zeit im System
mittlere Wartezeit in der Schlange
durchschnittliche Zeit in der Bedienstation
112
Beispiel Postschalter M / M / 1
nach Werners, S. 287 f.
mittlere Zwischenankunftszeit = 3 min,
also 10 Kunden pro halbe Stunde, also
lambda = 10 (Zeiteinheit ½ Stunde)
Abfertigungszeit durchschnittlich 2 min,
also 15 Kunden pro ½ Stunde
durchschnittliche Verkehrsdichte
durchschnittliche Leerzeit
durchschnittliche Länge der Warteschlange
(ohne Bedienung)
mittlere Wartezeit in der Schlange
Formeln gelegentlich einfügen
113
Wann werden Warteschlangen unendlich lang?
Wenn in der betrachteten Zeiteinheit durchschnittlich mehr Bearbeitungsfälle
ankommen als bedient werden können.
Ankunftsrate > Abfertigungsrate
Bedienstation
114
Beispielaufgabe - Dienstleistungsförster
• Im Forstamt Hirschwald ist die Aufgabe der Betreuung der Privatwaldbesitzer dem Förster Fritz Faulpelz übertragen.
• Fritz Faulpelz ist seiner Meinung nach überlastet und die Kunden klagen über lange Wartezeiten.
• Im Mittel nimmt Fritz Faulpelz im Monat (20 Arbeitstage) 15 Anfragen entgegen.
• Er benötigt im Mittel 1 Arbeitstag zur Bedienung der Kunden.
Wie sind die Klagen im Lichte dieser Informationen zu beurteilen?
Kann es Fritz Faulpelz zugemutet werden, im Monat im Revier
„Alte Tanne“ in der Zeit, in der er keine Anfragen bearbeitet,
5 Rehe zu erlegen?
vgl. Zimmermann, 1992, S. 368
115
Beispielaufgabe - Dienstleistungsförster
Kennzahl Formel und Berechnung Eregebnis
mittlere Ankunftsrate 15/Monat
mittlere Abfertigungsrate 20/Monat
mittlere Auslastung 0,75
Wahrscheinlichkeit, daß kein Kunde wartet
Wahrscheinlichkeit daß ein Kunde anwesend ist
Wahrscheinlichkeit, daß zwei Kunden anwesend sind
Wahrscheinlichkeit, daß drei Kunden anwesend sind
Wahrscheinlichkeit für die Anwesenheit von max. 3
Kunden
Wahrscheinlichkeit für die Anwesenheit von mehr als 3
Kunden
mittlere Schlangenlänge
mittlere Länge der nicht leeren Schlange
mittlere Wartezeit
mittlere Wartezeit in der nicht leeren Schalge
mittlere Verweilzeit