Operations Research - TUM

Forstliche Wirtschaftslehre - Prof. Dr. Martin Moog 1

TUM School of Management

Operations Research

Prof. Dr. Martin Moog

Lehrstuhl für Forstliche Wirtschaftslehre

Wer vom Ziel nicht weiß, kann den Weg nicht haben.Christian Morgenstern



Gliederung

(1) Allgemeine Einführung– Literatur– Modellbildung

(2) Logistische Prozesse– Reihenfolgeprobleme

• Rundreise• Postkutsche

– Zuordnungsprobleme• Transportproblem• Chinese-Postman Problem

(3) Produktionsplanung und -steuerung

– Optimierung von Losgrößen– Optimierung von Mischungen

– Optimierung der Kapazitätsauslastung

– Optimierung der Maschinenbelegung

– Optimierung des Werkzeugwechsels

– Sonderfall: Ganzzahlige Optimierung

(4) Standortentscheidung und Warteschlangenmodell



(1) Allgemeine Einführung

• Literatur

• Modellbildung



Übersetzungen von OR ins Deutsche

• Unternehmensforschung

• Operationsforschung

• Optimierungsrechnung

• Planungsforschung

• Planungsrechnung

• Optimalplanung

• mathematische Entscheidungsvorbereitung

haben sich nicht durchgesetzt



OR-Lehrbücher• Domschke und Drexl (2007): Einführung in Operations Research, Springer-Lehrbuch

• Zimmermann, Werner (1992) Operations Research – Quantitative Methoden zur Entscheidungsvorbereitung, 6. Auflage, Oldenbourg

• Heinrich, Gert: Operations Research, Oldenbourg, 2007

• Werners, Brigitte (2006) Grundlagen des Operations Research. Springer

• Zimmermann, Hans-Jürgen (2008): Operations-Research. 2. Auflage, Vieweg

• Gohout, Wolfgang (2009): Operations Research. 4. Auflage, Oldenbourg

• Hillier, Frederick S. und Lieberman, Gerald J.: Operations Research, 4. Auflage, 1988, Oldenbourg(übersetzt)

• Henn, R. und Künzi, H. P.: Einführung in die Unternehmensforschung Band I und II, Springer Verlag, 1968

• Müller-Merbach, H.: Operations-Research, 2. Auflage, Vahlen, 1971 (es gibt viele neuere Auflagen)

• Gritzmann, Peter und Brandenberg, René: Das Geheimnis des kürzesten Weges, 3. Auflage, Springer Verlag, 2005

• Ellinger, Beuermann, Leisten: Operations Research, 6. Auflage, Springer, 2003

eine kleine Auswahl



Gliederungsschemata in OR Lehrbüchern (1/2)

• 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



Gliederungsschemata in OR Lehrbüchern (2/2)

• Lineare Optimierung• Spieltheorie• Transportprobleme• Ganzzahlige Optimierung• Binäre Optimierung• Graphentheorie• Netzplantechnik• Simulation

• Grundlagen linearer Optimierung• Modellerweiterungen, Dualität,

Sensitivitätsanalyse• Anwendungen linearer Optimierung• Graphentheorie• Projektplanung• Simulation und

Warteschlangensystem• Lösungen der Aufgaben

Heinrich 2007 Werners 2006



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



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

Kannst Du mir Dein Ziel nicht sagen,brauchst nach Rat Du nicht zu fragen.



Literatur zu OR-Anwendungen in der ForstwirtschaftHÖ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.

Ein Beispiel für eine Darstellung von LP-Modellen für landw. Fragestellungen

Mußhoff, Oliver u. Hirschauer, Norbert: Modernes Agrar-Management. Vahlen 2010

Ein Beispiel für eine Arbeit mit forstlichen Fragestellungen:

Rose, Dietmar: Quantitative Modelle in der strategischen Planung am Beispielder Forstwirtschaft, Hochschulverlag, Freiburg, 1992



OR-Modell für die Flurbereinigung

TUM Faszination Forschung, Dez 2012, S. 22



OR-Modellbildung

Entwicklung vonAlgorithmen

OR im engeren Sinne

OR im weiteren Sinne

Modellbildung und Lösungsfindung



Erste OR-Anwendungen

Zusammenstellung vonSchiffskonvois im WKII

Optimierung derRadarerfassung derFlugbewegungen an derenglischen Küste

kommerzielle Anwendungen nach dem 2. Weltkrieg

unzählige Rechenknechte

Der Krieg ist Vater aller Dinge.



Computereinsatz notwendig

Konrad Zuse

Museum in Hünfeld (Rhön)

Logo der Konrad Zuse Gesellschaft

Z1 – 1938, ein mechanischer RechnerZ2 – 1938 der erste Versuch mit ElektronikZ3 – 1941 der erste funktionsfähige RechnerZ4 – noch in Berlin gebaut, im Allgäu

wiederaufgebaut, an die ETH vermietet.Plankalkül – die erste Programmiersprache (1945)

Konrad Zuse war auch künstlerisch begabt.Bill Gates ließ sich von ihm porträtieren.



Exkurs: MuseenHünfeldPaderborn – Heinz Nixdorf Museums ForumMünchen – Deutsches MuseumBletchley Park (UK)

Fehlt´s Deinem Tun an einem Ziel,nutzt auch ein Rat Dir nicht sehr viel.

Computer Land binär elektronisch

programmierbar

Zuse Z 3 D 5 / 1941 ja nein Lochstreifen

Atanasoff-Berry

USA Sommer 1941 ja ja nein

Colossus UK 1943 ja ja Neuverkabelung

Mark I USA 1944 nein nein Lochstreifen

Zuse Z 4 D 3 / 1945 ja nein Lochstreifen

ENIAC USA 1946 nein nein Neuverkabelung

Quelle: Wikipedia- Stichwort Colossus



Realität(objektiv)

PerceptionBewusstsein

Anspruchsniveaus(subjektiv)

Problem(im Bewusstsein eines

Menschen)

Entschluss

Nicht-quantifizierterelevante Probleme

TatbeständeLösung des

Problems

akzeptabel?

Anpassung der An-Sprüche, Änderung

des Realitätsaus-schnitts

Lösung des Real-Modelles

Lösung des Rechenmodelles

Rechenmodell

Mathematisches Real-Modell

Verbales Modell

Formale Sprache, Abstraktion

Interpretation

Algorithmus

Interpretation

Zusam

men

hän

ge zwisch

en P

rob

lemen

, Mo

dellen

un

d A

lgorith

men

(Zimm

erman

n, 1

99

2, S. 1

)

ja

natürliche Sprache



Improvisation Planung

Fehlen Ziele Deinen Taten,kann man Dir nicht wirklich raten.

Nach einem gängigen Bonmotist Planung das Ersetzen desZufalls durch den Irrtum.

Planungen sind bedingteEntscheidungen. Es gibt nochdie Möglichkeit der Planrevision,wenn die Umweltbedingungennicht so eintreten wie erwartet.



Grundsätzliche Vorgehensweise des OR

reales Problem

mathematisches Modell

Modell-Lösung

Lösungsvorschlagfü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 weitererUmstände ist sinnvoll.



Modelltypen

Modelle

Beschreibungs-modelle

Erklärungs-modelle

oderPrognosemodelle

Entscheidungs-oder

Optimierungs-modelle

Restriktionenin Optimierungs-modellen

Schwerpunkt des OR



Optimierungsmodelle

Optimierungsmodell = Zielfunktion + Nebenbedingungen

maximiere den Deckungsbeitrag

minimiere die Kosten beachte die zur Verfügung stehendenProduktionskapazitäten

bei vorgegebenen Produktionsmengen

Modelle zur Maximierung oder Minimierung

manchmal werden auch Zielwerte vorgegeben



Charakterisierung von Optimierungsmodellen

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



Ein Unternehmen besitzt an mehreren Orten Fabrikhallen.

Es stellt sich die Frage, wie die Abteilungen auf diese Orte verteilt werden sollen.

Die Abteilungen müssen untereinander Güter austauschen. Dadurch entstehenTransportkosten.

Je mehr Güter getauscht werden müssen und je größer die Distanzen sind,desto höher sind die Transportkosten.

C.E. Nugent, Th.E. Vollmann und J. Ruml haben 1968 einen Satz von Beispielenformuliert für 5, 6, 7, 8, 12, 15, 20 und 30 Standorte (Nug5 bis Nug30).

An diesen Beispielen werden Optimierungsprogramme getestet.

Nug12 wurde erstmals 1978 gelöst, Nug15 1979

Nug30 hat 2,65 x 1032 Lösungen. Es wurde mit einem Algorithmus gelöst,der die Lösungen aussondert, unter denen das Optimum nicht sein kann.Gerechnet wurde mit mehr als 1.000 zusammengeschalteten Computern.

FAZ vom 25. 10. 2000

Nug30 – gelöst im Jahr 2000



Vier wichtige Merkmale des OR

• Optimalitätsstreben

• Modellanalytische Vorgehensweise

• Problemquantifizierung

• Entscheidungsvorbereitung

Zimmermann, W., 1992, S. 4



Einteilung der Lösungsverfahren

• analytische Verfahren

• Näherungs-Verfahren

• heuristische Verfahren

• Simulations-Verfahren



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



Typische Fragestellungen

• Losgrößen

• Reihenfolgeprobleme

• Rundreiseprobleme

• Zuordnungsprobleme



(2) Logistische Prozesse

• Reihenfolgeproblem– Rundreise

– Postkutsche

• Zuordnungsproblem– Transportproblem

– Chinese-Postman Problem



Einfache Reihenfolgeprobleme

• Das bekannteste Lehrbuch-Reihenfolgeproblem ist das sogen. Travelling-Salesman-Problem oder Rundreiseproblem.

• Das Rundreiseproblem kann in der Forst- und Holzwirtschaft z.B. in Form einer Minimierung von Umsetzzeiten oder Umsetzkosten auftreten.

• Die Reihenfolge der Bearbeitung von Losen kann aber auch ein Reihenfolgeproblem sein, bei dem es darum gehen kann, die Rüstzeiten oder die Rüstkosten zu minimieren.



Start

1

2

3

3

2

2

1

3

3

1

3

1

2

2

1

Das Reihenfolgeproblem als Ereignisbaum (3 Stationen)

Kombinatorik – kombinatorische Explosion



Ein Beispiel für ein Rundreiseproblem

Die Reihenfolge, in der mit einem Bohr-Roboter Löcherin ein Werkstück gebohrt werden.

Der Bohrkopf beginnt mit dem ersten Loch, bohrt dannnacheinander die Löcher in das Werkstück und mußin die Ausgangsposition zurück, um beim nächstenWerkstück mit demselben Loch anzufangen.

Durch Optimierung der Reihenfolge läßt sich dieProduktivität der Maschine ggf. stark steigern.



Die Geschichte der gelösten Rundreiseprobleme

Jahr Art des Problems und Größe Autor, Algorithmus

1954 49 Städte, Hauptstädte der 48

Staaten der USA + Washingtonwww.math.princeton.edu/tsp/history.html

George Dantzig, Ray Fulkerson, Selmer

Johnson,

Branching and Bounding

1962 Wettbewerb von Proctor &

Gamble

1977 120 Knoten Martin Grötschel

1987 666 Knoten (world tour) Martin Grötschel und Olaf Holland

1991 3.038 Knoten David Applegate, Robert Bixby, Vasek

Chvátal

Die 15.112 Gemeinden in

Rheinland-Pfalz

2004 24.978 Orte in Schweden

vgl. Gritzmann und Brandenberg, 2005, S. 346 ff.

Stark symmetrische Probleme sind mit viel höherem Rechenaufwand verbunden.Ein Problem mit 225 Städten wurde erst 1995 geknackt.



Rundreise-Spiel

Internetseite von Herrn Kollegen Gritzmann, Fakultät für Mathematik

https://www-m9.ma.tum.de/Allgemeines/TravelingSalesman

Wer nicht weiß, wohin zu gehen,bleibt am besten einfach stehen.



E

F

C

D

A

Start undZiel

B

Rundreiseproblem (1/2)

Wie findet man intuitiv eine Lösung?



E

F

C

D

A

Start undZiel

B

Einfach zur jeweilsnächstgelegenen Station!

Algorithmus des besten Nachfolgers

führt tendenziell zulangen Rückwegen

Rundreiseproblem (2/2)

Dieser Algorithmus gehört zu den sog. Greedy-Heuristiken. Die zeichnen sich

dadurch aus, daß ohne Vorausschau die nächstbesten Lösungen gewählt werden.



Start/Ziel A B C

Start/Ziel 11 5 9

A 11 3 4

B 5 3 12

C 9 4 12

Start/Ziel

A

B

C

Es können auch Reisezeiten oderReisekosten sein.

11

9

5

3 4

12

Rundreiseproblem - Beispiel



Algorithmus des besten Nachfolgers (1/5)

Start/Ziel A B C

Start/Ziel 11 5 9

A 11 3 4

B 5 3 12

C 9 4 12

Es wird eine Entfernungsmatrix benötigt,diese ist symmetrisch, wenn Hin- und Rückwege gleichlang sind;die Felder auf der Hauptdiagonalen sind leer bzw. Null.

Bei der Rundreise liegt Start/Ziel fest, die erste Zeile und die erste Spalte sind dadurch bestimmt.

Die Reihenfolge der Spalten und Zeilen gibt die Reihenfolge der Stationen an;die Summe der grünen Felder folglich die Länge der Rundreise, hier 35 = 11+3+12+9.




Start/Ziel A B C

Start/Ziel 11 5 9

A 11 3 4

B 5 3 12

C 9 4 12

Um im Sinne des Algorithmus des besten Nachfolgers den Weg zu bestimmen,muß die Spalte A gegen die Spalte getauscht werden, in der in der ZeileStart/Ziel der kleinste Wert steht.

Es muß also Spalte B gegen Spalte A getauscht werden, dann die Zeilen entsprechend.



Start/Ziel A B C

