Transportproblem

Transportproblem Definition

Das klassische Transportproblem sieht beispielhaft so aus:

Beispiel

Es gibt 3 Produktionsstätten / Fabriken / Auslieferungslager etc. ("Quellen") Q1, Q2 und Q3, die z.B. jeweils eine bestimmte Menge produzieren bzw. liefern (können), z.B. 100, 200 und 300 Stück.

Es gibt 3 Eingangslager / Geschäfte etc. ("Ziele") Z1, Z2 und Z3, die eine bestimmte Menge benötigen, z.B. 250, 200 und 150 Stück (Liefer- und Nachfragemengen stimmen in Summe überein: 600 Stück).

Die Entfernungen zwischen den Quell- und Zielorten in km sind:

Entfernungstabelle
Z1 Z2 Z3
Q1 1 8 6
Q2 5 3 7
Q3 9 4 2

Das Transportproblem bzw. die zu lösende Aufgabe lautet: Wieviele Stück beziehen die 3 Ziele jeweils von den 3 Quellen, wenn die gesamten Transportkosten (die i.d.R. von der jeweiligen Entfernung in km und der Transportmenge in Stück oder Gewicht abhängen) minimal sein sollen?

Die Anzahl der Ziele und Quellen muss übrigens nicht identisch sein (das ist hier mit jeweils 3 Zufall).

Das Transportproblem kann man als Problem der linearen Optimierung modellieren, daneben gibt es einige Heuristiken (vereinfachte Verfahren). So kann mit dem Nord-West-Ecken-Verfahren oder mit der Vogelschen Approximationsmethode eine Ausgangslösung gefunden werden (d.h. eine Möglichkeit, bei der alle Produktionsmengen verteilt und alle Nachfragemengen bedient sind, die aber noch nicht zwingend kostenoptimal ist), die dann mit der Stepping-Stone-Methode optimiert werden kann.