Nord-West-Ecken-Verfahren

Nord-West-Ecken-Verfahren

Das Nord-West-Ecken-Verfahren ist ein Verfahren aus dem Operations Research, das eine zulässige Anfangslösung für das Transportproblem liefern soll. Von dieser Lösung aus startet der Optimierungsalgorithmus des Transportproblems.

Algorithmus

Dabei schaut man von der oberen linken Ecke der Matrix ausgehend, ob man in dem aktuellen Feld eine Kapazität ausschöpfen oder einen Bedarf befriedigen kann.

c(i,j) = min(B(j), K(i))

Wenn der Bedarf dieser Zeile gedeckt ist, sucht man in der Zeile abwärts nach dem nächsten Feld, bei dem eins der beiden Kriterien erfüllt werden kann. Wurde die Kapazität der Spalte ausgeschöpft, dann sucht man in der Zeile weiter. Wurde beides voll belegt, dann geht man ein Feld diagonal nach rechts unten weiter.

Effizienz

Das Nord-West-Ecken-Verfahren liefert ein Ausgangstableau, das häufig sehr viele weitere Iterationen des Lösungsalgorithmus bis zur optimalen Lösung erfordert.

Beispiel

Das Verfahren wird anhand des Beispiels im Artikel über das Transportproblem gezeigt. Grundlage ist das Gleichungssystem

x11 + x12 + x13 = 16
x21 + x22 + x23 = 14
x11 + x21 = 15
x12 + x22 = 5
x13 + x23 = 10

wobei es zwei Angebote A1 und A2 und drei Bedarfsanmeldungen B1, B2 und B3 gibt. xij bezeichnet hier die von i nach j gelieferte Menge. Man kann das Gleichungssystem tabellarisch zusammenfassen als

   |B 1  B2  B3 |
---------------------
A1 | x11 x12 x13| 16
A2 | x21 x22 x23| 14
---------------------
   | 15   5  10 | 30

Für die Nord-West-Eckenlösung wird nun zuerst möglichst viel in die Nord-West-Ecke gepackt. A1 liefert also 15 Einheiten an B1. A1 hat noch eine Einheit übrig, die an B2 geliefert wird. Den restlichen Bedarf von B2 deckt A2 mit 4 Einheiten. A2 hat noch 10 Einheiten übrig, welche an B3 gehen. Man erhält nun

   |B 1  B2  B3 |
---------------------
A1 | 15   1   0 | 16
A2 |  0   4  10 | 14
---------------------
   | 15   5  10 | 30

Durch die Anfangslösung wurde eine gültige Basislösung erreicht. Die Variablen mit positiven Mengen sind die Basisvariablen, Variablen mit Null sind Nichtbasisvariablen. Das ersieht man auch, wenn man das obige Gleichungssystem als Tableau hinschreibt:

x11 x12 x13 x21 x22 x23  b
-------------------------- 
 1   1   1   0   0   0  16
 0   0   0   1   1   1  14
 1   0   0   1   0   0  15
 0   1   0   0   1   0   5
 0   0   1   0   0   1  10

Werden die Vektoren unter x11, x12, x22 und x23 zu Basisvektoren umgeformt, ergibt sich das Tableau

x11 x12 x13 x21 x22 x23  b
-------------------------- 
 1   0   0   1   0   0  15
 0   0  -1   1   1   0   4
 0   1   1  -1   0   0   1
 0   0   1   0   0   1  10
 0   0   0   0   0   0   0

welches die Nord-West-Eckenlösung wiedergibt.


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • MODI — Die Modifizierte Distributionsmethode (MODI Methode), auch als Potentialmethode, u v Methode oder Transportalgorithmus bezeichnet, ist ein numerisches Verfahren, mit dem man (bei gegebener Anfangs Basislösung) ein Standard Transportproblem lösen… …   Deutsch Wikipedia

  • Sprungbrettmethode — Die Zyklenmethode bzw. Stepping Stone Methode ist ein numerisches Verfahren, mit dem man (bei gegebener Ausgangs Basislösung) ein Standard Transportproblem lösen kann. Es sind für ein Gut eine bestimmte Anzahl n Anbieter Ai (i = 1,...,n) und eine …   Deutsch Wikipedia

  • Stepping-Stone-Methode — Die Zyklenmethode bzw. Stepping Stone Methode ist ein numerisches Verfahren, mit dem man (bei gegebener Ausgangs Basislösung) ein Standard Transportproblem lösen kann. Es sind für ein Gut eine bestimmte Anzahl n Anbieter Ai (i = 1,...,n) und eine …   Deutsch Wikipedia

  • Zyklen-Methode — Die Zyklenmethode bzw. Stepping Stone Methode ist ein numerisches Verfahren, mit dem man (bei gegebener Ausgangs Basislösung) ein Standard Transportproblem lösen kann. Es sind für ein Gut eine bestimmte Anzahl n Anbieter Ai (i = 1,...,n) und eine …   Deutsch Wikipedia

  • Transportoptimierung — Das Transportproblem ist eine Fragestellung aus dem Operations Research: Zum Transport einheitlicher Objekte von mehreren Angebots zu mehreren Nachfrageorten ist ein optimaler, d.h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu… …   Deutsch Wikipedia

  • Nordwestecken — Das Nord West Ecken Verfahren ist ein Verfahren aus dem Operations Research, das eine zulässige Anfangslösung für das Transportproblem liefern soll. Von dieser Lösung aus startet der Optimierungsalgorithmus des Transportproblems. Algorithmus… …   Deutsch Wikipedia

  • Nordwesteckenregel — Das Nord West Ecken Verfahren ist ein Verfahren aus dem Operations Research, das eine zulässige Anfangslösung für das Transportproblem liefern soll. Von dieser Lösung aus startet der Optimierungsalgorithmus des Transportproblems. Algorithmus… …   Deutsch Wikipedia

  • Transportproblem — Das Transportproblem ist eine Fragestellung aus dem Operations Research: Zum Transport einheitlicher Objekte von mehreren Angebots zu mehreren Nachfrageorten ist ein optimaler, d.h. kostenminimaler Plan zu finden, wobei die vorhandenen und zu… …   Deutsch Wikipedia

  • Zyklenmethode — Die Zyklenmethode bzw. Stepping Stone Methode ist ein numerisches Verfahren, mit dem man (bei gegebener Ausgangs Basislösung) ein Standard Transportproblem lösen kann. Es sind für ein Gut eine bestimmte Anzahl n Anbieter Ai (i = 1,...,n) und eine …   Deutsch Wikipedia

  • MODI-Methode — Die Modifizierte Distributionsmethode (MODI Methode), auch als Potentialmethode, u v Methode oder Transportalgorithmus bezeichnet, ist ein numerisches Verfahren, mit dem man (bei gegebener Anfangs Basislösung) ein Standard Transportproblem lösen… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”