Zeilen- und Spaltenfolgeverfahren

Das Spaltenfolge- und das Zeilenfolgeverfahren sind heuristische Verfahren aus dem Operations Research, die eine zulässige Ausgangslösung für das Transportproblem liefern sollen. 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 des Spaltenfolgeverfahrens

Es wird mit der ersten Spalte begonnen und das kostengünstigste Feld maximal belegt. Ist die Spalten- oder Zeilenrestriktion erfüllt, so wird die Spalte bzw. Zeile gestrichen. Falls die Spaltenrestriktion noch nicht erfüllt ist, wird diese bei der strengen Form der Spaltenfolge zunächst unerfüllt gelassen. Dies wird für jede Spalte – aufsteigend der Spaltennummer – durchgeführt. Ist ein Feld in der letzten Spalte belegt, so ist der erste Durchlauf abgeschlossen. Anschließend wird aufsteigend der Spaltennummer das nächst kostengünstige Feld in allen Spalten, in denen die Spaltenrestriktion noch nicht erfüllt ist, maximal belegt. Dies wird so lange fortgeführt bis alle Spaltenrestriktion erfüllt sind.

Bei der aufgelockerten Form der Spaltenfolge wird, falls die Spaltenrestriktion beim ersten belegten Feld nicht erfüllt sind, direkt das Feld mit den zweitgünstigsten Kosten maximal belegt. Für den untypischen Fall, dass alle Spaltenfelder ausgewählt werden müssen, um die Spaltenrestriktion zu erfüllen, werden diese direkt nacheinander ausgewählt.

Beispiele für das Spaltenfolgeverfahren

Die rot markierten Zahlen entsprechen den kostenminimalen Feldern – nachfolgende Durchläufe mit eingeschlossen. In Klammern steht die Nummer der Belegungen. Die tiefgestellte Zahl hinter den Kosten spiegelt die Anzahl der Belegung wider. Ist diese grün markiert, so ist die Spaltenrestriktion erfüllt.

Das nachfolgende Beispiel ist für die strenge Form der Spaltenfolge:
${\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&Angebot\\\hline A_{1}&{\color {red}{\boldsymbol {4}}}_{1}^{(5)}&6&{\color {red}{\boldsymbol {2}}}\color {green}_{9}^{(3)}&3&10\\A_{2}&{\color {red}{\boldsymbol {8}}}\color {green}_{1}^{(7)}&{\color {red}{\boldsymbol {1}}}\color {green}_{7}^{(2)}&7&5&8\\A_{3}&{\color {red}{\boldsymbol {3}}}_{14}^{(1)}&2&2&4&14\\A_{4}&{\color {red}{\boldsymbol {7}}}_{2}^{(6)}&8&4&{\color {red}{\boldsymbol {2}}}\color {green}_{10}^{(4)}&12\\\hline Nachfrage&18&7&9&10&44\\\end{array}}$

Die Kosten $K$ der Ausgangslösung betragen:

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

Das nachfolgende Beispiel ist für die aufgelockerte Form der Spaltenfolge:
${\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&Angebot\\\hline A_{1}&{\color {red}{\boldsymbol {4}}}\color {green}_{4}^{(2)}&6&{\color {red}{\boldsymbol {2}}}_{5}^{(4)}&{\color {red}{\boldsymbol {3}}}_{1}^{(7)}&10\\A_{2}&8&{\color {red}{\boldsymbol {1}}}\color {green}_{7}^{(3)}&7&{\color {red}{\boldsymbol {5}}}\color {green}_{1}^{(8)}&8\\A_{3}&{\color {red}{\boldsymbol {3}}}_{14}^{(1)}&2&2&4&14\\A_{4}&7&8&{\color {red}{\boldsymbol {4}}}\color {green}_{4}^{(5)}&{\color {red}{\boldsymbol {2}}}_{8}^{(6)}&12\\\hline Nachfrage&18&7&9&10&44\\\end{array}}$

Die Kosten $K$ der Ausgangslösung betragen:
$K=\underbrace {3\cdot 14} _{(1)}+\underbrace {4\cdot 4} _{(2)}+\underbrace {1\cdot 7} _{(3)}+\underbrace {2\cdot 5} _{(4)}+\underbrace {4\cdot 4} _{(5)}+\underbrace {2\cdot 8} _{(6)}+\underbrace {3\cdot 1} _{(7)}+\underbrace {5\cdot 1} _{(8)}=115$

