Matrixminimumverfahren

Das Matrixminimumverfahren (oder aufsteigende Indexmethode, Rangfolgeverfahren) ist ein Eröffnungsverfahren aus dem Operations Research zur Lösung von Transportproblemen. Der Name leitet sich aus der Betrachtung der Kostenmatrix ab, in der das jeweilige Minimum für die nächste Iteration des Algorithmus herangezogen wird.

Das Matrixminimumverfahren liefert für das zugrunde liegende Transportproblem immer eine zulässige Lösung (auch Ausgangs- bzw. Basislösung), die jedoch nicht zwangsläufig optimal ist.

Algorithmus

Aufstellen der Kostenmatrix

Ziel bei der Lösung des Transportproblems ist es, möglichst kostengünstig ein Gut, welches an $m$ Orten $(A_{1},A_{2},\dotsc ,A_{m})$ in der Menge $a_{i}{\text{ }}(i=1,\dotsc ,m)$ angeboten wird, zu den $n$Nachfrageorten $(B_{1},B_{2},\dotsc ,B_{n})$, an denen die Mengen $b_{i}\ (i=1,\dotsc ,n)$ benötigt werden, zu transportieren. Die Summe der angebotenen Einheiten entspricht dabei im klassischen Transportsystem der Summe der nachgefragten Einheiten.

Aus den Informationen des Transportproblems lässt sich eine Matrix C erstellen, welche die Kosten $c_{ij}$ zwischen den Orten $A_{i}{\text{ }}(i=1,\dotsc ,m)$ und $B_{j}\ (j=1,\dotsc ,n)$ in Geldeinheiten (GE) pro transportierter Einheit aufzeigt. Zudem können in dieser so genannten Kostenmatrix die Angebots- bzw. Nachfragemengen eingebunden werden.

${\begin{array}{c|cccccc|c}&B_{1}&B_{2}&\dots &B_{j}&\dots &B_{n}&{\text{Angebot}}\\\hline A_{1}&c_{11}&c_{12}&\dots &c_{1j}&\dots &c_{1n}&a_{1}\\A_{2}&c_{21}&c_{22}&\dots &c_{2j}&\dots &c_{2n}&a_{2}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots \\A_{i}&c_{i1}&c_{i2}&\dots &c_{ij}&\dots &c_{in}&a_{i}\\\vdots &\vdots &\vdots &&\vdots &&\vdots &\vdots \\A_{m}&c_{m1}&c_{m2}&\dots &c_{mj}&\dots &c_{mn}&a_{m}\\\hline {\text{Nachfrage}}&b_{1}&b_{2}&\dots &b_{j}&\dots &b_{n}&{\text{Summe}}\\\end{array}}$

Die 1. Iteration

Die auf die Erstellung der Kostenmatrix folgenden Schritte sind:

1. Suchen der geringsten Kosten $c_{uv}=\min(c_{ij})$ in der Kostenmatrix $(i=1,\dotsc ,m$ und $j=1,\dotsc ,n)$.
2. Ermittlung der maximal möglichen Transportmenge $x_{uv}=\min(a_{u},b_{v})$ auf diesem Weg.
3. Subtraktion der ermittelten Transportmenge im Angebot der u-Zeile und in der Nachfrage der v-Spalte. Der Transport von $x_{uv}$ Einheiten vom Ort $A_{u}$ zum Ort $B_{v}$ ist nun Teil der Lösung.
4. Streichung einer Zeile bzw. Spalte, sobald das Angebot ausgeschöpft bzw. die Nachfrage befriedigt ist.
5. Aufstellen der neuen Kostenmatrix $C_{1}$.

Anmerkung zum 1. Schritt: Sollte $\min(c_{ij})$ aus mehr als einem Element bestehen, so ist die Wahl des Matrixelementes aus dieser Menge, über dem die Iteration ausgeführt wird, grundsätzlich frei. Um durch den Algorithmus schneller zu einer Lösung zu gelangen, ist es oft sinnvoll, die Iteration dort auszuführen, wo die maximal mögliche Transportmenge am größten ist.

Die weiteren Iterationen