Start/Ziel 11 5 9

A 11 3 4

B 5 3 12

C 9 4 12

Start/Ziel B A C

Start/Ziel 5 11 9

A 11 3 0 4

B 5 3 12

C 9 12 4

nach Tausch derSpalten A und B




Start/Ziel B A C

Start/Ziel 5 11 9

B 5 3 12

A 11 3 4

C 9 12 4

Start/Ziel B A C

Start/Ziel 5 11 9

A 11 3 0 4

B 5 3 12

C 9 12 4

nach Tausch derSpalten A und B

nach Tausch derZeilen A und B

Die Summe derDistanzen beträgtnun 21 = 5+3+4+9




Start/Ziel B A C

Start/Ziel 5 11 9

B 5 3 12

A 11 3 4

C 9 12 4

nach Tausch derSpalten A und Bund der Zeilen A und B

Es muß jetzt in der Zeile B rechts der Spalte B der kleinste Wert gesuchtwerden. Die Spalte müßte dann an die Position rechts neben Bgetauscht werden, dann entsprechend die Zeilen.

Hier steht aber schon der kleinste Wert an der richtigen Stelle.

Die Lösung lautet also: Start - B – A – C – Ziel


Bei symmetrischen Matrizenist der umgekehrte Weg eine

gleichgute Lösung.



E

F

C

D

AStart und

Ziel

B

Das Rundreiseproblem

Verfahren des sukzessiven Einbausvon Stationenoder des geringsten Umwegs

ersterWegbzw .Schleife

Verfahren des Sukzessiven Einbaus (1/7)



E

F

C

D

AStart und

Ziel

B


ersterWeg

ersterUmweg




E

F

C

D

AStart und

Ziel

B


ersterWeg

ersterUmweg

zweiter Umweg




E

F

C

D

AStart und

Ziel

B


ersterWeg

ersterUmweg

zweiter Umweg

dritter Umweg




E

F

C

D

AStart und

Ziel

B


ersterWeg

ersterUmweg

zweiter Umweg

dritter Umweg

vierter Umweg




E

F

C

D

AStart und

Ziel

B


ersterWeg

ersterUmweg

zweiter Umweg

dritter Umweg

vierter Umweg

fünfter Umweg




Wenn man mit diesem Algorithmus Lösungen für jede mögliche Ausgangsschleife (Start- Station – Ziel) berechnet, erhält manje eine Lösung.Aus diesen Lösungen kann man die beste auswählen.

Das wird wahrscheinlich eine relativ gute Lösung sein, vielleicht kommt sie dem Optimum nahe oder ist das Optimum.




• Das Rundreiseproblem kann dadurch gelöst werden, daß alle möglichen Wege berechnet werden (vollständige Enumeration)

• Die Zahl der möglichen Wege ist sehr groß, der Rechenaufwand dadurch ggf. zu hoch.

• Rechentechnisch erfolgt eine vollständige Enumeration dadurch, daß die Entfernungsmatrix vollständig durchgetauscht wird (vollständige Permutation).

Dabei wird nach jedem Tausch einer Spalte/Zeile die Rundreisestrecke berechnet.

Aus allen Rundreisestrecken wird schließlich die geringste ausgesucht. Deren Stationenfolge ist optimal.

Vollständige Enumeration (1/8)



Start/Ziel A B C

Start/Ziel

A

B

C Rückweg

Tausch Reihenfolge

A gegen B S/Z-B-A-C

A gegen C S/Z-B-C-A

B gegen C S/Z-C-B-A

B gegen A S/Z-C-A-B

C gegen A S/Z-A-C-B

der nächste Tausch C gegen B

würde die Ausgangssituation A-B-C

wiederherstellen.

Die Zeile/Spalte Start/Ziel soll an erster Position bleiben, die anderen sollen vollständig durchgetauscht werden. Also tauschen wir:

in der quadratischen Matrixmit je 3 Zeilen und Spaltengibt es 6 mögliche Reihenfolgender Zeilen bzw. Spalten.

6 = 3!

Die Zahl der Lösungen bei einemRundreiseproblem ist also immer:Zahl der Stationen ohne Start/ZielFakultät.




Tausch Reihenfolge Länge

Ausgangssituation 21

A gegen B S/Z-B-A-C 32

A gegen C S/Z-B-C-A

B gegen C S/Z-C-B-A

B gegen A S/Z-C-A-B

C gegen A S/Z-A-C-B

Start/Ziel A B C

Start/Ziel 9 11 5

A 9 4 12

B 11 4 3

C 5 12 3

Start/Ziel B A C

Start/Ziel 11 9 5

B 11 4 3

A 9 4 12

C 5 3 12

Weglänge: 21 Weglänge: 32

erster Tausch

Rückweg




Start/Ziel B C A

Start/Ziel 11 5 9

B 11 3 4

C 5 3 12

A 9 4 12

Start/Ziel B A C

Start/Ziel 11 9 5

B 11 4 3

A 9 4 12

C 5 3 12


zweiter Tausch





A gegen C S/Z-B-C-A 35

B gegen C S/Z-C-B-A

B gegen A S/Z-C-A-B

C gegen A S/Z-A-C-B



Start/Ziel B C A

Start/Ziel 11 5 9

B 11 3 4

C 5 3 12

A 9 4 12

Start/Ziel C B A

Start/Ziel 5 11 9

C 5 3 12

B 11 3 4

A 9 12 4


dritter Tausch






B gegen C S/Z-C-B-A 21

B gegen A S/Z-C-A-B

C gegen A S/Z-A-C-B



Start/Ziel C A B

Start/Ziel 5 9 11

C 5 12 3

A 9 12 4

B 11 3 4

Start/Ziel C B A

Start/Ziel 5 11 9

C 5 3 12

B 11 3 4

A 9 12 4


vierter Tausch







B gegen A S/Z-C-A-B 32

C gegen A S/Z-A-C-B



Start/Ziel C A B

Start/Ziel 5 9 11

C 5 12 3

A 9 12 4

B 11 3 4

Start/Ziel A C B

Start/Ziel 9 5 11

A 9 12 4

C 5 12 3

B 11 4 3


fünfter Tausch







B gegen A S/Z-C-A-B 32

C gegen A S/Z-A-C-B 35



Start/Ziel C B A

Start/Ziel 5 11 9

C 5 3 12

B 11 3 4

A 9 12 4

Start/Ziel A B C

Start/Ziel 9 11 5

A 9 4 12

B 11 4 3

C 5 12 3

Es gibt zwei gleichwertige Lösungen:

A-B-C und C-B-A

mit je einer Rundreisestrecke von 21


Wenn alle Wege zweiseitig befahrbar sind,(keine Einbahnstraßen und gleich lang), muß es

mindestens zwei gleichgute Lösungen geben.



Das Rundreiseproblem läßt sich auch mit dem sogenannten Ameisen-Algorithmuslösen. Das ist allerdings nur eine Heuristik.

Die Lösungsidee ist den Ameisen abgeschaut, die den Weg vom Bau zur Nahrungmit Pheromonen markieren. Günstige Wege bekommen viele Markierungen.

Der Ameisen-Algorithmus



Reihenfolgeprobleme, bei denen die erste und/oder letzte Stationnicht festliegt, haben n! Lösungen.

Ist die Reihenfolge von 3 Losen so zu bestimmen, dass die Rüstzeitenminimiert werden, ist eine Matrix mit den Zeiten für das jeweiligeUmrüsten aufzustellen

Latten Dielen Balken

Latten 4 3

Dielen 2 4

Balken 5 6

Die gesamte Zeit zum Umrüsten ergibt sich aus der Summe der Felderüber der Hauptdiagonalen.

Ereignisbaum (1/2)



Das Reihenfolgeproblem als Ereignisbaum

(3 Lose: Latten, Dielen, Balken)Start


Dielen Balken

Balken

Latten Balken Dielen Latten

Dielen Balken Latten Latten Dielen

4 3 2 4 6 5


Latten 4 3

Dielen 2 4

Balken 5 6

4 6 3 5 2 4

8 9 5 9 8 9Summe der Umrüstzeiten

Ereignisbaum (2/2)



Bei Müller-Merbach (1971) findet sich eine Lösung des Rundreiseproblemsmit Hilfe der Dynamischen Programmierung.

Das nachfolgend vorgestellten Postkutschenproblem findet man auch im OR-Lehrbuchvon Ellinger, Beuermann und Leisten, 6. Auflage, S. 249 ff., anschließend ein Problemder Produktionsplanung.

Dynamische Programmierung

Beispiel für die Einsparung von Rechenzeit: Ein Reihenfolgeproblem

der Dimension 10x10 hat 1010

Lösungen, die bei einer vollständigen Enumeration berechnet werden

müßten. Gelingt es, dieses Problem in drei Stufen zu fassen, dann sind nur noch 103 Lösungen zu berechnen.



Reduzierung der Problemgröße durch Bildung von Stufen

A B C D E F G H I Ziel

A

B

C

D

E

F

G

H

I

Ziel

Beispiel für die Einsparung von Rechenzeit: Ein Reihenfolgeproblem

der Dimension 10x10 hat 1010

Lösungen, die bei einer vollständigen Enumeration berechnet werden

müßten. Gelingt es, dieses Problem in drei Stufen zu fassen, dann sind nur noch 103 Lösungen zu berechnen.



Ein Reisender will mit der Postkutsche vom Osten in den Westen der USA reisen. Er sucht die sicherste Strecke. Es gibt jeweils Lebensversicherungs-Policen für die Teilstrecken. Die Gesamtstrecke mit den geringsten Lebensversicherungs-Kostensei die sicherste Strecke.Der Graph teilt das Problem in Stufen und zeigt die möglichen Wegevon Stufe zu Stufe.

vgl. Hillier u. Lieberman, 1988, S. 316 ff.

Die Aufteilung in Stufen ist wichtig.Sie vermindert die Zahl möglicher Wege.

Das Postkutschenproblem (1/3)

Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0

ZA C

B

D G

E

F

H

I



B C D

A 2 4 3

E F G

B 7 4 6

C 3 2 4

D 4 1 5

H I

E 1 4

F 6 3

G 3 3

Z

H 3

I 4

Die Kosten der Lebensversicherungen von Stufe zu Stufe

Das sind unsere Daten vgl. Hillier u. Lieberman, 1988, S. 316 ff.

Das Postkutschenproblem (2/3)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0

ZA C

B

D G

E

F

H

I



B C D

A 2 4 3

E F G

B 7 4 6

C 3 2 4

D 4 1 5

H I

E 1 4

F 6 3

G 3 3

Z

H 3

I 4

Die Wahl des jeweils besten Nachfolgers führt zu A B F I Z

mit Kosten von:

Das Postkutschenproblem (3/3)


ZA C

B

D G

E

F

H

I

2 + 4 + 3 + 4 = 13



Berechnung der Wege der Stationen der letzten Stufe

zum Ziel

Berechnung der Wege von denStationen der vorletzten Stufe

über die Stationen der letzten Stufezum Ziel

Berechnung der Wege von denStationen der drittletzten Stufe

über die Stationen der vorletzten Stufezum Ziel

usw. bis zum Erreichen des Starts

Der Ablauf ist auch vom Start aus in Richtung Zielmöglich.

Das Postkutschenproblem – dyn. Programmierung (1/8)



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

Wir suchen den Weg mit den geringsten Kosten1 A x1 x2 x3 x4

wobei x4 = Z



ZA C

B

D G

E

F

H

I



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.Von Stufe 3 nach Stufe 4 sind die Kosten 3 oder 4,die niedrigsten Kosten also 3.

derzeitiger Ort

s

Kosten

f*4(s)

Zielort

x4*

H 3 Z

I 4 Z

Das Postkutschenproblem – dyn. Programmierung (3/8)Stufe 1 Stufe 2 Stufe 3 Stufe 4Stufe 0

ZA C

B

D G

E

FH

I

B C D

A 2 4 3

E F G

B 7 4 6

C 3 2 4

D 4 1 5

H I

E 1 4

F 6 3

G 3 3

Z

H 3

I 4

Wie erreiche ich die Orte der 3. Stufemit geringsten Kosten?



Wir gehen eine Stufe in Richtung Startund berechnen für die Orte E, F und Gdie günstigsten Wege. derzeitiger Ort

s

Kosten

f*4(s)

Zielort

x4*

H 3 Z

I 4 ZKosten bei nächstem Ort

derzeitiger

Ort x3

s

Ort H Ort I geringste

Kosten

also über Ort

E 1+3 = 4 4 + 4 = 8 4 H

F 6+3 = 9 3 + 4 = 7 7 I

G 3 + 3 = 6 3 + 4 = 7 6 H

jeweils + 3

jeweils + 4


ZA C

B

D G

E

FH

I

H I

E 1 4

F 6 3

G 3 3

Wie erreiche ich die Orteder 2. Stufe zu geringsten Kosten?



derzeitiger

Ort x3

s

Kosten bei nächstem Ort

Ort H Ort I geringste

Kosten

also über

Ort

E 1+3 = 4 4 + 4 = 8 4 H

F 6+3 = 9 3 + 4 = 7 7 I

G 3 + 3 = 6 3 + 4 = 7 6 H

Wir gehen eine Stufe in Richtung Start und berechnen für die Orte B, C und D die günstigsten Wege.

derzeitiger

Ort x2

s

Kosten bei dem Weg über

E

je + 4

F

je + 7

G

je + 6

geringste

Kosten

also über

Ort

B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 E oder F

C 3 + 4 = 7 2 + 7 = 9 4 +6 = 10 7 E

D 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 E oder F

die zusätzlichen Kostenstehen in dieser Spalte

die Kosten der Stufe kommen aus dieser Matrix



ZA C

B

D G

E

FH

I

E F G

B 7 4 6

C 3 2 4

D 4 1 5

Wenn ich über E nach B fahre,dann auf dem kürzesten Wegnach E. Andere wären ineffizient.



derzeitiger

Ort x2

s


E

je + 4

F

