Transportproblem

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1: Ausgangslösung mit Nord-West-Ecken Verfahren

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: Ausgangslösung mit Zeilen-Spalten-Sukzession

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3: Ausgangslösung mit Zeilenfolgeverfahren

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4: Ausgangslösung mit Matrixminimumverfahren

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5: Ausgangslösung mit Kostendifferenzverfahren

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6: Ausgangslösung mit Kostendifferenzverfahren

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 7: Matrix bei 1. Iteration

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 8: Optimallösung nach 1. Iteration

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 9: Ausganslösung durch NW-Ecken-Verfahren

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 10: Tableau bei 1. Iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 11: Tableau bei 2. Iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 12: Tableau bei 3. Iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 13: Tableau bei 4. Iteration

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 14: Optimallösung nach 4. Iteration

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/Lecture

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

Transportproblem (English)

Bitte beachten Sie die Hinweise zum Betrachten der Vorlesung.

Fundamental concept

The Transportation problem is a special case of the MaxFlow-Problem. Though the optimal attribution of a homogenous good's transport is to be identified (cf. HMM 7.5.3). Present are i locations of supply with a supply of a_i quantity units of a certain product as well as j locations of demand with a demand of b_j. Remarkable is that demand has to be equal to supply. Now the question is to allocate the transport of the supply quantities at least possible transport costs c_ij. To provide more clarity we want to consider a simplified example that the city Hamburg needs 3 new park benches for sidewalks along Alster. Corporation XY has establishments in Bremen, Munich and Kaiserslautern, wherefrom identical benches may be delivered Thus it becomes clear that the transport from Bremen is much more cheaper than other transports since the distance to Hamburg is the shortest of all. However real transport costs do not only depend on distances but also on several other factors.

Mathematical formulation of the problem

a_i : supply quantity at location i (i=1,...,m)
b_j : demand quantity at location j (j=1,...,n)
c_ij : transportation cost per unit from supply location i to demand location j
x_ij : transportation quantity from i to j

  
Minimize K = ∑i ∑j cijxij
      
 ∑j xij = ai  for all i
      
 ∑i xij = bj  for all j
             
    xij ≥ 0   for all i,j
      
A solution only exists, if
            
  ∑i ai = ∑j bj

Exemplification

Opening method

North-West corner method

The North-West corner method is no approximation method in classical meaning and only has a traditional importance. Nowadays the solution of this method is hardly used since it does not consider costs and becomes very imprecise. Primarily we begin with the first field of the matrix (top left) and attribute to this location of demand the most possible supply. This amount is determined by the minimum of supply and demand quantity. In our case Frankfurt will deliver 35 QU to Köln. The remaining amount of 10 QU will be allocated to the next field of the matrix ( one step to right). Thus the supply of Frankfurt is fully consumed and we can skip to the next location of supply. Paris has to cover the rest of Hamburg's demand of 20QU. Now the most possible supply will be allocated to the next field (Wien) which is restricted by the demand (Wien) of 35 QU. Hence Paris has still a supply of 25 QU left, which are delivered to Bern. Though the demand of Bern is not fully covered, further 40QU are needed. This residual amount may be covered through the last location of supply. To conclude we can see that all demands are covered moreover all supplies are allocated and the condition demand=supply is satisfied.

The previously mentioned critique is also evident at the arrows in the following figure. The circumstance that we begin in the top left corner and iterate stepwise to down right does not make an economic sense. The imprecise initial solution may cause unneeded iterations to find the optimal solution.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 1: Ausgangslösung mit Nord-West-Ecken Verfahren

Row-column succession

The method of row-column succession is very good one to identify an initial solution.
The method begins with the allocation of the transport to the most advantageous field of the matrix (Berlin-Köln). To this field the maximum possible amount is allocated, whereat the minimum of supply an demand restricts this amount. Consequently either a supply is fully consumed or an demand fully covered. In this cas (Berlin-Köln)the demand of Köln is fully covered whereas Berlin still has a supply of 5 QU. Thus we remain in the concerned row (Berlin) and allocate the residual amount of supply to the next cheapest field (Hamburg). Since Berlin's supply is fully consumed and Hamburg still needs an amount of 25QU we continue the procedure considering the column of Hamburg. We find out the cheapest field in the current column and allocate the most possible amount.
According to this schema we iterate until all demands are cobvered and supplies are consumed.

To sum up the procedure:

1. Identify the cheapest field of the total matrix and allocate the maximum possible amount
2. Allocate the residual amount to the next beneficial field in the current row or column
3. Iterate until no more demand and supply is left

Since this method considers costs it is a good first approximation of the solution and therefore often used.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 2: Ausgangslösung mit Zeilen-Spalten-Sukzession

Simple row sequence/column sequence method

These 2 different methods work schematically alike. Firstly we will clarify row sequence method and lastly have a look on the column sequence method. The row sequence method begins with the most beneficial field of the first row and attaches the maximum possible amount to it. The maximum possible amount is again determined by the minimum of supply or demand. In this example we allocate field Frankfurt-Wien an amount of 35 QU. Afterwards the remaining quantity is attached to the next beneficial field of the current row. If the supply is fully consumed the next location of supply will be considered. There again the most beneficial field receives the most possible amount. The residual amount is allocated step by step to the next advantageous fields of the row.

To sum up the procedure:

1. Attachment of the most possible amount to the most beneficial field of the 1. row
2. Attachment of the residual amount to next cheap fields
3. Reiteration of the procedure for every row

Column sequence method works in principle alike with one difference that we now consider the most beneficial fields of the columns.

