Upload
nailah
View
30
Download
0
Embed Size (px)
DESCRIPTION
Operations Research. Transportaufgaben. Das Transportproblem. 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 - PowerPoint PPT Presentation
Citation preview
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