je + 7

G

je + 6

geringste

Kosten

also über

Ort

B 7 + 4 = 11 4 + 7 = 11 6 + 6 = 12 11 E oder F

C 3 + 4 = 7 2 + 7 = 9 4 +6 = 10 7 E

D 4 + 4 = 8 1 + 7 = 8 5 + 6 = 11 8 E oder F

Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst

derzeitiger

Ort x2

s


B C D geringste

Kosten

also über

Ort

A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 C oder D

die zusätzlichen Kostenstehen in dieser Spalte

die Kosten der Stufe kommenaus dieser Matrix


ZA C

B

D G

E

FH

I

B C D

A 2 4 3

Wenn ich über B nach A fahre,dann auf dem kürzesten Wegzwischen B und Z.Andere Wege wären ineffizient.



Wir gehen eine Stufe in Richtung Start und berechnen nun wie vor für den Start selbst

derzeitiger

Ort x2

s


B C D geringste

Kosten

also über Ort

A 2 + 11 = 13 4 + 7 = 11 3 + 8 = 11 11 C oder D

Jetzt ergibt sich der optimale Weg bzw. die optimalen Wege, die jeweils Kosten von 11 verursachen:

Man startet über C oder über Dbei Wahl von C muß die Reise über E fortgesetzt werden und dann über H

bei Wahl von D kann auch über E und H fortgesetzt werden, oder über F und I


ZA C

B

D G

E

FH

I



Jetzt ergibt sich der optimale Weg bzw. die optimalen Wege, die jeweils Kosten von 11 verursachen:

Man startet über C oder über Dbei Wahl von C muss die Reise über E fortgesetzt werden und dann über Hbei Wahl von D kann auch über E und H fortgesetzt werden, oder über F und I

A D E H ZA C E H Z

A D F I Z

oder4 3 1 3 = 11 3 4 1 3 = 11

3 1 3 4 = 11


ZA C

B

D G

E

FH

I

B C D

A 2 4 3

E F G

B 7 4 6

C 3 2 4

D 4 1 5

H I

E 1 4

F 6 3

G 3 3

Z

H 3

I 4



0

150

10100

1. Durchforstung 2. DurchforstungBestandesbegründung Endnutzung

490

3100

2110

1170

9110

8140

7160

6170

5240

110

Nummer

verbleibendeGrundfläche

In Anhalt an Bettinger u.a. 2009, S. 117

Durchforstungsoptimierung alsdynamische Programmierung

35 Jahre 45 Jahre 55 Jahre



Von der ersten zur zweiten Stufeoder die erste Durchforstung

Ernte in Festmetern diskontierter Erlös

keine Durchforstung ---- ---

schwache Durchforstung 3.378 244.96

mittlere Durchforstung 4.360 316.17

starke Durchforstung 5.352 388.11

Im Lehrbuch von Bettinger sind bei der ersten Durchforstung noch die Kulturkosten abgezogen (250.00 GE). Das ist jedoch nicht nötig, da hier ja die Kulturkosten konstant sind. Die Kulturkosten ändern also am Kapitalwert oder Endwert der Durchforstungen nichts. Daher sind die Zahlen hier zur Vereinfachung leicht verändert. Die Berücksichtigung der Kulturkosten ist aber nötig, wenn auch die Umtriebszeit variabel gestaltet wird. Dann muß

der Beitrag zum Bodenertragswert berechnet werden – darin sind auch die Kulturkosten enthalten.

0 1

0 2

30

0 4




Von der zweiten zur dritten Stufe oder die zweite Durchforstung


keine Durchforstung --- ---



starke Durchforstung 9.343 415.94







1 5

2 6

2 9

2 10

3 7

3 9

3 10

4 8

4 9

4 10




Von der dritten zur vierten Stufeoder die Endnutzung


Endnutzung 44.858 1,225.99

Endnutzung 36.620 1,000.85

Endnutzung 33.804 923.88




5 11

6 11

7 11

8 11

9 11

10 11




Optimale Durchforstung mit dynamischer ProgrammierungEin Beispiel von Bettinger u.a. (2009 S. 116 ff.)

Es geht um einen Douglasienbestand, der mit gegebener Umtriebszeit undzwei Durchforstungen bewirtschaftet werden soll, wobei die Durchforstungenunterbleiben können.

Die Durchforstungen können unterschiedlich stark sein.Sie werden hinsichtlich ihrer Stärke als Absenkung der Grundfläche auf einenbestimmten Wert (Quadratfuß/Hektar) definiert.

Voraussetzung einer solchen Optimierung ist naturgemäß ein vergleichsweiseleistungsfähiges Modell zur Prognose des Wachstums

Eingriffsstärke 1. Durchforstung 2. Durchforstung

schwach Absenkung um 60 GF/ha Absenkung um 60 GF/ha

mittel Absenkung um 70 GF/ha Absenkung um 70 GF/ha

stark Absenkung um 80 GF/ha Absenkung um 80 GF/ha




Die Durchforstungsmöglichkeiten in Baumstruktur

Kultur

ohneGF=170

ohneGF= 240

schwacheGF=170

mittlereGF=110

starkeGF=100

schwacheGF= 110

ohneGF=170

schwacheGF=110

mittlereGF=100

mittlere

GF=100

ohneGF=160

schwacheGF=110

mittlereGF=100

starke

GF= 90

ohneGF=140

schwacheGF=110

mittlereGF=100

GF die jeweils verbleibende Grundfläche (Quadratfuß/Hektar)



Rekursive Lösung, 1. Schritt

Erlös 1. Df. Erlös 2. Df. Erlös der EN Summe

1,225.99

1,000.85

923.88

848.09

669.60

628.60

Wir lösen das Problem jetzt rekursiv, also von der Endnutzung her.Dazu beginnen wir mit der Tabelle, die die diskontierten Endnutzungserlöse auflistete.

Betrachtet man nur diesen Schritt, dann ist natürlich der Weg 5-11 der vorteilhafteste.Aber das berücksichtigt die Stufe vorher nicht – das wollen wir in der nächsten Folie tun.

Man könnte es so ausdrücken:von 5 her kommend wird man

bei der EN mit 1.225 GE belohnt.

5 11

6 11

7 11

8 11

9 11

10 11





1. Df. 2. Df. Erlös EN Summe

--- 1,225.99 1,225.99

--- 1,000.85 1,000.85

353.08 669.60 1,022.68

415.94 628.60 1,044.54

--- 923.88 923.88

275.48 669.60 945.08

339.94 628.60 968.54

--- 848.09 848.09

193.52 669.60 863.12

256.52 628.60 885.12

Wir betrachten jetzt die Wege von Stufe 2 über Stufe 3 zur Endnutzung (Stufe 4)

1 5 11

1 6 11

2 9 11

2 10 11

3 7 11

3 9 11

3 10 11

4 8 11

4 9 11

4 10 11

In A

nh

alt an B

ettinger u

.a. 20

09

, S. 11

7





--- 1,225.99 1,225.99

--- 1,000.85 1,000.85

353.08 669.60 1,022.68

415.94 628.60 1,044.54

--- 923.88 923.88

275.48 669.60 945.08

339.94 628.60 968.54

--- 848.09 848.09

193.52 669.60 863.12

256.52 628.60 885.12

Wir betrachten jetzt die Wege von Stufe 1 über die Stufen 2 u. 3 zur Endnutzung (Stufe 4)markiert jeweils den besten Weg, der für den nächsten Schritt ausgewählt wird

1 5 11

2 6 11

2 9 11

2 10 11

3 7 11

3 9 11

3 10 11

4 8 11

4 9 11

4 10 11

In A

nh

alt an B

ettinger u

.a. 20

09

, S. 11

7





--- --- 1,225.99 1225.99

244.96 415.94 628.60 1289.50

316.17 339.94 628.60 1284.71

388.11 256.52 628.60 1273.23

Wir betrachten jetzt die Wege von Stufe 1 über die Stufen 2 u. 3 zur Endnutzung (Stufe 4)

Wir verlängern nur die jeweils besten Wege nun nach rückwärts weiter.Das sind die mit dem Stern markierten in der vorherigen Folie.So wird das Problem eingegrenzt.Jetzt wird das Ergebnis der ersten Durchforstung hinzugefügt.

Die Kulturkosten müssen, wie oben gesagt, hier nicht berücksichtigt werden.Damit kann aus den die 1. Df. einbeziehenden Lösungen nun die beste Gesamtlösungherausgesucht werden. Es ist die rechts mit dem Stern gekennzeichnete.

0 1 5 11

0 2 10 11

110 3 10

0 4 10 11




Rekursive Rechnung zusammengefasstrekursive Lösung1. Schritt 2. Schritt 3. Schritt

Weg Erlös EN Weg Erlös 2. Df. Zw.-Su. Weg Erlös 1. Df. Summe5 - 11 1.225,99

1 - 5 -11 0,00 1.225,99 *0 - 1 - 5 - 11 0,00 1.225,99

6 - 11 1.000,852 - 6 -11 0,00 1.000,85

7 -11 923,883 - 7 - 11 0,00 923,88

8 -11 848,094 - 8 - 11 0,00 848,09

9 -11 669,602 - 9 -11 353,08 1.022,683 - 9 - 11 275,48 945,084 - 9 - 11 193,52 863,12

10 -11 628,602 - 10 -11 415,94 1.044,54 *

0 - 2 -10 - 11 244,96 1.289,503 - 10 - 11 339,94 968,54 *

0 - 3 -10 - 11 316,17 1.284,714 - 10 -11 256,52 885,12 *

0 - 4 - 10 - 11 388,11 1.273,23



Vorwärtsrechnung

Das Problem muß nicht rekursiv gelöst werden, es kann auch von der Kultur beginnend die günstigste Lösung gesucht werden.

In diesem Fall wird zuerst die erste Durchforstung betrachtet, dann erste und zweite zusammen.Es werden die Wege gesucht, auf dem die „Stationen“ der 3. Stufe (Nrn. 5 bis 10) mit dem jeweils höchsten Erlös erreicht werden.Dann wird zur 4. Stufe (Endnutzung) für diese Wege weitergerechnet.

Es gibt aber Konstellationen, in denen die Vorwärtsrechnung nicht zum Optimum führt.

SensitivitätsanalysenEine naheliegende Erweiterung besteht darin, die zusätzlichen

Kosten zu berechnen, die dadurch entstehen, daß der Weg durch

einen bestimmten Knoten genommen wird.



Vorwärtsrechnung für dasselbe Problem

Vorwärtsrechnung1. Schritt 2. Schritt 3. Schritt

Weg Erlös 1. Df. Weg Erlös 2. Df. Zw.-Su. Weg Erlös EN Summe0 - 1 0,00

0 - 1 - 5 0,00 0,00 *0 - 1 - 5 - 11 1.225,99 1.225,99

0 - 2 244,960 - 2 - 6 0,00 244,96 *

0 - 2 - 6 - 11 1.000,85 1.245,810 - 2 - 9 353,08 598,04 *

0 - 2 - 9 - 11 669,60 1.267,640 - 2 - 10 415,94 660,90 *

0 - 2 - 10 - 11 628,60 1.289,500 - 3 316,17

0 - 3 - 7 0 316,17 *0 – 3 – 7 - 11 923,88 1.240,05

0 - 3 - 9 275,48 591,650 - 3 - 10 339,94 656,11

0 - 4 388,110 - 4 - 8 0 388,11 *

0 - 4 - 8 - 11 848,09 1236,200 - 4 - 9 193,52 581,63

0 - 4 - 10 256,52 644,63



Übungsaufgabe: maximiere die Erntemenge über 3 Durchforstungen(nur Holzmenge)

von nach Holzmenge

0 1 0

0 2 40

1 3 0

1 4 44

2 5 28

3 6 0

3 7 55

4 7 27

4 8 47

5 8 29

6 9 246

7 9 206

8 9 185

1. Durchforstung 1, 2

2. Durchforstung 3, 4, 5

3. Durchforstung 6, 7, 8

Endnutzung 9




98520

3

41

6

7

Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5

Alter 30 Alter 40 Alter 50 Alter 60 Alter 70

von nach Holzmenge

0 1 0

0 2 40

1 3 0

1 4 44

2 5 28

3 6 0

3 7 55

4 7 27

4 8 47

5 8 29

6 9 246

7 9 206

8 9 185



98520

3

41

6

7

Stufe 1 Stufe 2 Stufe 3 Stufe 4 Stufe 5

Verbale Formulierung der Lösungsidee (Vorwärtsrechnung für Reisekosten):Es wird für jeden Knoten auf jeder Stufe kalkuliert, welche Kosten für die möglichen Wege von allen Knoten der vorherigen Stufe entstehen.Da die niedrigsten möglichen Kosten zur Erreichung der Knoten der vorherigenStufe bereits bekannt sind, sind auch für jeden Knoten der aktuellen Stufe die niedrigsten Kosten leicht zu ermitteln.So werden sukzessive für alle Knotenvon Stufe zu Stufe die Wege bestimmt,auf denen sie mit den geringstenKosten erreicht werden,schließlich der Weg (oder dieWege), auf denen das Zielmit den geringstenKosten erreicht wird.



Transportproblem

Von den Ausgangsorten Ai sollen bestimmte Mengen zu denBestimmungsorten Bj transportiert werden.

A1

A3

A2

Z1 Z2 Z3

Die Kosten sind zu minimieren.

als Lösungsverfahren geeignet:der Simplex-Algorithmus

aber die Rechen-zeiten erfordern

effizientereAlgorithmen



Prinzipielle Vorgehensweise der effizienteren Algorithmen

Ermittlung einer Ausgangslösung

Ermittlung einer optimalen Lösung durchein iteratives Verfahren

BeispieleNordwest-Ecken-RegelVogelsches ApproximationsverfahrenSpalten-Minimum-Verfahren

zur Suche der optimalen LösungStepping-Stone-Methode

MODI-Methode

vgl. Heinrich, S. 65 ff.



