Transportprobleme

aus www.iwiki.de, der freien Wissensdatenbank

Das Transportproblem ist eine Fragestellung aus dem Operations Research: zum Transport einheitlicher Objekte von mehreren Angebots- zu mehreren Nachfrageorten ist ein optimaler, d.h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu liefernden Mengen an den einzelnen Standorten gegeben sowie die jeweiligen Transportkosten pro Einheit zwischen allen Standorten bekannt sind.

Beim Standardfall einer bezüglich der Transportmengen linearen Kostenfunktion handelt es sich um ein Problem der linearen Optimierung, für das neben den Standardmethoden wie Simplex-Verfahren spezielle Lösungsalgorithmen existieren. Als eines der ersten Themengebiete des Operations Research wurde das Problem schon 1939 von Kantorowitsch als mathematisches Modell formuliert. In den 50er Jahren des 20. Jahrhunderts entwickelten Dantzig, Charnes und Cooper, sowie Ford und Fulkerson verschiedene Lösungsalgorithmen.

[bearbeiten]

Allgemeines

Aus m Angebotssorten $A 1$ mit den Angebotsmengen $a 1$ soll der Bedarf an $b j$ in n Bedarfssorten $B j$ so befriedigt werden, dass die dabei entstehenden Gesamttransportkosten minimiert werden. Dabei soll der Bedarf $b j$ jedes Bedarfsortes gedeckt werden, die Angebotsmengen $a i$ jedes Angebotsortes ausgeschöpft werden und der Gesamtbedarf gleich dem Gesamtangebot sein.

Gesucht werden die Mengen $x i j$ , dass K minimal wird, wobei die Nebenbedingungen erfüllt werden.

K: Gesamtkosten

$c i j$ : Transportkosten pro Einheit von Ort i zum Ort j

$x i j$ : Mengen, die vom Ort i zum Ort j transportiert werden

$a i$ : Angebotsmenge von i

$b j$ : Bedarfsmenge von j

$K = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}$

Nebenbedingungen:

$\sum_{j=1}^m x_{ij} = b_i \quad$
$\sum_{i=1}^n x_{ij} = a_j \quad$
$\sum_{i=1}^m a_{i} = \sum_{i=1}^n b_{j} = a_j \quad$
$x_{ij} \geq 0 \quad$

Da das Transportproblem ein lineares Optimierungsproblem ist, ist die Lösung mittels Simplex-Verfahrens möglich, aber aufwendig. Wegen der speziellen Verhältnisse führen eigene Spezialverfahren schneller zur Optimallösung.

[bearbeiten]

Beispiel

Ein Getränkehändler hat einen Auftrag zur Lieferung von 30 Tankladungen eines Getränks erhalten, das an den Produktionsstätten Hamburg (16 Ladungen) und Paris (14 Ladungen) auf Lager liegt. 15 Ladungen sollen nach Lissabon, 5 nach Barcelona und 10 nach Florenz geliefert werden. In der Kalkulation werden die Transportkosten je Tankladung ermittelt. Folgende Tabelle fasst die Datensituation zusammen:

Entfernung und Transportkosten je Tankladung (TL)
von \ nach	Lissabon ( $B 1$ )	Barcelona ( $B 2$ )	Florenz ( $B 3$ )	Angebot
Hamburg ( $A 1$ )	2800 km	1800 km	1400 km	16 TL
Hamburg ( $A 1$ )	6 T€	4 T€	3 T€	16 TL
Paris ( $A 2$ )	1900 km	1100 km	1100 km	14 TL
Paris ( $A 2$ )	3 T€	2 T€	2 T€	14 TL
Nachfrage	15 TL	5 TL	10 TL	30 TL

Gesucht ist eine optimale Lösung zu folgendem linearen Optimierungsproblem:

Minimiere

K = 6 x 11 + 4 x 12 + 3 x 13 + 3 x 21 + 2 x 22 + 2 x 23

unter den Nebenbedingungen

$x 11 + x 12 + x 13 = 16$ und $x 21 + x 22 + x 23 = 14$
$x 11 + x 21 = 15$ , $x 12 + x 22 = 5$ und $x 13 + x 23 = 10$
$x_{ij} \geq 0$

Hier bezeichnet beispielsweise $x 21$ die Menge, die von Paris ( $A 2$ ) nach Lissabon ( $B 1$ ) transportiert werden soll.

[bearbeiten]

alternative Ausgangslösungsverfahren

Spalten-Minimum-Verfahren

In der Kostenmatrix wird in jeder Spalte der kostenminimale Wert aufgesucht und das entsprechende Feld in der Transportmatrix mit der jeweilsmaximal möglichen Transportmenge belegt.

Matrix-Minimum-Verfahren

Entsprechend wird mit allen Feldern der Kostenmatrix verfahren.

[bearbeiten]

Geschlossenes Transportproblem

Ist das Gesamtangebot gleich der Gesamtnachfrage liegt ein geschlossenes Transportproblem vor.

[bearbeiten]

Offenes Transportproblem

Bei dem offenen Transportproblem werden 2 Fälle unterschieden:

Nachfrage > Angebot Man führt eine zusätzliches Angebot in Höhe des fehlenden Angebots ein, d.h. eine zusätzliche Angebotszeile. Die Kosten dieses Zusatzangebotes entsprechen den Kosten durch Zukauf, Überstunden oder Fehlmengenkosten.

Angebot >Nachfrage Es wird eine zusätzliche Bedarfsspalte eingeführt, die das Überangebotfiktiv aufnimmt. Die zusätzliche Spalte kann als Lagerkapazität mit Transportkosten Null interpretiert werden. Danach entsteht wieder ein geschlossenes Transportproblem.

[bearbeiten]