Transportoptimierung PDF

Preview

Summary

SS18
Beschreibung des Lösungsverfahrens...

Description

Transportoptimierung Gegeben:  m Aufkommensorte Ai mit dem Aufkommen ai (i = 1,..,m)  n Bedarfsorte Bj mit Bedarf bj (j = 1,…,n)  m·n Kostenangaben cij: Kosten, die entstehen, wenn eine ME des Gutes von Ai nach Bj transportiert wird (i = 1,..,m und j = 1,…,n)  Es gelte a1 +…+ am = b1 +…+ bn. Gesucht:  m·n Variablen xij: Menge, die von Ai nach Bj transportiert wird (i = 1,..,m und j = 1,…,n) Modell: Minimum gesucht von

Mathematisches Modell: lineare Zielfunktion ZF Nebenbed.:

z = c11·x11 + c12·x12 +…+ c21·x21 + c22·x22 +…+ cmn·xmn

x11 + x12 +…+ x1n = a1 x21 + x22 +…+ x2n = a2 ,…., bis xm1 + xm2 +…+ xmn = am

und

x11 + x21 +…+ xm1 = b1 x12 + x22 +…+ xm2 = b2,…, bis x1n + x2n +…+ xmn = bn Nichtneg.bed.:

xij ≥ 0 für alle i = 1,..,m und j = 1,…,n

Bzw. m

ZF

n

 c

min

ij

 xij

i1 j1 n

NB

x

ij

 ai für alle i = 1,…,m

ij

 bj für alle ij= 1,…,n

j 1 m

x i 1

NNB

x ij  0

für alle i = 1,..,m und j = 1,…,n

Weil die Summe der ai gleich der Summe der bj ist, ist eine der Nebenbedingungen überflüssig, daher werden m + n – 1 Basisvariablen benötigt. Lineares Optimierungsproblem, kann mit der Simplexmethode gelöst werden, aber: aufwändig. Alternativ: Spezielles Verfahren, bei dem die spezielle Struktur ausgenutzt wird.

Verfahren zur Lösung der Transportaufgabe: Schritt 1: Bestimmung einer zulässigen Basislösung z.B. mit der Nord-West-Eckenregel Schritt 2: Optimierung der Zielfunktion

Tableau zur Berechnung B1

B2

c11

A1

c12

c21 c31

Im Beispiel:

A2 A3 bj

x23

c32

x24

c33

c34

x32

x33

b2

x34

b3

a1 a2 a3

b4

Tableau mit eingetragenen Kosten und Aufkommen und Bedarf B1

A1

c24

x22

b1

x14

c23

x31

bj

x13

c22

ai

c14

x12

x21

A3

B4

c13

x11

A2

B3

B2

B3

B4

50

63

84

60

84

52

24

136

120

76

100

44

18

10

14

ai 12 18 20

8

Zu Schritt 1: Bestimmung einer zulässigen Basislösung Es werden m+n-1 Basisvariablen (BV) benötigt, die anderen Variablen sind dann Nichtbasisvariablen (NBV). Die Werte der BV werden markiert (z.B. blau eingetragen), die NBV haben den Wert 0, dieser ist nicht eingetragen. Die Zellen, die zu Basisvariablen gehören, heißen auch „markierte Elemente“ (durch Eintrag einer blauen Zahl). Eine Möglichkeit, zu einer zulässigen Basislösung zu gelangen ist, zuerst dem Feld mit den niedrigsten Kosten die maximal mögliche Menge zuzuweisen. Dann ist entweder in der Zeile oder in der Spalte die Kapazitätsgrenze erreicht (im Beispiel ist in der Spalte b3 = 14 erreicht). Dort, wo die Kapazitätsgrenze nicht erreicht ist, wird die Differenz nun dem Feld (oder den Feldern) mit den geringsten Kosten zugeordnet (im Beispiel sind in der zweiten Zeile noch 4 ME übrig, diese werden von A2 zu B2 transportiert). Dieses Prinzip wird nun so lange angewendet, bis alle Basisvariablen gefunden sind (alle Kapazitätsgrenzen erreicht sind). Es kann auch sein, dass die Transportmenge 0 sein muss, damit der Zyklus nicht abreißt. Dass passiert, wenn gleichzeitig die Zeilen- und die Spaltenbeschränkung befriedigt werden (dann spricht man von Entartung). Im Beispiel benötigt B2 noch 6 ME, diese werden vom kostengünstigsten Anbieter bezogen, falls möglich, sonst vom zweitgünstigsten,….