Das Transportproblem als spezielles Zuordnungsproblem

Es sind n Elemente (Mittel, Personen) so auf k Aufgaben bzw. Stellenoder Orte zu verteilen, daß die Gesamtwirksamkeit maximiert wird.

E1

E3

E2

Z1 Z2 Z3

Ein Spezialfall ist das Stundenplanproblem.Es sind die Lehrer den Klassen und denRäumen zuzuteilen.Ähnlich bei Dienstplänen.



Ein nicht ganz ernstgemeintes Zuordnungsproblem

Töchter Jünglinge

Jakob Joachim Jens Jan Johann Joseph

Tina

Tiziana

Tirolia

Thea

Scheich Schuleiman möchte seine Töchter so verheiraten, daß die Zahlder Kamele maximiert wird.

vgl. Zimmermann, W., 1992, S. 120



Anzahl der Lösungen beim Zuordnungsproblem

Die Anzahl der Lösungen bei einem Zuordnungsproblem von n Sachenzu n Aufgaben ist n! (n Fakultät)

Bei n = 20 sind n! = 20x19x18x17 ....x2x1 = 2.432.902.008.176.640.000 Möglichkeiten

Ein Computer mit einer Arbeitsgeschwindigkeit von 10-6 Sekunden pro Operation(1 Mio. Operationen pro Sekunde) würde bei ununterbrochenem Einsatzfür die Berechnung aller Lösungen 80.000 Jahre benötigen.

kombinatorische Explosion



Ein einfaches Zuordnungsproblem

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

Ein Forstdienstleistungsunternehmen hat 5 Wartungsfahrzeuge mit denStandorten A1, ....., A5.5 Forstmaschinen an den Standorten P1, ...., P5 sind am nächsten Tagzu warten. Welcher Wartungstrupp fährt zu welchem Einsatzort?Gesucht sei die minimale Fahrtstrecke

Die Matrix enthält die Entfernungen zwischen allen Orten




Lösung des einfachen Zuordnungsproblems

Ausgangs-

orte

Bestimmungsorte

P1 P2 P3 P4 P5

A1 8 3 11 13 16

A2 2 8 17 2 7

A3 12 9 4 4 6

A4 5 11 9 7 14

A5 6 8 9 3 13

Fahrtstrecke 3+7+4+5+3 = 22 km




Lösungsmöglichkeiten für Zuordnungsprobleme

• Distributions-Methode• Stepping-Stone-Verfahren (auch Zyklusmethode)• Modi-Verfahren• Ungarische Methode• vollständige Enumeration

Methoden nach Zimmermann, W., 1992, S. 112ff

Die Vorgehensweise (außer bei der vollständigen Enumeration) besteht darin, im ersten Schritt eine Ausgangslösung zu suchen, die dann im zweiten Schritt verbessert wird.Eine gute Ausgangslösung findet man z.B. mit der Vogel´schen Methode.Alternativen sind das Nordwest-Ecken-Verfahren, das Matrixminimumverfahren,die Russel´sche Approximationsmethode, das Zeilen- oder Spaltenfolgeverfahren.



Transportkostenproblem - Vogel‘sches Verfahren (1/11)

Ausgangs-

orte

BestimmungsorteProduktion geliefert Rest

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

gedeckt

Rest

Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968

Die Felder der Matrix enthalten die Transportkosten je Mengeneinheit.

Wir suchen eine gute Ausgangslösung.

Im Beispiel entsprechen die Liefermengen genau den Bedarfsmengen.Das nennt man den Standardfall.

Ist die Summe der Liefermengen größer als der Bedarf, muß man eine Spalte für die überschüssigen Mengen einfügen.



Ausgangs-

orte

Bestimmungsorte Pro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 10

0

60 35 75 25 150

4 20 35 110 90 85 100

Bedarf 70 90 130 60 100

gedeckt

Rest


Wir suchen eine gute Ausgangslösung

Die Lösungsidee ist, zuerst das Feld mit den niedrigsten Transportkosten zu suchen und dort möglichst viele Mengeneinheiten einzusetzen.Dann geht man zum Feld mit den zweitniedrigsten Transportkosten und setztdort möglichst viele Mengeneinheiten ein; u.s.f……..




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 100 60 35 75 25 150

4 20 x 70 35 110 90 85 100 70 30

Bedarf 70 90 130 60 100

gedeckt 70

Rest 70-70 =

0



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




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 100 60 35 75 25 x 100 150 100 50

4 20 x 70 35 110 90 85 100 70 30

Bedarf 70 90 130 60 100

gedeckt 70 100

Rest 0 0



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




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 100 60 35 75 25 x 100 150 100 50

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30 100

Rest 0 90-30

=60

0


Wir suchen eine gute AusgangslösungFeld 2,I ist das Feld mit den drittniedrigsten Transportkosten, aber der Bedarf istschon gedeckt. Das Feld mit den viertniedrigsten Transportkosten ist 4,II, dort können 30 Einheiteneingeplant werden. Damit sind die Lieferungen aus Ort 4 ausgelastet.




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 100 60 35 x 50 75 25 x 100 150 100+50 0

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30 50 100

Rest 0 60 130-50

=80

0


Wir suchen eine gute AusgangslösungFeld 3,III ist das Feld mit den fünftniedrigsten Transportkosten.Vom Ausgangsort 3 sind noch 50 Einheiten lieferbar, die werden dort eingeplant. Damit ist auch Ort 3 nicht mehr lieferfähig.




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 45 x 80 80 75 120 80 40

2 25 90 50 70 60 80

3 100 60 35 x 50 75 25 x 100 150 100+50 0

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30 50+80

=130

100

Rest 0 60 80-80=0 0


Wir suchen eine gute AusgangslösungFeld 1,III ist das Feld mit den sechstniedrigsten Transportkosten.Am Bestimmungsort III werden noch 80 Einheiten benötigt, die werden dort eingeplant. Damit ist der Bedarf an Ort III gedeckt




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 x 40 45 x 80 80 75 120 80+40 0

2 25 90 50 70 60 80

3 100 60 35 x 50 75 25 x 100 150 100+50 0

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+40

=70

50+80 100

Rest 0 60-40

=20

0 0


Wir suchen eine gute AusgangslösungFeld 1,II ist das Feld mit den siebtniedrigsten Transportkosten.Am Bestimmungsort II werden noch 60 Einheiten benötigt, von Ort 1 könnennoch 40 Einheiten geliefert werden. Die werden dort eingeplant Damit ist die Lieferfähigkeit von Ort 1 erschöpft.




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 x 40 45 x 80 80 75 120 80+40 0

2 25 90 50 70 x 60 60 80 60 20

3 100 60 35 x 50 75 25 x 100 150 100+50 0

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+40

=70

50+80 60 100

Rest 0 20 0 60-60=0 0


Wir suchen eine gute AusgangslösungFeld 2,IV ist das Feld mit den siebtniedrigsten Transportkosten.Dort können 60 Einheiten eingeplant werden. Damit ist der Bedarf an Ort IV gedeckt.




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-

liefertRest

I II III IV V

1 30 50 x 40 45 x 80 80 75 120 80+40 0

2 25 90 x 20 50 70 x 60 60 80 60+20 0

3 100 60 35 x 50 75 25 x 100 150 100+50 0

4 20 x 70 35 x 30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+40 +

20=90

50+80 60 100

Rest 0 0 0 0 0


Wir suchen eine gute AusgangslösungNun sind von Ort 2 noch 20 Einheiten zu liefern, und in Ort II werden noch 20 Einheitenbenötigt.Diese werden in Feld 2,II eingeplant.




Ausgangs-

orteBestimmungsorte

ProduktionI II III IV V

1 30 50 x 40 45 x 80 80 75 120

2 25 90 x 20 50 70 x 60 60 80

3 100 60 35 x 50 75 25 x 100 150

4 20 x 70 35 x 30 110 90 85 100

Bedarf 70 90 130 60 100

Kosten

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:




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.

Transportkostenproblem – Nordwest-Ecken-Regel (1/8)



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 der Nord-West-Ecken-Regel

Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem Feld 2,II weitermachen und so fortfahren.





Quell-

orte

Zielorte

I II III IV

1 Wenn 1 mehr

liefern kann als

Zielort I braucht

2 Wenn der Bedarf

von Zielort I

größer ist als die

Lieferfähigkeit

von Quellort 1

Man beginnt in Feld 1,I im Nordwesten und trägt soviele Einheiten wie möglich ein.Ist die Lieferfähigkeit des Quellortes 1 größer als der Bedarf des Zielortes I, trägt man in Feld 1,II soviel Einheiten wie möglich ein – u.s.f. bis Quellort 1nicht mehr lieferfähig ist. Dann geht es in Zeile 2 mit der Spalte weiter, in derder Bedarf noch nicht gedeckt ist.Ist der Bedarf von Zielort I mit der Lieferfähigkeit von Quellort 1 nicht zu decken, geht man in Zeile 2 und trägt möglichst viele Einheiten ein, u.s.f.

Start



Ausgan

gs-orte

Bestimmungsorte Produkti

on

ge-

liefertRest

I II III IV V

1 30 x 70 50 x 50 45 80 75 120 70+50 0

2 25 90 50 70 60 80

3 100 60 35 75 25 150

4 20 35 110 90 85 100

Bedarf 70 90 130 60 100

gedeckt 70 50

Rest 0 40


Wir suchen eine zulässige Ausgangslösung mit der Nord-West-Ecken-Regel

Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem eine Zeile tiefer liegenden Feld weitermachen und so fortfahren.




Aus-

gangs-

orte

BestimmungsorteProdukti

on

ge-

liefertRestI II III IV V

1 30 x 70 50 x 50 45 80 75 120 70+50 0

2 25 90 x 40 50 x 40 70 60 80 40+40 0

3 100 60 35 75 25 150

4 20 35 110 90 85 100

Bedarf 70 90 130 60 100

gedeckt 70 50+40 40

Rest 0 0 90


Wir suchen eine zulässige Ausgangslösung mit dem Nordwest-Ecken-Regel Die Lösungsidee ist, im Feld 1,I anzufangen und dort möglichst viele Mengeneinheiten einzusetzen.Dann nach rechts fortzuschreiten, bis Ort 1 nicht mehr lieferfähig ist.Dann kann man mit dem eine Zeile tiefer liegenden Feld weitermachen und so fortfahren.




Aus-

gangs-

orte


on

ge-


1 30 x 70 50 x 50 45 80 75 120 70+50 0

2 25 90 x 40 50 x 40 70 60 80 40+40 0

3 100 60 35 x 90 75 x 60 25 150 90+60 0

4 20 35 110 90 85 100

Bedarf 70 90 130 60 100

gedeckt 70 50+40 40+90 60

Rest 0 0 0 0


Wir suchen eine zulässige Ausgangslösung mit der Nordwest-Ecken-Regel Wir machen mit Feld 3,III weiter. Dort setzen wir 90 ein.Dann in Feld 3,IV 60 Mengeneinheiten.




Aus-

gangs-

orte


on

ge-


1 30 x 70 50 x 50 45 80 75 120 70+50 0

2 25 90 x 40 50 x 40 70 60 80 40+40 0

3 100 60 35 x 90 75 x 60 25 150 90+60 0

4 20 35 110 90 x 0 85 x100 100 100 0

Bedarf 70 90 130 60 100

gedeckt 70 50+40 40+90 60 100

Rest 0 0 0 0 0


Wir suchen eine zulässige Ausgangslösung mit dem Nord-West-Ecken-Regel Wir machen mit Feld 4,IV weiter. Dort können wir aber nichts einsetzen, weil der Bedarfan Ort IV schon gedeckt ist.Wir gehen also zu Feld 4,V weiter und setzen dort die fehlenden 100 Mengeneinheiten ein.




Aus-

gangs-

orte


on

ge-


1 30 x 70 50 x 50 45 80 75 120 70+50 0

2 25 90 x 40 50 x 40 70 60 80 40+40 0

3 100 60 35 x 90 75 x 60 25 150 90+60 0

4 20 35 110 90 x 0 85 x100 100 100 0

Bedarf 70 90 130 60 100

gedeckt 70 50+40 40+90 60 100

Rest 0 0 0 0 0

Kosten 2.100 2.500

+3.600

= 6.100

2.000

+3.150

=5.150 4.500 8.500 26.350


Wir berechnen die Transportkosten für die mit dem Nordwest-Ecken-Regel gefundene Ausgangslösung.




Transportkostenproblem – Spalten-Minimum-Verfahren

Man beginnt in der linken Spalte.Dort sucht man den Weg mit den geringsten Kosten. Auf diesen setzt man die größtmögliche Menge.Dann sucht man den Weg mit den zweitgeringsten Kosten.Auf diesen setzt man die größtmögliche Menge.So arbeitet man die Spalte ab, bis der Bedarf gedeckt ist.Dann geht man eine Spalte weiter.Dort wiederholt man die Prozedur.




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


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

gedeckt

Rest



Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


1 30 50 45 80 75 120

2 25 90 50 70 60 80

3 100 60 35 75 25 150

4 20x70 35 110 90 85 100 70 30

Bedarf 70 90 130 60 100

gedeckt 70

Rest 0


In Spalte I betragen die minimalen Transportkosten 20 GE/ME.Da der Ort 4 mehr als den Gesamtbedarf von 70 ME liefern kann,ist der Bedarf von I völlig aus 4 zu decken. Spalte I scheidet aus der weiteren Betrachtung aus.



Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


1 30 50x60 45 80 75 120 60 60

2 25 90 50 70 60 80

3 100 60 35 75 25 150

4 20x70 35x30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+60

Rest 0 0




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


1 30 50x60 45 80 75 120 60 60

2 25 90 50 70 60 80

3 100 60 35x130 75 25 150 130 20

4 20x70 35x30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+60 130

Rest 0 0 0




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


1 30 50x60 45 80 75 120 60 60

2 25 90 50 70x60 60 80 60 20

3 100 60 35x130 75 25 150 130 20

