36
Operations Research Transportaufgaben

Operations Research

  • 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

Page 1: Operations  Research

Operations Research

Transportaufgaben

Page 2: Operations  Research

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

Page 3: Operations  Research

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

Page 4: Operations  Research

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

Page 5: Operations  Research

TransportaufgabenBeispiel einer Baufirma

Bedarf g:

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

min.....1111 mnmn cxcxZ

Page 6: Operations  Research

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

Page 7: Operations  Research

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

Page 8: Operations  Research

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

Page 9: Operations  Research

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

Page 10: Operations  Research

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

Page 11: Operations  Research

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

Page 12: Operations  Research

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

Page 13: Operations  Research

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

Page 14: Operations  Research

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

Page 15: Operations  Research

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

Page 16: Operations  Research

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

Page 17: Operations  Research

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

Page 18: Operations  Research

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

Page 19: Operations  Research

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

Page 20: Operations  Research

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

Page 21: Operations  Research

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

Page 22: Operations  Research

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.

Page 23: Operations  Research

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.

Page 24: Operations  Research

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

Page 25: Operations  Research

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

Page 26: Operations  Research

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(

Page 27: Operations  Research

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

Page 28: Operations  Research

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

Page 29: Operations  Research

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

Page 30: Operations  Research

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 .

Page 31: Operations  Research

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.

Page 32: Operations  Research

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

Page 33: Operations  Research

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

Page 34: Operations  Research

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

Page 35: Operations  Research

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

Page 36: Operations  Research