Transportproblem

Das Transportproblem (auch Transportmodell) 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.

Bereits 1781 formulierte Monge ein allgemeines Transportproblem mathematisch. 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.

Mathematische Formulierung des klassischen Transportproblems

Das klassische Transportproblem ohne Kapazitätsbeschränkungen wird durch folgende Daten beschrieben: m Angebotsorte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i} stellen Mengen von $a_{i}$ des Gutes (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i = 1, \dotsc , m} ) bereit, n Nachfrageorte Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_j} fragen das Gut in den Mengen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_j} nach (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j = 1, \dotsc , n} ). Die Mengen müssen größer oder gleich null sein, zudem muss das Gesamtangebot gleich der Gesamtnachfrage sein (ausgeglichenes Transportproblem). Ist dies im ursprünglichen Problem nicht der Fall, ist ein fiktiver Angebots- bzw. Nachfrageort einzuführen, der die Überschussnachfrage bereitstellt, bzw. das Überschussangebot aufnimmt. Des Weiteren sind – zum Beispiel in einer Matrix C – die nicht-negativen Kosten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_{ij}} für den Transport einer Mengeneinheit von Angebotsort $A_{i}$ zum Nachfrageort Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle B_{j}} gegeben. Transportkosten von bzw. zu einem fiktiven Ort werden auf Null gesetzt. Kann zwischen zwei Orten nichts transportiert werden, so sind die entsprechenden Transportkosten unendlich.

Formulierung als lineares Programm

Im Transportplan bezeichnet $x_{ij}$ die Transportmenge, die von $A_{i}$ nach $B_{j}$ transportiert wird. Die Gesamtkosten ergeben sich, indem man für jeden Transportweg die ermittelte Transportmenge mit den Kosten für den Transport auf dem jeweiligen Transportweg multipliziert und diese Produkte summiert. Gesucht ist ein Transportplan mit minimalen Kosten, der die Beschränkungen hinsichtlich der lieferbaren Mengen einhält und die Nachfrage an allen Nachfrageorten erfüllt. Mit den eingeführten Bezeichnern ergibt sich dann das mathematische Modell des Transportproblems:

Minimiere die Zielfunktion $z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}$

unter den Nebenbedingungen

1. $\sum _{j=1}^{n}x_{ij}=a_{i}\quad \forall i$
2. $\sum _{i=1}^{m}x_{ij}=b_{j}\quad \forall j$
3. $x_{ij}\geq 0\quad \forall i\forall j$

Die erste Nebenbedingung beschreibt, dass das Angebot an jedem Angebotsort komplett abgerufen werden soll, während die zweite für jeden Nachfrageort festlegt, dass die Nachfrage vollständig erfüllt werden soll. Alle Transportmengen müssen nichtnegativ sein. Oftmals wird auch die Ganzzahligkeit der Transportmengen gefordert, d. h. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{ij} \in \mathbb{N}_0} .

Falls die zu Beginn aufgeführten Bedingungen (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i \geq 0,\ b_j \geq 0,\ c_{ij} \geq 0 {\rm \ und\ } \sum a_i = \sum b_j} ) erfüllt und alle Wege benutzbar sind (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c_{ij} \neq \infty \ \forall i\forall j} ), so existiert mindestens eine Lösung für das Transportproblem. Kann zwischen einigen Orten nichts transportiert werden, so ist die Existenz einer Lösung nicht gesichert.

Formulierung als Minimum-Cost Flow Problem

→ Hauptartikel: Minimum-Cost Flow Problem

Mit Hilfe von Graphen kann das Problem auch als Minimum-Cost Flow Problem formuliert werden. Dabei geht es darum, in einem Graphen mit Kantenkosten zwischen zwei Knoten einen kostenminimalen Fluss mit gegebenem Flusswert zu finden. Jeder Ort wird hierbei durch einen Knoten repräsentiert, und von jedem Angebotsort zu jedem Nachfrageort wird eine Kante gezogen, deren Kosten den Transportkosten entsprechen. Zusätzlich werden zwei besondere Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} eingeführt. Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s} wird mit allen Angebotsorten verbunden und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} mit allen Nachfrageorten, wobei diese Kanten den Kostenwert 0 und als Kapazität die jeweiligen Angebots- bzw. Nachfragemengen der zugehörigen Knoten haben. Anschließend wird ein kostenminimaler Fluss mit der Gesamtnachfrage als Flusswert von $s$ nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle t} bestimmt. Der ermittelte Fluss auf der Kante zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_j} gibt an, wie viel zwischen diesen beiden Orten transportiert wird.

Beispiel

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

Entfernung und Transportkosten je Tankladung (TL)

