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 jeweils folgende Mengen produzieren bzw. liefern (können): 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).
| 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.
| 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:
| 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 Z3 nicht mehr benötigt, auch wenn Q3 mehr liefern könnte). Spalte 3 wird gestrichen.
Nach diesem Schema wird weiter verfahren:
| Z1 | Z2 | ZD | |
|---|---|---|---|
| Q2 | 5 | 3 | 2 |
| Q3 | 9 | 4 (150) | 5 |
| SD | 4 | 1 |
| 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).