Theoretische Konzeption und praktische Implementierung von Lernsoftware für ausgewählte Bereiche des Operations Research: Transportalgorithmen
©2004
Diplomarbeit
83 Seiten
Zusammenfassung
Inhaltsangabe:Einleitung:
Der Transport von Waren, vom Ort der Produktion zu den Märkten, war schon immer ein bedeutender Bestandteil in der Wirtschaft. Für den Standort eines Unternehmens ist auch heute noch die Anbindung an die Verkehrswege von entscheidender Bedeutung, da der Transport von Waren einen nicht zu unterschätzenden Kostenfaktor darstellt.
Im Zeitalter der Globalisierung und des Internets rücken die Entfernungen zwischen dem Ort der Produktion und dem Ort des Konsums immer weiter auseinander. Große internationale Konzerne produzieren in Ländern mit niedrigen Arbeitslöhnen und können trotz riesiger Transportstrecken bessere Preise als lokale Produzenten, anbieten. Der Vorteil der billigeren Produktion gegenüber möglichen Konkurrenten kann nur solang ein Vorteil sein, bis die Kosten für den Transport der Waren zum Markt den Produktionskostenvorteil aufheben. Aus diesem Grund sollten die Transportkosten so niedrig wie möglich gehalten werden, denn mit der Einsparung von Transportkosten steigt der Gewinn des Unternehmens. Die Kostensenkung durch eine Reduzierung der Transportkosten wird mit der Planung und Auswahl von optimalen Transportwegen erreicht. Durch ein Unternehmen sind häufig folgende Entscheidungen zu treffen: Was wird von welchen Produktionsstandort, zu welchem Markt, zu welcher Zeit und zu welchen Kosten transportiert. Diese Entscheidungen sind so komplex und wichtig für das Unternehmen, dass fundierte Methoden angewendet werden müssen, die den Entscheidungsträgern eines Unternehmens die Entscheidungsfindung erleichtern.
Die Notwendigkeit logistischer und anderer kriegsstrategischer Entscheidungen während des zweiten Weltkrieges erforderten die Entwicklung mathematischer Methoden für eine optimale Lösung der Entscheidungsprobleme. Aus diesem kriegsstrategischen Zusammenhang entstand in England und den USA ab dem Jahr 1940 das Operations Research (OR), dass sich genau mit dieser Thematik auseinandersetzte.
Eine Definition, was Operations Research besonders charakterisiert, wurde durch die OR-Gesellschaft Operational Research Society beschrieben: Unter Operations Research versteht man die Anwendung von wissenschaftlichen Erkenntnissen auf das Problem der Entscheidungsfindung in der Unsicherheits- oder Risikosituation, mit dem Ziel, den Entscheidungsträgern bei der Suche nach optimalen Lösungen eine quantitative Basis zu liefern. Dabei können grundsätzlich Erkenntnisse aus allen wissenschaftlichen Disziplinen herangezogen […]
Der Transport von Waren, vom Ort der Produktion zu den Märkten, war schon immer ein bedeutender Bestandteil in der Wirtschaft. Für den Standort eines Unternehmens ist auch heute noch die Anbindung an die Verkehrswege von entscheidender Bedeutung, da der Transport von Waren einen nicht zu unterschätzenden Kostenfaktor darstellt.
Im Zeitalter der Globalisierung und des Internets rücken die Entfernungen zwischen dem Ort der Produktion und dem Ort des Konsums immer weiter auseinander. Große internationale Konzerne produzieren in Ländern mit niedrigen Arbeitslöhnen und können trotz riesiger Transportstrecken bessere Preise als lokale Produzenten, anbieten. Der Vorteil der billigeren Produktion gegenüber möglichen Konkurrenten kann nur solang ein Vorteil sein, bis die Kosten für den Transport der Waren zum Markt den Produktionskostenvorteil aufheben. Aus diesem Grund sollten die Transportkosten so niedrig wie möglich gehalten werden, denn mit der Einsparung von Transportkosten steigt der Gewinn des Unternehmens. Die Kostensenkung durch eine Reduzierung der Transportkosten wird mit der Planung und Auswahl von optimalen Transportwegen erreicht. Durch ein Unternehmen sind häufig folgende Entscheidungen zu treffen: Was wird von welchen Produktionsstandort, zu welchem Markt, zu welcher Zeit und zu welchen Kosten transportiert. Diese Entscheidungen sind so komplex und wichtig für das Unternehmen, dass fundierte Methoden angewendet werden müssen, die den Entscheidungsträgern eines Unternehmens die Entscheidungsfindung erleichtern.
Die Notwendigkeit logistischer und anderer kriegsstrategischer Entscheidungen während des zweiten Weltkrieges erforderten die Entwicklung mathematischer Methoden für eine optimale Lösung der Entscheidungsprobleme. Aus diesem kriegsstrategischen Zusammenhang entstand in England und den USA ab dem Jahr 1940 das Operations Research (OR), dass sich genau mit dieser Thematik auseinandersetzte.
Eine Definition, was Operations Research besonders charakterisiert, wurde durch die OR-Gesellschaft Operational Research Society beschrieben: Unter Operations Research versteht man die Anwendung von wissenschaftlichen Erkenntnissen auf das Problem der Entscheidungsfindung in der Unsicherheits- oder Risikosituation, mit dem Ziel, den Entscheidungsträgern bei der Suche nach optimalen Lösungen eine quantitative Basis zu liefern. Dabei können grundsätzlich Erkenntnisse aus allen wissenschaftlichen Disziplinen herangezogen […]
Leseprobe
Inhaltsverzeichnis
ID 8322
Lautner, Stefan: Theoretische Konzeption und praktische Implementierung von
Lernsoftware für ausgewählte Bereiche des Operations Research: Transportalgorithmen
Hamburg: Diplomica GmbH, 2004
Zugl.: Universität Leipzig, Diplomarbeit, 2004
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2004
Printed in Germany
I. Inhaltsverzeichnis
1 Einleitung... 1
2 Transportoptimierung... 3
2.1 Einführung in die Transportoptimierung... 3
2.2 Definition und Modellformulierung des Transportproblemes... 4
2.3 Initialisierung des Transportproblemes... 8
2.4 Die Eröffungsverfahren... 11
2.4.1 Das Nord-West-Ecken-Verfahren... 11
2.4.2 Das Kostenminimierungsverfahren... 14
2.4.3 Das Vogelsche Approximationsverfahren... 15
2.4.4 Degeneration des Transportproblemes... 16
2.5 Die Modifizierte Distributionsmethode... 17
3 Konzeption der Lernsoftware... 23
3.1 Theoretische Konzeption... 23
3.2 Spezifika einer Lernsoftware... 27
3.3 Auswertung der Anwendererwartung (Fragebogen)... 31
3.4 Zusammenfassung: Der SOLL-Zustand... 35
4 Praktische Implementierung der Lernsoftware... 40
4.1 System- und Komponentenentwurf... 40
4.2 Implementierung der Transportalgorithmen... 44
4.2.1 Implementierung Nord-West-Ecken-Verfahren... 44
4.2.2 Implementierung Kostenminimierungsverfahren... 48
4.2.3 Implementierung Vogelsches Approximationsverfahren... 49
4.2.4 Implementierung des MODI-Verfahrens... 51
4.3 Besonderheiten bei der Implementierung einer Lernsoftware... 57
4.4 Erweiterungsfähigkeit der Software... 60
5 Zusammenfassung... 63
I
II. Abkürzungsverzeichnis
Bsp
Beispiel
bzw.
beziehungsweise
CAI
Computer Assisted Instruction
CBT
Computer Based Training
CUL
computergestütztes Lernen
d.h.
das heisst
GE
Geldeinheiten
GUI
Graphic User Interface
MODI-Methode
Modifizierte Distributionsmethode
MPS
Mathematical Programming Structure
MVC
Model-View-Control
NBV
Nichtbasisvariable
OR
Operations Research
OSI
Online Simplex Instructor
PAP
Programmablaufplan
RapTOr
Rapid Transport Optimizer
UCM
Use-Case-Modell
UML
Unified Modeling Language
u.a.
und andere
usw.
und so weiter
VAM
Vogelsche Approximationsverfahren
vgl.
vergleiche
VM
Virtuelle Maschine
z.B.
zum Beispiel
II
III. Symbolverzeichnis
i...n
Zeilen
j...m
Spalten
a
i
Angebotsmenge i
A
i
Angebotsort i
b
j
Bedarfsmenge
B
j
Bedarfsort
c
ij
Transportkosten pro Einheit
c
ij
Schlupf (Opportunitätskosten)
u
i
Potential zwischen Angebotsort A
i
und Bedarfsort B
j
v
j
Potential zwischen Bedarfsort B
j
und Angebotsort A
i
x
ij
Transportmenge von Angebotsort A
i
zum Bedarfsort B
j
Transportmengenänderung entlang des Zyklus
Ablaufpläne
Ergebnis :
=x
Wertzuweisung von x an Ergebnis in Algorithmen
i
Erhöhe die Zeile um den Wert 1
j
Erhöhe die Spalte um den Wert 1
min
a
i
, b
j
Minimum zwischen Angebots- und Bedarfsmenge
min
c
ij
Minimum der Transportkosten pro Einheit bestimmen
//
Kommentarzeile
III
IV. Abbildungs- und Tabellenverzeichnis
Abbildungsverzeichnis
Abbildung 2-1 Beispiel übertragen in das Transporttableau... 13
Abbildung 2-2 Ausgangslösung des Nord-West-Ecken-Verfahrens... 14
Abbildung 2-3 Ausgangslösung des Kostenminimierungsverfahrens...15
Abbildung 2-4 Ausgangslösung des VAM... 16
Abbildung 2-5 Transporttableau nach Berechnung der Ui und Vj... 19
Abbildung 2-6 Transporttableau, kleinster Schlupf ist markiert... 20
Abbildung 2-7 Basislösung nach abgeschlossener MODI-Iteration...22
Abbildung 3-1 Wasserfallmodell... 23
Abbildung 3-2 Interaktionszyklus... 28
Abbildung 4-1 Use-Case-Diagramm der Lernsoftware RapTOr... 42
Abbildung 4-2 Pseudocode des Nord-West-Ecken-Verfahrens... 45
Abbildung 4-3 Pseudocode des Kostenminimierungsverfahrens... 49
Abbildung 4-4 Pseudocode des Vogelschen Approximationsverfahren... 50
Abbildung 4-5 Pseudocode für die Berechnung der Potentiale Ui und Vj... 52
Abbildung 4-6 Pseudocode für die Berechnung des Schlupfes... 53
Abbildung 4-7 Pseudocode Suchalgorithmus kleinster Schlupf... 53
Abbildung 4-8 Pseudocode Rekursion: Bestimmung des Zyklus... 55
Tabellenverzeichnis
Tabelle 1 Transportmengenmatrix... 6
Tabelle 2 Einheits-Transportkosten-Matrix... 7
Tabelle 3 Matrix der Transportmethode Transporttableau... 7
Tabelle 4 Erweitertes Transporttableau... 19
IV
1
Einleitung
Der Transport von Waren, vom Ort der Produktion zu den Märkten, war schon
immer ein bedeutender Bestandteil in der Wirtschaft. Für den Standort eines Un-
ternehmens ist auch heute noch die Anbindung an die Verkehrswege von ent-
scheidender Bedeutung, da der Transport von Waren einen nicht zu un-
terschätzenden Kostenfaktor darstellt.
Im Zeitalter der Globalisierung und des Internets rücken die Entfernungen zwi-
schen dem Ort der Produktion und dem Ort des Konsums immer weiter ausein-
ander. Große internationale Konzerne produzieren in Ländern mit niedrigen
Arbeitslöhnen und können trotz riesiger Transportstrecken bessere Preise als lo-
kale Produzenten, anbieten. Der Vorteil der billigeren Produktion gegenüber
möglichen Konkurrenten kann nur solang ein Vorteil sein, bis die Kosten für den
Transport der Waren zum Markt den Produktionskostenvorteil aufheben. Aus
diesem Grund sollten die Transportkosten so niedrig wie möglich gehalten
werden, denn mit der Einsparung von Transportkosten steigt der Gewinn des Un-
ternehmens. Die Kostensenkung durch eine Reduzierung der Transportkosten
wird mit der Planung und Auswahl von optimalen Transportwegen erreicht. Durch
ein Unternehmen sind häufig folgende Entscheidungen zu treffen: Was wird von
welchen Produktionsstandort, zu welchem Markt, zu welcher Zeit und zu welchen
Kosten transportiert. Diese Entscheidungen sind so komplex und wichtig für das
Unternehmen, dass fundierte Methoden angewendet werden müssen, die den
Entscheidungsträgern eines Unternehmens die Entscheidungsfindung erleichtern.
Die Notwendigkeit logistischer und anderer kriegsstrategischer Entscheidungen
während des zweiten Weltkrieges erforderten die Entwicklung mathematischer
Methoden für eine optimale Lösung der Entscheidungsprobleme. Aus diesem
kriegsstrategischen Zusammenhang entstand in England und den USA ab dem
Jahr 1940 das Operations Research (OR), dass sich genau mit dieser Thematik
auseinandersetzte.
Eine Definition, was Operations Research besonders charakterisiert, wurde durch
die OR-Gesellschaft ,,Operational Research Society" beschrieben: ,,Unter Opera-
1
tions Research versteht man die Anwendung von wissenschaftlichen Erkennt-
nissen auf das Problem der Entscheidungsfindung in der Unsicherheits- oder Risi-
kosituation, mit dem Ziel, den Entscheidungsträgern bei der Suche nach optima-
len Lösungen eine quantitative Basis zu liefern. Dabei können grundsätzlich Er-
kenntnisse aus allen wissenschaftlichen Disziplinen herangezogen werden."
1
Die Erkenntnisse und Methoden des Operations Research hielten nach Beendi-
gung des zweiten Weltkrieges Einzug in mathematische Planungsmethoden der
Privatwirtschaft und sind durch den großen Konkurrenzdruck zwischen den Unter-
nehmen unabdingbar geworden. Das Optimalitätsstreben, die modellanalytische
Vorgehensweise, die genaue Problemquantifizierung der Entscheidungsprobleme
und die Möglichkeiten der Entscheidungsvorbereitung, welche sich in den OR-Me-
thoden wiederspiegeln, machen das Operations Research sehr attraktiv für Privat-
unternehmen. Vor allem das Optimalitätsstreben deckt sich mit der unternehme-
rischen Zielsetzung der Gewinnmaximierung. Dies führte dazu, dass die OR-Me-
thoden nicht nur an Universitäten, sondern auch in der Wirtschaft weiterentwickelt
wurden. So ist es auch nicht verwunderlich, dass sich das Operations Research
bis 1975 vorwiegend mit betriebswirtschaftlichen Problemstellungen ausein-
andersetzte.
2
Anwendungsgebiete im privatwirtschaftlichen Bereich umfassen:
·
Telekommunikation
·
Logistik (z.B. Transport- und Tourenplanung)
·
Produktionsplanung und -steuerung
·
Projektmanagement und -steuerung
·
Investitions- und Finanzplanung
Durch die Entwicklung der Computertechnik wurden in den letzten 10 Jahren das
Operations Research um neue Anwendungsgebiete der Informatik z.B. Kom-
munikationsnetze, organisatorische Integration von Datenverarbeitungssystemen
in betriebliche Strukturen (CIM), Simulation u.a. erweitert.
1
RUNZ95 S.14
2
UULM04, Abruf: 17.05.2004
2
2
Transportoptimierung
2.1 Einführung in die Transportoptimierung
Die lineare Programmierung ist ein Spezialfall der mathematischen Optimierung.
Sie beruht auf der Prämisse, dass sich Zielsetzungen und Nebenbedingungen der
Optimierung durch lineare Funktionen ausdrücken lassen.
3
Historisch gesehen ist
die Transportoptimierung eines der ältesten Verfahren der linearen Program-
mierung
4
. Bereits in der 30iger Jahren des zwanzigsten Jahrhunderts beschäftigte
sich der Russische Ökonom L.V. Kantorovitch damit, mathematische Methoden
zur Produktionsplanung zu entwickeln. Aus praktisch ökonomischen Überle-
gungen heraus, beschrieb er 1939, wie das Problem von Organisation und Pla-
nung in der Produktion
5
mathematisch dargestellt werden kann. Zwei Jahre später
wurde in den USA ein Verfahren durch F.L. Hitchcock
6
vorgestellt, welches zur Lö-
sung und Optimierung von Transportaufgaben eingesetzt wurde. Hitchcock
beschreibt dabei, die klassische Form des Transportproblemes und Algorithmen
zu dessen Lösung. 1949 wurde durch T.C. Koopmans die grundlegende Arbeit
7
veröffentlicht, die sich mit Verfahren zur optimalen Ressourcenallokation beschäf-
tigt. Das klassische Transportproblem wird wegen Hitchcocks und Koopmans
Arbeiten auch als ,,Hitchcock-Koopmans-Transportproblem" bezeichnet.
8
Um der
Bedeutung für die Ökonomie gerecht zu werden, erhielten 1975 L.V. Kantorovitch
und T.C. Koopmans den Ökonomie-Nobelpreis.
9
Das modifizierte Distributionsverfahren (MODI-Verfahren) wurde 1951 von
Danzig
10
entwickelt und basiert auf den Überlegungen zur dualen Simplexmetho-
de. Obwohl Transportprobleme auch mit der Simplexmethode gelöst werden
können, bietet das MODI-Verfahren eine vereinfachte Lösung des Transportpro-
3
RUNZ95
4
KAMU95
5
KANT60
6
HITC41
7
KOOP49
8
ELLI03
9
KAMU95
10
DANT51
3
blemes an.
11
Aus der Verwandtschaft zur Simplexmethode heraus, verwendet die
MODI-Methode die selben Schritte zur Lösung.
12
Sie ist in ihrer mathematischen
Struktur ein Spezialfall der linearen Programmierung. Einzig allein aus dem Um-
stand besonderer Eigenarten des Transportproblemes heraus, lässt sich das
Transportproblem rationeller
13
mit Hilfe des MODI-Verfahrens als mit der Simplex-
Methode lösen. Die Besonderheiten, die ein Transportproblem kennzeichnen,
sind:
·
es werden homogene Güter verteilt
·
die Koeffizienten der zu bestimmenden Variablen des Gleichungssystems, wel-
che die Gegebenheiten des Transportproblemes wiedergeben, sind sämtlich
Eins
14
Da das Transportproblem aus einer Vielzahl von Variablen und Nebenbe-
dingungen besteht, ist es mit Hilfe der Simplexmethode nur mit einem immensen
Rechenaufwand zu lösen.
15
2.2 Definition und Modellformulierung des Transportproblemes
Als Transportproblem kann ein Problem angesehen werden, bei dem der
Transport von homogenen Gütern von einer Vielzahl von Anbietern (Ausgangs-
orten A
i
) zu einer Vielzahl von Nachfragern (Bestimmungsorten B
j
) erfolgt. Da
beim Transport von A
i
(i = 1, 2, ..., n) zu B
j
(j=1, 2, ..., m) Transportstückkosten in
Höhe von c
ij
anfallen, sind die Gesamttransportkosten der möglichen Verteilung zu
minimieren. Die Aufgabenstellung sieht dabei meist den Transport der gesamten
Angebotsmenge a
i
(i = 1, 2, ..., n) bzw. Nachfragemenge b
j
(j=1, 2, ..., m) vor. Bei
der Transportkostenminimierungsaufgabe sind die Transportkosten pro Einheit c
ij
konstant (lineare Zielfunktion) und stehen in ihrem Wert fest.
16
Im Ergebnis der
Transportplanung steht fest, welcher Nachfrager B
i
von welchem Anbieter A
i
mit
welcher Menge x
ij
zu beliefern ist. Die Transportmengen x
ij
sind im Transportpro-
blem die Unbekannten (Entscheidungsvariablen), alle anderen Informationen sind
bekannt.
11
ELLI03
12
HMTA95
13
ebenda.
14
ebenda.
15
LIEB97
16
RUNZ95
4
Das mathematische Modell zum Transportproblem besitzt die gleiche Struktur, wie
die Modelle der linearen Programmierung
17
. Als Spezialfall der Simplexmethode
kann das Transportproblem auch mit dem Simplex Algorithmus gelöst werden
18
.
Ein wichtige Voraussetzung für die Erstellung des mathematischen Modells ist der
Ausgleich von Angebotsmenge a
i
und Bedarfsmenge b
j.
Abschließend ergibt sich
das folgende mathematische Modell für ein geschlossenes Transportproblem:
(1) Zielfunktion:
Minimiere K
=
i
=1
m
j
=1
n
c
ij
x
ij
unter den Nebenbedingungen
(2) Angebotsgleichungen:
j
=1
n
x
ij
=a
i
(für alle Angebotsorte i = 1, 2, ..., m)
(3) Nachfragegleichungen:
i
=1
m
x
ij
=b
j
(für alle Nachfrageorte j = 1, 2, ..., n)
(4) Gesamtangebot und Gesamtnachfrage gleichen sich aus:
i
=1
m
a
i
=
J
=1
n
b
j
(5) Gesamtangebot und Gesamtnachfrage sind größer als Null
i
=1
m
a
i
0
j
=1
n
b
j
0
(6) Nichtnegativitätsbedingung der Transportmengen:
x
ij
0 (für alle i = 1, 2, ... m und alle j = 1, 2, ... n)
17
ebenda.
18
ZIMM99
5
Interpretiert werden können die Ausdrücke folgendermaßen:
Die Zielfunktion (1) verlangt, dass die Gesamttransportkosten zu minimieren sind.
Die Angebotsgleichung (2) fordert, dass alle Angebotsmengen aufgebraucht
werden. Im Gegensatz dazu sagt die Nachfragegleichung (3) aus, dass der Bedarf
vollständig gedeckt sein muss. Der Ausgleich von Angebot und Nachfrage ist nur
möglich, wenn die Gesamtmengen von Angebot und Nachfrage gleich sind (4).
Ein Transportproblem, welches Restriktion (4) erfüllt, heisst geschlossenes
Transportproblem. Ein geschlossenes Transportproblem ist die hinreichend und
notwendige Bedingung für die Existenz einer Lösung des vorliegenden linearen
Optimierungsproblems
19
. Die Summe von Gesamtangebot und Gesamtnachfrage
müssen größer als Null sein. Ein Transportproblem, in dem nichts transportiert
wird, muss nicht optimiert werden. Die Nichtnegativitätsbedingung (6) bestimmt,
dass Rücktransporte nicht zulässig sind.
Die Darstellungsform des mathematischen Modells eines Transportproblems er-
folgt mit Hilfe eines Matrixtableaus:
von i nach j
Bestimmungsorte B
j
Ausgangsorte A
i
B
1
B
2
B
3
...
B
n
Angebotsmengen a
i
A
1
x
11
x
12
x
13
...
x
1n
a
1
A
2
x
21
x
22
x
23
...
x
2n
a
2
...
...
...
...
...
...
...
A
m
x
m1
x
m2
x
m3
...
x
mn
a
m
Nachfragemengen b
j
b
1
b
2
b
3
...
b
n
Tabelle 1 Transportmengenmatrix
20
Die Transportmengenmatrix (Tabelle 1) stellt zeilenweise die Angebotsglei-
chungen der Nebenbedingungen dar. Spaltenweise gelesen werden die
Nachfragegleichungen der Nebenbedingungen erfasst. Bei der Aufstellung der
Transportmengenmatrix muss sichergestellt sein, dass ein Ausgleich von Gesamt-
angebot und Gesamtnachfrage besteht. Der Ausgleich von Gesamtangebot und
Gesamtnachfrage ist die Restriktion, welche ein Transportproblem als ge-
19
MAPH01, (Stand 31.03.2001, Abruf: 19.05.2004)
20
RUNZ95
6
schlossenes Transportproblem charakterisiert. Die Transportkosten pro Einheit c
ij
,
die beim Transport von A
i
nach B
j
anfallen, werden in der Einheits-Transport-
kosten-Matrix (Tabelle 2) erfasst:
von i nach j
Bestimmungsorte B
j
Ausgangsorte A
i
B
1
B
2
B
3
...
B
n
A
1
c
11
c
12
c
13
...
c
1n
A
2
c
21
c
22
c
23
...
c
2n
...
...
...
...
...
...
A
m
c
m1
c
m2
c
m3
...
c
mn
Tabelle 2 Einheits-Transportkosten-Matrix
21
Die Trennung von Transportmengen in der Transportmengenmatrix (Tabelle 1)
und den Transportkosten pro Einheit (Tabelle 2) ist für eine rechnerische Behand-
lung nicht notwendig. Die Struktur der Tabellen ist so ähnlich, dass sie vereinigt
werden können. Im Ergebnis der Vereinigung von Transportmengenmatrix und
Einheits-Transportkosten-Matrix entsteht die Matrix der Transportmethode, die als
Tabelle 3 dargestellt ist. Im weiteren Verlauf wird diese Matrix als Transport-
tableau bezeichnet werden.
von i nach j
Bestimmungsorte B
j
Ausgangsorte A
i
B
1
B
2
B
3
...
B
n
Angebotsmengen a
i
A
1
c
11
x
11
c
12
x
12
c
13
x
13
...
...
c
1n
x
1n
a
1
A
2
c
21
x
21
c
22
x
22
c
23
x
23
...
...
c
2n
x
2n
a
2
...
...
...
...
...
...
...
...
...
...
...
...
A
m
c
m1
x
m1
c
m2
x
m2
c
m3
x
m3
...
...
c
mn
x
mn
a
m
Nachfragemengen b
j
b
1
b
2
b
3
...
b
n
i
=1
m
a
i
=
j
=1
n
b
j
Tabelle 3 Matrix der Transportmethode Transporttableau
22
21
RUNZ95
22
ebenda.
7
Im Transporttableau bleiben während der Berechnung die Größen c
ij
, a
i
und b
j
un-
verändert. Die Änderung der Zielfunktion:
Minimiere K
=
i
=1
m
j
=1
n
c
ij
x
ij
für alle (i = 1,2, ..., m; j = 1,2, ..., n)
wird durch die Entscheidungsvariablen x
ij
bestimmt. Durch die enge Verwandt-
schaft zur Simplexmethode ist auch die Transportmethode ein Iterationsverfahren.
Ausgehend von einer zulässigen Ausgangslösung bis zur schrittweisen
Optimierung kann im Transporttableau (Tabelle 3) die Änderung der Zuordnung
der x
ij
dargestellt werden. Da alle, für die Rechnung notwendigen Informationen im
Transporttableau enthalten sind, ist das Transporttableau das geeignete Darstel-
lungsmittel für die Berechnung eines Transportproblems. Mit der Betrachtung des
Transporttableaus kann sehr leicht die Behauptung bewiesen werden, dass der
Transportalgorithmus rationeller ist als der Simplex-Algorithmus
23
. Während ein
Simplextableau zur Berechnung eines Transportproblems mit m Ausgangsorten
und n Bestimmungsorten einem Umfang von (m+n+1) Zeilen und (m+1)(n+1)
Spalten besitzt, ist für die Lösung mit Hilfe des Transportproblems ein Transport-
tableau mit nur m Zeilen und n Spalten notwendig.
24
2.3 Initialisierung des Transportproblemes
Das Ziel der Initialisierung ist die Bestimmung einer zulässigen Ausgangslösung
25
.
Die Initialisierung erfolgt in drei Schritten:
1. Stufe
Ausgleichsprüfung
2. Stufe
Matrizenreduktion
3. Stufe
Festlegung einer zulässigen Ausgangslösung
4. Stufe
Ermittlung einer optimalen Lösung
Erst nach der Erstellung einer Ausgangslösung kann die eigentliche Optimierung
des Transportproblemes beginnen.
23
RUNZ95
24
LIEB97
25
ebenda.
8
Die Optimierung zählt damit als eigenständige Stufe, der insgesamt vier stufigen
Distributionsmethode
26
.
(1) Stufe Ausgleichsprüfung:
Eine Ausgleichsprüfung muss immer den ersten Schritt bei der Lösung eines
Transportproblemes darstellen. Die Ausgleichsprüfung entspricht der zentralen
Forderung eines geschlossenen Transportproblemes, nach einem Ausgleich von
Angebotsmenge a
i
und der Nachfragemenge b
j
, wie sie im mathematischen
Modell als Restriktion (3) aufgeführt wird:
i
=1
m
a
i
=
J
=1
n
b
j
für alle (i = 1,2, ..., m; j = 1,2, ..., n)
Entspricht die Angebotsmenge a
i
nicht der Nachfragemenge b
j
so wird eine Aus-
gleichszeile bzw. Ausgleichsspalte in das Transporttableau aufgenommen. Eine
Ausgleichszeile entspricht einem fiktiven Abnehmer, der in das Transporttableau
aufgenommen wird, wenn
a
i
b
j
ist. Die Ausgleichsspalte entspricht einem
fiktiven Anbieter, wenn
a
i
b
j
erfüllt ist. Die Transportkosten pro Einheit c
ij
werden bei der Einführung einer Ausgleichszeile oder Ausgleichsspalte sehr hoch
im Vergleich zu den übrigen Transportkosten pro Einheit im Transporttableau
gesetzt, da Belegungen dieser Zeilen oder Spalten unerwünscht sind
27
.
(2) Stufe Matrizenreduktion:
Die Matrizenreduktion ist besonders bei der manuellen Berechnung von
Transportproblemen zu empfehlen. Sie ermöglicht eine Reduzierung des Rechen-
aufwandes und damit verbunden eine Einschränkung von Fehlermöglichkeiten.
Die Reduzierung wird auf der Einheits-Transportkostenmatrix ausgeführt (Tabelle
2). ,,Nach einem Satz aus der Matrizenrechnung bleibt das Verteilungsproblem un-
verändert, wenn die Elemente in irgendeiner Zeile oder Spalte der Kostenmatrix
[Einheits-Transportkostenmatrix d.Verf.] um die gleiche Größe vermehrt oder
vermindert werden"
28
. Eine einfache Begründung für diesen Satz, ohne Durchfüh-
rung eines Beweises, ist die folgende: Bei einer Subtraktion von allen Kosten c
ij
in
einer Zeile i oder Spalte j (i = 1,2, ..., m; j = 1, 2, ... n) in der Einheits-Transportkos-
26
ZIMM99
27
ZIMM99
28
ebenda. S.93
9
tenmatrix (Tabelle 2) ändern sich die Werte der Transportkosten c
ij
nur absolut,
aber nicht relativ zu einander.
Eine Reduktion kann in mehreren Schritten erfolgen:
1. Zeilen und Spalten, in denen eine Angebotsmenge a
i
bzw. Bedarfsmenge b
j
von Null ausgeschrieben sind, können aus dem Transportproblem entfernt
werden. Die Löschung von Zeilen bzw. Spalten ist nur in der Phase der Ma-
trizenreduktion zulässig. Im Verlauf der Erstellung einer zulässigen Ausgangslö-
sung oder in der Optimierungsphase ist es nicht zulässig, Zeilen bzw. Spalten
aus dem Transportproblem zu entfernen.
2. Der kleinste Transportkostenwert pro Einheit c
ij
der Einheits-Transportkosten-
matrix wird von allen anderen Transportkosten pro Einheit abgezogen.
3. Der kleinste Transportkostenwert pro Einheit c
ij
aus jeder Spalte wird von allen
anderen Transportkostenwerten dieser Spalte abgezogen. Es wird ein
Transportkostenwert pro Spalte eliminiert. In jeder Spalte wird eine Null, als Ko-
effizient für c
ij
erzeugt.
4. Ist nicht in jeder Zeile der Transportkostenmatrix ein Transportkostenwert pro
Einheit c
ij
gleich Null, wird der kleinste Transportkostenwert pro Einheit c
ij
von
jeder Zeile von allen Transportkostenwerten pro Einheit in dieser Zeile subtra-
hiert. In jeder Zeile wird eine Null, als Koeffizient für c
ij
erzeugt.
(3) Stufe - Festlegung einer zulässigen Ausgangslösung:
Als zulässige Ausgangslösung, wird ein Transporttableau (Tabelle 3) bezeichnet,
welches alle Restriktionen des mathematischen Modells eines Transportproble-
mes erfüllt. Eine Belegung von x
ij
=0 bei positiven Angebots- und Nachfrage-
mengen, für alle Ausgangsorte A
i
und Bestimmungsorte B
j
ist keine zulässige
Ausgangslösung eines Transportproblemes.
29
Die wesentliche Eigenschaft einer
Ausgangslösung ist, dass sie genau
mn-1 Basisvariablen (Allokationen), bei
m Angebotsorten und n Bestimmungsorten, besitzt. Aus Gründen der linearen
Kombination kann eine der m
n Nebenbedingungen eines Transportproblemes
entfallen.
30
Die Nichtnegativitätsbedingung besagt, dass die
mn-1 Basisva-
29
DODR95
30
ebenda.
10
riablen mit positiven Werten belegt werden müssen. Zusätzlich ergeben sich in
den Basislösungen ganzzahlige Transportmengen x
ij
, wenn die Angebotsmengen
a
i
und die Bedarfsmengen b
j
ebenfalls ganzzahlig sind.
31
Für die Bestimmung einer zulässigen Ausgangslösung können mehrere Verfahren
eingesetzt werden. Jedes Verfahren setzt für die Bestimmung einer zulässigen
Ausgangslösung die
mn-1 Basisvariablen nacheinander fest. In jedem Aus-
wahlschritt wird einer Variablen x
ij
ein Wert zugewiesen, der eine Restriktion der
Form
j
=1
n
x
ij
=a
i
oder
i
=1
m
x
ij
=b
j
für alle (i = 1,2, ... m; j = 1, 2, ... n)
erfüllt. Nach
mn-1 Auswahlschritten ist eine Ausgangslösung gefunden, die
alle Restriktionen eines Transportproblemes erfüllt.
32
Die Anzahl der
mn-1
Basisvariablen darf sich im weiteren Verlauf, der Optimierung eines Transportpro-
blemes, nicht mehr verändern. Die Verfahren für die Bestimmung einer zulässigen
Ausgangslösung unterscheiden sich darin, wie weit sie ein Transportproblem an
die optimale Lösung heranführen können. Die Verfahren, die eine zulässige Aus-
gangslösung bestimmen, werden auch als Eröffnungsverfahren bezeichnet.
(4) Stufe - Ermittlung einer optimalen Lösung:
Nach der Ermittlung einer zulässigen Ausgangslösung ist zu prüfen, ob es sich um
die optimale Lösung handelt. Das Verfahren für den Optimalitätstest der Aus-
gangslösung wird im Kapitel 2.5 beschrieben.
2.4 Die Eröffungsverfahren
2.4.1 Das Nord-West-Ecken-Verfahren
Das Nord-West-Ecken-Verfahren ist in der Literatur das am meisten beschriebene
Verfahren, zur Auffindung einer zulässigen Ausgangslösung. Es zählt zur Klasse
der heuristischen Verfahren. Heuristiken beinhalten Vorgehensregeln, die für die
jeweilige Problemstruktur sinnvoll und erfolgsversprechend sind. Deshalb kann
von heuristischen Verfahren nicht erwartet werden, dass ein Optimum gefunden
31
WERM03 Kapitel 4, (Stand: 11.04.2003, Abruf: 19.05.2004)
32
LIEB97
11
wird.
33
Somit sind Heuristiken Verfahren ohne garantierte Lösungsgüte.
34
In Mül-
ler-Mehrbach
35
wird dazu vermerkt: "Das einfachste Verfahren, das eigentlich gar
kein Näherungsverfahren ist, sondern lediglich eine Ausgangslösung hervorbringt,
ist das Nord-West-Ecken-Verfahren. Es hat praktisch nur historische Bedeutung,
erfreut sich aber eines sicheren Platzes in jedem Lehrbuch. Der außer dem schö-
nen Namen einzige Vorteil des Verfahrens ist, daß mit ihm sogar bei kleinen Pro-
blemen meist sehr schlechte Ausgangslösungen erzeugt werden, die so viele an-
schließende iterative Verbesserungen erfordern, daß sich die Optimierungsverfah-
ren anschaulich erläutern lassen"
36
Müller-Mehrbach hat in seiner Aussage über das Nord-West-Ecken-Verfahren die
Vor- und Nachteile auf einem Punkt gebracht. Obwohl das Nord-West-Ecken-
Verfahren schlechte Ausgangslösungen, durch die Nichtbeachtung der Einheits-
Transportkostenmatrix (Tabelle 2) liefert, ist die Einfachheit und damit verbunden
der geringe Rechenaufwand der große Vorteil dieses Verfahrens. Zimmermann
weist dem Nord-West-Ecken-Verfahren eine große Rolle bei der Lösung von
Transportproblemen mittels EDV-Anlagen zu.
37
Kapitel 4.2.1 wird Zimmermanns
Aussage jedoch widerlegen. Somit bleibt die triviale Einfachheit des Nord-West-
Ecken-Verfahrens als einzigster Vorteil in der Anwendung bestehen.
Die Bestimmung einer Ausgangslösung mit dem Nord-West-Ecken-Verfahren be-
ginnt in der linken oberen (Nord-West) Ecke und verläuft in die rechte untere Ecke
der Transportmengenmatrix (Tabelle 1). ,,Kennzeichnend ist, daß mit jeder Zuord-
nung mindestens eine Nebenbedingung erfüllt wird, d.h. entweder ein Angebots-
oder eine Nachfragerestriktion. Die entsprechende Zeile oder Spalte gilt dann für
den weiteren Auswahlprozeß als gesperrt."
38
Durch die Eliminierung von einer Zei-
le oder Spalte in jedem Zuordnungsschritt, wird nach maximal
mn-1 Zuord-
nungen einer Basisvariable in die Transportmengenmatrix (Tabelle 1) eine zu-
lässige Ausgangslösung mit Hilfe des Nord-West-Ecken-Verfahrens erstellt. Ein
33
DODR95
34
GALT92
35
MÜME73
36
GALT92 S.305
37
ZIMM99
38
GALT92 S.305
12
Programmablaufplan (PAP), dass die Heuristik des Nord-West-Ecken-Verfahren
darstellt, befindet sich im Anhang unter Abbildung A1.
Beispiel
39
: Gegeben sei ein Problem mit drei Angebotsorten
m=3 und vier Be-
darfsorten
n=4 . Die Angebotsmengen a
i
=10,8,7 , den Nachfragemengen
b
j
=6,5,8,6 und der Kostenmatrix C mit:
C
=c
ij
=
[
7 2 4 7
9 5 3 3
7 7 6 4
]
Das Problem wird in das Transporttableau übertragen:
Abbildung 2-1 zeigt das Beispiel, übertragen in die Darstellungsform eines
Transporttableaus. Die Abbildung stammt aus dem Applet Rapid Transport Opti-
mizer (RapTOr), welches im praktischen Teil dieser Diplomarbeit entstanden ist.
Die Transportkosten pro Einheit c
ij
sind aus der Kostenmatrix in das Transportpro-
blem übernommen worden, ebenso wie die Angebotsmengen a
i
und die Bedarfs-
mengen b
j
. Die zulässige Ausgangslösung mit Hilfe des Nord-West-Ecken-Verfah-
rens wird in Abbildung 2-2 dargestellt.
Der Zielfunktionswert K
=
i
=1
m
j
=1
n
c
ij
x
ij
beträgt 106 Geldeinheiten (GE).
39
DODR95 S.76
Abbildung 2-1 Beispiel übertragen in das Transporttableau
13
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2004
- ISBN (eBook)
- 9783832483227
- ISBN (Paperback)
- 9783838683225
- DOI
- 10.3239/9783832483227
- Dateigröße
- 897 KB
- Sprache
- Deutsch
- Institution / Hochschule
- Universität Leipzig – Wirtschaftswissenschaftliche Fakultät, empirische Wirtschaftsforschung
- Erscheinungsdatum
- 2004 (Oktober)
- Note
- 1,7
- Schlagworte
- modifizierte distributionsmethode modi-methode java applet eclipse projekt server-version