4 20x70 35x30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+60 130 60

Rest 0 0 0 0




Aus-

gangs-

orte

BestimmungsortePro-

duktion

ge-


1 30 50x60 45 80 75x60 120 60+60 0

2 25 90 50 70x60 60x20 80 60+20 0

3 100 60 35x130 75 25x20 150 130+20 0

4 20x70 35x30 110 90 85 100 70+30 0

Bedarf 70 90 130 60 100

gedeckt 70 30+60 130 60 20+20+

60

Rest 0 0 0 0 0

Kosten 1.400 3.000

+1.050

= 4.050

4.550 4.200 4.500

+1.200

+ 500

= 6.200

Summe der Kosten: 20.400


Die Lösung ist weniger gut als die nach dem

Vogel´schen Verfahren, aber besser als die nach

der NW-Ecken-Regel.



Ausgangs-

orte


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

Transportkostenproblem – Stepping Stone Verf. (1/15)

Das Stepping-Stone-Verfahren wird auch Zyklusmethode genannt, weil nach einerzyklischen Tauschmöglichkeit gesucht wird, mit der die Transportkosten vermindert

werden können.Ein Beispiel findet man auch in Wikipedia.



Ausgangs-

orte


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,IWenn von 2,II eine Einheit nach 2,I verschoben wird, muß von 1,I eine nach 1,IIverschoben werden. Es entstehen die folgenden Kostendifferenzen:c2,I - c2,II + c1,II - c1,I in Zahlen: 25-90+50-30=-45Wir tragen diese Kostendifferenzen nun in alle freien Felder ein.




Ausgangs-

orte


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, dieKostenwirkung bei Verschiebung einer Mengeneinheit in das bisher unbelegte Feld.

Felder, in die eine Verschiebung zu Mehrkosten führt, enthalten rote Zahlen.Felder, in die eine Verschiebung zu Einsparungen führt, enthalten grüne Zahlen.Die fetten schwarzen Zahlen sind die Mengen der Ausgangslösung.




Ausgangs-

orte


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 Mengeneinheitenauf die Felder mit den grünen negativen Zahlen zu bringen.

Man muß nicht mit dem Feld beginnen, das die höchsten Einsparungen erbringt.

Die Operation wird solange fortgesetzt, bis keine Einsparungen mehr zu erzielen sind.Dann ist das Optimum gefunden.




Ausgangs-

orte


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

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

He

nn

un

d K

ün

zi, Einfü

hru

ng in

die U

ntern

ehm

ensfo

rschu

ng II, S. 2

2 ff.1

96

8

Wir wählen das Feld 3,V als erstes.

60




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

Hen

n u

nd

Kün

zi, Einfü

hru

ng in

die U

ntern

ehm

ensfo

rschu

ng II, S. 2

2 ff.1

96

8

Wir wählen das Feld 3,V als erstes.Wenn 60 ME von 3,IV nach 3,V verschoben werden, müssen zum Ausgleich 60 MEvon 4,V nach 4,IV verschoben werden.Dadurch entstehen für die Lieferungen des Ortes 4 zwar keine Mehrkosten,aber die Rückverschiebung würde in Zeile 3 Mehrkosten von 45 GE verursachen.Deshalb müssen die Verschiebungskosten in Zeile 4 um je 45 GE gemindert werden.Das erhöht die Vorteile einer Verschiebung in diese Felder. In den Spalten IV und Verhöhen sich die Verschiebungskosten um 45 GE/ME.Wir suchen daher als nächstes das Feld 4,II aus.

60

60




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

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

Hen

n u

nd

Kün

zi, Einfü

hru

ng in

die U

ntern

ehm

ensfo

rschu

ng II, S. 2

2 ff.1

96

8

Wir wählen das Feld 4,2 als nächstes. Aus Feld 4,5 lassen sich 40 ME verschieben

40




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

Hen

n u

nd

Kün

zi, Einfü

hru

ng in

die U

ntern

ehm

en

sforsch

un

g II, S. 22

ff.19

68

Wir wählen das Feld 4,II als nächstes. Aus Feld 4,V lassen sich 40 ME verschieben.Zum Ausgleich müssen 40 ME aus Spalte II in die Spalte V verschoben werden.Dies geschieht in zwei Schritten durch Verschiebung von Spalte II in Spalte III und dann in Vohne Mehrkosten.

In Zeile 4 sind die Verschiebungskosten jeweils um die 100 GE/ME zu vermindern.In Spalte IV sind die Verschiebungskosten um 100 GE/ME zu vermindern.

40

40

40




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


Wir wählen das Feld 2,I als nächstes. Die Verschiebung von 0 aus Feld 2,II nach Feld 2,I verändert allerdings die Gesamtkostennicht.




Ausgangs-

orte


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


Wir wählen das Feld 2,I als nächstes. Die Verschiebung von 0 aus Feld 2,II nach Feld 2,I verändert allerdings die Gesamtkostennicht.Sie führt allerdings zu Veränderungen der Verschiebungskosten.




Ausgangs-

orte


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


Wir wählen das Feld 1,III als nächstes.




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


Wir wählen das Feld 2,IV als nächstes.




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


Wir wählen das Feld 1,I als nächstes.




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


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




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

vgl. Henn und Künzi, Einführung in die Unternehmensforschung II, S. 22 ff.1968

Nun weist kein Feld mehr negative Verschiebungskosten auf, so daß eine optimaleLösung erreicht sein muß.


Die Lösung mit dem Vogel´schen Verfahren war: 17.800



Schema der Vorgehensweise des Stepping Stone-Verfahrens

Start

Berechnung einer gültigen Ausgangslösung

Berechnung der Vorteilhaftigkeit von Tausch

Durchführung eines vorteilhaften Tauschs

vorteilhaftmöglich

nein Ende

ja

Das etwas einfachere Modi-Verfahrenfunktioniert nach demselben Schema

Ein Optimum ist gefunden,wenn eine Verbesserungnicht mehr möglich ist.



Transportkostenproblem

Mit dem Excel-Solver läßt sich das Transportkosten-Beispiel aus dem Buch von Henn&Künzi auch lösen.



Die Lösung des Transportkostenproblems

mit dem Excel-Solver



Besonders beeindruckende logistische Leistungen

Umzug des Flughafens München in der Nacht vom 16./17. Mai 1992von Riem nach Erding.

Austausch aller Schilder auf dem Flugfeld des Rhein-Main-Flughafensin einer Nacht (FAZ vom 12.6. 2010).

Umzug der Ministerien von Bonn nach Berlin



Das Problem des Postboten unterscheidet sich vom Problem desHandlungsreisenden dadurch, dass es nicht darum geht, eine Reihe vonOrten zu besuchen, sondern ein Netz auf einem möglichst kurzen Wegvollständig abzulaufen.

Im Graphen kommt es also darauf an, alle Kanten zu durchlaufen, wobeimöglichst wenige (nur kurze) unproduktive Strecken vorkommen sollen.

Praktische Anwendungen könnten z.B. sein:

• eine optimierte Strecken für die Schneeräumung auf den Waldwegen• eine optimierte Strecke für die Begutachtung der Randbäume an Wegen• eine optimierte Strecke für die Prüfung der Wege nach einem Sturm• ein Plan für die Räumung der Gräben der Waldwege mit einem Grader

oder einer Grabenfräse (nicht alle Kanten müssen durchlaufen werden – diese Variante wird auch als rural chinese postman problem bezeichnet)

Das Chinese Postman Problem

eigenes Foto

behandelt u.a. von Dempe u. Schreier: Operations Research, Teubner, 2006, S. 271 ff.



(3) Produktionsplanung und -steuerung

• Optimierung von Losgrößen

• Optimierung von Mischungen

• Optimierung der Kapazitätsauslastung

• Optimierung der Maschinenbelegung

• Optimierung des Werkzeugwechsels

• Sonderfall: Ganzzahlige Optimierung



Optimierung der Bearbeitungsreihenfolge von Losen

• Reihenfolgeprobleme ergeben sich in der industriellen Produktion besonders dann, wenn zur Bearbeitung von Losen mehrere Kapazitätseinheiten nacheinander in Anspruch genommen werden müssen und die Bearbeitung der Lose jeweils unterschiedliche Zeit in Anspruch nimmt. Die Optimierung der Reihenfolge der Bearbeitung führt dann zur Minimierung der Leerzeiten der Kapazitätseinheiten.

• In der Sägeindustrie ist z.B. vorstellbar, dass Einschnitt und Trocknung hintereinandergeschaltet sind. Durch Optimierung der Reihenfolge könnten dann Leerzeiten der Trocknungsanlage vermieden werden.

• Ein solches Reihenfolgeproblem lässt sich mit Johnson´s-Algorithmus elegant lösen.



Es sei ein Reihenfolgeproblem aus 8 Losen betrachtet.

Die Zahl der möglichen Lösungen ist 8! = 40.320

Es liegt eine zweistufige Bearbeitungsfolge vor, wie sie in der Holzindustriebeispielsweise beim Sägen und Trocknen vorkommen könnte, oder bei einemBearbeitungs- und einem Verleimungsprozeß.

Dabei soll es Ziel der Optimierung sein, die Leerzeiten des zweiten Prozesseszu minimieren (Zielfunktion). Bei einem Trockner, einem Brennofen, einer beheizten Presse etc. ist der Zweck offensichtlich (Energieeinsparung).

Es kann aber auch darum gehen, die Arbeitszeit der zweiten Bearbeitungs-stufe zu minimieren, weil diese noch für einen anderen Produktionsprozeßbenötigt wird und daher ein Engpaßfaktor ist.

der vorgestellte Algorithmusfunktioniert auch bei 3 Maschinen

(OR Handbook, in unserem Bestand)

Ein Beispiel (fahrende Künstler) findetman bei Kaufmann u. Faure, Methoden

des OR, Walter de Gruyter, S 231 ff.

Johnson‘s Algorithmus (1/13)



Los Nr. 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20

Die Tabelle zeigt die Zeiteinheiten, die für die Bearbeitung der Lose nötig sind.

grafische Darstellung der Leerzeiten, zufällige Reihenfolge

Stufe 12 6 3 8 7 1 4 5

Stufe 2 8 12 11 20 20 25

10 18 14 15 25 20 12 12

10 10 2 4 5 Leerzeiten




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20

Nun suchen wir uns das Los mit der kürzesten Bearbeitungszeit.

Das ist Los 2, mit 8 Minuten in Stufe 2.

Wenn diese kürzeste Bearbeitungszeit auf Stufe 1 fällt, reihen wir dieses Losan den Anfang.

Wenn die kürzeste Bearbeitungszeit auf die Stufe 2 fällt, reihen wir dieses Losan das Ende.

Wir wiederholen diesen Schritt und tragen das Ergebnis in eine Matrix ein, die in der Waagerechten die Reihenfolge zeigt und in der Senkrechten dieAuswahlschritte (Iterationen).

also an das Ende




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20

Position in der Reihenfolge

1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2

3

4

5

6

7

8

Johnson‘s Algorithmus – 1. Auswahlschritt (4/13)



Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3

4

5

6

7

8




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4

5

6

7

8




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4 (5) 6

5

6

7

8

2 Möglichkeiten




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4 (5) 6

5 5 (6)

6

7

8




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4 (5) 6

5 5 (6)

6 8

7

8




Los 1 2 3 4 5 6 7 8

Stufe 1 20 10 14 12 12 18 25 15

Stufe 2 25 8 11 10 15 12 20 20


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4 (5) 6

5 5 (6)

6 8

7 1 (7)

8 (1) 7

2 Möglichkeiten

Johnson‘s Algorithmus – 7. und 8. Auswahlschritt (10/13)



Position 1. 2. 3. 4. 5. 6. 7. 8.

LOS Nr. 5 8 1 7 6 3 4 2


1. 2. 3. 4. 5. 6. 7. 8.

Au

sw

ah

lsch

ritt

1 2

2 4

3 3

4 (5) 6

5 5 (6)

6 8

7 1 (1)

8 (7) 7

Die Reihenfolge

ist eine optimale Lösung

Johnson‘s Algorithmus – Ergebnis (11/13)



Fräsen

Ai

Schleifen

Bi

Lackieren

Ci

P1 7 6 4

P2 11 5 12

P3 8 3 7

P4 7 5 8

P5 6 3 3

Ai + Bi Bi + Ci

P1 13 10

P2 16 17

P3 11 10

P4 12 13

P5 9 6

Johnsons Algorithmus gibt es auch für eine dreistufige Produktion,Bedingung ist, dass entweder min Ai >= max Bi oder min Ci >= max Bi

Ein Beispiel findetman bei Kaufmann u. Faure, Methoden

des OR, Walter de Gruyter, S 239.

min Ai = 6, max Bi = 6 min Ci = 3, die erste Bedingung ist erfüllt.Es ergeben sich zwei gleichwertige Reihenfolgen:p4, p2, p3, p1 p5 und p4, p2, p1, p3, p5

Johnson‘s Algorithmus – dreistufige Produktion (12/13)



Position in der

Reihenfolge

1. 2. 3. 4. 5.

Au

sw

ah

lsch

ritt

1 P5

2 P1

3 P3

4 P4

5 P2

Ai + Bi Bi + Ci

P1 13 10

P2 16 17

P3 11 10

P4 12 13

P5 9 6 Wird als erste Zeile gestrichen, nach hinten

Wird als zweite Zeile gestrichen, nach hinten

Wird als dritte Zeile gestrichen, nach hinten

Wird als vierte Zeile gestrichen, nach vorne

Ein Beispiel findetman bei Kaufmann u. Faure, Methoden

des OR, Walter de Gruyter, S 239.

Johnson‘s Algorithmus – dreistufige Produktion (13/13)



• Mit der Optimierung von Losgrößen wird versucht, Leerkosten zu vermeiden.

• Leerkosten entstehen oft, wenn zwei Produktionsprozesse aufeinander aufbauen bzw. aneinander anschließen (mehrstufige Produktion) sowie bei Kuppelproduktion.

