Transportproblem: Unterschied zwischen den Versionen

Version vom 31. Januar 2008, 18:26 Uhr

Grundlegendes Konzept

Das Transportproblem ist ein Sonderfall des MaxFlow-Problems. Dabei soll die optimale Transportzuordnung eines homogenen Gutes x bestimmt werden (vgl. HMM 7.5.3). Es gibt i Angebotsorte mit einem Angebot von a_i Mengeneinheiten des Produktes x, und j Bedarfsorte mit einem Bedarf von b_j Mengeneinheiten, wobei zu beachten ist, dass immer Angebot = Bedarf sein muss. Nun besteht die Aufgabe darin, den Transport der Angebotsmengen zu den Bedarfsorten so zu verteilen, dass die Transportkosten c_ij minimal werden.
Um dies etwas anschaulicher zu erläutern, wollen wir als vereinfachtes Beispiel annehmen, dass die Stadt Hamburg 3 neue Parkbänke für die Fußgängerwege entlang der Alster benötigt. Die Firma XY, die die Parkbänke produziert, hat Niederlassungen in Bremen, München und Kaiserslautern, von wo aus die baugleichen Bänke geliefert werden könnten. Somit wird schnell deutlich, dass der Transport von Bremen der günstigste sein würde, da die Entfernung um ein vielfaches kürzer ist, als zu den übrigen Niederlassungen. Allerdings können die Transportkosten bei realen Problemen von vielen Einflussgrößen, und nicht nur von der Entfernung, abhängig sein.

Mathematische Formulierung

a_i : Angebotsmenge am Angebotsort i (i=1,...,m)
b_j : Bedarfsmenge am Bedarfsort j (j=1,...,n)
c_ij : Transportkosten je ME von Angebotsort i zu Bedarfsort j
x_ij : Transportmenge von i nach j

  
Minimiere K = ∑i ∑j cijxij
      
 ∑j xij = ai  für alle i
      
 ∑i xij = bj  für alle j
             
    xij ≥ 0   für alle i,j
      
Eine Lösung exisitiert nur, wenn
            
  ∑i ai = ∑j bj

Erörterung am Beispiel

Eröffnungsverfahren

Nord-West-Ecken Verfahren

Das Nord-West-Ecken Verfahren stellt kein Näherungsverfahren im eigentlichen Sinne dar und hat nur noch traditionelle Bedeutung. Es wird heute eigentlich nicht mehr verwendet, da es durch die Nichtberücksichtigung der Kosten eine relative ungenaue erste Lösung liefert.
Man beginnt im ersten Feld der Matrix (oben links) und beliefert diesen Bedarfsort mit der maximal möglichen Menge. Die größtmögliche Menge ergibt sich jeweils aus dem Minimum von Angebots- und Bedarfsmenge. In diesem Fall wird Frankfurt 35 ME nach Köln liefern. Die restliche Angebotsmenge von 10 ME wird nun dem nächsten Feld (ein Schritt nach rechts) zugeteilt. Somit ist das Angebot aus Frankfurt vollkommen aufgebraucht und man springt zum nächsten Angebotsort.
Paris muss nun zu erst den Restbedarf in Hamburg mit 20 ME decken. Nun wird dem nächsten Feld (Wien) die wiederum größtmögliche Menge zugeteilt, die in diesem Fall durch den Bedarf (Wien) auf 35 ME beschränkt ist. Dadurch bleiben in Paris weitere 25 ME übrig, die daher dem letzten Bedarfsort Bern geliefert werden.
Der Bedarf von Bern ist allerdings noch nicht vollkommen gedeckt, denn er beläuft sich noch auf weitere 40 ME. Diese Restmenge kann nun vom letzten Angebotsort gedeckt werden.
Abschließend erkennt man bei der Kontrolle der gesamten Angebots- und Bedarfsmenge, dass die Bedingung Angebot=Bedarf erfüllt ist, und somit weder ein ungedeckter Bedarf zu finden ist, noch eine nicht verteile Angebotsmenge.

