Operations ResearchÜbungen zu 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 je Ort Bedarfsorte Bedarfsmenge je Ort Transportkosten von A nach B sind Menge von A nach B ist

Das Transportproblem

mA 1

ian-1 B

kb

ikcikx

Einführendes Beispiel

Eine Fluggesellschaft verfügt über zwei Heimatflughäfen Wien und Innsbruck, mit Wien=4 Flugzeugen sowie Innsbruck=3 Flugzeugen.

Sie soll für einen Reiseveranstalter Flugzeuge für die Flughäfen München und Frankfurt mit Franfurt=2 und München=2 Maschinen bereitstellen.

Die Kosten (Sie orientieren sich an der Distanz – Faktor x 100km) für den Transport sind in folgender Kostenmatrix dargestellt:

min24

47)(

ikc

Beispiel

Gesamtaufkommen größer Gesamtbedarf

Beispiel

Gesamtaufkommen größer Gesamtbedarf

Anbieter

Kosten/ Distanz

Kosten/ Distanz

Wien 7 4Innsbruck

4 2

Frankfurt München

7

4

2

4

Beispiel

Zusätzlicher Nachfrager mit 0 Kosten

Kosten Kosten Kosten Menge Anbieter

7 4 0 4 Wien

4 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Anbieter Kosten/ Distanz

Kosten/ Distanz

Wien 7 4Innsbruck 4 2

Frankfurt München

MengeNachfrage

r

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

7 4 0 4 Wien

4 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

1.) zeilenweise die erste kleinste Bewertungszahl, anfangs nur reale Transporte2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

1 Rest

Beispiel Gesamtaufkommen größer Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

7 0 4 Wien

4 0 1 Innsbruck

2 3

Frankfurt fiktiver Flughafen

Menge

Beispiel Gesamtaufkommen größer Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

7 0 4 Wien

4 1 0 1 Innsbruck

2 3

Frankfurt fiktiver Flughafen

1 Rest

Beispiel Gesamtaufkommen größer Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl, so lange wie möglich nur reale Transporte.2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

7 0 4 Wien

1 3

Frankfurt fiktiver Flughafen

Menge

Beispiel Gesamtaufkommen größer Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl, so lange wie möglich nur reale Transporte.2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

7 1 0 4 Wien

1 3

Frankfurt fiktiver Flughafen

3 Rest

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Menge Anbieter

0 3 Wien

3fiktiver Flughafen

1.) zeilenweise die erste kleinste Bewertungszahl, so lange wie möglich nur reale Transporte.2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

Menge

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Menge Anbieter

0 3 3 Wien

3fiktiver Flughafen

1.) zeilenweise die erste kleinste Bewertungszahl, so lange wie möglich nur reale Transporte.2.) Eintrag des Kostenoptimums3.) Abwechselndes streichen v. Spalten/ Zeilen

0 Rest

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

7 4 0 4 Wien

4 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Eintragung aller Kostenoptima ergibt eine mögliche Lösung:

Z =?

Menge

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

7 1 4 0 3 4 Wien

4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Eintragung aller Kostenoptima ergibt eine mögliche Lösung:

Z =7x1+ 0x3+ 4x1+ 2x2= 15

Beispiel

Suche nach dem optimalen Ergebnis

Einführung von Potenzialen nach der MODI/Potenzialmethode.

Für jedes Anbieter und für jeden Nachfrager werden die Potenziale u und v festgelegt.

Kosten Kosten Kosten Menge Anbieter

7 1

4 0 3 4 Wien

4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

kv

iu

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0

7 1

4 0 3 4 Wien

4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Die Einführung von Potenzialen erfolgt nach ; 01 v

ikki cvu

ki vu \

kv

iu

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0

7 1

4 0 3 4 Wien

4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Die Einführung von Potenzialen erfolgt nach Es werden nur besetzte Felder herangezogen erstes besetztes Feld

ikki cvu

ki vu \

kv

iu

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1

4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

Transporttabelle nach Einführung der Potenziale mit der Formel: ikki cvu

ki vu \

kv

iu

Menge

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1

4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Einführen von fiktiven Bewertungszahlen mit Hilfe der Potenziale mit

Nur nichtbesetzte Felder

ikkiik cvuc

1

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1

4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver FlughafenZ =7x1+ 0x3+ 4x1+ 2x2= 15

ki vu \

Einführen von fiktiven Bewertungszahlen mit Hilfe der Potenziale mit

Nur nichtbesetzte Felder

ikkiik cvuc

1

3

Das Optimalitätskriterium ist noch nicht erfüllt, da eine Bewertungszahl noch positiv ist.

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1

4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Feld der höchsten positiven Bewertungszahl wird mit versehen. Streichen aller Zeilen und Spalten, die nur ein besetztes Feld aufweisen. Das Deltafeld wird mitgezählt.

1

3

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1

4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Feld der höchsten positiven Bewertungszahl wird mit versehen. Streichen aller Zeilen und Spalten, die nur ein besetztes Feld aufweisen. Das Deltafeld wird mitgezählt.

1

3