• Optimierung von Losgrößen besitzt in Forst- und Holzwirtschaft gleichermaßen Bedeutung.

• Sehr anschaulich ist der Sinn von Losgrößen-Optimierung an Produktionsprozessen mit anschließenden Transportvorgängen zu zeigen. Beispielsweise bei der Holzernte, wenn die eingeschlagene Menge bei der Abfuhr den letzten Lastwagen nur zu einem Bruchteil auslastet. Die Transportkosten können dadurch erheblich höher liegen als notwendig.

• Auch wenn Rüstkosten (Einstellung von Maschinen, Werkzeugwechsel) eine Rolle spielt, ist es offensichtlich, daß die Zusammenfassung von Aufträgen zu größeren Losen sinnvoll ist, die gerade so groß sein sollen, daß die Rüstkosten minimal sind.

Optimierung von Losgrößen



• Bei manchen Produktionen ist eine Veränderung des Einsatzes von Produktionsfaktoren in Grenzen möglich. Dadurch stellt sich die Frage der optimalen Mischung dieser Produktionsfunktionen.

• Ein anschauliches Beispiel aus dem Bereich der Holznutzung ist der Betrieb von Holzfeuerungsanlagen, bei denen die Brennstoffzusammensetzung in (teilweise durch vertragliche Vereinbarungen oder rechtliche Vorschriften gegebenen) Grenzen variiert werden kann (Waldhackschnitzel, Altholz, Sägerestholz).

• Die einzelnen Brennstoffe zeichnen sich durch unterschiedliche Preise, unterschiedlichen Heizwert und unterschiedliche Transportkosten aus. Ggf. fallen noch unterschiedliche Kosten der Entsorgung von Reststoffen an.

• Gesucht ist regelmäßig eine kostenminimale Mischung.

• Eine geeignete Methode ist regelmäßig die lineare Programmierung.

Optimierung von Mischungen (1/5)



Restriktionen

Sortiment 1

Sortiment 2

max.Menge

min.Menge

min.Menge

Kapazität

Sortiment 1

Sortiment 2

Zielfunktion undProduktionsmöglichkeiten

Zielfunktion

Optimum

Optimierung von Mischungen – graf. Lösung LP-Modell (2/5)

Ausführliche Darstellung der Linearen Programmierung in Ellinger, Beuermann, Leisten: Operations Research, Springer, 6. Auflage 2003



Zielfunktion undProduktionsmöglichkeiten Die Neigung der Zielfunktion

bestimmt, welche Eckegetroffen wird

Sortiment 1

Sortiment 2 Zielfunktion

Sortiment 1

Zielfunktion

Optimierung von Mischungen – graf. Lösung LP-Modell (3/5)

Sortiment 1 ist relativ zu Sortiment 2 preisgünstig, die Zielfunktion ist steil, die

rechte untere Ecke wird getroffen.

Sortiment 2 ist relativ zu Sortiment 2 preisgünstig, die Zielfunktion ist flach, die

linke obere Ecke wird getroffen.



Start

0 1 2

0 1

3

0 1 0 1

2 2 1 1

2

3

3

1

2

Stoff 1

Stoff 2

Stoff 3

Es ist eine Mischung aus drei Stoffen und drei Teilen herzustellen

Optimierung von Mischungen – Baumstruktur (4/5)



Optimierung einer Brennstoffmischung

Brennstoffe

Energie-

gehalt Preis

Transport-

kosten

Ent-

fernung Kosten Kosten Menge Kosten

relativ GE/t GE/t/km km GE/t

GE/Energie-

einheit

Waldhackschnitzel 0,8 25 0,20 15 28,00 35,00 65 2.275

Sägemehl 0,9 20 0,15 25 23,75 26,39 10 264

Pellets 1 30 0,15 35 35,25 35,25 0 0

Altholz 0,85 18 0,17 40 24,80 29,18 15 438

Rinde 0,5 6 0,25 20 11,00 22,00 10 220

100 3.197

Bedarf Energieeinheiten

100

Restriktionen

Mindest-

mengen

Höchst-

mengen

Waldhackschnitzel 25

Sägemehl 10

Pellets

Altholz 15

Rinde 10

Optimierung von Mischungen (5/5)



• Wenn ein Betrieb Kapazitäten vorhält, die grundsätzlich dieselben Leistungen erbringen, aber eine unterschiedliche Kostenstruktur aufweisen, stellt sich bei schwankender Kapazitätsauslastung die Frage, welche Kapazitätseinheiten zuerst in Betrieb genommen werden sollen, bzw. welche zuerst abgeschaltet werden sollen, wenn die Produktion zurückgefahren werden muß.

• In Forstbetrieben können dies beispielsweise unterschiedliche Holzerntemaschinen sein, in der Holzindustrie Sägelinien mit unterschiedlicher Technologie

• Es gilt grundsätzlich, daß die Kapazitätseinheiten mit der höchsten Fixkostenbelastung zuerst in Betrieb genommen werden müssen (also die Einheiten mit den höchsten variablen Kosten zuerst abgeschaltet werden müssen).

Maschinenbelegung bei steigender Kapazitätsauslastung (1/2)



Fixkosten

Kosten

Auslastung

Maschine I

Maschine II

Maschine III Gesamtkosten

Maschinenbelegung bei steigender Kapazitätsauslastung (2/2)

alle Maschinen

var. Kosten Maschine I

var. Kosten Maschine II

var. Kosten Maschine III



• Bei Maschinen, deren Geschwindigkeit variiert werden kann, sind die Kosten oft abhängig von der Geschwindigkeit (Gutenberg-Produktionsfunktion)

• Von der Geschwindigkeit abhängig sind i.d.R. die Energiekosten, die Ausschußproduktion, ggf. der Kühlmittelverbrauch.

• In der Sägeindustrie sind insbesondere die Sägemaschinen selbst in der Geschwindigkeit variierbar.

• Die Verbrauchsfunktionen können in Kostenkurven überführt werden, um die optimale Geschwindigkeit zu ermitteln.

• Die Geschwindigkeit, bei der die Kosten der Zunahme um eine Einheit gleich den zusätzlichen Erlösen sind, darf nicht überschritten werden.

Optimierung der Maschinengeschwindigkeit (1/2)



Geschwindigkeit

KostenErlöse

Erlöse der zusätzlichenProduktion

Kosten derErhöhung derGeschwindigkeit

OptimaleGeschwindigkeit

Optimierung der Maschinengeschwindigkeit (2/2)



Zu berücksichtigen sind insbesondereKosten des Werkzeugwechsels (Stillstand)Kosten des Schärfens Energiekosten in Abhängigkeit von der Schärfe des WerkzeugsMaterialverluste in Abhängigkeit von der Schärfe des Werkzeugs

Es ist eine Minimierung der Kosten in der Periode vorzunehmen

Optimierung des Werkzeugwechsels (1/3)



Kosten in der Periode

Häufigkeit desWerkzeugwechsel

Stillstand + Schärfen

Energiekostenund Materialverlust


Gesamtkosten



KostenWerkzeugwechsel nach

1 Los 2 Losen 3 Losen 4 Losen

Schärfen

Energie

Material-

verlust

Stillstand u.

Wechseln

Gesamt-

kosten17 12 10 13




Ganzzahlige lineare Optimierung als Lösungsansatz (1/7)

Es gibt Probleme, bei denen die Variablen nur Werte aus der Mengeder 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 Mengenatürlicher Zahlen, daß der Lösungsraum aus einer Menge von Gitternetzpunkten besteht, statt im zweidimensionalen Fall aus einer Fläche.



Einige ganzzahlige Probleme:

Aus den 30 Mitarbeitern der Forstdirektion sind 2 Teams zu je 5 Mitarbeitern als Nothilfe-Teams zur Unterstützung einer befreundetenForstverwaltung auszuwählen.

Das Jagdgatter „Hubertushohn“ will 7 Erntehirsche so an drei Weidmännerverkaufen, 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 gebildetenOrganisationseinheiten zu verteilen.

Zuschnitt-Optimierungen (Weil halbe Sitzflächen nichts nutzen.)

Bestimmung optimaler Investitionsprogramme




Hütte Villa zusammen

maximale Anzahl 5 keine Restriktion 7

Fertigungszeit (Tage) 4 20

Deckungsbeitrag 7.000 GE 22.000 GE

Ein Fertighaus-Unternehmen fertigt zwei Produkte, Haus „Hütte“ und Haus „Villa“.

Es gelten folgende Restriktionen

Der Deckungsbeitrag soll maximiert werden.




Hütte Villa zusammen

maximale Anzahl 5 keine Restriktion 7

Fertigungszeit (Tage) 4 20

Deckungsbeitrag 7.000 GE 22.000 GE

Wir formulieren das lineare Ungleichungssystem

Hütte + Villa <= 7Hütte <= 54 x Hütte + 20 x Villa <= 85

Zielfunktion7.000 x Hütte + 22.000 x Villa = max Das folgende Schaubild zeigt

die Lösungsmöglichkeiten


Es stehen 85 Tage zur Verfügung



Zielfunktion7000 x Hütte + 22000 x Villa = max

wir lösen die Ungleichungennach Villa auf

nach Villa aufgelöst

R1 Hütte + Villa <= 7 Villa <= – Hütte + 7

R2 4 x Hütte + 20 x Villa <= 85 Villa <= – 1/5 Hütte + 17/4

R3 Hütte <= 5 bleibt so

Z Villa = – 7/22 Hütte

Nach Villa aufgelöst sind die Ungleichungen als Restriktionen inden Graphen einzuzeichnen.




Anzahl der Häuser Typ Hütte

An

zah

l de

r H

äuse

r Ty

p V

illa

Zielfunktion: Gerade mit der Steigung -7/22


5

10

5 10 15 20

Z



Anzahl der Häuser Typ Hütte

An

zah

l de

r H

äuse

r Ty

p V

illa

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 Hütte, 4 Villa


5

10

5 10 15 20

P(1/4)

nach Villa aufgelöst

R1 Villa <= – Hütte + 7

R2 Villa <= – 1/5 Hütte + 17/4

R3 Hütte <= 5

Z – 7/22 Hütte

R3

R1 R2

17/4 = 4,25

Z



(4) Standortentscheidungen



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

Ähnlich läßt sich auch eine Naturschutz-Fragestellungbearbeiten: Es sollen x Prozent der Fläche als Naturschutzflächeausgewiesen werden. Es ist zu entscheiden, wie groß dieeinzelnen Flächen gewählt werden sollen. Ähnlich wie bei den Feuerlöschteichen geht es um ein „Netz“von Naturschutzflächen.



Standortwahl für Feuerlöschteiche (1/4)

Das Waldgebiet wird in Teilbereiche eingeteilt, die durch ihre Mittelpunkterepräsentiert werden.Die Fahrtzeiten (oder Distanzen) zwischen den Knoten werden ermittelt.

Manche Bereiche können dabei herausgenommen werden, z.B. vomWald 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 werdendurch 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, diein 10 Minuten erreicht werden können. Die Menge dieser Knoten seimit N1 ... Nn bezeichnet.

vgl. Werners, 2006, S. 129 ff.



Nummer des

Knotens

Nummern der innerhalb

von 10 Minuten

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

j

jxz1

n

Nj

ij

i

Ix 1

Die Anzahl der Löschteichesoll minimal gehalten werden.

Die Restriktion gewährleistet,daß jeder Standort in höchstens10 Minuten von mind. einem Teicherreicht werden kann.

min





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


Das Problem ist ein Bool´sches kombinatorisches Problem.Es kann in eine Baumstruktur gebracht werden. Dann kann es gelöst werden wie untengezeigt wird (Bau von Fabriken, 5 Standorte).



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





• Es sind x Rundholzlose gegeben, die in den y Sägewerken des Unternehmens eingeschnitten werden sollen.

• Die Einschnittkosten in den einzelnen Sägewerken sind unterschiedlich.

• Die Transportkosten zu den einzelnen Sägewerken sind bekannt.

• Die Kapazitäten der Sägewerke sind gegeben (Mindestauslastung 1 Schicht, Obergrenze 3 Schichten).

• Es ist zu berechnen, welche Lose in welchem Werk eingeschnitten werden.

Wahl des Sägewerks – einfache Optimierung (1/6)



Hafen

Meer

Werk 1

Werk 2

Holzeinschläge




Holznutzungen Werk 1 Werk 2 Mengen Kosten

Menge

Ent-

fernung

Trans-

port

Ein-

schnitt Kosten

Ent-

fern

ung

Tran-

sport

Ein-

schnitt Kosten

Werk

1

Werk

2 Summe

Fm km €/km €/Fm €/Fm km €/km €/Fm €/Fm Fm Fm Fm €

Goldberg 340 20 0,12 40 42,4 35 0,1 38 41,5 260 80 340 14.344

Weiltal 570 80 0,11 45 53,8 40 0,18 34 41,2 0 570 570 23.484

Siebental 780 60 0,1 35 41 100 0,12 45 57 780 0 780 31.980

Rotrücken 234 10 0,15 41 42,5 70 0,1 41 48 234 0 234 9.945

Sonnhang 550 50 0,16 37 45 30 0,2 36 42 0 550 550 23.100

Summe 2474 1274 1200 2474 102.853

Kapazität Werk 1 1800

Kapazität Werk 2 1200

Beispiel für eine optimale Zuordnung der an mehreren Waldortenanfallenden Holzmengen zu zwei Sägewerken – Minimierung der Kostenaus Transport und Einschnitt




• Zuordnung von in der Fläche anfallendem Holz zu Verarbeitungsorten (Sägewerken) zur Minimierung der Transportkosten

• Bestimmung optimaler Verarbeitungskapazitäten bei gegebenen Standorten

• Auswahl eines Standortes bei schon bestehenden Standorten und mehreren Alternativen

Wahl des Sägewerks – alternative Fragestellungen (4/6)



• Für die bestehenden Standorte und Holzquellen ist das Modell zu formulieren