Algorithmus des Zeilenfolgeverfahrens

Der Algorithmus zum Zeilenfolgeverfahren ist analog zum Algorithmus des Spaltenfolgeverfahren, nur dass hier Spalten durch Zeilen ersetzt werden.
Es wird mit der ersten Zeile begonnen und das kostengünstigste Feld maximal belegt. Ist die Spalten- oder Zeilenrestriktion erfüllt, so wird die Spalte bzw. Zeile gestrichen. Falls die Zeilenrestriktion noch nicht erfüllt ist, wird diese bei der strengen Form der Zeilenfolge zunächst unerfüllt gelassen. Dies wird für jede Spalte – aufsteigend der Zeilennummer – durchgeführt. Ist ein Feld in der letzten Zeile belegt, so ist der erste Durchlauf abgeschlossen. Anschließend wird aufsteigend der Zeilennummer das nächst kostengünstige Feld in allen Zeilen, in denen die Zeilenrestriktion noch nicht erfüllt ist maximal belegt. Dies wird so lange fortgeführt bis alle Zeilenrestriktion erfüllt sind.

Bei der aufgelockerten Form der Zeilenfolge wird, falls die Zeilenrestriktion beim ersten belegten Feld nicht erfüllt sind, direkt das Feld mit den zweitgünstigsten Kosten maximal belegt. Für den untypischen Fall, dass alle Zeilenfelder ausgewählt werden müssen, um die Zeilenrestriktion zu erfüllen, werden diese direkt nacheinander ausgewählt.

Beispiele Zeilenfolgeverfahren

Die rot markierten Zahlen entsprechen den kostenminimalen Feldern – nachfolgende Durchläufe mit eingeschlossen. In Klammern steht die Nummer der Belegungen. Die tiefgestellte Zahl hinter den Kosten spiegelt die Anzahl der Belegung wider. Ist diese grün markiert, so ist die Zeilenrestriktion erfüllt.

Das nachfolgende Beispiel ist für die strenge Form der Zeilenfolge:

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

Die Kosten $K$ der Ausgangslösung betragen:
$K=\underbrace {2\cdot 9} _{(1)}+\underbrace {1\cdot 7} _{(2)}+\underbrace {3\cdot 14} _{(3)}+\underbrace {2\cdot 10} _{(4)}+\underbrace {4\cdot 1} _{(5)}+\underbrace {8\cdot 1} _{(6)}+\underbrace {7\cdot 2} _{(7)}=113$

Das nachfolgende Beispiel ist für die aufgelockerte Form der Zeilenfolge:

${\begin{array}{c|cccc|c}&B_{1}&B_{2}&B_{3}&B_{4}&Angebot\\\hline A_{1}&4&6&{\color {red}{\boldsymbol {2}}}_{9}^{(1)}&{\color {red}{\boldsymbol {3}}}\color {green}_{1}^{(2)}&10\\A_{2}&8&{\color {red}{\boldsymbol {1}}}_{7}^{(3)}&7&{\color {red}{\boldsymbol {5}}}\color {green}_{1}^{(4)}&8\\A_{3}&{\color {red}{\boldsymbol {3}}}\color {green}_{14}^{(5)}&2&2&4&14\\A_{4}&{\color {red}{\boldsymbol {7}}}\color {green}_{4}^{(7)}&8&4&{\color {red}{\boldsymbol {2}}}_{8}^{(6)}&12\\\hline Nachfrage&18&7&9&10&44\\\end{array}}$
Die Kosten $K$ der Ausgangslösung betragen:
$K=\underbrace {2\cdot 9} _{(1)}+\underbrace {3\cdot 1} _{(2)}+\underbrace {1\cdot 7} _{(3)}+\underbrace {5\cdot 1} _{(4)}+\underbrace {3\cdot 14} _{(5)}+\underbrace {2\cdot 8} _{(6)}+\underbrace {7\cdot 4} _{(7)}=119$

Literatur

• Tomáš Gál: Grundlagen des Operations Research 2: Graphen und Netzwerke Netzplantechnik Transportprobleme Ganzzahlige Optimierung. 3. Auflage, Springer, Berlin 1992, S. 307. ISBN 3-540-55294-4.