OR-Anwendungen in Forst- und Holzwirtschaft · 2009. 9. 28. · 2 OR-Lehrbücher • Domschke und Drexl (2007): Einführung in Operations Research, Springer-Lehrbuch • Zimmermann,

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


• Transport und Zuordnungsoptimierung

• Ganzzahlige Optimierung

• Kombinatorische Optimierung



• Wahrscheinlichkeitstheoretische Grundlagen

• Entscheidungstheoretische Grundlagen

• Theorie der Spiele

• Simulationstechnik

• Warteschlangensysteme

• Optimale Lagerhaltung


• Graphentheorie

• Lineare Optimierungsprobleme mit spezieller Struktur

• Netzplantechnik

• Ganzzahlige und kombinatorische Optimierung



• Warteschlangentheorie

• Simulation

Zimmermann, W., 1992 Domschke und Drexl 1991, 2007

20

Gliederungsschemata in OR Lehrbüchern


• 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


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


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



Ausgangs-

orte


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 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



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


Feld 4,1 ist das Feld mit den niedrigsten Transportkosten.

32



Ausgangs-

orteBestimmungsorte


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


Feld 3,5 ist das Feld mit den zweitniedrigsten Transportkosten.

33



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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


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



Ausgangs-

orteBestimmungsorte


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



Ausgangs-

orte


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



Ausgangs-

orte


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



Ausgangs-

orte


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




Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.


44



Ausgangs-

orte


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




Dann nach rechts fortzuschreiten, bis Ort 1 nicht menr lieferfähig ist.


45



Ausgangs-

orte


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 machen mit Feld 3,3 weiter. Dort setzen wir 90 ein.

Dann in Feld 3,4 60 Mengeneinheiten.

46



Ausgangs-

orte


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 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



Ausgangs-

orte


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



Ausgangs-

orte


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



Ausgangs-

orte


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



Ausgangs-

orte


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



Ausgangs-

orte


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


Ausgangs-

orte


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,5 als erstes.

Ausgangs-

orte


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



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


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


Ausgangs-

orte


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

Ausgangs-

orte


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



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


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



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


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




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


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




Ausgangs-

orte


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




Ausgangs-

orte


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




Ausgangs-

orte


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



Wir wählen das Feld 4,1 als nächstes, das als einziges eine Kostenminderung ermöglicht.

Ausgangs-

orte


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


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


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


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


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



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



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


E F G

B 7 4 6

C 3 2 4

D 4 1 5


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


B C D

A 2 4 3


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


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


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



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


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



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


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


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


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


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



kleinster zulässiger Zielwert = 19

91

Berechnung, 2. Ebenezweite Ebene von links


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



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



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



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



unzweckmäßig, schon bessere Lösung


92

Berechnung 3. Ebenedritte Ebene


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




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



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




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




93

Berechnung 4. Ebene

vierte Ebene


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




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



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



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



unzweckmäßig


94

Berechnung 5. Ebene

fünfte Ebene – von links


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



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



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




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



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


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


101


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


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


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

Documents

OR-Anwendungen in Forst- und Holzwirtschaft · 2009. 9. 28. · 2 OR-Lehrbücher • Domschke und Drexl (2007): Einführung in Operations Research, Springer-Lehrbuch • Zimmermann,