von \ nach	Lissabon Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (B_1)}	Barcelona Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (B_2)}	Florenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (B_3)}	Angebot
Hamburg (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_1} )	2800 km	1800 km	1400 km	16 TL
	6 T€	4 T€	3 T€
Paris ($A_{2}$)	1900 km	1100 km	1100 km	14 TL
	3 T€	2 T€	2 T€
Nachfrage	15 TL	5 TL	10 TL	30 TL

Da die hinreichenden Bedingungen für die Existenz einer Lösung gegeben sind, existiert mindestens ein Transportplan für dieses Transportproblem. Gesucht ist nun eine optimale Lösung zu folgendem linearen Optimierungsproblem:

Minimiere

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z = 6 x_{11} + 4 x_{12} + 3 x_{13} + 3 x_{21} + 2 x_{22} + 2 x_{23}}

unter den Nebenbedingungen

1. Angebot
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{11} + x_{12} + x_{13} = 16}
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{21} + x_{22} + x_{23} = 14}
2. Nachfrage
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{11} + x_{21} = 15}
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{12} + x_{22} = 5}
   • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{13} + x_{23} = 10}
3. Keine negativen Transporte
   • Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle x_{ij}\geq 0}

Hier bezeichnet beispielsweise Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{21}} die Menge, die von Paris (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A_2} ) nach Lissabon (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_1} ) transportiert werden soll.

Lösungsverfahren

Exakte Verfahren

In der oben vorgestellten Formulierung als lineares Programm lässt sich das Problem beispielsweise mit dem Simplex-Verfahren optimal lösen. Sofern die Angebots- und Nachfragemengen ganzzahlig sind und eine zulässige Lösung existiert, liefert das Simplex-Verfahren für dieses spezielle Problem immer eine ganzzahlige Lösung, da aufgrund der totalen Unimodularität der Nebenbedingungsmatrix jede Ecke des zugehörigen Polyeders ganzzahlig ist. Für dieses Problem kann statt des allgemeinen Simplex-Verfahrens auch die Netzwerk-Simplexmethode verwendet werden, eine schnellere Variante, die speziell für Min-Cost-Flow-Probleme geeignet ist.

Alternativ kann das Problem auch mit einem beliebigen kombinatorischen, also nicht auf linearer Optimierung beruhenden, Algorithmus zum Finden kostenminimaler Flüsse gelöst werden.

Eröffnungsheuristiken

Mehrere iterative Verfahren suchen erst mit Hilfe einer einfachen Eröffnungsheuristik eine zulässige Ausgangslösung (auch Basislösung genannt) und versuchen dann, diese durch eine Verbesserungsheuristik zu verbessern. Folgende Verfahren werden hierbei üblicherweise als Eröffnungsheuristik verwendet (aufsteigend nach dem Aufwand geordnet):

• Nord-West-Ecken-Verfahren
• Zeilen- und Spaltenfolgeverfahren
• Zeilen-Spalten-Sukzession
• Matrixminimumverfahren (auch Rangfolgeverfahren, aufsteigende Indexmethode oder Spaltenminimum-Methode)
• Vogelsche Approximationsmethode (VAM, VAV)
• Frequenzmethode

In den meisten Fällen führt die relativ aufwändige Vogelsche Approximationsmethode relativ schnell eine optimale Lösung herbei. In der Datenverarbeitung wird häufig die Nord-West-Ecken-Methode bevorzugt, weil sie einfacher zu programmieren ist und die Zahl der benötigten Iterationen nicht ins Gewicht fällt.

Verbesserungsverfahren

Aus einer zulässigen Ausgangslösung kann iterativ eine Optimallösung ermittelt werden. Als Verfahren kommen beispielsweise in Frage

• die Zyklenmethode (Stepping-Stone-Methode)
• die MODI-Methode, auch Potentialverfahren genannt.

Bei beiden Methoden werden einzelne Zellen der Tabelle überprüft, inwieweit ihre Änderung eine Verbesserung der Kostensituation herbeiführt. Dabei pflanzt sich die Änderung in andere Zellen fort. Diese Änderungen können als geschlossener Kreis beschrieben werden. Es werden so oft Zellen geändert, bis keine Verbesserung mehr möglich ist und das Optimum erreicht worden ist. Die MODI-Methode führt in endlich vielen Schritten zu einer Optimallösung, wenn die oben genannten Bedingungen erfüllt sind. Mit ihr wird die optimale Lösung im Allgemeinen schneller gefunden als mit der Zyklenmethode.

Siehe auch

• Optimaler Transport
• Rucksackproblem

Weblinks

• Fernuni Hagen: Das Transportproblem in der Betriebswirtschaftslehre
• Transportproblem: Transportproblem in JavaScript