Die Kritik an dem Verfahren, die bereits anfangs genannt wurde, erkennt man auch sehr deutlich an den Pfeilen im Schaubild. Die Tatsache, dass unabhängig der angegeben Kosten, im oberen linken Feld begonnen wird, und man stufenweise nach unten rechts „wandert“, macht betriebswirtschaftlich wenig Sinn. Die ungenaue Ausgangslösung kann dazu führen, dass man unnötig viele Iterationsschritte durchführen muss, um die Optimallösung zu finden.

Zeilen-Spalten-Sukzession

Das Verfahren der Zeilen-Spalten-Sukzession stellt eine sehr gute Methode zur Bestimmung der Ausgangslösung dar.
Man beginnt mit der Zuteilung der Mengen im günstigsten Feld der gesamten Matrix (Berlin-Köln). Diesem Feld wird die größtmögliche Menge zugeordnet, wobei sich diese Menge wiederum durch die Beschränkung des Minimums von Angebot und Bedarf ergibt. Durch diese Zuteilung ist nun entweder der Bedarf des Ortes gedeckt oder das Angebot aufgebraucht. In diesem Fall ist der Bedarf von Köln gedeckt und in Berlin noch ein Angebot von 5 ME vorhanden. Daher bleibt man nun in der Zeile (Berlin) und ordnet dem nächst günstigsten Feld (Hamburg) die Restmenge zu. Da dadurch das Angebot Berlins verbraucht ist, allerdings in Hamburg noch ein Bedarf von 25 ME übrig bleibt, sucht man das nächst günstigste Feld in der aktuellen Spalte (Hamburg) und bestimmt für dieses die maximale Menge.
Nach diesem Schema wird verfahren bis alle Bedarfe gedeckt, und alle Angebotsmengen verbraucht sind.

Zusammenfassung der Vorgehensweise:

1. Dem günstigsten Feld der Gesamtmatrix die maximal mögliche Menge zuordnen
2. Dem nächst günstigsten Feld in der Zeile od. Spalte die Restmenge zuteilen
3. Fortführen bis jeglicher Bedarf gedeckt ist

Durch die Berücksichtigung der Kosten liefert diese Methode eine gute erste Näherung der Lösung und wird daher auch öfters verwandt.

einfaches Zeilenfolge-/Spaltenfolgeverfahren

Hierbei handelt es sich um 2 verschiedene Verfahren, die allerdings schematisch gleich funktionieren. Wir wollen hier anfangs das Zeilenfolge-Verfahren erläutern und am Ende auch kurz auf das Spaltenfolge-Verfahren eingehen. Beim Zeilenfolge-Verfahren wird im günstigsten Feld der ersten Zeile mit der Zuteilung der größtmöglichen Menge begonnen. Die größtmögliche Menge ergibt sich, wie bereits bei den anderen Verfahren erklärt, aus dem Minimum von Bedarf und Angebotsmenge. In unserem Beispiel ordnen wir dem Feld Frankfurt-Wien 35 ME zu. Anschließend wird die Restmenge dem nächst günstigsten Feld in der Zeile zugeteilt. Ist die Menge eines Angebotsortes aufgebraucht wird der nächste Angebotsort betrachtet. Dort wird wiederum mit dem günstigsten Feld der Zeile begonnen, und die Mengen Stück für Stück an die jeweils nächst günstigsten Felder verteilt.

Zusammenfassung der Vorgehensweise:

1. Zuteilung der max. möglichen Menge ins günstigste Feld der 1. Zeile
2. Verteilung der Restmengen auf die jeweils nächst günstigsten Felder dieser Zeile
3. Wiederholung des Verfahrens für jede Zeile

Das Spaltenfolge-Verfahren läuft prinzipiell genauso ab, nur wird dabei im günstigsten Feld der ersten Spalte begonnen, und man durchläuft die Matrix spaltenweise.

