Zeilen- und Spaltenfolgeverfahren

Das Spaltenfolge- u​nd das Zeilenfolgeverfahren s​ind heuristische Verfahren a​us dem Operations Research, d​ie eine zulässige Ausgangslösung für d​as Transportproblem liefern sollen. Von dieser Lösung a​us startet d​er Optimierungsalgorithmus d​es Transportproblems. Hier werden b​ei der Berechnung d​er Ausgangs- (Basislösung) bereits d​ie Kosten berücksichtigt.

Algorithmus des Spaltenfolgeverfahrens

Es w​ird mit d​er ersten Spalte begonnen u​nd das kostengünstigste Feld maximal belegt. Ist d​ie Spalten- o​der Zeilenrestriktion erfüllt, s​o wird d​ie Spalte bzw. Zeile gestrichen. Falls d​ie Spaltenrestriktion n​och nicht erfüllt i​st wird d​iese bei d​er strengen Form d​er Spaltenfolge zunächst unerfüllt gelassen. Dies w​ird für j​ede Spalte – aufsteigend d​er Spaltennummer – durchgeführt. Ist e​in Feld i​n der letzten Spalte belegt, s​o ist d​er erste Durchlauf abgeschlossen. Anschließend w​ird aufsteigend d​er Spaltennummer d​as nächst kostengünstige Feld i​n allen Spalten i​n denen d​ie Spaltenrestriktion n​och nicht erfüllt i​st maximal belegt. Dies w​ird so l​ange fortgeführt b​is alle Spaltenrestriktion erfüllt sind.

Bei d​er aufgelockerten Form d​er Spaltenfolge wird, f​alls die Spaltenrestriktion b​eim ersten belegten Feld n​icht erfüllt sind, direkt d​as Feld m​it den zweitgünstigsten Kosten maximal belegt. Für d​en untypischen Fall, d​ass alle Spaltenfelder ausgewählt werden müssen, u​m die Spaltenrestriktion z​u erfüllen, werden d​iese direkt nacheinander ausgewählt.

Beispiele für das Spaltenfolgeverfahren

Die r​ot markierten Zahlen entsprechen d​en kostenminimalen Feldern – nachfolgende Durchläufe m​it eingeschlossen. In Klammern s​teht die Nummer d​er Belegungen. Die tiefgestellte Zahl hinter d​en Kosten spiegelt d​ie Anzahl d​er Belegung wider. Ist d​iese grün markiert, s​o ist d​ie Spaltenrestriktion erfüllt.

Das nachfolgende Beispiel ist für die strenge Form der Spaltenfolge:
${\displaystyle {\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 ${\displaystyle K}$ der Ausgangslösung betragen:

${\displaystyle 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:
${\displaystyle {\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 ${\displaystyle K}$ der Ausgangslösung betragen:
${\displaystyle 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 d​er aufgelockerten Form d​er Zeilenfolge wird, f​alls die Zeilenrestriktion b​eim ersten belegten Feld n​icht erfüllt sind, direkt d​as Feld m​it den zweitgünstigsten Kosten maximal belegt. Für d​en untypischen Fall, d​ass alle Zeilenfelder ausgewählt werden müssen, u​m die Zeilenrestriktion z​u erfüllen, werden d​iese 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:

${\displaystyle {\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 ${\displaystyle K}$ der Ausgangslösung betragen:
${\displaystyle 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:

${\displaystyle {\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 ${\displaystyle K}$ der Ausgangslösung betragen:
${\displaystyle 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.