Zeilen-Spalten-Sukzession

Die Zeilen-Spalten-Sukzession ist ein heuristisches Verfahren aus dem Operations Research, die eine zulässige Ausgangslösung für das Transportproblem liefert. Von dieser Lösung aus startet der Optimierungsalgorithmus des Transportproblems. Hier werden bei der Berechnung der Ausgangs- (Basislösung) bereits die Kosten berücksichtigt.

Algorithmus

Der Algorithmus beginnt, indem man das kostengünstigste Element der Transportkosten-Matrix maximal belegt. In der Matrix ist in der äußeren rechten Spalte das Angebot angegeben und in der untersten Zeile die Nachfrage. Wenn nach der Wahl des ersten Elements die Zeile noch ein Angebots-Überschuss hat, wird das nächstgünstigste Element der Zeile ausgewählt. Hat die Spalte noch einen Nachfrage-Überschuss, dann wird das nächstgünstigste Element der Spalte genommen. Dies wird so lange fortgeführt, bis es keinen Überschuss mehr gibt.

Beispiele

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

Die Kosten $K$ der Ausgangslösung betragen.

$K=\underbrace {1\cdot 7} _{(1)}+\underbrace {5\cdot 1} _{(2)}+\underbrace {2\cdot 9} _{(3)}+\underbrace {4\cdot 3} _{(4)}+\underbrace {2\cdot 6} _{(5)}+\underbrace {4\cdot 4} _{(6)}+\underbrace {3\cdot 14} _{(7)}=112$

Da nach Schritt 4 zwei Elemente mit denselben Transportkosten zur Verfügung stehen, gibt es zwei Lösungen.

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

Die Kosten $K$ der Ausgangslösung betragen

$K=\underbrace {1\cdot 7} _{(1)}+\underbrace {5\cdot 1} _{(2)}+\underbrace {2\cdot 9} _{(3)}+\underbrace {4\cdot 3} _{(4)}+\underbrace {2\cdot 6} _{(5)}+\underbrace {4\cdot 1} _{(6)}0+\underbrace {3\cdot 8} _{(7)}=118$.

Nachteil dieses Verfahrens

Anfangs existiert noch ein sehr hoher Freiheitsgrad. Für eine Belegung sind $m\times n$ Zuordnungen möglich. Dieser Freiheitsgrad wird jedoch sehr schnell eingeschränkt, so dass am Ende wegen bereits erfüllter Restriktionen sehr ungünstige Zuordnungen in Kauf genommen werden müssen.

Literatur

• Heiner Müller-Merbach: Operations Research: Methoden und Modelle der Optimalplanung, 1971, Franz Vahlen, S. 310.