Zeilenfolgeverfahren

In diesem Abschnitt soll das Zeilenfolgeverfahren aufgezeigt werden.

Zeilenfolgeverfahren - Definition

Das Zeilenfolgeverfahren ist ein Eröffnungsverfahren für Transportprobleme und hat eine zulässige Ausgangslösung zum Ergebnis. Die Vorgehensweise sei im Folgenden beschrieben:

Die Vorgehensweise bei dem Zeilenfolgeverfahren ist analog zum Spaltenfolgeverfahren, nur das die Spalten durch Zeilen ersetzt werden. Es wird wieder die folgende Mengenmatrix betrachtet:

Die Mengenmatrix beinhaltet zu Beginn noch keine Mengenbelegung. Die Kosten der reduzierten Kostenmatrix (sofern eine Reduktion vorgenommen worden ist, sonst die Kosten der Ausgangskostenmatrix) werden die obere rechte Ecke geschrieben. Nach Anwendung des Zeilenfolgeverfahrens ergibt sich die folgenden Mengenbelegung:

Vorgehensweise bei Zeilenfolgeverfahren

Die Vorgehensweise zur Erreichung der obigen Mengenbelegung ist wie folgt:

1. Zeile:

Zunächst wird die Spalte $j = 1$ betrachtet. Hier wird das kleinste Element ausgewählt $c_{11} = 0$. Da auch $c_{14} = 0$ als kleinsten Element auftaucht wird hier das mit dem kleinsten Spaltenindex $j =1$ gewählt. 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 $b_1 = 0$ wird die Spalte $j = 1$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 1. Zeile und sucht das kleinste Element. 

Das kleinste Element ist $c_{14} = 0$. Man setzt $x_{14} =  min \{600; 600 \} = 600$. Die neue Angebotsmenge ist dann $a_1 = 600 - 600 = 0$ und die neue Nachfragemenge $b_4 = 0$. Da $b_4 = 0$ wird die Spalte $j = 4$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 1. Zeile und sucht das kleinste Element. 

Das kleinste Element ist $c_{12} = c_{15} = 10$. Man wählt das Element mit dem kleinsten Spaltenindex $j = 2$. Man setzt $x_{12} =  min \{0; 500 \} = 0$. Die neue Angebotsmenge ist dann $a_1 = 0$ und die neue Nachfragemenge $b_2 = 500 - 0 = 500$. Da $b_2 \neq 0$ geht man als nächstes zur Zeile $i + 1 = 2$ über.

2. Zeile:

(Nicht vergessen, die markierten Spalten $j = 1$ und $j = 4$ dürfen nicht weiter berücksichtigt werden)

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

(Nicht vergessen, die markierten Spalten $j = 1$, $j = 3$ und  $j = 4$ dürfen nicht weiter berücksichtigt werden)

Das kleinste Element ist $c_{25} = 10$. Man setzt $x_{25} =  min \{400; 300 \} = 300$. Die neue Angebotsmenge ist dann $a_2 = 400 - 300 = 100$ und die neue Nachfragemenge $b_5 = 0$. Da $b_5 = 0$ wird die Spalte $j = 5$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 2. Zeile und sucht das kleinste Element. 

(Nicht vergessen, die markierten Spalten $j = 1$, $j = 3$, $j = 4$ und $j = 5$ dürfen nicht weiter berücksichtigt werden)

Das kleinste Element ist $c_{22} = 40$. (Alle anderen Element dürfen nicht berücksichtigt werden). Man setzt $x_{22} =  min \{100; 500 \} = 100$. Die neue Angebotsmenge ist dann $a_2 = 0$ und die neue Nachfragemenge $b_2 = 500 - 100 = 400$. Da $b_2 \neq 0$ geht man als nächstes zur Zeile $i + 1 = 3$ über.

3. Zeile:

(Nicht vergessen, die markierten Spalten $j = 1$, $j = 3$, $j = 4$ und $j = 5$ dürfen nicht weiter berücksichtigt werden)

Es wird die Zeile $i = 3$ betrachtet. Es wird das kleinste Element ausgewählt $c_{32} = 0$ (ist das einzige Element, welches ausgewählt werden darf). Die Menge wird $x_{32} = min \{400; 400 \} = 400$ gesetzt. Die neue Angebotsmenge ist dann $a_3 = 0$ und die neue Nachfragemenge $b_2 = 0$. 

Das Verfahren endet hier, da alle Zeilen 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 + 0 \cdot 10 + 100 \cdot 40 + 400 \cdot 0 + 400 \cdot 0 + 600 \cdot 30 + 300 \cdot 0 = 4.000$.

Die tatsächlichen Transportkosten betragen:

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

Alternative Vorgehensweise

Es existiert noch eine alternative Vorgehensweise für die Durchführung des Zeilenfolgeverfahrens. Dies soll im folgenden aufgezeigt werden.

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

Bei dieser Vorgehensweise sind die gesamten reduzierten Kosten:

$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 130 + 100 \cdot 160 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 291.000$.