Quelltext der Seite Matrixminimumverfahren

Das '''Matrixminimumverfahren''' (oder '''aufsteigende Indexmethode'', ''Rangfolgeverfahren'''<ref name="Domschke">W. Domschke. ''Transport: Grundlagen, lineare Transport- und Umladeprobleme'' 2007, S. 106–108.</ref>) ist ein Eröffnungsverfahren aus dem [[Operations Research]] zur Lösung von [[Transportproblem]]en. Der Name leitet sich aus der Betrachtung der [[Kostenmatrix]] ab, in der das jeweilige [[Größtes und kleinstes Element|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 <math>m</math> Orten <math>(A_1, A_2,\dotsc, A_m)</math> in der Menge <math>a_i \text{ } (i=1,\dotsc,m)</math> angeboten wird, zu den <math>n</math>Nachfrageorten <math>(B_1, B_2,\dotsc, B_n)</math>, an denen die Mengen <math>b_i \ (i=1,\dotsc,n)</math> 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 <math>c_{ij}</math> zwischen den Orten <math>A_i \text{ } (i=1,\dotsc,m)</math> und <math>B_j \ (j=1,\dotsc,n)</math> in Geldeinheiten (GE) pro transportierter Einheit aufzeigt. Zudem können in dieser so genannten Kostenmatrix die Angebots- bzw. Nachfragemengen eingebunden werden.

<math>
\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}
</math>

=== Die 1. Iteration ===

Die auf die Erstellung der Kostenmatrix folgenden Schritte sind:

#Suchen der geringsten Kosten <math>c_{uv} = \min(c_{ij})</math> in der Kostenmatrix <math>(i = 1,\dotsc,m</math> und <math>j = 1,\dotsc,n)</math>.
#Ermittlung der maximal möglichen Transportmenge <math>x_{uv} = \min(a_u, b_v)</math> auf diesem Weg.
#[[Subtraktion]] der ermittelten Transportmenge im Angebot der u-Zeile und in der Nachfrage der v-Spalte. Der Transport von <math>x_{uv}</math> Einheiten vom Ort <math>A_u</math> zum Ort <math>B_v</math> 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 <math>C_1</math>.

Anmerkung zum 1. Schritt: Sollte <math>\min(c_{ij})</math> 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 <math>C_{h-1}</math> zugrunde. Die Iterationsschritte selbst sind die gleichen, wie bei der ersten Iteration. Erreicht die Kostenmatrix die Dimension <math>(0\times0)</math>, 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 <math>A_1</math> bis <math>A_4</math> mit den Angebotsmengen:

*<math>a_1 = 10</math>
*<math>a_2 = 8</math>
*<math>a_3 = 14</math>
*<math>a_4 = 12</math>

und vier Nachfrageorten <math>B_1</math> bis <math>B_4</math> mit den Nachfragemengen:

*<math>b_1 = 18</math>
*<math>b_2 = 7</math>
*<math>b_3 = 9</math>
*<math>b_4 = 10</math>

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

<math>
\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}
</math>

=== Die 1. Iteration ===

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

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

Die neue Kostenmatrix <math>C_1</math> sieht folgendermaßen aus:

<math>
\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}
</math>

=== 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 <math>\min(c_{ij}) = c_{13} = c_{33} = c_{44} = 2</math> ist. An dieser Stelle ist die Wahl des nächsten Elements aus dieser Menge grundsätzlich frei. Im Folgenden wird jedoch <math>c_{44}</math> 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 <math>A_4</math> zum Ort <math>B_4</math> wird Teil der Lösung. <math>C_2</math> stellt sich wie folgt dar:

<math>
\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}
</math>

==== Die 3. Iteration ====

Der Transport von 9 Einheiten vom Ort <math>A_1</math> zum Ort <math>B_3</math> wird Teil der Lösung. <math>C_3</math> stellt sich wie folgt dar:

<math>
\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}
</math>

==== Die 4. Iteration ====

Der Transport von 14 Einheiten vom Ort <math>A_3</math> zum Ort <math>B_1</math> wird Teil der Lösung. <math>C_4</math> stellt sich wie folgt dar:

<math>
\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}
</math>

==== Die 5. Iteration ====

Der Transport von 1 Einheit vom Ort <math>A_1</math> zum Ort <math>B_1</math> wird Teil der Lösung. <math>C_5</math> stellt sich wie folgt dar:

<math>
\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}
</math>

==== Die 6. Iteration ====

Der Transport von 2 Einheiten vom Ort <math>A_4</math> zum Ort <math>B_1</math> wird Teil der Lösung. <math>C_6</math> stellt sich wie folgt dar:

<math>
\begin{array}{c|c|c}
          & B_1 & \text{Angebot} \\ \hline
A_2       & 8   & 1 \\ \hline
\text{Nachfrage} & 1   & 1  \\
\end{array}
</math>

==== Die 7. Iteration ====

Der Transport von 1 Einheit vom Ort <math>A_2</math> zum Ort <math>B_1</math> wird Teil der Lösung. <math>C_7</math> hat die Dimension <math>(0 \times 0)</math>, womit das Abbruchkriterium des Algorithmus erreicht ist.

==== Ergebnisauswertung ====

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

{| class="wikitable" style="text-align:center"
|-
! Angebotsort
! Nachfrageort
! Transportmenge
! Preis pro Einheit
! Gesamtpreis
|-
| A<sub>2</sub>
| B<sub>2</sub>
| 7 Einheiten
| 1 GE
| 7 GE
|-
| A<sub>4</sub>
| B<sub>4</sub>
| 10 Einheiten
| 2 GE
| 20 GE
|-
| A<sub>1</sub>
| B<sub>3</sub>
| 9 Einheiten
| 2 GE
| 18 GE
|-
| A<sub>3</sub>
| B<sub>1</sub>
| 14 Einheiten
| 3 GE
| 42 GE
|-
| A<sub>1</sub>
| B<sub>1</sub>
| 1 Einheiten
| 4 GE
| 4 GE
|-
| A<sub>4</sub>
| B<sub>1</sub>
| 2 Einheiten
| 7 GE
| 14 GE
|-
| A<sub>2</sub>
| B<sub>1</sub>
| 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ätstheorie|Komplexität]] des Algorithmus vergleichsweise gering, was zu kurzen [[Laufzeit (Informatik)|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.

== Quellen ==
<references />

[[Kategorie:Transportproblem]]