Operations Research

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