Die weiteren Iterationen nehmen als Grundlage jeweils die letzte erstellte neue Kostenmatrix. Der h-ten Iteration liegt also die Kostenmatrix $C_{h-1}$ zugrunde. Die Iterationsschritte selbst sind die gleichen, wie bei der ersten Iteration. Erreicht die Kostenmatrix die Dimension $(0\times 0)$, sind also weder Spalten noch Zeilen übrig, so hat der Algorithmus sein Abbruchkriterium erreicht und die Basislösung ist gefunden.

Beispiel

Aufstellung der Kostenmatrix

Anhand des folgenden Beispiels soll das Matrixminimumverfahren erläutert werden.

Ausgehend von vier Angebotsorten $A_{1}$ bis $A_{4}$ mit den Angebotsmengen:

• $a_{1}=10$
• $a_{2}=8$
• $a_{3}=14$
• $a_{4}=12$

und vier Nachfrageorten $B_{1}$ bis $B_{4}$ mit den Nachfragemengen:

• $b_{1}=18$
• $b_{2}=7$
• $b_{3}=9$
• $b_{4}=10$

sowie den Informationen zu den jeweiligen Transportkosten wird folgende Kostenmatrix C erstellt:

${\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&{\text{Angebot}}\\\hline A_{1}&4&6&2&3&10\\A_{2}&8&1&7&5&8\\A_{3}&3&2&2&4&14\\A_{4}&7&8&4&2&12\\\hline {\text{Nachfrage}}&18&7&9&10&44\\\end{array}}$

Die 1. Iteration

Aus dieser Kostenmatrix wird nun in mehreren Schritten eine Basislösung gewonnen. In der ersten Iteration geschieht Folgendes:

1. Suchen der geringsten Kosten $c_{uv}=\min(c_{ij})$ in der Kostenmatrix $(i,j=1,\dotsc ,4)$. Hier ist $\min(c_{ij})=c_{22}=1$.
2. Ermittlung der maximal möglichen Transportmenge $x_{uv}=\min(a_{u},b_{v})$ auf diesem Weg. Im Beispiel also $\min(a_{2},b_{2})=\min(8,7)=7$.
3. Subtraktion der ermittelten Transportmenge im Angebot der u-Zeile und in der Nachfrage der v-Spalte. Es ergibt sich also neu, dass $a_{2}=8-7=1$ und $b_{2}=7-7=0$ ist. Der Transport von 7 Einheiten vom Ort $A_{2}$ zum Ort $B_{2}$ ist nun Teil der Lösung.
4. Streichung einer Zeile bzw. Spalte, sobald das Angebot ausgeschöpft bzw. die Nachfrage befriedigt ist. Die Nachfrage $b_{2}=0$ am Ort $B_{2}$ ist nun befriedigt. Die zweite Spalte wird daher gestrichen.
5. Aufstellen der neuen Kostenmatrix $C_{1}$.

Die neue Kostenmatrix $C_{1}$ sieht folgendermaßen aus:

${\begin{array}{c|ccc|c}&B_{1}&B_{3}&B_{4}&{\text{Angebot}}\\\hline A_{1}&4&2&3&10\\A_{2}&8&7&5&1\\A_{3}&3&2&4&14\\A_{4}&7&4&2&12\\\hline {\text{Nachfrage}}&18&9&10&37\\\end{array}}$

Die weiteren Iterationen

Das Beispiel lässt sich nun bis zum Ende fortführen. Bereits im zweiten Schritt ist die Iteration über mehreren Elementen möglich, da $\min(c_{ij})=c_{13}=c_{33}=c_{44}=2$ ist. An dieser Stelle ist die Wahl des nächsten Elements aus dieser Menge grundsätzlich frei. Im Folgenden wird jedoch $c_{44}$ verwendet, da hier die maximale Transportmenge am größten ist.

Auf eine einzelne Berechnung der Iterationen wird hier verzichtet. Die im Folgenden dargestellten weiteren Kostenmatrizen und Lösungsbestandteile sollen die Nachvollziehbarkeit des Beispiels gewährleisten.

Die 2. Iteration

Der Transport von 10 Einheiten vom Ort $A_{4}$ zum Ort $B_{4}$ wird Teil der Lösung. $C_{2}$ stellt sich wie folgt dar:

