Inhaltsverzeichnis
In diesem Abschnitt wird das Vogelsche-Approximationsverfahren aufgezeigt. Auch dieses Verfahren stellt ein Eröffnungsverfahren von Transportproblemen dar und hat das Ziel eine zulässige Ausgangslösung zu finden.
Merke
Für das Vogelsche Approximationsverfahren ist es sinnvoll die Ausgangskostenmatrix heranzuziehen. Es wird also vorher keine Reduktion der Kostenmatrix vorgenommen.
Vogelsches Approximationsverfahren - Ablauf
Die Vorgehensweise des Vogelschen Approximationsverfahren soll im folgenden ausführlich beschrieben werden.
Methode
Vogelsches Approximationsverfahren
Zu Beginn sind alle Zeilen und Spalten unmarkiert.
1. Für jede unmarkierte Zeile $i$ wird die Differenz $dz_i$ zwischen dem zweitkleinsten und dem kleinsten Element gebildet. Diese Differenz wird neben die Angebotsmenge $a_i$ geschrieben.
Für jede unmarkierte Spalte $j$ wird die Differenz $ds_j$ zwischen zweitkleinstem und kleinstem Element gebildet. Diese Differenz wird unter die Nachfragemenge $b_j$ geschrieben.
2. Es wird dann die maximale Differenz $max \{dz_i, ds_j \}$ gewählt. Man bestimmt in der dazugehörigen Zeile oder Spalte die minimalen Kosten $min \{c_{ij} \}$. Sind mehrere maximale Differenzen gegeben, so wird die mit minimalen $c_{ij}$ gewählt.
3. Es wird dann $x_{ij} = min \{a_i, b_j \}$ gesetzt. Danach werden die Angebots- und Nachfragemengen angepasst durch $a_i := a_i - x_{ij} $ und $b_j := b_j - x_{ij}$.
Ist danach $a_i = 0$, wird die Zeile $i$ bis auf das Element $x_{ij}$ gestrichen.
Ist danach $b_j = 0$, wird die Spalte $j$ bis auf das Element $x_{ij}$ gestrichen.
Ist danach $a_i = b_j = 0$, wird entweder die Zeile $i$ oder die Spalte $j$ bis auf das Element $x_{ij}$ gestrichen.
4. Die Schritte 1-3 werden solange wiederholt, bis alle Zeilen und Spalten durchgestrichen sind.
Für das Vogelsche Approximationsverfahren kann ebenfalls die Mengenmatrix herangezogen werden. Die Kosten werden dabei wieder in die obere rechte Ecke geschrieben. Hier werden die Ausgangskosten verwendet:
Die obere Mengenmatrix zeigt am oberen rechten Rand die Kosten der Ausgangsmatrix.
Der 1. Schritt ist die Bildung der Differenzen $dz_i$ und $ds_j$. Für $d_i$ zum Beispiel ist die Zeile i herangezogen worden und die kleinste Kosten von den nächstkleineren Kosten abgezogen worden (z.B. $dz_1 = 140 - 130 = 10$). Für $d_j$ wurde die Spalte $j$ herangezogen und die kleinsten von den nächstkleineren EKosten abgezogen (z.B. $ds_3 = 170 - 140 = 30$). Dies wird für alle Spalten und Zeilen durchgeführt.
Der 2. Schritt ist die Auswahl der maximalen Differenz $max \{dz_i, ds_j \}$. In den obigen Beispiel ist dies die Differenz $dz_3 = 40$ (Zeile 3). Es müssen dann in dieser 3. Zeile die minimalen Kosten ausgewählt werden. Diese betragen $c_{32} = 120$.
Der 3. Schritt ist dann die Festlegung von $x_{32} = min \{400; 500 \} = 400$. Danach werden die Angebots- und Nachfragemengen angepasst durch $a_3 := 400 - 400 = 0$ und $b_2 := 500- 400 = 100$. Die Zeile $a_3 = 0$ wird dann (bis auf das Element $x_{32} = 400$ gestrichen.
Es wird wieder mit Schritt 1 begonnen. Die Differenzen müssen nun neu gebildet werden, da die 3. Zeile gestrichen wurde. Hier ändern sich vor allem die Differenzen der Spalten.
Der 2. Schritt ist die Auswahl der maximalen Differenz $max \{dz_i, ds_j \}$. In den obigen Beispiel ist dies die Differenz $ds_2 = ds_3 = ds_4 = 30$ (Spalte 2,3,4). Bei meheren maximalen Werten, wird derjenige gewählt, welcher die geringsten Kosten besitzt. Für die drei Spalten liegen die geringsten Kosten in der 2. Spalte mit $c_{12} = 130$.
Der 3. Schritt ist die Festlegung von $x_{12} = min \{900; 100 \} = 100$. Danach werden die Angebots- und Nachfragemengen angepasst durch $a_1 := 900 - 100 = 800$ und $b_2 := 100 - 100 = 0$. Die Spalte $b_2 = 0$ wird dann (bis auf das Element $x_{12} = 100$ gestrichen.
1.Schritt: Bildung der Differenzen.
2. Schritt: Auswahl der maximalen Differenz $ds_3 = ds_4 = 30$. Auswahl der geringsten Kosten $c_{23} = 140$.
3. Schritt: Festlegung von $x_{23} = min \{800; 400 \} = 400$. Anpassung der Angebots- und Nachfragemengen durch $a_2 = 800 - 400 = 400$ und $b_3 = 400 - 400 = 0$. Die Spalte $b_3 = 0$ wird dann gestrichen.
1.Schritt: Bildung der Differenzen.
2. Schritt: Auswahl der maximalen Differenz $ds_4 = 30$. Auswahl der geringsten Kosten $c_{14} = 150$.
3. Schritt: Festlegung von $x_{14} = min \{800; 600 \} = 600$. Anpassung der Angebots- und Nachfragemengen durch $a_1 = 800 - 600 = 200$ und $b_4 = 600 - 600 = 0$. Die Spalte $b_4 = 0$ wird dann gestrichen.
1.Schritt: Bildung der Differenzen.
2. Schritt: Auswahl der maximalen Differenz $dz_2 = 20$. Auswahl der geringsten Kosten $c_{25} = 130$.
3. Schritt: Festlegung von $x_{25} = min \{400; 300 \} = 300$. Anpassung der Angebots- und Nachfragemengen durch $a_2 = 400 - 300 = 100$ und $b_5 = 300 - 300 = 0$. Die Spalte $b_5 = 0$ wird dann gestrichen.
1.Schritt: Bildung der Differenzen.
2. Schritt: Auswahl der maximalen Differenz $ds_1 = 10$. Auswahl der geringsten Kosten $c_{11} = 140$.
3. Schritt: Festlegung von $x_{11} = min \{200; 300 \} = 200$. Anpassung der Angebots- und Nachfragemengen durch $a_1 = 200 - 200 = 0$ und $b_1 = 300 - 100 = 100$. Die Zeile $a_1 = 0$ wird dann gestrichen.
Es verbleiben nur noch die Kosten $c_{21} = 150$. Diese werden mit den restlichen Angebots-und Nachfragemengen $x_{12} = 100$ belegt. Es ergibt sich demnach eine zulässige Ausgangslösung von:
Die gesamten Transportkosten für die obige Ausgangslösung sind:
$K = 200 \cdot 140 + 100 \cdot 150 + 100 \cdot 130 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 289.000$.
Die Transportkosten nach dem Vogelschen Approximationsverfahren für die Ausgangslösung sind geringer, als nach den Rangfolgeverfahren und nach dem Nord-West-Ecken-Verfahren.
Weitere interessante Inhalte zum Thema
-
Summen und Differenzen trigonometrischer Funktionen
Vielleicht ist für Sie auch das Thema Summen und Differenzen trigonometrischer Funktionen (Elementare Funktionen) aus unserem Online-Kurs Analysis und Lineare Algebra interessant.
-
Verfahren des besten Nachfolgers
Vielleicht ist für Sie auch das Thema Verfahren des besten Nachfolgers (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
