Vogelsche Approximationsmethode

Die Vogelsche Approximationsmethode i​st ein heuristisches Verfahren a​us dem Bereich d​es Operations Research z​ur Lösung e​ines Transportproblems. Diese Methode zeichnet s​ich dadurch aus, d​ass sie d​em Optimum s​chon sehr nahekommt. Der Aufwand i​st allerdings gegenüber anderen Methoden, w​ie z. B. d​em Nord-West-Ecken-Verfahren o​der dem Matrixminimumverfahren, vergleichsweise hoch.

Algorithmus
  1. Als Erstes wird eine Hilfsmatrix mit den Opportunitätskosten, die sich aus der Differenz der beiden kleinsten Werte der jeweiligen Zeile und Spalte zusammensetzen, erstellt.
  2. Dann wird die Zeile oder die Spalte mit den höchsten Opportunitätskosten aus der Hilfsmatrix herausgesucht.
  3. Aus dieser Zeile oder Spalte wird dann der niedrigste Wert herausgesucht. Diesem Feld werden in der Ursprungsmatrix die maximal möglichen Kapazitäten zugeordnet.
  4. Falls die Angebots- oder Bedarfsmenge erschöpft ist, wird die betreffende Spalte oder die betreffende Zeile, in der Ursprungsmatrix, mit Nullen aufgefüllt und in der Hilfsmatrix gestrichen.
  5. Nach jedem Durchgang werden die Opportunitätskosten neu berechnet und das Zuordnen beginnt wieder von vorne.
  6. Diese Methode endet, wenn alle Kapazitäten zugeordnet sind.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.