• Dann sind die alternativen neuen Werksstandorte und ggf. Holzquellen hinzuzufügen

• Es wird dann geschaut, welcher der alternativen Standorte die insgesamt geringste Erhöhung der Produktionskosten bewirkt.

Wahl des Sägewerks – Neuer Standort (5/6)



• Wie zuvor können Einschlagsorte in einem ersten Schritt Sägewerken zugeordnet werden, wobei die Transportkosten zu den Sägewerken minimiert werden.

• In einem zweiten Schritt können dann die Einschlagsorte mehreren Harvestern zugeordnet werden, wobei die Einschlagskosten minimiert werden.

• In einem dritten Schritt kann für jeden Harvester die Reihenfolge der Schläge optimiert werden, wobei die Umsetzkosten minimiert werden.

Andere sinnvolle Kombinationen, z.B. die Suche nach einer optimalen Reihenfolge zur zeitgerechten Auslieferung bestimmter Aufträge sind genausomöglich.

Wahl des Sägewerks – mehrstufige Optimierung (6/6)



Binäre lineare OptimierungDie binäre lineare Optimierung zeichnet sich dadurch aus, daß alle Variablen nur die Werte 0 und 1 annehmen dürfen.

Probleme mit dieser Struktur sind beispielweise:Das Rucksackproblem des Wanderers:Der Wanderer hat die Wahl, welche Gegenstände er jeweils einmal inden 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, derPreis 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 zurVerfügung. Welche Flächen werden aufgeforstet, welche bleiben liegen?

Bool´sche Probleme



Entscheidungsbaumverfahren - Grundgedanke

Es sollen nicht alle möglichen Lösungen berechnet werden.

Dadurch sind die Verfahren relativ effizient.



Entscheidungsbaum – „1-0-Problem“

Start

erste Ebenehier wird die Variable 1variiert (=0 oder = 1)

zweite Ebenehier wird zusätzlichdie Variable 2 variiert

dritte Ebenehier wird zusätzlichdie Variable 3 variiert

alle Variablen sind 1 oder alle Variablen sind 0



Start

Sobald sich eine Varianteentweder als unzulässig(nicht mit den Restriktionenverträglich) oder alsunwirtschaftlich (schlechterals eine schon berechnete)erweist, braucht der Astdes Baumes nichtweiterverfolgt zu werden.

unzulässig oderunwirtschaftlichAst kann „abgeschnitten“werden

müssen nichtberechnet werden

Entscheidungsbaum



EntscheidungsbaumverfahrenBranching and Bounding – Vorgehen bei Minimierung

Als Branching wird das Zuweisen von Werten für die Variablen bezeichnet.Bei Bool´schen Problemen sind das nur 0 und 1, wodurch die grafischeDarstellung erleichtert wird.Als Bounding bezeichnet man das Abschneiden von Ästen.

Wichtig ist, dass 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, dass man dadurch bei einem Minimierungsproblem gleichüber eine relativ tief liegende untere Schranke verfügt, die als Kriterium für den Abbruch der Berechnung eines Astes verwendet wird.

Die untere Schranke kann man beispielsweise mit einer Heuristik schätzen.Im Laufe der Berechnung kann sie dann ggf. abgesenkt werden, wenn manLösungen findet, die günstiger sind.



EntscheidungsbaumverfahrenBranching and Bounding – Vorgehen bei Maximierung

Die Schranke muss bei Maximierung so gewählt werden, dass man Äste abschneiden kann, für die das Ergebnis unter der Schranke liegt.

Im Laufe der Berechnung kann sie dann ggf. erhöht werden, wenn manLösungen findet, die günstiger sind.



Beispiel für Branching und BoundingZimmermann, 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 werdenkann, wobei die Mindestmengen produziert werden können.Da an jedem Standort entweder gebaut oder nicht gebaut werden kann,ist es ein 1-0-Problem



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

Priorität 1 2 5 3 4

Der Standort mit den relativ höchsten Kosten bekommt die höchste Priorität. So kann man

wahrscheinlich relativ früh Äste streichen.



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

0si =

1

Die Variablenwerte für die Standorte sindentweder 0 oder 1

bei gleichem Wert der Zielfunktionist eine Variante mit höherer Kapazität besser



Berechnung des Baumes (1/9)

Bei der Berechnung des Baumeswerden erst alle Variablen =1 gesetzt.

Die erste Verzweigung besteht dannaus der Variation s1=0 und s1=1,weil s1 mit hoher Wahrscheinlichkeit= 0 ist (Standort 1 nicht gebaut wird).

Start

s1=0z=19

RP1= 54RP2=34

s1=1z=26

RP1= 69RP2=44

Für die Berechnung der Werte der Zielfunktionund der Restriktionen gilt also hier: Alle Standorte außer S1 werden gebaut.



Start

s1=0z=19

RP1= 54RP2=34

s1=1z=26

RP1= 69RP2=44

erste Ebenes1 = 0 oder =1

zweite Ebenes2 = 0 oder = 1

s2=0z=11

RP1= 34RP2=22

s2=1z=19

RP1= 54RP2=34

s2=0z=18

RP1= 49RP2=32

s2=1z=26

RP1=69 RP2=44

da RP2 < 24ist die Variante

unzulässig

Berechnung des Baumes (2/9)Start: Alle Variablen = 1

Liegt die Zielfunktion über einem Wert (Schranke), der sicher unterschritten wird (oder das Optimum ist), dann kann man den Ast wegen Unzweckmäßigkeit

abschneiden.Der in der vorherigen Stufe günstigste Zielwert kann

jeweils verwendet werden.



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

Berechnung des Baumes – Ebene 1 (3/9)



zweite 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=0,s2=1 s1 s2 s3 s4 s5 s1 s2 s3 s4 s5

Zielfunktion 7 8 3 6 2 0 1 1 1 1 19



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, beste der 1. Ebene war 19





dritte 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



zulässig

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, beste der 2. Ebene war 18

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



zulässig





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



unzweckmäßig, denn der kleinste Wert in Stufe 3 war 13

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, denn der kleinste Wert in Stufe 3 war 13





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, denn der kleinste Zielwert in Stufe 4 war 13





Start

1 10

11 182 3

4 9 12 13

5 6 14 17

7 8 15 16

Variation von s1

Variationvon s2

Variationvon s4

Variationvon s5

Variationvon s3

Variation nachPriorität

unzulässig

zulässig

unzweckmäßig

Entscheidungsbaum – Beispiel (8/9)



Start

0 1

7

0 1

8

0 1

8

0 1 0 1

6

0 1

2

0 1

2

0 1

3

0 1

3

Variation von s1

Variationvon s2

Variationvon s4

Variationvon s5

Variationvon s3

Variation nachPriorität

unzulässig

zulässig

unzweckmäßig

Entscheidungsbaum – Beispiel (8/9)

1613



Entscheidungsbaum Beispiel (9/9)

Standorte Zielfunktion Kapazitäten

S1 S2 S3 S4 S5 Baukosten Produkt 1 Produkt 2

nein 20 - 12 10 - 8 nein 6 - 4 36 24

8 3 2 13

15 - 10 nein 10 - 8 18 - 10 nein 43 28

7 3 6 16

15 - 10 nein 10 - 8 18 - 10 6 - 4 49 32

7 3 6 2 18

Auswertung – die drei besten Ergebnisse



Beispiel Holzernte

Aufträge Deckungsbeiträge Ernte-Kapazität Transportkapazität

A1 20 10 12

A2 17 11 8

A3 15 8 8

A4 11 6 6

A5 8 7 9

verfügbar 26 20

Entscheidungsbaum Beispiel Holzernte

Welche Aufträge sollen angenommen werden?

Die Aufgabe besteht darin, den Deckungsbeitrag zu maximieren, unter Einhaltung der beiden Kapazitätsrestriktionen als Nebenbedingung.

Da es eine Maximierungsaufgabe ist, wird man in einer Baumstruktur zuerst alle Variablen auf 0 setzen.



Aufträge

Deckungs-

beiträge

Ernte-

Kapazität DB/EK Priorität

Transport-

kapazität DB/TK Priorität

A1 20 10 2 1 12 1,667 4

A2 17 11 1,545 4 8 2,125 1

A3 15 8 1,875 2 8 1,875 2

A4 11 6 1,833 3 6 1,833 3

A5 8 7 1,143 5 9 0,889 5

Entscheidungsbaum Beispiel Holzernte

Priorisierung

Priorisierung ist nicht einfach. A5 bekommt eindeutig geringe Priorität.A1 und A2 sind hinsichtlich der Kapazitäts-Effizienz sehr unterschiedlichzu beurteilen. A3 ist eher günstig und A4 liegt eindeutig im Mittelfeld.

Die heuristische Lösung, die Aufträge nach der Priorität zu reihen und bis zur Ausschöpfung der Kapazität abzuarbeiten, ist hier eher nicht zu empfehlen.



Das RucksackproblemGegenstand a b c d e f g h Su.Gewicht 3 4 4 6 6 8 8 9 48Wert 3 5 5 10 10 11 11 13 68Wert/Gewicht 1 1,25 1,25 1,67 1,67 1,38 1,38 1,44Priorität 8 6 6 1 1 4 4 3

Es dürfen 5 Dinge in den Rucksack gepackt werden, und der Wert ist zu maximieren.Das Gewicht darf 20 nicht überschreiten.

Einen Schätzwert für die Wert-Schranke erhält man, indem man die wertvollstenDinge aufaddiert, bis das Gewicht von 20 erreicht ist (G = 17 = 9 (h) + 8 (f/g))

Quelle: Petra Mutzel, TU Dortmund, DAP2 SS08

Dinge d e h

Wert 10 10 13

Gewicht 6 6 9

Gewicht kumuliert 6 12 5 von 9 würden noch hineinpassen

Wert kumuliert 10 20 5/9 von 13 = 7,3 also 7 also kumuliert 27



Gegenstand a b c d e f g h Su.

Gewicht 3 4 4 6 6 8 8 9 48

Wert 3 5 5 10 10 11 11 13 68

Wert/Gewicht 1 1,25 1,25 1,67 1,67 1,38 1,38 1,44

Priorität 8 6 6 1 1 4 4 3

Start

1

3

3a

b

c

f

g

0

0

0

0

0

1

3

3

1

4

5

1

4

5

1

8

11

1

8

11

0

0

0

0

0

0

1

3

3

1

4

5

2

7

8

0

0

0

1

4

5

1

3

3

2

7

8

1

4

5

2

8

10

2

7

8

3

11

13

0

0

0

1

4

5

2

8

10

1

3

3

2

7

8

3

11

13

1

4

5

1

8

11

2

12

16

2

12

16

3

16

21

2

11

14

3

12

16

3

15

19

4

19

24

0

0

0

1

8

11

1

4

5

2

12

16

1

4

5

2

12

16

2

8

10

3

16

21

1

3

3

2

11

14

3

12

16

2

7

8

3

15

19

4

11

13

4

19

24

2

7

8

2

7

8

1

8

11

2

16

22

2

12

16

3

20

27

2

12

16

3

20

27

3

16

21

4

24

32

3

19

25

3

15

19

4

20

27

3

15

19

4

23

30

4

19

24

5

27

35

2

11

14

Ist G >=17 erreicht,würde bei der nächstenIteration 20 überschritten.

Ist N=5 erreicht,muß abgebrochen werden.



(5) Warteschlangen-Modelle

Bis wir dran sind, dauert es mindestens ....



Anwendung von Warteschlangen-Modellen

Die Warteschlangen-Theorie ist recht alt.Telefonsysteme

Die Anwendungen sind vielfältig.

Warteschlangen sind ein wichtiges Anwendungsgebiet für Simulationen.

In der Forst- und Holzwirtschaft liegt es besonders nahe, denAufbau und Abbau von Lagerbeständen und Pufferbeständen zu simulieren.

Bedienstation

Zur Zeit sind alle Leitungen belegt!

Bitte haben Sie einen Moment Geduld.



A. K. Erlang (1878 – 1929)

Mathemathiker der Danish Telephone Company

The Theory of Probabilities and Telephone Conversations (1909)

Erste Modelle zur Optimierung einfacher Telefonnetze

Erlang-B-Formel (Erlang-Verlustformel)Wahrscheinlichkeit, daß in einem System ohne Warteraum (z.B. Telefonleitungen)ein Kunde nicht bedient werden kann

Erlang-C-FormelWahrscheinlichkeitsverteilung für die Wartezeit in einem System mit Warteraum und c parallelen Servern.



Die Welt ist voller Warteschlangen

Elemente Servicestelle

Post Kunden Postschalter

Mensa Studenten Essenausgabe

Personenverkehrsunternehmen Fahrgäste Taxis

EDV-System Druckaufträge Drucker

Bürogebäude Fahrgäste Fahrstuhl

Wartung Maschinen Wartungsmechaniker

Gericht Klagen Richter

Krankenhaus Patienten Computertomograph

Autobahn Autos verengte Fahrbahn

Fuhrbetrieb Waren LKW

Forstbehörde Aufforstungsantrag Forstamtsleiter



Warteschlange vor einem Sägewerk

eigenes Foto



Warum Warteschlangen optimieren?

Kunde Service-Anbieter

Wie lange muß ich hier

warten?

Wieviel Wartezeit erträgt mein

Kunde?

Kunden stellen sich nicht an.Kunden springen ab.Kunden wählen beim nächsten Mal einen Konkurrenten

Er kann das Systemgestalten.

Er ist vom Systemabhängig.



Grundelemente von Warteschlangen

Ausgang



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ß muss der

Lagerplatz sein?



Der prinzipielle Warteschlangen-Kalkül



z.B. c.p. höhereKerosinpreise

altes Optimum

In Warteschleifen wirdviel Treibstoff verbraucht.



1,0

mittlereWartezeit

Auslastung

Welches System ist besser?

Warum stehen wir immer in der falschen Schlange?



Bedienstation

Wie verteiltsich der Output überdie Zeit?