Das Verfahren liefert durch den willkürlichen Beginn in der 1. Zeile (Spalte) eine einigermaßen gute Näherung und ist durch die Berücksichtigung der Kosten (innerhalb der Zeilen) wenigstens dem Nord-West-Ecken-Verfahren vorzuziehen.

Matrixminimumverfahren

Ein weiteres brauchbares Verfahren zur Bestimmung einer Ausgangslösung stellt das Matrixminimumverfahren dar. Dabei beginnt man im günstigsten Feld der Gesamtmatrix (Berlin-Köln) und teilt diesem die größtmögliche Menge zu (35 ME). Anschließend sucht man das nächst günstigste Feld der Gesamtmatrix, dem daraufhin die wiederum maximal mögliche Menge zugeteilt wird. In unserem Fall wäre dies Frankfurt-Wien mit Kosten von 45 GE, dem eine Menge von 35 ME zugeordnet wird. Daraufhin wird das nächst günstigste Feld der Gesamtmatrix gesucht, und auch diesem wird wieder die größtmögliche Menge zugeteilt. Dieses einfache Verfahren verteilt also die Mengen auf die Felder in der Reihenfolge der Kosten, wobei beim Feld mit den geringsten Kosten begonnen wird. Zu beachten ist vor allem, dass bei der Suche der Felder immer die gesamte Restmatrix Beachtung findet, und nicht nur einzelne Zeilen oder Spalten. Die zugeordnete Menge entspricht, wie auch schon bei allen anderen Verfahren, jeweils dem Minimum des (Rest-)Bedarfs oder (Rest-)Angebots eines Angebots- oder Bedarfsortes.

Kostendifferenzverfahren

Das Kostendifferenzverfahren ist eine etwas aufwändigere Vorgehensweise, die allerdings die beste Näherung der Lösung liefert. Manchmal wird dieses Verfahren auch nach seinem Erfinder mit Vogel´s Approximation Method (VAM) bezeichnet.
Der Grundgedanke besteht darin, dass man in jedem Schritt zuerst die Kostendifferenzen zwischen dem günstigsten und zweitgünstigsten Feld für jede Zeile und jede Spalte ermittelt. Anschließend wählt man die Zeile oder Spalte, deren Differenz am größten ist, und ordnet dem günstigsten Feld dieser Zeile (Spalte) die maximale Menge zu. Daraufhin werden wiederum für jede Zeile und jede Spalte die Kostendifferenzen gebildet, und die Menge nach dem angegeben Kriterium zugeteilt. Ist der Bedarf einer Spalte gedeckt oder das Angebot einer Zeile aufgebraucht braucht dieser Zeile (Spalte) keine weitere Beachtung geschenkt werden, und man kann sie daher streichen. Dieses etwas komplexere Vorgehen wollen wir am Beispiel ausführlich erläutern.
Dafür bestimmen wir nun also die Kostendifferenz zwischen dem günstigsten und dem zweitgünstigsten Feld in Spalte 1. Diese ergibt sich zu (50-15 = ) 35 und wird am unteren Ende der Spalte notiert. Nun muss auch für die übrigen Spalten und Zeilen jeweils die Kostendifferenz bestimmt werden. Exemplarisch errechnet sich der Wert in Zeile 1 zu 50 – 45 = 5 . Hat man nun alle Kostendifferenzen ermittelt, gilt es den größten Wert aller Differenzen zu finden. Das Maximum finden wir bei Hamburg mit einer Kostendifferenz von 50 GE (in der Graphik zeigt die Zahl in der Klammer jeweils an, in welchem Schritt dieser Wert das Maximum darstellt). Daher ordnen wir nun dem günstigsten Feld der Spalte Hamburg die maximal mögliche Menge zu, nämlich dem Feld Berlin-Hamburg 30 ME. Aus der Tatsache, dass nun der Bedarf von Hamburg vollkommen gedeckt ist, ergibt sich, dass wir diese Spalte im Folgenden nicht mehr berücksichtigen müssen und sie daher, der Übersichtlichkeit wegen, durchstreichen.
Anschließend müssen wir wiederum alle Kostendifferenzen bestimmen, wobei zu beachten ist, dass die Werte der Spalte Hamburg außen vor gelassen werden. Somit ändert sich z.B. die Kostendiff. der Zeile Berlin auf (70-15 = ) 55. Nachdem alle Werte berechnet sind, erkennt man, dass gerade der Wert der Zeile Berlin das Maximum darstellt, und man somit das günstigste Feld dieser Zeile suchen muss. Wir ordnen nun also dem Feld Berlin-Köln die größtmögliche Menge von 10 ME zu, die durch das Restangebot der Zeile beschränkt wird. Da das Angebot von Berlin dadurch vollständig aufgebraucht ist, kann auch diese Zeile nun gestrichen werden, und bedarf keiner weiteren Berücksichtigung.
Nun werden wiederum jegliche Kostendifferenzen gebildet und nach dem nun ausführlich erklärten Schema die Mengen zugeordnet. Dieses Verfahren wird so oft wiederholt bis alle Angebotsmengen verbraucht und alle Bedarfsmengen gedeckt sind.

