ingenieurkurse
online lernen

Besser lernen mit Online-Kursen

NEU! Jetzt online lernen:
Operations Research 1
Den Kurs kaufen für:
einmalig 39,00 €
Zur Kasse
Transport- und Zuordnungsprobleme > Das klassische Transportproblem > Eröffnungsverfahren:

Vogelsches-Approximations-Verfahren

WebinarTerminankündigung aus unserem Online-Kurs Thermodynamik:
 Am 13.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Thermodynamik) Innere Energie, Wärme, Arbeit
- Innerhalb dieses 60-minütigen Webinares wird der 1. Hauptsatz der Thermodynamik für geschlossene Systeme behandelt und auf die innere Energie, Wärme und Arbeit eingegangen.
[weitere Informationen] [Terminübersicht]

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.


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:

Vogelsches Approximationsverfahren 1

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. 

Vogelsches Approximationsverfahren 2

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. 

Vogelsches Approximationsverfahren 3

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. 

Vogelsches Approximationsverfahren 4

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. 

Vogelsches Approximationsverfahren 5

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. 

Vogelsches Approximationsverfahren 6

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:

Vogelsches Approximationsverfahren 7

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.

Vorstellung des Online-Kurses Operations ResearchOperations Research
Dieser Inhalt ist Bestandteil des Online-Kurses

Operations Research 1

Ingenieurkurse (ingenieurkurse.de)
Diese Themen werden im Kurs behandelt:

[Bitte auf Kapitelüberschriften klicken, um Unterthemen anzuzeigen]

  • Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
    • Einleitung zu Kurs: Operations Research 1 - Lineare Optimierung, Graphentheorie und Netzplantechnik
  • Lineare Programmierung
    • Einleitung zu Lineare Programmierung
    • Definition: Lineares Programm
    • Standardform: Maximierungsproblem
      • Einleitung zu Standardform: Maximierungsproblem
      • Grafische Lösung eines Maximierungsproblems
        • Einleitung zu Grafische Lösung eines Maximierungsproblems
        • Beispiel: Grafische Lösung eines Maximierungsproblems
      • Umformung in die Standardform (Maximierungsproblem)
      • Umformung in die Normalform (Maximierungsproblem)
      • Simlpex-Algorithmus: Einführung
        • Einleitung zu Simlpex-Algorithmus: Einführung
        • Primales Simlpexverfahren
          • Einleitung zu Primales Simlpexverfahren
          • Primales Simplexverfahren: Anfangstableau aufstellen
          • Primales Simplexverfahren: Pivotspalte/-zeile/-element
          • Primales Simplexverfahren: 1. Simplexschritt
          • Primales Simplexverfahren: Weitere Simplexschritte (optimale Lösung)
          • Beispiel: Maximierungsproblem / grafische Lösung
          • Beispiel: Maximierungsproblem / Primales Simplexverfahren
        • Duales Simplexverfahren
          • Einleitung zu Duales Simplexverfahren
          • Duales Simplexverfahren: Pivotzeile/-spalte/-element
          • Duales Simplexverfahren: Simplexschritte
        • Die Big-M-Methode des primalen Simplexverfahrens
          • Einleitung zu Die Big-M-Methode des primalen Simplexverfahrens
          • Die Big-M-Methode: Einfügen von künstlichen Variablen
          • Die Big-M-Methode: Künstliche Variablen als Basisvariablen
          • Big-M-Methode: Simplexschritt durchführen
          • Big-M-Methode: Weiterer Simplexschritt (zulässige Lösung)
          • Big-M-Methode: Weitere Simplexschritte (optimale Lösung)
      • Kanonische Form, Standardform, Normalform
      • Zusammenfassung: Maximierungsproblem
    • Minimierungsproblem
      • Einleitung zu Minimierungsproblem
      • Dualität - Primalproblem als Maximierungsproblem
      • Dualität - Primalproblem als Minimierungsproblem
      • Dualität - Dualproblem in Primalproblem
      • Beispiel: Primalproblem als Minimierungsproblem
      • Minimierungsproblem- Big-M/dualer Simplex
      • Zusammenfassung: Minimierungsproblem
    • Sonderfälle bei Optimierungsmodellen
      • Einleitung zu Sonderfälle bei Optimierungsmodellen
      • Beispiel: Minimierungsproblem ohne optimal Lösung
    • Sensitivitätsanalyse
      • Einleitung zu Sensitivitätsanalyse
      • Änderung der Zielfunktionskoeffizienten
        • Einleitung zu Änderung der Zielfunktionskoeffizienten
        • Beispiel: Sensitivitätsanalyse Zielfunktionskoeffizienten
      • Änderung der Restriktionen
    • Obere und untere Schranken bei Variablen
      • Untere Schranken
      • Obere Schranken
        • Einleitung zu Obere Schranken
        • Beispiel: Primaler Simplexalgorithmus
        • Beispiel: Vielzahl an beschränkten Variablen
    • Revidierter Simplex-Algorithmus
      • Einleitung zu Revidierter Simplex-Algorithmus
      • Beispiel: Revidierter Simplex-Algorithmus
  • Transport- und Zuordnungsprobleme
    • Das klassische Transportproblem
      • Einleitung zu Das klassische Transportproblem
      • Ausgleichsprüfung
      • Reduktion der Kostenmatrix
      • Eröffnungsverfahren
        • Einleitung zu Eröffnungsverfahren
        • Nord-Westecken-Verfahren
        • Rangfolgeverfahren
          • Einleitung zu Rangfolgeverfahren
          • Spaltenfolgeverfahren
          • Zeilenfolgeverfahren
          • Matrixminimumverfahren
        • Vogelsches-Approximations-Verfahren
      • Optimierungsverfahren
        • Einleitung zu Optimierungsverfahren
        • Stepping-Stone-Methode
        • MODI-Methode
    • Lineare Zuordnungsprobleme
      • Definition: Zuordnungsprobleme
      • Ungarische Methode
  • Netzplantechnik
    • Einführung Netzplantechnik
    • Ablaufplanung
      • Einleitung zu Ablaufplanung
      • Strukturplanung
      • Netzplanerstellung
    • Zeitplanung
      • Einleitung zu Zeitplanung
      • Beispiel 1: Vorgangsknotennetzplan
      • Beispiel 2: Vorgangsknotennetzplan
    • Kostenplanung
    • Kapazitätsplanung
  • Graphentheorie
    • Einführung: Graphentheorie
    • Kürzeste Wege
      • Einleitung zu Kürzeste Wege
      • Dijkstra-Algorithmus
      • Fifo-Algorithmus
  • 74
  • 11
  • 42
  • 144
einmalig 39,00
umsatzsteuerbefreit gem. § 4 Nr. 21 a bb) UStG
Online-Kurs Top AngebotTrusted Shop

Unsere Nutzer sagen:

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 22.06.2016:
    "top!! ;)"

  • Gute Bewertung für Operations Research 1

    Ein Kursnutzer am 05.12.2015:
    "Super erklärt !! "

NEU! Sichere dir jetzt die perfekte Prüfungsvorbereitung und spare 10% bei deiner Kursbuchung!

10% Coupon: lernen10

Zu den Online-Kursen