Vogelsche Approximationsmethode

Vogelsche Approximationsmethode Definition

Auch die Vogelsche Approximationsmethode bestimmt eine mögliche Ausgangslösung für das Transportproblem (diese Ausgangslösung muss dann mit einem anderen Algorithmus optimiert werden).

Beispiel

Beispiel: Vogelsche Approximationsmethode

Das Beispiel zum Transportproblem war:

Es gibt 3 Quellorte Q1, Q2 und Q3, die z.B. jeweils folgende Mengen produzieren bzw. liefern (können), z.B. 100, 200 und 300 Stück.

Es gibt 3 Zielorte Z1, Z2 und Z3, die jeweils eine bestimmte Menge benötigen: 250, 200 und 150 Stück (Liefer- und Nachfragemengen stimmen in Summe überein: 600 Stück).

Die Tabelle enthält die Entfernungs-km zwischen den Quell- und Zielorten. Wir gehen davon aus, dass die Transportkosten (die minimal sein sollen) den km mal der transportierten Menge entsprechen (d.h., jede transportierte Mengeneinheit kostet extra, was halbwegs realistisch ist).

Entfernungstabelle
Z1 Z2 Z3
Q1 1 8 6
Q2 5 3 7
Q3 9 4 2

Die Tabelle hat 9 Felder.

Erster Schritt: Für die 3 Zeilen und 3 Spalten jeweils die Differenz zwischen den zweitniedrigsten und niedrigsten Transportkosten (hier gleich km) berechnen: ZD ("Zeilendifferenz") und SD ("Spaltendifferenz").

Diese Differenz wird auch als "Strafe" oder Opportunitätskosten bezeichnet; sie spiegelt wider, inwiefern sich die Kosten erhöhen, wenn nicht die beste Alternative in der jeweiligen Zeile oder Spalte gewählt wird, sondern die zweitbeste.

1. Tabelle
Z1 Z2 Z3 ZD
Q1 1 (100) 8 6 5
Q2 5 3 7 2
Q3 9 4 2 2
SD 4 1 4

Zweiter Schritt: In der Zeile oder Spalte mit der höchsten Differenz das Feld mit den niedrigsten Transportkosten suchen; das ist hier die erste Zeile und das erste Feld. Dieses Feld bekommt die höchstmögliche Transportmenge zugewiesen, das sind hier 100 (da Q1 nur 100 liefern kann).

Die Transportmengen werden hier in Klammern gesetzt.

Anschließend die Zeile streichen und dadurch die Tabelle verkürzen.

Danach wieder die Differenzen berechnen:

2. Tabelle
Z1 Z2 Z3 ZD
Q2 5 3 7 2
Q3 9 4 2 (150) 2
SD 4 1 5

Die größte Differenz ist in Spalte 3, das Feld mit den niedrigsten Transportkosten ist das Feld in Zeile Q3 mit 2 (km). Dieses Feld bekommt wieder die höchstmögliche Transportmenge zugewiesen, das sind hier 150 (da Q3 nicht mehr benötigt, auch wenn Z3 mehr liefern könnte). Spalte 3 wird gestrichen.

Nach diesem Schema wird weiter verfahren:

3. Tabelle
Z1 Z2 ZD
Q2 5 3 2
Q3 9 4 (150) 5
SD 4 1
4. Tabelle
Z1 Z2 ZD
Q2 5 (150) 3 (50) 2
SD 5 3

Das besondere an dieser letzten Tabelle ist, dass es nur noch eine Zeile gibt und diese deshalb nicht mehr über die Differenz ausgewählt werden muss. Die Zelle mit den geringsten Kosten bzw. km bekommt die maximal noch mögliche Menge von 50 zugewiesen (Z2 ist dann vollständig bedient) und die andere Zelle den Rest von 150 (das was Q2 noch liefern kann und Z1 noch benötigt).

Nun sind alle produzierten Stück der Quellen verteilt, jedes Ziel hat seine benötigte Menge in Summe bekommen.

M11 bezeichne die Transportmenge von Q1 nach Z1, M23 bezeichne die Transportmenge von Q2 nach Z3 usw.; die mit dem jeweiligen Feld (d.h. mit km) bewerteten Transportkosten sind dann:

M11 = 100 × 1 = 100

M33 = 150 × 2 = 300

M32 = 150 × 4 = 600

M22 = 50 × 3 = 150

M21 = 150 × 5 = 750

Das sind in Summe 1.900.

Das ist wie gesagt nur eine mögliche (Ausgangs-)Lösung, noch keine optimale (die optimalen Kosten können niedriger als 1.900 sein).