Es werden m+n-1 = 6 Basisvariablen benötigt, ggf. haben auch Basisvariablen den Wert 0 (dann liegt Entartung vor). Hier ein Beispiel für eine zulässige Basislösung: B1 A1

B2

50

63 6

A2 A3

B3

84

84

60

24

136

12

76

18

14

4 100

44

12

bj

ai

6 52

120

B4

8

18

10

14

20

8

Es sind also x11 = 6, x12 = 6, x22 = 4, x23 = 14, x31 = 12, x34 = 8 die 6 Basisvariablen (BV), die zugehörigen Felder sind die markierten Elemente. Hier liegt keine Entartung vor, da alle xij in den markierten Elementen größer als Null sind. Die xij in den nicht markierten Elementen sind immer Null (Werte der NBV sind Null). Inhaltlich bedeutet das: Vom Ort A1 müssen 6 ME zum Ort B1 transportiert werden, von A1 zu B2 werden 6 ME transportiert,… von A3 zu B4 werden 8 ME transportiert. Dann können die A-Orte alles absetzen und die B-Orte den Bedarf decken. Der ZF-Wert beträgt z = 50 · 6 + 63 · 6 + 52 · 4 + 24 · 14 + 120 · 12 + 44 · 8 = 3014. Es gibt verschiedene Möglichkeiten, eine zulässige Basislösung schnell zu konstruieren. Zulässige Basislösung: -

m+n-1 markierte Basisvariablen (markierte Elemente) Einhaltung der Nebenbedingungen Spezielle Struktur der Anordnung der markierten Elemente

Einfachste Möglichkeit: Nord-West-Eckenregel m+n-1 Felder werden stufenförmig von links oben (Nord-West) nach rechts unten (Süd-Ost) mit der jeweils maximal möglichen Transportmenge belegt (auch die Menge 0 ist möglich). Nachteil: die Kosten bleiben unberücksichtigt Vorteil: einfaches Verfahren

zulässige Basislösung nach Nord-West-Eckenregel B1 A1

B2

50

B3

B4

63

84

60

52

24

136

ai 12

12 A2 A3 bj

84 6 120

76

18

2

10 100

44 12

18

10

14

8 8

20

Es sind also x11 = 12, x21 = 6, x22 = 10, x23 = 2, x33 = 12, x34 = 8 die 6 Basisvariablen (BV), die zugehörigen Felder sind die markierten Elemente. Hier liegt keine Entartung vor, da alle xij in den markierten Elementen größer als Null sind. Die xij in den nicht markierten Elementen sind immer Null (Werte der NBV sind Null). Inhaltlich bedeutet das: Vom Ort A1 müssen 12 ME zum Ort B1 transportiert werden, von A2 zu B1 werden 6 ME transportiert,… von A3 zu B4 werden 8 ME transportiert. Dann können die A-Orte alles absetzen und die B-Orte den Bedarf decken. Der ZF-Wert beträgt z = 50 · 12 + 84 · 6 + 52 · 10 + 24 · 2 + 100 · 12 + 44 · 8 = 3224.

