Quelltext der Seite Transportproblem

Das '''Transportproblem''' (auch Transportmodell) ist ein [[Optimierungsproblem]] und eine Fragestellung aus dem [[Operations Research]]: Zum Transport einheitlicher Objekte von mehreren [[Angebot (Volkswirtschaftslehre)|Angebots-]] zu mehreren [[Nachfrage]]orten ist ein [[Optimierungsproblem|optimaler]], d.&nbsp;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 [[Gaspard Monge|Monge]] ein allgemeines Transportproblem mathematisch.<ref name=Monge>{{Literatur |Autor=Gaspard Monge |Titel=Mémoire sur la théorie des déblais et de remblais |Sammelwerk=Histoire de l’Académie Royale des Sciences |WerkErg=Avec les Mémoires de Mathématique et de Physique pour la même année |Verlag=Imprimérie Royale |Ort=Paris |Datum=1781 |Seiten=666–704 |Online={{Google Buch | BuchID=JYzFOW74j7gC | Seite=666 }} |Abruf=2025-10-13 }}</ref> Beim Standardfall einer bezüglich der Transportmengen [[Lineare Funktion|linearen Kostenfunktion]] handelt es sich um ein Problem der [[Lineare Optimierung|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 [[Leonid Witaljewitsch Kantorowitsch|Kantorowitsch]] als mathematisches Modell formuliert. In den 1950er Jahren entwickelten [[George Dantzig|Dantzig]], [[Abraham Charnes|Charnes]] und [[William W. Cooper]] sowie [[Lester Randolph Ford junior|Ford]] und [[Delbert Ray Fulkerson|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) [[Umladeproblem]]s, 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 <math>A_i</math> stellen Mengen von <math>a_i</math> des [[Ökonomisches Gut|Gut]]es (<math>i = 1, \dotsc , m</math>) bereit, ''n'' Nachfrageorte <math>B_j</math> fragen das Gut in den Mengen <math>b_j</math> nach (<math>j = 1, \dotsc , n</math>). 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 (Mathematik)|Matrix]] ''C'' – die nicht-negativen Kosten <math>c_{ij}</math> für den Transport einer Mengeneinheit von Angebotsort <math>A_i</math> zum Nachfrageort <math>B_j</math> 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<!-- oder ein beliebiger anderer Wert, der größer als alle anderen tatsächlichen Transportkosten ist-->.

=== Formulierung als lineares Programm ===

Im Transportplan bezeichnet <math>x_{ij}</math> die Transportmenge, die von <math>A_i</math> nach <math>B_j</math> 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]] <math>z = \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}</math>
:unter den [[Nebenbedingung]]en
:#<math>\sum_{j=1}^n x_{ij} = a_i \quad \forall i</math>
:#<math>\sum_{i=1}^m x_{ij} = b_j \quad \forall j</math>
:#<math>x_{ij} \geq 0 \quad \forall i\forall j</math>

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.&nbsp;h. <math>x_{ij} \in \mathbb{N}_0</math>.

Falls die zu Beginn aufgeführten Bedingungen (<math>a_i \geq 0,\ b_j \geq 0,\ c_{ij} \geq 0 {\rm \ und\ } \sum a_i = \sum b_j</math>) erfüllt und alle Wege benutzbar sind (<math>c_{ij} \neq \infty \ \forall i\forall j</math>), 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 [[Graph (Graphentheorie)|Graphen]] kann das Problem auch als Minimum-Cost Flow Problem formuliert werden. Dabei geht es darum, in einem Graphen mit Kantenkosten zwischen zwei [[Knoten (Graphentheorie)|Knoten]] einen kostenminimalen [[Flüsse und Schnitte in Netzwerken|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 (Graphentheorie)|Kante]] gezogen, deren Kosten den Transportkosten entsprechen. Zusätzlich werden zwei besondere Knoten <math>s</math> und <math>t</math> eingeführt. Knoten <math>s</math> wird mit allen Angebotsorten verbunden und <math>t</math> 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 <math>s</math> nach <math>t</math> bestimmt. Der ermittelte Fluss auf der Kante zwischen <math>A_i</math> und <math>B_j</math> 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:

{| class="wikitable"
|+ Entfernung und Transportkosten je Tankladung (TL)
|-
| style="text-align:center" | von \ nach
! width="90px" | Lissabon <math>(B_1)</math>
! width="90px" | Barcelona <math>(B_2)</math>
! width="90px" | Florenz <math>(B_3)</math>
! Angebot
|-
! rowspan="2" | Hamburg (<math>A_1</math>)
| style="text-align:right; font-size:80%" | 2800 km
| style="text-align:right; font-size:80%" | 1800 km
| style="text-align:right; font-size:80%" | 1400 km
| rowspan="2" style="text-align:right" | 16 TL
|-
| style="text-align:right" | 6 T€
| style="text-align:right" | 4 T€
| style="text-align:right" | 3 T€
|-
! rowspan="2" | Paris (<math>A_2</math>)
| style="text-align:right; font-size:80%" | 1900 km
| style="text-align:right; font-size:80%" | 1100 km
| style="text-align:right; font-size:80%" | 1100 km
| rowspan="2" style="text-align:right" | 14 TL
|-
| style="text-align:right" | 3 T€
| style="text-align:right" | 2 T€
| style="text-align:right" | 2 T€
|-
! Nachfrage
| style="text-align:right" | 15 TL
| style="text-align:right" | 5 TL
| style="text-align:right" | 10 TL
| style="text-align:right; border-top:double; border-left:double" | 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
::<math>z = 6 x_{11} + 4 x_{12} + 3 x_{13} + 3 x_{21} + 2 x_{22} + 2 x_{23}</math>

:;unter den Nebenbedingungen
:#Angebot
:#*<math>x_{11} + x_{12} + x_{13} = 16</math>
:#*<math>x_{21} + x_{22} + x_{23} = 14</math>
:#Nachfrage
:#*<math>x_{11} + x_{21} = 15</math>
:#*<math>x_{12} + x_{22} = 5</math>
:#*<math>x_{13} + x_{23} = 10</math>
:#Keine negativen Transporte
:#*<math>x_{ij} \geq 0</math>

Hier bezeichnet beispielsweise <math>x_{21}</math> die Menge, die von Paris (<math>A_2</math>) nach Lissabon (<math>B_1</math>) transportiert werden soll.

== Lösungsverfahren ==

=== Exakte Verfahren ===

In der oben vorgestellten Formulierung als [[Lineare Optimierung|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 [[Total unimodulare Matrix|totalen Unimodularität]] der Nebenbedingungsmatrix jede Ecke des zugehörigen [[Polyeder]]s 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''<ref name=Domschke>W. Domschke. ''Transport: Grundlagen, lineare Transport- und Umladeprobleme'' 2007, S. 106–108.</ref>)
* [[Vogelsche Approximationsmethode]] (VAM, VAV)
* [[Ungarische Methode#Die Frequenzmethode nach Habr et al.|Frequenzmethode]]<ref>Winkler Heiko: ''Warenverteilungsplanung: Ein Beitrag zur Theorie der Industriebetrieblichen Warenverteilung'' (German Edition), 1977, Gabler, S 160. [https://books.google.de/books?id=1OPOBgAAQBAJ&pg=PA159&dq=Frequenzmethode+operations+research&hl=de&sa=X&ei=gRWZVa7iJKXOyQPyjoOADA&ved=0CDwQ6AEwBQ#v=onepage&q=Frequenzmethode%20operations%20research&f=false web]</ref>

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 [[Iteration|iterativ]] eine Optimallösung ermittelt werden. Als Verfahren kommen beispielsweise in Frage

* die [[Zyklenmethode]] (Stepping-Stone-Methode) <!-- Sprungbrettmethode -->
* 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]]

== Quellen ==
<references />

== Weblinks ==
{{Wiktionary}}
* [https://www.fernuni-hagen.de/BWLOR/multimedia/transport.php Fernuni Hagen]: Das Transportproblem in der Betriebswirtschaftslehre
* [https://www.bemdev.com/Services/Transportproblem.htm Transportproblem]: Transportproblem in JavaScript

[[Kategorie:Transportproblem| ]]