Matrixminimumverfahren

Das Matrixminimumverfahren (oder aufsteigende Indexmethode, Rangfolgeverfahren, Spaltenminimum-Methode^[1]) 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 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₁, A₂,..., A_m) in der Menge a_i (i =1,...,m) angeboten wird, zu den n Nachfrageorten (B₁, B₂,..., B_n), an denen die Mengen b_i (i=1,...,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 (i=1,...,m) und B_j (j=1,...,n) in Geldeinheiten (GE) pro transportierter Einheit aufzeigt. Zudem können in dieser so genannten Kostenmatrix die Angebots- bzw. Nachfragemengen eingebunden werden.

          |B1  B2  .. Bj .. Bn |Angebot
---------------------------------------
A1        |c11 c12 .. c1j.. c1n|  a1
A2        |c21 c22 .. c2j.. c2n|  a2
.         |    .            .  |
.         |       .         .  |
Ai        |ci1 ci2 .. cij.. cin|  ai
.         |           .     .  |
.         |              .  .  |
Am        |cm1 cm2 .. cmj.. cmn|  am
---------------------------------------
Nachfrage |b1  b2  .. bj .. bn |Summe

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,...,m und j = 1,...,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₁.

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ührten, wo die maximal möglich 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 (0x0), 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 Spaltenminimumverfahren erläutert werden.

Ausgehend von vier Angebotsorten A₁ bis A₄ mit den Angebotsmengen:

• a₁ = 10
• a₂ = 8
• a₃ = 14
• a₄ = 12

und vier Nachfrageorten B₁ bis B₄ mit den Nachfragemengen:

• b₁ = 18
• b₂ = 7
• b₃ = 9
• b₄ = 10

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

          |B1 B2 B3 B4|Angebot
------------------------------
A1        | 4  6  2  3|  10
A2        | 8  1  7  5|   8
A3        | 3  2  2  4|  14
A4        | 7  8  4  2|  12
------------------------------
Nachfrage |18  7  9 10|  44

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,...,4). Hier ist min(c_ij) = c₂₂ = 1.
2. Ermittlung der maximal möglichen Transportmenge x_uv = min(a_u, b_v) auf diesem Weg. Im Beispiel also min(a₂, b₂) = 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₂ = 8 - 7 = 1 und b₂ = 7 - 7 = 0 ist. Der Transport von 7 Einheiten vom Ort A₂ zum Ort B₂ 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₂ = 0 am Ort B₂ ist nun befriedigt. Die zweite Spalte wird daher gestrichen.
5. Aufstellen der neuen Kostenmatrix C₁.

Die neue Kostenmatrix C₁ sieht folgendermaßen aus:

          |B1 B3 B4|Angebot
---------------------------
A1        | 4  2  3|  10
A2        | 8  7  5|   1
A3        | 3  2  4|  14
A4        | 7  4  2|  12
---------------------------
Nachfrage |18  9 10|  37

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₁₃ = c₃₃ = c₄₄ = 2 ist. An dieser Stelle ist die Wahl des nächsten Elements aus dieser Menge grundsätzlich frei. Im Folgenden wird jedoch c₄₄ 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₄ zum Ort B₄ wird Teil der Lösung. C₂ stellt sich wie folgt dar:

          |B1 B3|Angebot
------------------------
A1        | 4  2|  10
A2        | 8  7|   1
A3        | 3  2|  14
A4        | 7  4|   2
------------------------
Nachfrage |18  9|  27

Die 3. Iteration

Der Transport von 9 Einheiten vom Ort A₁ zum Ort B₃ wird Teil der Lösung. C₃ stellt sich wie folgt dar:

          |B1|Angebot
---------------------
A1        | 4|   1
A2        | 8|   1
A3        | 3|  14
A4        | 7|   2
---------------------
Nachfrage |18|  18

Die 4. Iteration

Der Transport von 14 Einheiten vom Ort A₃ zum Ort B₁ wird Teil der Lösung. C₄ stellt sich wie folgt dar:

          |B1|Angebot
---------------------
A1        | 4|   1
A2        | 8|   1
A4        | 7|   2
---------------------
Nachfrage | 4|   4

Die 5. Iteration

Der Transport von 1 Einheit vom Ort A₁ zum Ort B₁ wird Teil der Lösung. C₅ stellt sich wie folgt dar:

          |B1|Angebot
---------------------
A2        | 8|   1
A4        | 7|   2
---------------------
Nachfrage | 3|   3

Die 6. Iteration

Der Transport von 2 Einheiten vom Ort A₄ zum Ort B₁ wird Teil der Lösung. C₆ stellt sich wie folgt dar:

          |B1|Angebot
---------------------
A2        | 8|   1
---------------------
Nachfrage | 1|   1

Die 7. Iteration

Der Transport von 1 Einheit vom Ort A₂ zum Ort B₁ wird Teil der Lösung. C₇ hat die Dimension (0x0), 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 mit die Lösung beispielsweise mittels MODI-Methode oder Stepping-Stone-Methode (Sprungbrettmethode) optimiert wird.

Quellen

1. ↑ W. Domschke. Transport: Grundlagen, lineare Transport- und Umladeprobleme 2007, S. 106-108.