Exkurs Entartung Zwischenüberlegung an einem anderen Beispiel: Bestimmung einer zulässigen Basislösung bei Entartung Analoges Vorgehen, aber: falls durch eine Zuordnung sowohl die Zeilen- als auch die Spaltenbeschränkung erfüllt werden, bleibt keine Differenz, die weiterverteilt werden kann, dann wird in der Zeile bzw. Spalte, die „dran“ wäre eine Basisvariable Null gesetzt, um die noch vorhandenen Kapazitäten verteilen zu können. Beispiel 2: zulässige Basislösung nach Nord-West-Eckenregel bei Entartung Die Bedarfsmengen bj sind gegenüber dem bisherigen Beispiel geändert. Nach der Zuordnung von 10 ME, die von A2 nach B2 transportiert werden sollen, bleibt man „hängen“. Gemäß Nord-West-Eckenregel muss die nächste Zuordnung im Feld von A3 zu B2 erfolgen. Dort wird die Transportmenge 0 eingetragen, dann geht es weiter, bis alles verteilt ist. B1 A1 A2 A3 bj

B2

50

B3

63

B4

84

60

24

136

100

44

ai 12

12 84

52 8

120

76

8

0 20

18

10

10

8

12

20

12

Eine zulässige Basislösung mit 6 Basisvariablen (markierten Elementen) ist gefunden. Ende des Exkurses, weiter mit dem Ausgangsbeipiel

Schritt 2: Optimierung der Zielfunktion Opportunitätskosten – wie kann man zu geringeren Kosten kommen? Es werden nun Varianten durchgespielt, die beleuchten, wie sich die Kosten ändern würden, wenn von dieser Ausgangslösung abgewichen wird. Die Änderung wird immer so vollzogen, dass die spezielle Struktur der markierten Elemente erhalten bleibt. Da die Zeilensummen und Spaltensummen vorgegeben sind, muss entsprechend in der jeweiligen Zeile und Spalte eine ME weniger korrigierend ausgeglichen werden. Danach in diesen Zeilen bzw. Spalten wieder korrigieren, solange, bis die Summen stimmen. Abwechselnd wird also addiert und

subtrahiert. Man benötigt einen kleinsten „Kreis“, der außer dem neuen Feld nur markierte Elemente enthält. Die (theoretische) Kostenänderung, die sich durch diese Verschiebung ergeben würde, bezeichnet man als Opportunitätskosten oij. Genauer bezeichnet man also mit oij die Änderung der Zielfunktion, die sich ergeben würde, wenn eine ME neu von Ai zu Bj transportiert werden würde und dafür entsprechend andere Transportmengen in einem kleinsten Kreis markierter Elemente abwechselnd um eine ME verringert bzw. erhöht werden würden. Wir überlegen uns das an der zulässigen Basislösung für das Ausgangsbeispiel (ohne Entartung), die mit der Nord-West-Eckenregel bestimmt wurde. a) Was würde passieren, wenn eine ME von A1 zu B2 transportiert wird? B1 A1 A2 A3

B2

50

B3

63 12-1

84

84

60

24

136

6+1

12

76

18

2

10-1 100

44 12

18

bj

ai

+1 52

120

B4

10

8

14

20

8

Auswirkung auf die ZF: die Änderung beträgt 63 ·(+1) + 50·(-1) + 84 ·(+1) + 52·(-1) = 63 – 50 + 84 – 52 = 45 Opportunitätskosten o12 = 45 Sind die Opportunitätskosten größer als Null, würde sich der ZF-Wert vergrößern, wenn diese durchgespielte Verschiebung tatsächlich vollzogen werden würde. Da die ZF aber verkleinert werden soll, ist diese (durch rot markierte Addition bzw. Subtraktion einer Mengeneinheit durchgespielte) Verschiebung nicht zielführend.

b) Was würde passieren, wenn eine ME von A3 zu B2 transportiert wird? B1 A1 A2 A3 bj

B2

50

B3

B4

63

84

60

52

24

136

ai 12

12 84 6 120

76

100

44 12 -1

+1 18

10

18

2 +1

10 -1