Spalte weist nur ein besetztes Feld auf

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1 4 0 3 4 Wien

4 4 1 2 2 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \1

3

Geschlossener Zickzackweg abwechselnd in vertikaler und in horizontaler Richtung. (Nur über besetzte Felder)

In den besetzten Feldern wird abwechselnd -/+ hinzugefügt.

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -7

7 7 1-

4 0 3 4 Wien

4 4 1+ 2 2- 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \1

3

Geschlossener Zickzackweg abwechselnd in vertikaler und in horizontaler Richtung. (Nur über besetzte Felder)

In den besetzten Feldern wird abwechselnd -/+ hinzugefügt.

1)2,1min( ; -aller unter Minimum Werte(1- ); (2- ) 1

Dann in einsetzen

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

7 4 1 0 3 4 Wien

4 2 2 1 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Einsetzen in Es sollten sich immer m+n-1=4 besetzte

Felder ergeben

ikki cvu ikkiik cvuc

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0

7 4 1 0 3 4 Wien

4 2 2 1 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Einfügen der neuen Potenziale und Bewertungszahlen

ikki cvu ikkiik cvuc

Beispiel Gesamtaufkommen größer Gesamtbedarf

Kosten Kosten Kosten Menge Anbieter

0 -2 -6

6 7 4 1 0 3 4 Wien

4 4 2 2 1 0 3 Innsbruck

2 2 3

Frankfurt München fiktiver Flughafen

ki vu \

Einfügen der neuen Potenziale und Bewertungszahlen

ikki cvu ikkiik cvuc

1

2

Z =4x1+ 4x2+ 2x1+ 0x3= 14

Alle Bewertungszahlen sind neg. Optimalitätskriterium

Beispiel

Gesamtaufkommen größer Gesamtbedarf

Anbieter

Kosten/ Distanz

Kosten/ Distanz

Wien 7 4Innsbruck

4 2

Frankfurt München

0

2 Stück

1 Stück

1 Stück

Grafische Darstellung der Lösung:

Beispiel

Gesamtaufkommen größer Gesamtbedarf

Übungsbeispiel I

Gesamtaufkommen Gesamtbedarf Eine Molkereizentrale verfügt über zwei

Lager L1, L2 mit l1=40l, l2=60l und hat zwei Abnehmer A1, A2 mit a1=70l und a2=50l.

Die Kosten für den Transport sind in folgender Kostenmatrix dargestellt:

62

43( )ikc

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

Gesamtaufkommen = 100l Gesamtbedarf = 120l Einführen eines fiktiven Anbieters L3 in

Höhe der Differenz, also 20l mit Null Transportkosten.

Kosten Kosten Menge Anbieter

3 4 40l Lager 1

2 6 60l Lager 2

0 0 20l Lager 3

70l 50l

Abnehmer1 Abnehmer2

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl-anfangs nur echte Transporte

2.) Eintrag des Kostenoptimums 3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

3 4 40l Lager 1

2 60 6 60l Lager 2

0 0 20l Lager 3

70l 50l

Abnehmer1 Abnehmer2

10l Rest

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl, anfangs nur echte Transporte

2.) Eintrag des Kostenoptimums 3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Kosten Menge Anbieter

3 10 4 40l Lager 1

0 0 20l Lager 3

10l 50l

Abnehmer1 Abnehmer2

30l Rest

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl, anfangs nur echte Transporte

2.) Eintrag des Kostenoptimums 3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Menge Anbieter

4 30 30l Lager 1

0 20l Lager 3

50l

Abnehmer2

20l Rest

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

1.) zeilenweise die erste kleinste Bewertungszahl, anfangs nur echte Transporte

2.) Eintrag des Kostenoptimums 3.) Abwechselndes streichen v. Spalten/ Zeilen

Kosten Menge Anbieter

0 20

20l Lager 3

20l

Abnehmer20l Rest

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

Kosten Kosten Anbieter

3 10 4 30 Lager 1

2 60 6 Lager 2

0 0 20 Lager 3

Abnehmer1 Abnehmer2

Eintragung aller Kostenoptima ergibt eine mögliche Lösung

ikc ikx

Z =3x10 + 4x30 + 2x60 + 0x20 = 270

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

Kosten Kosten Anbieter

0 1

3 3 10 4 30 Lager 1

2 2 60 6 Lager 2

-1 0 0 20 Lager 3

Abnehmer1 Abnehmer2

Die Einführung von Potenzialen erfolgt nach ; nur besetzte Felder

ki vu \

01 vikki cvu

Übungsbeispiel IGesamtaufkommen kleiner Gesamtbedarf

Kosten Kosten Anbieter

0 1

3 3 10 4 30 Lager 1

2 2 60 6 Lager 2

-1 0 0 20 Lager 3

Abnehmer1 Abnehmer2

ki vu \

Einführen von fiktiven Bewertungszahlen mit Hilfe der Potenziale.

ikkiik cvuc

1

3

Alle Bewertungszahlen sind negativ Optimaltätskriterium

Z =3x10 + 4x30 + 2x60 + 0x20 = 270