ZU DEN KURSEN!

Operations Research 1 - Spaltenfolgeverfahren

Kursangebot | Operations Research 1 | Spaltenfolgeverfahren

Operations Research 1

Spaltenfolgeverfahren

Inhaltsverzeichnis

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:

Methode

Hier klicken zum Ausklappen

Spaltenfolgeverfahren

Zu Beginn des Verfahrens sind alle Zeilen unmarkiert. Die Iteration erfolgt von $j = 1, .., n$ ($j$ = Spalte).

1. Es wird das kleinste Element der Spalte $j$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Zeilenindex $i$ 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 $a_i = 0$, wird die Zeile $i$ markiert und die Elemente dieser Zeile für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und derselben Spalte $j$.

Ist danach $a_i \neq 0$, dann geht es weiter mit Schritt 1 und Spalte $j + 1$.

Das Spaltenfolgeverfahren wird nun anhand des folgenden Transportproblems aufgezeigt:

Nord-West-Ecken-Verfahren Mengenmatrix

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:

Spaltenfolgeverfahren

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 Fabriken $i$ sind die Zeilenmarkierungen die im Laufe des Algorithmus durchgeführt worden sind.

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

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

Methode

Hier klicken zum Ausklappen

Spaltenfolgeverfahren (alternative Vorgehensweise)

Zu Beginn des Verfahrens sind alle Zeilen unmarkiert. Die Iteration erfolgt von $j = 1, .., n$   ($j$ = Spalte).

1. Es wird das kleinste Element der Spalte $j$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Zeilenindex $i$ 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 $a_i = 0$, wird die Zeile $i$ markiert und die Elemente dieser Zeile für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und der nächsten Spalte $j+1$.

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

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:

Spaltenfolgeverfahren alternative Vorgehensweise

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

Merke

Hier klicken zum Ausklappen

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