ZU DEN KURSEN!

Operations Research 1 - Nord-Westecken-Verfahren

Kursangebot | Operations Research 1 | Nord-Westecken-Verfahren

Operations Research 1

Nord-Westecken-Verfahren

Das Nord-West-Ecken-Verfahren führt zu einer zulässigen Ausgangslösung für Transportprobleme. Hierbei wird die Mengenmatrix herangezogen. Das Ziel dieses Verfahrens ist es, die Angebotsmenge so auf die Warenhäuser zu verteilen, dass deren Nachfrage komplett abgedeckt wird. Die Kosten des Transports werden hierbei nicht berücksichtigt. Die Minimierung der Kosten erfolgt dann später bei den Optimierungsverfahren. Die Mengenmatrix für das Beispiel sieht wie folgt aus:

Nord-West-Ecken-Verfahren Mengenmatrix

Innerhalb der Matrix werden die Kosten der redzuierten Kostenmatrix (sofern eine Reduktion vorgenommen worden ist, sonst der Ausgangskostenmatrix) an die obere rechte Ecke geschrieben. Dies dient der Übersicht halber bei der späteren Summation der Kosten. Die Mengen die transportiert werden sind zunächst leer und werden mittels des folgenden Algorithmus bestimmt:

Methode

Hier klicken zum Ausklappen

Algorithmus Nord-West-Ecken-Verfahren

Beginnend in der oberen linken Ecke (Nord-West-Ecke) schreitet das Verfahren entweder waagerecht oder senkrecht voran.

1. Ist $a_1 > b_1$, so wird $x_{11} = b_1$ gesetzt. Es geht dann waagerecht weiter. Ist $a_1 - x_{11} > b_2$, so wird $x_{12} = b_2$ gesetzt, sonst $a_1 - x_{11}$ und weiter mit Schritt 2, usw.

2. Ist $a_1 < b_1$, so wird $x_{11} = a_1$ gesetzt. Es geht dann senkrecht weiter. Ist $a_2 < b_1 - x_{11}$, so wird $x_{12} = a_2$ gesetzt, sonst $b_1 - x_{11}$ und weiter mit Schritt 1, usw.

3. Ist $a_1 = b_1$, so wird $x_{11} = a_1 = b_1$ gesetzt. Es geht dann waagerecht weiter und setzt $x_{12} = 0$. Es geht dann senkrecht weiter und legt $x_{22}$ gemäß Schritt 1-3 fest.

(Alternativ, man setzt $x_{11} = a_1 = b_1$. Es geht dann senkrecht weiter und setzt $x_{21} = 0$. Es geht dann senkrecht weiter und legt $x_{22}$ gemäß Schritt 1-3 fest.

4. Man verfahren solange mit Schritt 1-3 bis die Menge $x_{mn}$ festgelegt ist.

Nach Anwendung des Algorithmus für das Nord-West-Ecken-Verfahren ergibt sich das folgende Tableau mit zulässiger Ausgangslösung:

Nord-West-Ecken-Verfahren Ausgangslösung

Es wurde wie folgt vorgegangen:

Für $x_{11}$:

$a_1 > b_1$ (900 > 300). Schritt 1: $x_{11} = b_1 = 300$. Waagerecht weiter.

Für $x_{12}:

$a_1 - x_{11} > b_2$ (600 > 500). Schritt 1: $x_{12} = b_2 = 500$. Waagerecht weiter.

Für $x_{13}$:

$a_1 - x_{11} - x_{12} < b_3$ (100 < 400). Schritt 2: $x_{13} = a_1 - x_{11} - x_{12} = 100$. Senkrecht weiter.

Für $x_{23}$:

$a_2 > b_3 - x_{13}$ (800 > 300). Schritt 1: $x_{23} = b_3 - x_{12} = 300$. Waagerecht weiter.

Für $x_{24}$:

$a_2 - x_{23} < b_4$ (500 < 600). Schritt 2: $x_{24} = a_2 - x_{23} = 500$. Senkrecht weiter.

Für $x_{34}$:

$a_3 > b_4 - x_{24}$ (400 > 100). Schritt 1: $x_{34} = b_4 - x_{24} = 100$. Waagerecht weiter.

Für $x_{35}$:

$a_3 - x_{34} = b_5$ (300 = 300). Schritt 3: $x_{35} = a_3 - x_{34} = b_5 = 300$. ENDE

Es ist immer wichtig, dass nachdem eine Transportmenge von der Fabrik zum Warenhaus festgelegt worden ist, diese beim weiteren Vorgehen zu berücksichtigen, denn die Angebots- und Nachfragemenge verringert sich um diese festgelegte Transportmenge. So ist zum Beispiel bei der Festlegung von $x_{11} = 300$ Mengen für die weitere Betrachtung die Angebotsmenge $a_1$ um diese Menge zu reduzieren, da von Fabrik 1 diese 300 Mengen schon für den Nachfrageort 1 verplant sind. Genauso wird auch für den Nachfrageort 1 für die nachfolgenden Betrachtungen diese Menge von der Nachfragemenge $b_1$ abgezogen. Je mehr Mengen bereits festgelegt wurden, desto mehr Mengen müssen berücksichtigt werden. Zur besseren Übersicht kann man die Angebots- und Nachfragemenge auch an der Seite durchstreichen und die aktuelle Menge daneben schreiben:

Nord-West-Ecken-Verfahren Ausgangslösung

Es liegt nun eine zulässige Ausgangslösung vor. Die gesamten reduzierten Transportkosten für diese Ausgangslösung betragen:

$K_R = 300 \cdot 0 + 500 \cdot 10 + 100 \cdot 30 + 300 \cdot 0 + 500 \cdot 30 + 100 \cdot 20 + 300 \cdot 60 = 43.000$.

Hierbei handelt es sich um die Kosten der reduzierten Kostenmatrix. Diese können zum Vergleich der anderen Eröffnungsverfahren herangezogen werden. Für die anderen Eröffnungsverfahren (die nun folgen) müssen zum Vergleich der zulässigen Ausgangslösung dann aber ebenfalls die reduzierten Kosten herangezogen werden. Das Eröffnungsverfahren mit den geringsten Kosten besitzt die beste Ausgangslösung.

Die tatsächlichen Kosten (Ausgangskostenmatrix) für den obigen Transport betragen:

$K = 300 \cdot 140 + 500 \cdot 130 + 100 \cdot 170 + 300 \cdot 140 + 500 \cdot 180 + 100 \cdot 170 + 300 \cdot 190 = 330.000$.