Spaltenfolgeverfahren

In diesem Abschnitt soll das Spaltenfolgeverfahren aufgezeigt werden. Das Spaltenfolgeverfahren ist ein Eröffnungsverfahren für Transportprobleme und hat eine zulässige Ausgangslösung als Ergebnis. Die Vorgehensweise sei im Folgenden beschrieben:

Das Spaltenfolgeverfahren wird nun anhand des folgenden Transportproblems aufgezeigt:

Hierzu wird die Mengenmatrix herangezogen. In die Mengenmatrix werden die reduzierten Kosten (sofern eine Reduktion der Kostenmatrix vorgenommen wurde, sonst die Kosten der Ausgangsmatrix) an die rechte obere Ecke geschrieben. Die Mengenbelegung nach Durchführung des Spaltenfolgeverfahrens ergibt sich wie folgt:

Die Vorgehensweise zur Erreichung der obigen Mengenbelegung ist wie folgt:

1. Spalte:

Zunächst wird die Spalte $j = 1$ betrachtet. Hier wird das kleinste Element ausgewählt $c_{11} = 0$. Es wird dann $x_{11} = min \{900; 300 \} = 300$ gesetzt. Die neue Angebotsmenge ist dann $a_1 = 900 - 300 = 600$ und die neue Nachfragemenge $b_1 = 0$. Da $a_1 \neq 0$ geht man als nächstes zur Spalte $j + 1 = 2$ über.

2. Spalte:

Es wird nun die Spalte $j = 2$ betrachtet. Es wird das kleinste Element ausgewählt $c_{32} = 0$. Die Menge wird $x_{32} = min \{400; 500 \} = 400$ gesetzt. Die neue Angebotsmenge ist dann $a_3 = 0$ und die neue Nachfragemenge $b_2 = 500 - 400 = 100$. Da $a_3 = 0$ wird die Zeile $i = 3$ markiert. Die Elemente dieser Zeile dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 2. Spalte und sucht das kleinste Element. 

Das kleinste Element ist $c_{12} = 10$. Man setzt $x_{12} =  min \{600; 100 \} = 100$. Die neue Angebotsmenge ist dann $a_1 = 600 - 100 = 500$ und die neue Nachfragemenge $b_2 = 0$. Da $a_1 \neq 0$ geht man als nächstes zur Spalte $j + 1 = 3$ über.

3.Spalte:

(Nicht vergessen, die markierte Zeile $i = 3$ darf nicht weiter berücksichtigt werden)

Es wird die Spalte $j = 3$ betrachtet. Es wird das kleinste Element ausgewählt $c_{14} = 0$. Die Menge wird $x_{14} = min \{800; 400 \} = 400$ gesetzt. Die neue Angebotsmenge ist dann $a_2 = 800 - 400$ und die neue Nachfragemenge $b_3 = 0$. Da $a_2 \neq 0$ geht man als nächstes zur Spalte $j + 1 = 4$ über.

4. Spalte:

(Nicht vergessen, die markierte Zeile $i = 3$ darf nicht weiter berücksichtigt werden)

Es wird die Spalte $j = 4$ betrachtet. Es wird das kleinste Element ausgewählt $c_{14} = 0$. Die Menge wird $x_{14} = min \{500; 600 \} = 500$ gesetzt. Die neue Angebotsmenge ist dann $a_1 = 0$ und die neue Nachfragemenge $b_4 = 100$. Da $a_1 = 0$ wird die Zeile $i = 1$ markiert. Die Elemente dieser Zeile dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 4. Spalte und sucht das kleinste Element. 

Das kleinste Element wäre in der marktierten Zeile $i = 3$. Da diese aber nicht berücksichtigt werde darf, wird das nächstkleinere Element gewählt. Dieses ist $c_{24} = 30$. Man setzt $x_{24} =  min \{400; 100 \} = 100$. Die neue Angebotsmenge ist dann $a_2 = 400 - 100 = 300$ und die neue Nachfragemenge $b_4 = 0$. Da $a_1 \neq 0$ geht man als nächstes zur Spalte $j + 1 = 5$ über.

5. Spalte:

(Nicht vergessen, die markierte Zeilen $i=1$ und $i = 3$ dürfen nicht weiter berücksichtigt werden)

Es wird die Spalte $j = 5$ betrachtet. Hier wird das kleinste Element ausgewählt $c_{25} = 0$. Es wird dann $x_{25} = min \{300; 300 \} = 300$ gesetzt. Die neue Angebotsmenge ist dann $a_2 =0$ und die neue Nachfragemenge $b_5 = 0$. 

Das Verfahren endet hier, da alle Spalten abgearbeitet worden sind und $m + n - 1 = 3 + 5 - 1 = 7$-Basisvariablen bestimmt worden sind. 

Die gesamten reduzierten Kosten ergeben sich zu:

$K_R = 300 \cdot 0 + 100 \cdot 10 + 400 \cdot 0 + 400 \cdot 0 + 500 \cdot 0 + 100 \cdot 30 + 300 \cdot 0 = 4.000$.

Die tatsächlichen Transportkosten betragen:

$K = 300 \cdot 140 + 100 \cdot 130 + 400 \cdot 120 + 400 \cdot 140 + 500 \cdot 150 + 100 \cdot 180 + 300 \cdot 130 = 291.000$.

Alternative Vorgehensweise

Es existiert noch eine alternative Vorgehensweise für das Spaltenfolgeverfahren. Dieses soll im folgenden aufgezeigt werden.

Bei dieser Vorgehensweise verbleibt man nicht in der Spalte, wenn $a_i = 0$, sondern schreitet immer von einer Spalte zur nächsten. Das ganze wiederholt sich solange, bis die $m + n -1$-Basisvariablen gefunden sind. Nach dieser Vorgehensweise ergibt sich die folgenden Mengenbelegung:

Die gesamten reduzierten Kosten bei dieser Vorgehensweise betragen:

$K_R = 300 \cdot 0 + 0 \cdot 10 + 100 \cdot 40 + 400 \cdot 0 + 400 \cdot 0 + 600 \cdot 0 + 300 \cdot 0 = 4.000$.

Die tatsächlichen Transportkosten betragen:

$K = 300 \cdot 140 + 0 \cdot 150 + 100 \cdot 160 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 291.000$.