${\begin{array}{c|cc|c}&B_{1}&B_{3}&{\text{Angebot}}\\\hline A_{1}&4&2&10\\A_{2}&8&7&1\\A_{3}&3&2&14\\A_{4}&7&4&2\\\hline {\text{Nachfrage}}&18&9&27\\\end{array}}$

Die 3. Iteration

Der Transport von 9 Einheiten vom Ort $A_{1}$ zum Ort $B_{3}$ wird Teil der Lösung. $C_{3}$ stellt sich wie folgt dar:

${\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{1}&4&1\\A_{2}&8&1\\A_{3}&3&14\\A_{4}&7&2\\\hline {\text{Nachfrage}}&18&18\\\end{array}}$

Die 4. Iteration

Der Transport von 14 Einheiten vom Ort $A_{3}$ zum Ort $B_{1}$ wird Teil der Lösung. $C_{4}$ stellt sich wie folgt dar:

${\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{1}&4&1\\A_{2}&8&1\\A_{4}&7&2\\\hline {\text{Nachfrage}}&4&4\\\end{array}}$

Die 5. Iteration

Der Transport von 1 Einheit vom Ort $A_{1}$ zum Ort $B_{1}$ wird Teil der Lösung. $C_{5}$ stellt sich wie folgt dar:

${\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{2}&8&1\\A_{4}&7&2\\\hline {\text{Nachfrage}}&3&3\\\end{array}}$

Die 6. Iteration

Der Transport von 2 Einheiten vom Ort $A_{4}$ zum Ort $B_{1}$ wird Teil der Lösung. $C_{6}$ stellt sich wie folgt dar:

${\begin{array}{c|c|c}&B_{1}&{\text{Angebot}}\\\hline A_{2}&8&1\\\hline {\text{Nachfrage}}&1&1\\\end{array}}$

Die 7. Iteration

Der Transport von 1 Einheit vom Ort $A_{2}$ zum Ort $B_{1}$ wird Teil der Lösung. $C_{7}$ hat die Dimension $(0\times 0)$, womit das Abbruchkriterium des Algorithmus erreicht ist.

Ergebnisauswertung

Mit der Matrixminimummethode ist nun eine Basislösung gefunden, die sich zusammengefasst folgendermaßen darstellt:

Angebotsort	Nachfrageort	Transportmenge	Preis pro Einheit	Gesamtpreis
A2	B2	7 Einheiten	1 GE	7 GE
A4	B4	10 Einheiten	2 GE	20 GE
A1	B3	9 Einheiten	2 GE	18 GE
A3	B1	14 Einheiten	3 GE	42 GE
A1	B1	1 Einheiten	4 GE	4 GE
A4	B1	2 Einheiten	7 GE	14 GE
A2	B1	1 Einheiten	8 GE	8 GE
Gesamt		44 Einheiten		113 GE

Ob es sich dabei zugleich um die Optimallösung handelt, müsste im Folgenden beispielsweise unter Nutzung der MODI-Methode geprüft werden.

Vorteile

Aufgrund des einfachen Algorithmus, der nur die Transportkosten als Auswahlkriterium heranzieht, ist das Matrixminimumverfahren leicht anwend- und programmierbar. Zudem ist die Komplexität des Algorithmus vergleichsweise gering, was zu kurzen Rechenzeiten bei Computerprogrammen führt.

Nachteile

Das Matrixminimumverfahren liefert zwar eine gültige Basislösung für das Transportproblem, jedoch nicht zwangsläufig die Optimallösung. Das bedeutet, dass eine nachfolgende Lösungsverbesserung notwendig werden kann, was den Aufwand zur Lösung des Problems mitunter erheblich erhöht.

Anwendung

Als Eröffnungsheuristik ist das Matrixminimumverfahren insgesamt meist dann sinnvoll, wenn lediglich eine beliebige zulässige Lösung für ein Transportproblem benötigt wird. Daher findet es häufig Anwendung zur Ermittlung einer Ausgangslösung, bevor die Lösung beispielsweise mittels MODI-Methode oder Zyklenmethode (Stepping-Stone-Methode) optimiert wird.