Transportproblem

Das Transportproblem (auch Transportmodell) ist ein Optimierungsproblem und 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.

Bereits 1781 formulierte Monge ein allgemeines Transportproblem mathematisch.^[1] 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 Operation Research wurde das Problem schon 1939 von Kantorowitsch als mathematisches Modell formuliert. In den 1950er Jahren entwickelten Dantzig, Charnes und William W. Cooper sowie Ford und Fulkerson verschiedene Lösungsalgorithmen.

Das klassische Transportproblem ohne Kapazitätsbeschränkungen auf den Transportwegen ist ein Spezialfall des kapazitierten Transportproblems, das für Wege Mindest- oder Höchsttransportmengen festlegt. Klassisches und kapazitiertes Transportproblem sind wiederum Spezialfälle des (kapazitierten) Umladeproblems, bei dem es neben Angebots- und Nachfrageorten noch reine Umladeorte gibt. Ein Sonderfall des Transportproblems ist das Zuordnungsproblem, bei dem an jedem Ort nur eine Einheit angeboten bzw. nachgefragt wird.

1. ↑ G. Monge. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, S. 666–704.