Bestimmung der Optimallösung

Zur Erläuterung des Verfahrens zur Bestimmung der optimalen Lösung wollen wir die Ausgangslösung verwenden, die wir mit Hilfe des Kostendifferenzverfahrens ermittelt haben. Da wir angenommen hatten, dass dieses die beste Näherung liefert, sollten wir mit den wenigsten Iterationen zur optimalen Lösung kommen.

Im ersten Schritt müssen wir die Anzahl der Basisfelder mit folgender Formel bestimmen:

  m + n -1 = Anzahl der Basisfelder
  m = Anzahl der Angebotsorte und n= Anzahl der Bedarfsorte

Dieser Formel liegt der Gedanke zu Grunde, dass man zur Umverteilung der Mengen immer einen vollständigen Baum benötigt. In unserem Falle haben wir also 3+4-1 = 6 Basisfelder. Als Basisfelder werden zuerst die Felder deklariert, denen bereits eine Menge x_ij zugeteilt wurde. In unserem Beispiel gibt es 6 Basisfelder und 6 Felder mit einer Menge, wodurch sich die Sache vereinfacht. Wären z.B. nur 5 Felder vorhanden, die eine Menge x_ij beinhalten würden, so müsste das 6. Basisfeld frei gewählt werden. In den Basisfeldern werden nun die reduzierten Kosten c_ij* gleich Null gesetzt, wobei man der Übersichtlichkeit halber anstatt einer Null ein X notiert. Anschließend setzt man einen beliebigen Multiplikator u_i oder v_j ebenfalls 0. Dabei ist die Wahl zwar prinzipiell auch egal, allerdings sollte man den Multiplikator der Zeile oder Spalte wählen, in der die meisten Basisfelder sind, da dies die weitere Berechnung vereinfacht. Nun berechnen wir die restlichen Multiplikatoren mit Hilfe der folgenden Formel:

          cij* = cij - ui - vj

die dann je nach Bedarf nach u_i oder v_j umgestellt werden kann

          ui =  cij - cij* - vj
          vj =  cij - cij* - ui

In unserem Fall setzten wir das u_i der Zeile Paris gleich 0. Dadurch können wir mit Hilfe der oben genannten Formel v_j für Köln, Wien und Bern sofort ablesen, da die reduzierten Kosten, wie auch der Multiplikator u_i null sind. Somit ergeben sich die Multiplikatoren dieser Spalten zu den Kosten der Felder der Zeile Paris. v_Köln = 55, v_Wien = 50 und v_Bern = 115. Nun gilt es einen Weg zu finden, wie die restlichen Multiplikatoren zu berechnen sind. Es bietet sich z.B. an, den Wert für u_Berlin zu bestimmen, der sich zu 15 – 0 - 55 = - 40 ergibt. Anschließend ergibt sich v_Hamburg zu 50 -0 - (-40 ) = 90. Es fehlt nur noch u_Frankfurt, welcher sich durch 70 – 0 – 115 = - 45 bestimmt.

