Kursangebot | Operations Research 1 | Zeilenfolgeverfahren

Operations Research 1

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:

Methode

Hier klicken zum Ausklappen

Zeilenfolgeverfahren

Zu Beginn des Verfahrens sind alle Spalten unmarkiert. Die Iteration erfolgt von $i = 1, .., n$ ($i$ = Zeile).

1. Es wird das kleinste Element der Zeile $i$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Spaltenindex $j$ gewählt.

2. Es wird dann $x_{ij} = min \{a_i, b_j \}$ gesetzt. Danach werden die Angebots- und Nachfragemengen angepasst durch $a_i := a_i - x_{ij} $ und $b_j := b_j - x_{ij}$.  

Ist danach $b_j = 0$, wird die Spalte $j$ markiert und die Elemente dieser Spalte für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und derselben Zeile $i$.

Ist danach $b_j \neq 0$, dann geht es weiter mit Schritt 1 und Zeile $i + 1$.

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

Nord-West-Ecken-Verfahren Mengenmatrix

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:

Zeilenfolgeverfahren Mengenmatrix zulässige Ausgangslösung

Vorgehensweise bei Zeilenfolgeverfahren

Die Vorgehensweise zur Erreichung der obigen Mengenbelegung ist wie folgt:

Hinweis

Hier klicken zum Ausklappen

Hinweis: Die roten Zahlen links unten stellen die Reihenfolge der Mengenbelegung dar. Die Sternchen an den Warenhäusern $j$ sind die Spaltenmarkierungen die im Laufe des Algorithmus durchgeführt worden sind.

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$.

Merke

Hier klicken zum Ausklappen

Im Gegensatz zum Nord-West-Ecken-Verfahren ist diese zulässige Ausgangslösung um einiges besser, da die reduzierten Kosten $K_R$ geringer sind. 

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$.

Merke

Hier klicken zum Ausklappen

Das Spaltenfolgeverfahren und das Zeilenfolgeverfahren führen nicht immer zu den selben Transportkosten!

Alternative Vorgehensweise

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

Methode

Hier klicken zum Ausklappen

Zeilenfolgeverfahren (alternative Vorgehensweise)

Zu Beginn des Verfahrens sind alle Spalten unmarkiert. Die Iteration erfolgt von $i = 1, .., n$ ($i$ = Zeile).

1. Es wird das kleinste Element der Zeile $i$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Spaltenindex $j$ gewählt.

2. Es wird dann $x_{ij} = min \{a_i, b_j \}$ gesetzt. Danach werden die Angebots- und Nachfragemengen angepasst durch $a_i := a_i - x_{ij} $ und $b_j := b_j - x_{ij}$.  

Ist danach $b_j = 0$, wird die Spalte $j$ markiert und die Elemente dieser Spalte für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und der nächsten Zeile $i + 1$.

Nachdem alle Zeilen betrachtet worden sind, fängt das Verfahren wieder bei der 1. Zeile an. Dies wird solange durchgeführt, bis alle $m + n - 1$-Basisvariablen gefunden sind. 

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:

Zeilenfolgeverfahren alternative Vorgehensweise

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$.

Merke

Hier klicken zum Ausklappen

Die beiden Zeilenfolgeverfahren führen nicht immer zu den selben Transportkosten!