Download pptx - 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


Bedarf g:

•Gesamtaufkommen = Gesamtbedarf: 176344176164 4141 ggll•Zielfunktion = Stück x Kosten:

min.....1111 mnmn cxcxZ


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


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


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


6 7 5 49 8 7 65 5 6 17 7 4 2 2|2

G fordert:

4 3 64 Rest



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



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



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



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.


9 8 3 6G fordert:

3 3|6

3 Rest



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


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.


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



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



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



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


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.



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



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:



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.



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.



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:


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:


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:



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.



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



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



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 .



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.



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



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


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


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