14

8

20

8

Auswirkung auf die ZF: die Änderung beträgt 76 ·(+1) + 52·(-1) + 24 ·(+1) + 100·(-1) =76 – 52 + 24 – 100 = – 52 Opportunitätskosten o32 = – 52

Sind die Opportunitätskosten kleiner als Null, kann der ZF-Wert verkleinert werden dadurch, dass von A3 nach B2 transportiert wird. Diese Änderung verringert die ZF, ist also zielführend. Wie viel kann transportiert werden? Maximal 10 ME, da x22 nicht kleiner als Null werden darf. Neues Tableau

B1 A1

B2

50

B3

B4

63

84

60

52

24

136

ai 12

12 A2 A3

84 6 120

76

100

44 2

10

bj

18

18

12

0

10

20

8

14

8

Man erhält eine neue zulässige Basislösung mit kleinerem ZF-Wert: Wenn x11 = 12, x21 = 6, x23 = 12, x32 = 10, x33 = 2, x34 = 8 ist, beträgt der ZF-Wert nur noch z = 50 · 12 + 84 · 6 + 24 · 12 + 76 · 10 + 100 · 2 + 44 · 8 = 2704 (= 3224 - 52· 10)

Man benötigt eine einfache Methode, um jeweils für alle nicht markierten Felder die Opportunitätskosten zu bestimmen.

Bestimmung der Opportunitätskosten mit Hilfe von Potentialen

Wir gehen von der zulässigen Basislösung nach Nord-West-Eckenregel aus und bestimmen zunächst die Potentiale pi für alle Anbieter (Hilfsspalte neben der ai-Spalte) und qj für alle Bedarfsorte (Hilfszeile unter der bj-Zeile). B1 A1 A2 A3 bj

B2

50

B3

B4

63

84

60

52

24

136

ai 12

12 84 6 120

76

18

2

10 100

44 12

18

10

14

8

20

8

zulässige Basislösung nach Nord-West-Eckenregel mit Potentialen Ansatz: Dazu werden alle markierten Elemente betrachtet (d.h. Felder, die eine blaue Zahl enthalten und somit zu BV gehören). Für diese Felder muss gelten, dass die Kosten die Summe der beiden zugehörigen Potentiale sind, d.h. cij = pi + qj für alle markierten Elemente. Da m+n-1

Elemente markiert sind und m+n Potentiale berechnet werden sollen, darf ein Potential beliebig vorgegeben werden, z.B. beginnen wir mit p1 = 0. Dann wird q1 so bestimmt, dass p1 + q1 = 50 ist. Danach bestimmt man p2 usw….

B1 A1 A2 A3 bj qj

B2

50 12 84

84

60

45 52

94 24

126 136 168 44

2+

10 – 76 – 52

18 50

B4

63

6 120 – 40

B3

100

+ 10 18

12 – 14 -10

8

ai

pi

12

0

18

34

20

110

8 - 66

Nun werden für alle nicht markierten Elemente die Opportunitätskosten berechnet, indem von den Ausgangskosten die jeweiligen Zeilen- und Spaltenpotentiale abgezogen werden. oij = cij – pi – qj für alle nicht markierten Elemente. Diese Opportunitätskosten tragen wir mit grün in die entsprechenden Felder ein. Man kann auch eine Extra-Tabelle mit dieser „Kostenreduktionsmatrix“ aufschreiben. Beispiel für das Feld in der 3. Zeile und 2. Spalte o32 = 76 – 110 – 18 = – 52 . Da es Opportunitätskosten kleiner als Null gibt, kann die ZF noch verringert werden. Wir wählen das Feld mit den kleinsten Opportunitätskosten aus und weisen diesem Feld die maximal mögliche Menge 10 zu.

