Formulierung als lineares Programm

Im Transportplan bezeichnet ${\displaystyle x_{ij}}$ die Transportmenge, die von ${\displaystyle A_{i}}$ nach ${\displaystyle 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 ${\displaystyle z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}}$

unter den Nebenbedingungen

1. ${\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i}\quad \forall i}$
2. ${\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j}\quad \forall j}$
3. ${\displaystyle 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. ${\displaystyle x_{ij}\in \mathbb {N} _{0}}$.

Falls die zu Beginn aufgeführten Bedingungen (${\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 (${\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

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 ${\displaystyle s}$ und ${\displaystyle t}$ eingeführt. Knoten ${\displaystyle s}$ wird mit allen Angebotsorten verbunden und ${\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 ${\displaystyle s}$ nach ${\displaystyle t}$ bestimmt. Der ermittelte Fluss auf der Kante zwischen ${\displaystyle A_{i}}$ und ${\displaystyle B_{j}}$ gibt an, wie viel zwischen diesen beiden Orten transportiert wird.

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.