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 betrachtet. Hier wird das kleinste Element ausgewählt . Es wird dann gesetzt. Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da geht man als nächstes zur Spalte über.

2. Spalte:

Es wird nun die Spalte betrachtet. Es wird das kleinste Element ausgewählt . Die Menge wird gesetzt. Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da wird die Zeile 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 . Man setzt . Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da geht man als nächstes zur Spalte über.

3.Spalte:

(Nicht vergessen, die markierte Zeile darf nicht weiter berücksichtigt werden)

Es wird die Spalte betrachtet. Es wird das kleinste Element ausgewählt . Die Menge wird gesetzt. Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da  geht man als nächstes zur Spalte über.

4. Spalte:

(Nicht vergessen, die markierte Zeile  darf nicht weiter berücksichtigt werden)

Es wird die Spalte betrachtet. Es wird das kleinste Element ausgewählt . Die Menge wird gesetzt. Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da wird die Zeile 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 . Da diese aber nicht berücksichtigt werde darf, wird das nächstkleinere Element gewählt. Dieses ist . Man setzt . Die neue Angebotsmenge ist dann und die neue Nachfragemenge . Da geht man als nächstes zur Spalte über.

5. Spalte:

(Nicht vergessen, die markierte Zeilen und  dürfen nicht weiter berücksichtigt werden)

Es wird die Spalte betrachtet. Hier wird das kleinste Element ausgewählt . Es wird dann gesetzt. Die neue Angebotsmenge ist dann und die neue Nachfragemenge . 

Das Verfahren endet hier, da alle Spalten abgearbeitet worden sind und -Basisvariablen bestimmt worden sind. 

Die gesamten reduzierten Kosten ergeben sich zu:

.

Die tatsächlichen Transportkosten betragen:

.

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 , sondern schreitet immer von einer Spalte zur nächsten. Das ganze wiederholt sich solange, bis die -Basisvariablen gefunden sind. Nach dieser Vorgehensweise ergibt sich die folgenden Mengenbelegung:

Die gesamten reduzierten Kosten bei dieser Vorgehensweise betragen:

.

Die tatsächlichen Transportkosten betragen:

.