Das klassische Transportproblem

Transportprobleme weisen eine spezielle Struktur auf, für welche spezielle Lösungsverfahren entwickelt worden sind. Diese speziellen Lösungsverfahren sollen in den folgenden Abschnitt ausführlich beschrieben werden. Die Anwendung der Simplex-Algorithmen ist für diese Probleme zwar möglich, aber sehr rechenaufwendig. Im Weiteren wird das klassische Transportproblem ohne Kapazitätsbeschränkungen aufgezeigt. 

Bei Transportprobleme müssen bestimmte Mengen eines Produktes von mehreren Angebotsorten zu mehreren Nachfrageorten so transportiert werden, so dass die Gesamtkosten minimiert werden. Es müssen die folgenden Bedingungen erfüllt sein:

• Die transportierten Mengen müssen größer oder gleich Null sein: .
• Das Gesamtangebot muss gleich der Gesamtnachfragen sein: . Ist dieser Fall nicht gegeben, so muss ein fiktiver Angebots- bzw. Nachfrageort eingeführt werden, welcher die Überschussnachfrage bzw. -angebot aufnimmt. 
• Es sind nicht-negative Transportkosten gegeben. Transportkosten für den Transport von bzw. zu einem fiktiven Ort werden Null gesetzt. Ist der Transport zwischen zwei Orten nicht möglich, so werden die dortigen Transportkosten unendlich gesetzt.

Mathematische Formulierung des Problems

Die Transportkosten sollen miminiert werden. Die Zielfunktion lautet demnach:

    min!

Dabei ergeben sich die Gesamtkosten, indem die Transportmenge für jeden Weg mit den dazugehörigen Kosten multipliziert werden. Es ergibt sich dann die Summe der Kosten pro Transportweg. Werden dann die Kosten aller Transportwegen miteinander addiert, so ergeben sich die Gesamtkosten des Problems. Diese sollen unter Einhaltung der nachfolgenden Bedingungen minimiert werden:

Die erste und zweite Nebenbedingung bedeuten, dass das komplette Angebot abgerufen und die komplette Nachfrage befriedigt werden soll. Die dritte Nebenbedingung beschreibt, dass das Angebot und die Nachfrage übereinstimmen müssen und die letzte Nebenbedingung, dass nur nicht-negative Transportmengen gegeben sein dürfen. Wird die Ganzzahligkeit der Transportmengen gefordert, so gilt:

Das Problem kann zum eine in eine Kostenmatrix und zum anderen in eine Mengenmatrix eingetragen werden:

Es wird nun in den folgenden Abschnitten gezeigt, wie man ein klassischen Transportproblem lösen kann. Hiefür müssen die folgenden Schritte durchgeführt werden:

1. Ausgleichsprüfung

Es muss zunächst geprüft werden, ob die Angebotsmenge gleich der Nachfragemenge entspricht. Ist dies nicht der Fall, so müssen fiktive Angebots- bzw. Nachfrageorte eingefügt werden, welche diese fehlende Menge aufnehmen. Ist , so muss ein Angebotsort zugefügt werden mit der Menge . Ist , so muss ein Nachfrageort zugefügt werden mit der Menge . 

2. Reduktion der Kostenmatrix

Die Reduktion der Kostenmatrix (vor allem bei Anwendung der Stepping-Stone-Methode) führt zu einem geringeren Rechenaufwand. 

3. Bestimmung einer zulässigen Ausgangslösung

Es muss eine zulässige Ausgangslösung bestimmt werden. Hierfür stehen die folgenden Verfahren zur Verfügung:

- Nordwestecken-Verfahren (Mengenmatrix) 

- Zeilenminimum, Spaltenmimum, Matrixminimum (Mengen- und Kostenmatrix)

- Vogelsches Approximationsverfahren (Kostenmatrix)

4. Bestimmung der optimalen Lösung

Nachdem eine zulässige Lösung bestimmt worden ist, kann die optimale Lösung ermittelt werden. Hierfür können die folgenden zwei Verfahren angewandt werden:

- Stepping-Stone-Methode

- die Modi-Methode.

Beispiel: Transportproblem

In den folgenden Abschnitten werden die obigen 4 Schritte zur Lösung des Transportproblems ausführlich dargestellt.