Operations Research
Transportaufgaben
Ist ein Spezialfall der Linearen Optimierung Sind Gesamtaufkommen und Gesamtbedarf
unterschiedlich, so ist das Transportproblem auf ein adäquates mit Gleichheit zurückzuführen.
Aufkommensorte Menge Bedarfsorte Bedarfsmenge Transportkosten von A nach B sind Menge von A nach B ist
Das Transportproblem
mA 1
ian-1 B
kbikc
ikx
Vorläufige Voraussetzung ist das Gleichgewicht:◦ Alle Orte versenden ihre ganze Produktion, alle
Bedarfsorte empfangen die ganze Produktion.a =
Aufkommensmengeb = Bedarfsmenge
◦ Zielfunktion = Menge c Kosten x min◦ Restriktionen:
Das TransportproblemDie Verfahrenweise
n
kk
m
ii ba
11
0,....,....:....:
11
11111
11111
mn
m
n
xxbxxBaxxA
Eine Firma für Baumaschinen besitzt 4 Lager für Bagger, , die dort mit den Stückzahlen bereit sind. An den Orten werden an einem Tag Bagger angefordert.
Die Kosten des Transports eines Baggers vonnach sind in der folgenden Matrix ausgedrückt:
TransportaufgabenBeispiel einer Baufirma
41 LL 6 ,1 ,6 ,4 4321 llll
41 GG 6,3 ,4 ,4 4321 gggg
iLkG
4774655578965766
)( ikc
sind? minimalen Gesamtkost diedamit niert werde transportlleGroßbauste
zu welcherLager welchemmüssen von Bagger x Wieviele ik
k
i
TransportaufgabenBeispiel einer Baufirma
Bedarf g:
•Gesamtaufkommen = Gesamtbedarf: 176344176164 4141 ggll•Zielfunktion = Stück x Kosten:
min.....1111 mnmn cxcxZ
TransportaufgabenBeispiel einer Baufirma
Transporttabelle L liefert:
6 6 7 5 46 9 8 7 65 5 5 6 14 7 7 4 6
G fordert:
4 4 3 6
Überführen in eine Transporttabelle für das Matrixminimumverfahren
ikc Kosten
TransportaufgabenBeispiel einer Baufirma
TransporttabelleL liefert:
6 6 7 5 46 9 8 7 65 5 5 6 1
4 4
7 7 4 6
G fordert:
4|1 4 3 6Kostenoptimum = min(6,4), da nicht mehr geliefert werden kann als nachgefragt wird:
1.) zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums = min(6,4)3.) Abwechselndes streichen v. Spalten/ Zeilen
2 Rest
TransportaufgabenBeispiel einer Baufirma
1. Reduzierte Tabelle:
1.) Neuer Randwert sind die verbleibenden Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums = min (2,6)3.) Streichen dieser Zeile
TransporttabelleL liefert:
6 7 5 49 8 7 65 5 6 17 7 4 2 2|2
G fordert:
4 3 64 Rest
TransportaufgabenBeispiel einer Baufirma
2. Reduzierte Tabelle:
1.) Neuer Randwert sind die restlichen geforderten Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums = min(4,4)3.) Streichen dieser Spalte
Transporttabelle L liefert:
6 7 5 4 49 8 7 65 5 6 1
G fordert:
4 3 4|3
0 Rest
TransportaufgabenBeispiel einer Baufirma
3. Reduzierte Tabelle:
1.) Neuer Randwert sind die restlichen lieferbaren Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums3.) Streichen dieser Zeile
Transporttabelle
L liefert:
6 7 09 8 6
5 1 5 1|4G fordert:
4 3
TransportaufgabenBeispiel einer Baufirma
4. Reduzierte Tabelle:
1.) Neuer Randwert sind die restlichen geforderten Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums =min (0,3)3.) Streichen dieser Zeile da null; würde G null fordern und L drei liefern wäre die Spalte zu streichen.
Transporttabelle
L liefert:
6 0 7 0|59 8 6
G fordert:
3 3
TransportaufgabenBeispiel einer Baufirma
5. Reduzierte Tabelle:
1.) Neuer Randwert sind die restlichen lieferbaren Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums3.) Streichen dieser Spalte da zuvor die Zeile gestrichen wurde.
TransporttabelleL liefert:
9 8 3 6G fordert:
3 3|6
3 Rest
TransportaufgabenBeispiel einer Baufirma
6. Reduzierte Tabelle:
1.) Neuer Randwert sind die restlichen lieferbaren Bagger2.)zeilenweise die erste kleinste Bewertungszahl2.) Eintag des Kostenoptimums3.) Streichen dieser Zeile
Transporttabelle L
liefert:
9 3 3|7G fordert:
3
TransportaufgabenBeispiel einer Baufirma
Transporttabelle6 6 0 7 5 46 9 3 8 3 75 5 1 5 6
4 4 7 7 4 2
Eintragung aller Kostenoptima ergibt eine mögliche Lösung
Z = 6x0 + 5x4 + 9x3 + 8x3 + 5x1 + 4x4 + 4x2 = 100
ikc
ikx
Einführung von Potenzialen nach der MODI/Potenzialmethode.
Für jedes Lager und für jeden Bedarfsort (Baustelle) werden die Potenziale u und v festgelegt.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle
6 6 0 7 5 46 9 3 8 3 75 5 1 5 6
4 4
7 7 4 2
ki vu \
iu
kv
Es gibt m+n-1=7 besetzte Felder, daraus folgen 7 lineare Gleichungen mit 8 unbekannten Potenzialen
, da nur eine Lösung benötigt wird
TransportaufgabenBeispiel einer Baufirma
Transporttabelle06 6 0 7 5 46 9 3 8 3 75 5 1 5 6
4 4
7 7 4 2
ki vu \
iu
kv
01 v
Die Einführung von Potenzialen erfolgt nach Es werden nur besetzte Felder herangezogen
TransportaufgabenBeispiel einer Baufirma
Transporttabelle06 6 0 7 5 46 9 3 8 3 75 5 1 5 6
4 4
7 7 4 2
ki vu \
iu
kv
ikki cvu
440 44 uucvu ikki
4u
Das nächste mögliche besetzte Feld wäre Es werden nur besetzte Felder herangezogen
TransportaufgabenBeispiel einer Baufirma
Transporttabelle06 6 0 7 5 46 9 3 8 3 75 5 1 5 6
4 4 4
7 7 4 2
ki vu \
iu
kv
44c
0 ;44 44 vvcvu ikki
4v
Vervollständigen der restlichen Potenziale nach der gleichen Methode
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
ikki cvu
Einführen von fiktiven Bewertungszahlen mit den Potenzialen. Betrifft nur nichtbesetzte Felder.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
ikkiik cvuc
Einsetzen in die Gleichung
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
ikkiik cvuc
160511 c 2705 ; 13 c
1 2
Vervollständigen der restlichen Bewertungszahlen Das Ergebnis ist optimal wenn für alle Bewertungszahlen
gilt:
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
1 2
2 1
1 1 2
2 3
mtskriteriuOptimalitäcvuc ikkiik 0
Das Ergebnis ist noch nicht optimal wegen +2, +1.
Höchste positive Bewertungszahl wird mit versehen. Streichen aller Zeilen und Spalten des Tableaus, die
nur ein besetztes Feld aufweisen.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
1 2
2 1
1 1 2
2 3
Achtung: Durch das Streichen können weitere Zeilen/ Spalten mit nur einem besetzten Feld entstehen.
Geschlossener Zickzackweg abwechselnd in vertikaler /horizontaler Richtung. (Nur über besetzte Felder)
In den besetzten Feldern wird abwechselnd -/+ hinzugefügt.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 0 0
5 6 6 0 7 5 48 6 9 3 8 3 74 5 5 1 5 64 4
47 7 4 2
ki vu \
iu
kv
1
2
3
45
1. Vertikal beginnend2. Horizontal3.Vertikal4. Horizontal5.Vertikal6. Kein weiteres besetztes Feld7. Mit -beginnend
In Richtung des Zickzagweges nur über besetzte Felder abwechselnd +/- beginnend mit minus.
Tabelle nachdem alle -Variablen hinzugefügt wurden:
TransportaufgabenBeispiel einer Baufirma
Transporttabelle
6 6 0+ 7 5 4-6 9 3- 8 3 75 5 1 5 6
4 4- 7 7 4 2+
ki vu \
iu
kv
Durch die Korrekturen stimmen alle Zeilen- und Spaltensummen
Unter allen - -Werten wird der kleinste ausgesucht:
TransportaufgabenBeispiel einer Baufirma
Transporttabelle
6 6 0+ 7 5 4-6 9 3- 8 3 75 5 1 5 6
4 4- 7 7 4 2+
ki vu \
iu
kv
3
3)4,3,4min(
Das Einsetzen der -Werte ergibt die Werte der neuen besetzten Felder
Beginnend mit ergeben sich neue Potenziale:
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3 7 5 16 6 3 9 8 3 74 5 5 1 5 64 4 1 7 7 4 5
ki vu \
iu
kv
01 v ikki cvu
Mit lassen sich die neuen Bewertungszahlen für nicht besetzte Felder finden.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3 7 5 16 6 3 9 8 3 74 5 5 1 5 64 4 1 7 7 4 5
ki vu \
iu
kv
ikkiik cvuc
1
ikkiik cvuc
Bewertungszahl
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3 7 5 16 6 3 9 8 3 74 5 5 1 5 64 4 1 7 7 4 5
ki vu \
iu
kv
1 0
2 1
1 1 2
2 1
Da unter noch eine positive Bewertungszahl vorhanden ist, ist das Optimalitätskriterium noch nicht erreicht.
Ist keine Reihe zu streichen beginnt der Zickzackweg sofort.33c
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3 7 5 16 6 3+ 9 8 3- 74 5 5 1 5 64 4 1 7 7 4 5
ki vu \
iu
kv
1 0
2 1
1 1 2
2 1
33c
Der Zickzackweg über die besetzten Felder beginnt mit der höchsten positiven Bewertungszahl vertikal beginnend mit einem - , hier .
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3+ 7 5 1-6 6 3+ 9 8 3- 74 5 5 1- 5 64 4 1- 7 7 4 5+
ki vu \
iu
kv
1 0
2 1
1 1 2
2 1
Der Zickzackweg wird fortgesetzt bis alle besetzten Felder eine -Variable aufweisen.
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 1 2 0
5 6 6 3+ 7 5 1-6 6 3+ 9 8 3- 74 5 5 1- 5 64 4 1- 7 7 4 5+
ki vu \
iu
kv
1 0
2 1
1 1 2
2 1
Der kleinste negative -Wert tritt hier dreifach auf. In diesem Fall wird das erste teuerste Feld ausgesucht.
Die übrigen Basisvariablen erhalten den Wert Null.
1)1,1,3,1min( 1
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 2 2 0
4 6 6 4 7 5 6 6 4 9 8 2 73 5 5 0 5 1 64 4 0 7 7 4 6
ki vu \
iu
kv
Das Einsetzen der -Werte ergibt die Werte der neuen besetzten Felder.
Beginnend mit ergeben sich neue Potenziale:1
01 v
ikki cvu
TransportaufgabenBeispiel einer Baufirma
Transporttabelle0 2 2 0 Lager
4 6 6 4 7 5 16 6 4 9 8 2 7 23 5 5 0 5 1 6 34 4 0 7 7 4 6 4
Zu Baustelle
1 2 3 4
ki vu \
iu
kv
2 1
1 1
2
1
3
1 1
Mit lassen sich die neuen Bewertungszahlen in den unbesetzten Feldern erstellen.
Da alle Bewertungszahlen negativ sind handelt es sich um die optimale zulässige Basislösung.
ikkiik cvuc
Z=6x4+6x4+8x2+5x0+5x1+4x0+4x6=93
TransportaufgabenBeispiel einer Baufirma
Grafische Darstellung der Lösung:
Lager
6 4 1
6 4 8 2 2
5 0 5 1 3
4 0 4 6 4
Zu Baustelle
1 2 3 4