Das Transportproblem ist ein klassisches Optimierungsproblem aus dem Operations Research: Güter sollen von mehreren Angebotsorten zu mehreren Nachfrageorten transportiert werden, sodass alle Angebote aufgebraucht, alle Nachfragen gedeckt und die Gesamtkosten minimal sind. Es ist ein Spezialfall der linearen Optimierung.
Das Modell
Gegeben sind m Angebotsorte mit Angebotsmengen ai, n Nachfrageorte mit Bedarfsmengen bj sowie die Transportkosten cij je Einheit von Angebotsort i zu Nachfrageort j. Gesucht sind die Transportmengen xij, sodass gilt:
- Jeder Angebotsort liefert sein gesamtes Angebot: Summe über j von xij = ai.
- Jeder Nachfrageort erhält seinen gesamten Bedarf: Summe über i von xij = bj.
- Die Gesamtkosten (Summe über alle cij multipliziert mit xij) werden minimiert.
Das System muss balanciert sein: Gesamtangebot und Gesamtnachfrage müssen übereinstimmen. Ist das nicht der Fall, führt man einen Dummy-Angebots- oder Dummy-Nachfrageort mit Kosten null ein, der die Differenz aufnimmt.
Lösungsverfahren
Da das Transportproblem ein lineares Optimierungsproblem ist, löst es jedes LP-Verfahren wie der Simplex-Algorithmus. Klassisch nutzt man jedoch spezialisierte Verfahren: eine Startlösung liefert etwa die Nordwest-Ecken-Regel, verbessert wird sie mit der Stepping-Stone- oder der MODI-Methode (Modified Distribution). Das Problem ist in polynomieller Zeit lösbar — die Komplexität wird über die Big-O-Notation beschrieben.
Sonderfälle und Abgrenzung
- Das Assignment-Problem (Zuordnungsproblem) ist ein Spezialfall mit gleich vielen Angebots- und Nachfrageorten, bei dem jede Menge genau 1 ist — gelöst wird es mit der ungarischen Methode.
- Nicht zu verwechseln ist das Transportproblem mit Routen- und Tourenproblemen wie dem Handlungsreisendenproblem, das NP-vollständig ist.
Anwendungen: Logistik- und Lieferkettenplanung, Standortverteilung, Produktions- und Lagerzuteilung — überall dort, wo Angebot und Nachfrage über einen Kostenfaktor verbunden sind.