Ankunft Warteschlange Bedienung Abgang

Wie hoch ist dieAuslastung derBedienstation?

Wieviele Stationenwerden gebraucht, damit die Schlangenicht länger wird als ..?

Wie lang ist dieWarteschlange?

maximale Wartezeitminimale Wartezeitmittlere Wartezeit

Mit welcher Wahrschein-lichkeit kommt es zu einerWarteschlange länger als ...?

Wie verteilensich die Ankünfteüber die Zeit?

Reicht der Platzfür die Wartenden?

Fragestellungen für Warteschlangenmodelle



Kennzahlen von Warteschlangen-Modellen

Wie viele Kunden sind insgesamt im System?

sind in der Warteschlange?

sind im Bedienprozeß?

Wie lang müssen die Kunden warten bis sie bedient werden?

bis sie abgefertigt sind?

Mit welcher Wahrscheinlichkeit ist die Wartezeit länger als ... ?

ist die gesamte Zeit länger als ...?

ist die Warteschlange länger als ...?

ist das System unbeschäftigt (leer)?



Wie beschreiben wir den Ankunftsprozeß?

Zwischenankunftszeiten



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



Einfache Simulationsrechnungen

Die Anzahl der ankommenden Kundenkann mit der Funktion

Zufallsbereich(Untergrenze;Obergrenze)

modelliert werden. Hier wurden 0 und 4als Unter- bzw. Obergrenze eingesetzt).

Auch die Bearbeitungszeit kann ggf. sosimuliert werden.



Postschalter-Beispiel von Werners (2008, S. 276)

Bediendauer Summe Zeitpunkt des WartezeitKunde ai ti bi Bedienzeit Verlassens

Nummer (zufällig) (zufällig) fi wi1 1 1 1 1 2 0

2 3 4 3 4 7 0

3 2 6 2 6 9 1

4 5 11 2 8 13 0

5 4 15 3 11 18 0

6 1 16 3 14 21 2

7 3 19 1 15 22 2

8 2 21 3 18 25 1

9 2 23 3 21 28 2

10 5 28 2 23 30 0

11 4 32 2 25 34 0

12 1 33 1 26 35 1

13 3 36 2 28 38 0

14 3 39 2 30 41 0

15 1 40 1 31 42 1

16 1 41 1 32 43 1

17 4 45 2 34 47 0

18 5 50 2 36 52 0

19 3 53 3 39 56 0

20 5 58 2 41 60 0

21 4 62 3 44 65 0

22 1 63 3 47 68 2

23 2 65 2 49 70 3

24 2 67 1 50 71 3

25 1 68 2 52 73 3

25 52 22

Abstand zumKunden

bi + Maximum aus ti oder fi - 1

fi –(ti + bi)

Summen

Auslastung = 52/73 = 0,712 = 71%

mittlere Wartezeit= 22/25= 0,88 Minuten pro Kunde

mittlere Schlangenlänge= 22/73 = 0,30 Personen



Simulation mit normalverteilten ZufallswertenDie Monte Carlo-Simulation mit Excel läßt sich realisieren mit Hilfe der Funktion

NORMINV (Arg. 1, Arg. 2, Arg. 3)

Die Funktion NORMINV gibt den Wert der Inversen der Standardnormalverteilung.

Es muss als erstes Argument die Funktion ZUFALLSZAHL ( ) eingesetzt werden.Dann müssen der Mittelwert und die Standardabweichung eingesetzt werden.

Man erhält dann einen mit der eingesetzten Standardabweichung um den eingesetzten Mittelwert streuenden Wert.



Simulations-Software

ARENA

SIMAN

Systems Dynamics

ist prinzipiell gut geeignet,weil auf Levels and Rates basierendund über diskrete Zeitschrittedie Levels ändernd.

Beispiel für eine umfangreichere Simulation:

Seminararbeit von Christoph Kahle

Skilifte in einem Gletscher Skigebiet

Lehrstuhl von Prof. Dr. Klaus G. TroitzschUniversität Koblenz, Fachbereich Informatik

(im Internet verfügbar)

Es gibt (Demo-)Programmeim Internet und auch freie

Software.



Typen der Simulation von Warteschlangen

stochastischeSimulation

kontinuierlich diskret

intervallorientiert ereignisorientiert



(homogene) Markov-KettenDie Simulationen basieren regelmäßig auf sogenannten Markov-Ketten.

Dabei geht es um Zustände und die Übergangswahrscheinlichkeiten, mit denendie Elemente ihre Zustände verändern. Die Zeit wird als diskret behandelt.

1 2 3

Wahrscheinlichkeit = 1 Wahrscheinlichkeit = 1

Wahrscheinlichkeit = 1

Wichtig ist, daß die Überganswahrscheinlichkeiten über die Zeit konstant sind.

Zustände

Für den jeweiligen Übergang sinddie Zustände des Elements in derVergangenheit unerheblich.(stochastischer Prozeß ohne Gedächtnis).

0 1 0

0 0 1

1 0 0

Übergangsmatrix dazu



Exkurs: Markov-Ketten zur Simulation von Altersklassenwald

Akl. IAkl.

IIAkl. III

Wahrscheinlichkeit = 1,0 Wahrscheinlichkeit = 0,9

Wahrscheinlichkeit = 1

Kalamitäts-Wahrscheinlichkeit = 0,1

Altersklassen-flächen

planmäßigeEndnutzung

Kalamitäts-Nutzung

Alterung



„Normierte“ Beschreibung von einstufigen Warteschlangen-Systemen (Kendall-Notation)

Warteschlangen-Systeme lassen sich durch drei bzw. fünf Eigenschaftenbeschreiben:

Bedien-station

Warteschlange

Ankunftsprozeß x

Bedienprozeß y

Zahl der Kanäle zSchlangenkapazität a

Anzahl der relevantenendlich vielen Input-Elemente b

oft alsunendlich

angenommen

können dannvernachlässigt werden

die dreizur Analyse

notwendigenEigenschaften

Angabe von 3 oder fünf Kenngrößenx / y / z / a / bwobei für die Verteilungen Kennungenverwendet werden.



Verteilungen für den Ankunfts- und Abfertigungsprozess

• Markov-Verteilung (M)• Erlang-Verteilung (E)• beliebige Verteilung (G)• deterministisch (D)

Warteschlangen können nicht nur simuliert, sondern auch analytischbehandelt 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.



Bedienstrategien

FIFOLIFO

SIRO (Selection in Random Order)

relative Priorität Bevorzugung mancher Kunden, aber ohneUnterbrechung der laufenden Bedienung.

absolute PrioritätBevorzugung mit Unterbrechung derlaufenden Bedienung

RR (Round Robin)jeder Kunde wird eine Zeiteinheit bedient,dann muß er sich wieder anstellen.



Abarbeitung von Warteschlangen

FIFO first in first out

LIFO last in first out

SIRO zufällige Auswahl des nächsten Kunden (selection in random order)

relative Priorität

Bevorzugung mancher Kunden, aber ohne Unterbrechung der laufenden Abfertigung

absolute Priorität

Bevorzugung mancher Kunden mit Unterbrechung laufender Abfertigungen

RoundRobin (RR)

Jedem Kunden wird die gleiche Zeit zugeteilt, danach muß er sich wieder anstellen



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.

Berechnen Sie die Kennzahlen auch für das Brennholz-Beispiel (2 Bediener).



Das Warteschlangensystem M / M / 1

durchschnittliche Verkehrsdichte je

Zeiteinheit

durchschnittliche Leerzeit einer

Bedieneinheit je Zeiteinheit

durchschnittliche Länge der

Warteschlange (ohne Bedienung)

mittlere Zahl der Elemente im System

mittlere Wartezeit in der Schlange

durchschnittliche Kunden je Zeiteinheit

durchschnittliche Abfertigung je Zeiteinheit

1 – durchschnittliche Verkehrsdichte je Zeiteinheit

(Durchschnittliche Verkehrsdichte je Zeiteinheit)²

Durchschnittliche Leerzeit je Zeiteinheit

Durchschnittliche Verkehrsdichte je Zeiteinheit

Durchschnittliche Länge der Warteschlange ohne Bedingung+


durchschnittliche Abfertigung je

Zeiteinheit

durchschnittliche Abfertigung je

Zeiteinheit


* -



Beispiel Postschalter M / M / 1 (nach Werners, S. 287 f.)mittlere Zwischenankunftszeit = 3 Minuten (durchschnittlich alle 3 Minuten kommt ein Kunde)

Durchschnittliche Kunden je Zeiteinheit => 10 Kunden pro halbe Stunde (Zeiteinheit ½ Stunde)

Durchschnittliche Abfertigungszeit = 2 min => 15 Kunden pro halbe Stunde

durchschnittliche Verkehrsdichte =10/15 = 66,66%

durchschnittliche Leerzeit = 1- 10/15 = 1/3 = 33,33%

durchschnittliche Länge der Warteschlange

(ohne Bedienung)(2/3)²/(1-2/3) = 4/3 = 1,33

mittlere Wartezeit in der Schlange= 15/[10/(10-15)] = 2/15 (Zeiteinheiten)

(2/15) * 30 Min = 4 min



Das Warteschlangensystem M / M / s

Wahrscheinlichkeit für ein leeres System

Wahrscheinlichkeit, daß gewartet werden

muß, daß also s oder mehr Elemente im

System sind

mittlere Schlangenlänge, bezogen auf alle

Einheiten

mittlere Anzahl der Einheiten im System

(unendlich, FIFO)Mehr-Kanal-System mit parallelen Kanälen undunendlichem Warteraum bei FIFO-Abarbeitung

Zimm

erman

n, 1

99

2, S. 3

70

f.)



Das Warteschlangensystem M / M / s

mittlere Wartezeit in der Schlange

mittlere Verweilzeit im System

mittlere Länge der nicht-leeren Schlange

mittlere Wartezeit in der nicht-leerenSchlange

(unendlich, FIFO)

Mehr-Kanal-System mit parallelen, identisch leistungsfähigen Kanälen undunendlichem Warteraum bei FIFO-Abarbeitung

Zimmermann, 1992, S. 370 f.)



Ankunftsrate und Bedienzeit

Wie viele Kunden kommen pro Zeiteinheit?

Das Forstamt gibt im Rathaus am Freitag von 8 bis 12 Uhr Brennholz-Sammelscheineaus. Der Förster rechnet mit 5 Kunden pro Stunde

Die Ankunftsrate Lamda (λ) beträgt also :

5 Kunden/Stunde oder 5/60 Kunden pro Minute.

Wie viele Kunden werden pro Zeiteinheit bedient?

Es ist zu erwarten, daß die Bedienung eines Brennholz-Kunden 15 Minuten dauert.

Bedienzeit (b) = 15 Minuten pro Kunde



Durchsatz

Wie viele Kunden werden pro Zeiteinheit bedient?

Der Durchsatz (μ) ist der Kehrwert der Bedienzeit.

Bedienzeit im Beispiel 15 Minuten pro Kunde.

Durchsatz (μ) = 1 Kunde pro 15 Minuten = 1/15

Kehrwert von 15 ist 0,066, also ist der Durchsatz (μ) 0,066 Kunden pro Minuteoder 4 Kunden pro Stunde.



Auslastung (ρ) (Rho)

Wie stark ist das System ausgelastet?

Ist das System leistungsfähig genug? Können alle Kunden bedient werden?

Im Beispiel ist offensichtlich: 20 Kunden werden erwartet, aber nur 16 können abgefertigt werden, wenndie Ausgabe mit einem Bediener besetzt wird.

Die Auslastung ρ berechnet sich als Ankunftsrate/Abfertigungsrate = λ / μ

Im Beispiel ρ = 5 / 4 = 1,25

Es gibt also bei nur einem Bediener einen Stau; um 12 Uhr stehen noch Kunden an(falls sie nicht abgesprungen sind).

Bei Auslastungen < 1 gibt es zwar auch ggf. Stau, aber alle Kunden könnten bedientwerden.



Wann werden Warteschlangen unendlich lang?

Wenn in der betrachteten Zeiteinheit durchschnittlich mehr Bearbeitungsfälleankommen als bedient werden können.

Ankunftsrate > Abfertigungsrate

Bedienstation



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



Beispielaufgabe - DienstleistungsförsterKennzahl Formel und Berechnung Ergebnis

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 Schlange

mittlere Verweilzeit



Beispielaufgabe Skiwettkampf

Sie organisieren die Europameisterschaft der Förster im Skilaufen.

Es werden am Ankunftstag 500 Teilnehmer erwartet, die sich an Schalternanmelden sollen. Sie rechnen mit 10 Minuten Anmeldezeit pro Sportler.

Die Schalter sollen von 8 Uhr bis 18 Uhr geöffnet sein.

Wie viele Schalter brauchen Sie, damit kein Sportler mehr als 20 Minuten warten muß?

Wie viele Schalter brauchen Sie, damit die Wartezeit im Durchschnitt 30 Minuten beträgt?

M/M/s/ unendlich/FIFO



Beispielaufgabe Weihnachtsbaumverkauf

Bei dem vom Forstamt Hirschwald geplanten Weihnachtsbaumverkauf dürfendie Kunden sich den stehenden Baum aussuchen. Wenn sie sich entschieden haben,rufen sie Wilhelm Waldarbeiter, der den Baum absägt und ihnen zur Vermessung trägt. Der Baum wird von Fritz Förster gemessen und genetzt. Dann müssen die Kunden den Baum selbst in ihr Auto verladen.

Es stellt sich die Frage, wieviel Parkplätze bei gegebenen Ankunftsraten benötigt werden.

Zeit von der Ankunft bis zur Entscheidung

Wartezeit auf Wilhelm Waldarbeiter

Arbeitszeit von WW

Wartezeit auf Fritz Förster

Arbeitszeit von FF

Zeit zum Verladen



Psychologie des Wartens









































Warteschlangenmodelle



1515

10

5

10

10

5

10

15

10

5

Fabrik

Documents

Operations Research - TUM