Im nächsten Schritt werden wir mit der oben genannten Formel, und den bereits berechneten Multiplikatoren, die restlichen reduzierten Kosten c_ij* der Matrix bestimmen. Exemplarisch ergeben sich die reduzierten Kosten im Feld Frankfurt-Köln zu 50 - (-45) – 55 = 40. Durch einsetzen der weiteren Werte in die Formel ergeben sich die übrigen c_ij* die in der unten stehenden Tabelle angegeben sind.

Da nun alle benötigten Werte berechnet sind, muss man sich überlegen, wie man die Kosten reduzieren, und somit die Lösung verbessern kann. Die reduzierten Kosten der Matrix geben an, wieviele GE man einsparen könnte, wenn man eine bestimmte Menge über diese Felder verteilen würde, anstatt über den bisherigen Weg. Das Feld mit den größten negativen Kosten ermöglicht dementsprechend die Chance auf die größte Kosteneinsparung. Daher versucht man nun, auf dieses Feld eine möglichst große Menge umzuverteilen, ohne dabei die Bedingung Angebot = Bedarf zu verletzen.
Die Umverteilung auf dieses Feld (in unserem Beispiel: Berlin-Bern) muss über einen vollständigen Baum erfolgen, und somit über die Basisfelder (!!). Vereinfacht gesagt bedeutet dies, dass ich in jeder Zeile oder Spalte, in der ich eine Menge an ein neues Feld hinzugebe, die gleiche Menge in einem anderen Feld wegnehmen muss, da sich das Angebot (bzw. der Bedarf) dieser Zeile (Spalte) nicht verändert.
Ich muss jetzt also einen geschlossenen Weg finden, auf dem ich Menge so umverteilen kann, dass das Feld Berlin-Bern mehr Menge erhält. Das Maximum dieser Menge ist durch das Minimum der Felder bestimmt, von denen ich Menge wegnehme.
Zurück zu unserem Beispiel: Nehmen wir an, ich teile dem Feld Berlin-Bern eine Menge Y zu, so muss ich irgendwo in dieser Zeile bei einem Basisfeld die Menge Y abziehen, da Berlin ja nur die Menge a_i im Angebot hat. Ich hätte also die Möglichkeit mir diese Menge vom Feld Berlin-Köln, oder vom Feld Berlin-Hamburg zu nehmen. Würde ich jetzt allerdings im Feld Berlin-Hamburg eine bestimmte Menge Y wegnehmen, wäre der Bedarf von Hamburg nicht mehr gedeckt, und man müsste Hamburg von einem anderen Angebotsort diese Menge Y liefern. Wir haben jedoch gesagt, dass diese Umverteilung nur über Basisfelder geschehen darf, und in der Spalte Hamburg gibt es kein weiteres Basisfeld, dem ich diese Menge zuteilen dürfte.
Ganz anders sieht dies beim Feld Berlin-Köln aus. Angenommen ich verringere diese Lieferung um das gewünschte Y, so kann ich einfach die Lieferung aus Paris nach Köln um die Menge Y erweitern. Dadurch bleibt der Bedarf von Köln gedeckt, und das Angebot von Berlin bleibt ebenfalls bei a_i. Man erkennt nun jedoch, dass Paris die Menge Y mehr liefern müsste, als sie eigentlich im Angebot hat, und somit muss diese Menge woanders wiederum gekürzt werden. Dies trifft sich eigentlich ganz gut, da ja durch die Erhöhung der Menge im Feld Berlin-Bern der Bedarf von Bern auch um Y ME überstiegen wurde. Es wird nun also die Menge Paris-Bern um Y ME verringert, und somit ist erstens das Angebot von Paris wieder bei Normzustand, wie auch der Bedarf von Bern.
Wenn man sich die Lösung nun im Schaubild ansieht, erkennt man, dass man einen „Umtauschkreis“ gebildet hat, wobei deutlich wird, dass in jeder Zeile oder Spalte in der eine Menge Y hinzukommt, in einem anderen Feld die gleiche Menge auch wieder subtrahiert wird, da sich das Angebot eines Ortes, sowie auch der Bedarf eines Ortes nicht verändern kann.
Wir müssen nun nur noch die Umtauschmenge Y bestimmen. Wie bereits gesagt wurde, ergibt sich Y aus dem Minimum der Menge eines Feld in dem etwas subtrahiert wird. In unserem Fall wird im Feld Berlin-Köln, sowie im Feld Paris-Bern die Menge verringert, wobei einmal 10 ME und einmal 20 ME vorhanden sind. Dadurch ergibt sich die Umtauschmenge zu 10 ME. Hierbei ist wichtig zu erwähnen, dass man stets die Legende der Matrix beachten muss. In unserem Falle wird jeweils die neue Menge x_ij* notiert, es kann aber auch sein, dass die Mengenänderung eingetragen werden muss. Die kleinen roten Plus- und Minuszeichen dienen nur der Übersichtlichkeit, damit man besser erkennen kann, wo Menge hinzugefügt, und wo Menge weggenommen wurde.

