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 Bearbeiten
Aufstellen der Kostenmatrix Bearbeiten
Ziel bei der Lösung des Transportproblems ist es, möglichst kostengünstig ein Gut, welches an Orten in der Menge angeboten wird, zu den Nachfrageorten , an denen die Mengen 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 zwischen den Orten und in Geldeinheiten (GE) pro transportierter Einheit aufzeigt. Zudem können in dieser so genannten Kostenmatrix die Angebots- bzw. Nachfragemengen eingebunden werden.
Die 1. Iteration Bearbeiten
Die auf die Erstellung der Kostenmatrix folgenden Schritte sind:
- Suchen der geringsten Kosten in der Kostenmatrix und .
- Ermittlung der maximal möglichen Transportmenge auf diesem Weg.
- Subtraktion der ermittelten Transportmenge im Angebot der u-Zeile und in der Nachfrage der v-Spalte. Der Transport von Einheiten vom Ort zum Ort ist nun Teil der Lösung.
- Streichung einer Zeile bzw. Spalte, sobald das Angebot ausgeschöpft bzw. die Nachfrage befriedigt ist.
- Aufstellen der neuen Kostenmatrix .
Anmerkung zum 1. Schritt: Sollte 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 Bearbeiten
Die weiteren Iterationen nehmen als Grundlage jeweils die letzte erstellte neue Kostenmatrix. Der h-ten Iteration liegt also die Kostenmatrix zugrunde. Die Iterationsschritte selbst sind die gleichen, wie bei der ersten Iteration. Erreicht die Kostenmatrix die Dimension , sind also weder Spalten noch Zeilen übrig, so hat der Algorithmus sein Abbruchkriterium erreicht und die Basislösung ist gefunden.
Beispiel Bearbeiten
Aufstellung der Kostenmatrix Bearbeiten
Anhand des folgenden Beispiels soll das Matrixminimumverfahren erläutert werden.
Ausgehend von vier Angebotsorten bis mit den Angebotsmengen:
und vier Nachfrageorten bis mit den Nachfragemengen:
sowie den Informationen zu den jeweiligen Transportkosten wird folgende Kostenmatrix C erstellt:
Die 1. Iteration Bearbeiten
Aus dieser Kostenmatrix wird nun in mehreren Schritten eine Basislösung gewonnen. In der ersten Iteration geschieht Folgendes:
- Suchen der geringsten Kosten in der Kostenmatrix . Hier ist .
- Ermittlung der maximal möglichen Transportmenge auf diesem Weg. Im Beispiel also .
- Subtraktion der ermittelten Transportmenge im Angebot der u-Zeile und in der Nachfrage der v-Spalte. Es ergibt sich also neu, dass und ist. Der Transport von 7 Einheiten vom Ort zum Ort ist nun Teil der Lösung.
- Streichung einer Zeile bzw. Spalte, sobald das Angebot ausgeschöpft bzw. die Nachfrage befriedigt ist. Die Nachfrage am Ort ist nun befriedigt. Die zweite Spalte wird daher gestrichen.
- Aufstellen der neuen Kostenmatrix .
Die neue Kostenmatrix sieht folgendermaßen aus:
Die weiteren Iterationen Bearbeiten
Das Beispiel lässt sich nun bis zum Ende fortführen. Bereits im zweiten Schritt ist die Iteration über mehreren Elementen möglich, da ist. An dieser Stelle ist die Wahl des nächsten Elements aus dieser Menge grundsätzlich frei. Im Folgenden wird jedoch 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 Bearbeiten
Der Transport von 10 Einheiten vom Ort zum Ort wird Teil der Lösung. stellt sich wie folgt dar:
Die 3. Iteration Bearbeiten
Der Transport von 9 Einheiten vom Ort zum Ort wird Teil der Lösung. stellt sich wie folgt dar:
Die 4. Iteration Bearbeiten
Der Transport von 14 Einheiten vom Ort zum Ort wird Teil der Lösung. stellt sich wie folgt dar:
Die 5. Iteration Bearbeiten
Der Transport von 1 Einheit vom Ort zum Ort wird Teil der Lösung. stellt sich wie folgt dar:
Die 6. Iteration Bearbeiten
Der Transport von 2 Einheiten vom Ort zum Ort wird Teil der Lösung. stellt sich wie folgt dar:
Die 7. Iteration Bearbeiten
Der Transport von 1 Einheit vom Ort zum Ort wird Teil der Lösung. hat die Dimension , womit das Abbruchkriterium des Algorithmus erreicht ist.
Ergebnisauswertung Bearbeiten
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 Bearbeiten
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 Bearbeiten
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 Bearbeiten
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.
Quellen Bearbeiten
- W. Domschke. Transport: Grundlagen, lineare Transport- und Umladeprobleme 2007, S. 106–108.