The method illustrates with the arbitrarily starting in the 1. row (column) a good approximation. Since costs are involved in this method it is at least better than North-West corner method.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 3: Ausgangslösung mit Zeilenfolgeverfahren

Matrix-Minimum method

A further useful method to find an initial solution is the Matrix-Minimum method. Thereby we begin with the cheapest field of the total matrix (Berlin-Köln) and attach the most possible amount to this field (35QU). Afterwards the next beneficial field of the total matrix will be considered. This field gets again the most possible amount, in this case Frankfurt-Wien with costs of 45MU and an attachment of 35 QU. Thereupon the next cheapest field is to be detected and the most possible amount is allocated. This simple technique allocates the amounts to the fields in the order of the costs by beginning with the least cost. Remarkable is that always the total matrix is considered instead of isolated rows or columns. The allocated amount is in accordance to the minimum of the (remaining) demand or (remaining) supply alike to other methods.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 4: Ausgangslösung mit Matrixminimumverfahren

Cost difference method

The cost difference method is a quite more extensive method to find out an initial solution. However this method delivers the best approximation of the optimal solution. This method is also known as Vogel' s approximation method(VAM) named after its inventor.
The main idea is to find out in each step the cost difference of the beneficial and the second beneficial field for each row and column. Afterwards the row or column with the greatest difference is selected and the most possible amount to the most beneficial field in the current row (column) is allocated. Thereupon again all cost differences are calculated and the most possible amount attached according to the previously mentioned criteria. If a demand or supply of a row or column is fully covered or rather consumed, this row or column will be neglected and crossed out. To provide more clarity we will explain this method by the following example.
First of all we find out the cost difference of the most beneficial and the next beneficial field of column 1. The calculation delivers a difference of (50-15=)35 and is noted at the bottom of the column. Now the cost differences of the remaining columns and rows are to identify and note at the figure. For example the cost difference of the first row resluts to 50–45 =5. If all cost differences are calculated we will consider the greatest difference. In our example the greatest cost difference is to find in Hamburg with a difference of 50MU ( the paranthesized number in the figure shows the number of the step in which the cost difference is the maximum of all diferences). Consequently we attach the most possible amount(30 QU) to the most beneficial field (Berlin-Hamburg) of the Hamburg column. Since the demand of the current column is fully covered we can delete this column to prevent clarity in the further procedure.
Again all cost differences without considering the column of Hamburg are to find out. So for example the cost difference of Belin changes to (70-15=)55. If all cost differences are calculated we will select the greatest one to allocate in its column or row the most possible amount to the most beneficial field. In this stage Berlin offers the greatest cost difference. To this row we attach the most possible amount to the cheapest field namely Berlin-Köln (=10QU, determined by the residual amount of row). Berlin's row can be deleted since its supply is fully consumed.
According tho this schema all cost differences are calculated and the amounts allocated. This procedure is reiterated until all supply quantities are consumed and demand quantities are covered.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 5: Ausgangslösung mit Kostendifferenzverfahren

Determination of the optimal solution

For the determination of the optimal solution we will consider the initial solution detected by cost difference method. Since we supposed that the solution detected by cost difference method delivers the best approximation, we should find out the optimal solution within few steps.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

Abb. 6: Ausgangslösung mit Kostendifferenzverfahren

In the first step we will figure out the basis fields according to the following formula:

  m + n -1 = number of basis fields
  m = number of supply locations and n= number of demand locations

The basis idea is that we need a complete tree for the reallocation of the amounts. In this case we have 3+4-1=6 basis fields. Firstly these fields already which have an amount x_ij are defined as basis fields. In the present example we have 6 basis fields and also 6 fields with an quantity allocation because of this circumstance the whole situation simplifies. If we had for example 5 fields with an amount x_ij the 6. basis field would be selected arbitrarily. Now the reduced costs c_ij* of the basis fields are set null. For the sake of clarity we note X instead of zero. Afterwards an optional multiplier u_i or v_j is also set null. Although the choice of the multiplier is optional it is better to choose these ones where the most basis fields are in the relevant row or column, since this simplifies further calculation. Now we calculate further multipliers according to the following formula:

   cij* = cij - ui - vj

the equation may be transposed as necessary to u_i or v_j

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

In the present case we set null u_i of the Paris row. Thus we can see immediately according to the previous formula the value of v_j for Köln, Wien and Bern, since the reduced costs as well as multiplier u_i are zero. Thus the multipliers of these columns result of the costs of the fields in the Paris row.v_Köln = 55, v_Wien = 50 and v_Bern = 115. Now we have to find a way to figure out the remaining multipliers. The multiplier of Belin u_Berlin seems to be easily calculable by 15 – 0 - 55 = - 40. Afterwards we calculate v_Hamburg by 50 -0 - (-40 ) = 90. Only u_Frankfurt is missing which is calculated by 70 – 0 – 115 = - 45.

In the next step we will calculate the remaining reduced costs by using the already calculated multipliers and the presented above formula. Examplarily we determine reduced costs of the field Frankfurt-Köln to 50 - (-45) – 55 = 40. The remaining reduced costs c_ij* can be calculated with the known values and formula (end solution cf. figure 7).

Since all needed values are calculated we have to find out a way to reduce costs and thus optimize the solution. The reduced costs of the fields in the matrix show how much costs may be saved by attaching the quantities to the current fields instead of the previous allocation. Thus the field containing the highest negative value represents the greatest chance to save costs. Consequently we try to reallocate to this field the most possible amount without violating the condition of supply=demand.
The Reallocation to this field has to proceed through the complete tree hence basis fields. Simply put, by increasing the allocation of a certain field we simultaneously have to take off the same amount from another field to hold the condition of supply=demand.