allgemein Optimalitätskriterium: Eine zulässige Basislösung ist optimal, falls alle Opportunitätskosten größer oder gleich Null sind. Falls es Opportunitätskosten kleiner als Null gibt, kann die ZF noch verringert werden. Wir wählen das Feld mit den kleinsten Opportunitätskosten aus und weisen diesem Feld die maximal mögliche Menge (gemäß den zugehörigen Werten in der ai-Zeile und bj-Spalte) zu. Auf einem kürzesten Kreis markierter Elemente wird die neue Transportmenge so verschoben, dass die Nebenbedingungen nicht verletzt werden. Dadurch, dass die maximal mögliche Menge verschoben wird, entspricht dieses Vorgehen einem Tausch einer Basisvariable (an einer bisher markierten Stelle entsteht eine 0, diese Variable wird NBV). Suche nach einem kürzesten Kreis Zwei Matrixelemente heißen benachbart, wenn sie in derselben Zeile oder Spalte stehen. Es wird eine Verbindung von dem neu aufzunehmenden Element mit den schon markierten Elementen so gesucht, dass jeweils abwechselnd in Zeile und Spalte benachbarte markierte Elemente gewählt werden.

In diesem Kreis wird abwechselnd addiert und subtrahiert, die maximal zu verschiebende Menge ist die kleinste Zahl, die mit einem Minus versehen ist. Diese Menge wird nun bei den Kreiselementen addiert bzw. subtrahiert. Das Vorgehen wird solange wiederholt, bis alle Opportunitätskosten größer oder gleich Null sind und somit eine Optimallösung gefunden ist. Weiter Beispiel: neues Tableau mit den entsprechenden Potentialen B1 A1 A2 A3

B2

50

B3

B4

63

84

60

52

24

136

12 84

12

6 120

76

100

44 2

10

bj qj

18 50

10 -34

8

14 -10

8 - 66

B3

B4

ai

pi

12

0

18

34

20

110

ai

pi

12

0

18

34

20

110

Berechnung der neuen Opportunitätskosten B1 A1 A2 A3 bj qj

B2

50 12 84 6 120

63 97 52 52 76

84 94 24 12 100

– 40

2

10 18 50

10 -34

60 126 136 168 44

14 -10

8 8 -66

Nicht optimal, ZF-Wert kann verringert werden, wenn x31 BV wird. Um zu entscheiden, welche Variable NBV wird, braucht man den kürzesten Kreis von markierten Elementen, der die neue BV einschließt. B1 A1 A2 A3 bj qj

B2

B3

B4

ai

12 6–

+

12 + 10

2–

8

pi

Die maximal zu verschiebende Menge beträgt 2 (Minimum der mit – markierten Elemente), es wird also x33 zur NBV und man erhält nun nach dem Tausch von x33 zu x31 diese markierten Elemente (Basisvariablen). B1 A1

B2

B3

B4

ai

pi

12

A2

14

4

A3

2

8

10

bj qj Nun werden wieder Potentiale und Opportunitätskosten berechnet, es ergibt sich B1 A1 A2 A3 bj qj

B2

50 12 84 4 120

63 57 52 12 76

B4

84 94 24

60 86 136 14

100

2 18 50

B3

10 10 6

128 44

40

8 14 -10

ai

pi

12

0

18

34

20

70

8 - 26

Alle Opportunitätskosten sind größer als Null die Optimallösung ist gefunden. Minimale Kosen entstehen, wenn x11 = 12, x21 = 4, x23 = 14, x31 = 2, x32 = 10, x34 = 8 und alle anderen Variablen Null sind. Inhaltlich bedeutet das: Vom Ort A1 müssen 12 ME zum Ort B1 transportiert werden, von A2 zu B1 werden 4 ME transportiert,… von A3 zu B4 werden 8 ME transportiert. Dann können die A-Orte alles absetzen und die B-Orte den Bedarf decken. Der minimale ZF-Wert beträgt z = 50 · 12 + 84 · 4 + 24 · 14 + 120 · 2 + 76 · 10 + 44 · 8 = 2624....