Kursangebot | Operations Research 1 | Das klassische Transportproblem

Operations Research 1

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 $x_{ij}$ von mehreren Angebotsorten $a_i$ zu mehreren Nachfrageorten $b_j$ 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: $x_{ij} \ge 0$.
  • Das Gesamtangebot muss gleich der Gesamtnachfragen sein: $\sum a_i = \sum b_j$. 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 $c_{ij}$ 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 $c_{ij}$ sollen miminiert werden. Die Zielfunktion $z$ lautet demnach:

$z = \sum_{j = 1}^n \sum_{i = 1}^m c_{ij} x_{ij}$    $\rightarrow$ 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:

$\sum_{j = 1}^n x_{ij} = a_i$       $i = 1,2,...,m$

$\sum_{i = 1}^m x_{ij} = b_j$       $j = 1,2,...,n$

$\sum a_i = \sum b_j$

$x_{ij} \ge 0$

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:

Methode

$x_{ij} \in \mathbb{N}$             Ganzzahligkeit der Transportmengen

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

Transportproblem Kostenmatrix
Kostenmatrix
Transportproblem Mengenmatrix
Mengenmatrix

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 $\sum a_i$ gleich der Nachfragemenge $\sum b_j$ entspricht. Ist dies nicht der Fall, so müssen fiktive Angebots- bzw. Nachfrageorte eingefügt werden, welche diese fehlende Menge aufnehmen. Ist $\sum a_i < \sum b_j$, so muss ein Angebotsort zugefügt werden mit der Menge $a'_i = \sum b_j - a_i$. Ist $\sum b_j < \sum a_i$, so muss ein Nachfrageort zugefügt werden mit der Menge $b'_j = \sum a_i - \sum b_j$. 

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

Beispiel

Die xy-AG produziert ein Produkt in drei Fabriken. Anschließend erfolgt der Transport durch LKW's an fünf Warenhäuser. Die Transportkosten stellen einen zentralen Kostenpunkt dar, weshalb das Unternehmen die Transportkosten so weit wie möglich reduzieren möchte. Die nachfolgende Tabelle zeigt die geschätzten Kosten pro LKW-Ladung der kommenden Saison zwischen den einzelnen Fabriken und Warenhäuser:

Transportproblem Beispiel Kostenmatrix

Das Produkt soll nun so auf die 5 Warenhäuser verteilt werden, dass die Transportkosten minimal sind!

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