Anschließend werden nun die berechneten Mengen x_ij* in eine neue Matrix eingetragen. Man bestimmt nach dem bekannten Verfahren die Basisfelder, die Multiplikatoren, sowie die reduzierten Kosten. Dabei wird nun in diesem Fall deutlich, dass es kein Feld gibt, in dem die reduzierten Kosten negativ sind. Dies bedeutet, dass es keine Möglichkeit gibt, die Kosten durch eine weitere Umverteilung nochmals zu verringern, und damit hat man die Optimallösung gefunden.
Dadurch haben wir also nun mit nur einer einzigen Iteration die optimale Lösung gefunden, was die These bestätigt, dass die Kostendifferenzmethode eine sehr gute erste Näherung liefert.

Im folgenden wollen wir noch aufzeigen, wie aufwändig das Finden der Lösung wäre, wenn wir mit der Ausgangslösung des Nord-West-Ecken-Verfahrens begonnen hätten.

Zusammenfassung

1. Ausgangslösung bestimmen
2. m+n-1 Basisfelder bestimmen und c_ij* = 0 setzen
3. beliebiges u_i oder v_j null setzen
4. restliche Multiplikatoren bestimmen
5. bestimmen der reduzierten Kosten c_ij* mit Hilfe der Multiplikatoren
6. suchen des größten NEGATIVEN c_ij*
7. Austauschkette über Basisfelder bestimmen und x_ij* bestimmen --> ein Basisfeld verschwindet, ein neues wird generiert
8. neues Tableau aufstellen und weiter mit Schritt 2 bis keine negativen c_ij* mehr auftauchen

--> falls alle c_ij* größer oder gleich 0 --> OPTIMALLÖSUNG

Literatur

HMM 9.4.1

Applet

Auf den Seiten der Fernuniversität Hagen finden Sie ein Applet, das das Transportproblem sehr anschaulich darstellt.

Vorlesung

Sie können Sich zu diesem Themengebiet eine Vorlesung ansehen.

Wintersemester 2007/2008

Vorlesungsmitschnitt zum Transportproblem

Wintersemester 2006/2007

• 14.11.2006

• Transportproblem Initialisierung 14.11.2006 (Download)
• Transportproblem Initialisierung 14.11.2006 (Stream)
• Transportproblem Initialisierung 14.11.2006 (scaled Stream)

• 21.11.2006

• Transportproblem Initialisierung 21.11.2006 (Download)
• Transportproblem Initialisierung 21.11.2006 (Stream)
• Transportproblem Initialisierung 21.11.2006 (scaled Stream)

• Transportproblem Iteration 21.11.2006 (Download)
• Transportproblem Iteration 21.11.2006 (Stream)
• Transportproblem Iteration 21.11.2006 (scaled Stream)

Achtung: die Dateien aus dem WS06/07 können fehlerhaft sein!
Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.