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:

Nord-Westecken-Verfahren

WebinarTerminankündigung aus unserem Online-Kurs Technische Mechanik 3: Dynamik:
 Am 06.12.2016 (ab 16:00 Uhr) findet unser nächstes Webinar statt.
Gratis-Webinar (Dynamik) Gradlinige Bewegung eines Massenpunktes
- Dieses 60-minütige Gratis-Webinar behandelt die geradlinige Bewegung eines Massenpunktes.
[weitere Informationen] [Terminübersicht]

Das Nord-West-Ecken-Verfahren führt zu einer zulässigen Ausgangslösung für Transportprobleme. Hierbei wird die Mengenmatrix herangezogen. Das Ziel dieses Verfahrens ist es, die Angebotsmenge so auf die Warenhäuser zu verteilen, dass deren Nachfrage komplett abgedeckt wird. Die Kosten des Transports werden hierbei nicht berücksichtigt. Die Minimierung der Kosten erfolgt dann später bei den Optimierungsverfahren. Die Mengenmatrix für das Beispiel sieht wie folgt aus:

Nord-West-Ecken-Verfahren Mengenmatrix

Innerhalb der Matrix werden die Kosten der redzuierten Kostenmatrix (sofern eine Reduktion vorgenommen worden ist, sonst der Ausgangskostenmatrix) an die obere rechte Ecke geschrieben. Dies dient der Übersicht halber bei der späteren Summation der Kosten. Die Mengen die transportiert werden sind zunächst leer und werden mittels des folgenden Algorithmus bestimmt:

Methode

Algorithmus Nord-West-Ecken-Verfahren

Beginnend in der oberen linken Ecke (Nord-West-Ecke) schreitet das Verfahren entweder waagerecht oder senkrecht voran.

1. Ist $a_1 > b_1$, so wird $x_{11} = b_1$ gesetzt. Es geht dann waagerecht weiter. Ist $a_1 - x_{11} > b_2$, so wird $x_{12} = b_2$ gesetzt, sonst $a_1 - x_{11}$ und weiter mit Schritt 2, usw.

2. Ist $a_1 < b_1$, so wird $x_{11} = a_1$ gesetzt. Es geht dann senkrecht weiter. Ist $a_2 < b_1 - x_{11}$, so wird $x_{12} = a_2$ gesetzt, sonst $b_1 - x_{11}$ und weiter mit Schritt 1, usw.

3. Ist $a_1 = b_1$, so wird $x_{11} = a_1 = b_1$ gesetzt. Es geht dann waagerecht weiter und setzt $x_{12} = 0$. Es geht dann senkrecht weiter und legt $x_{22}$ gemäß Schritt 1-3 fest.

(Alternativ, man setzt $x_{11} = a_1 = b_1$. Es geht dann senkrecht weiter und setzt $x_{21} = 0$. Es geht dann senkrecht weiter und legt $x_{22}$ gemäß Schritt 1-3 fest.

4. Man verfahren solange mit Schritt 1-3 bis die Menge $x_{mn}$ festgelegt ist.

Nach Anwendung des Algorithmus für das Nord-West-Ecken-Verfahren ergibt sich das folgende Tableau mit zulässiger Ausgangslösung:

Nord-West-Ecken-Verfahren Ausgangslösung

Es wurde wie folgt vorgegangen:

Für $x_{11}$:

$a_1 > b_1$ (900 > 300). Schritt 1: $x_{11} = b_1 = 300$. Waagerecht weiter.

Für $x_{12}:

$a_1 - x_{11} > b_2$ (600 > 500). Schritt 1: $x_{12} = b_2 = 500$. Waagerecht weiter.

Für $x_{13}$:

$a_1 - x_{11} - x_{12} < b_3$ (100 < 400). Schritt 2: $x_{13} = a_1 - x_{11} - x_{12} = 100$. Senkrecht weiter.

Für $x_{23}$:

$a_2 > b_3 - x_{13}$ (800 > 300). Schritt 1: $x_{23} = b_3 - x_{12} = 300$. Waagerecht weiter.

Für $x_{24}$:

$a_2 - x_{23} < b_4$ (500 < 600). Schritt 2: $x_{24} = a_2 - x_{23} = 500$. Senkrecht weiter.

Für $x_{34}$:

$a_3 > b_4 - x_{24}$ (400 > 100). Schritt 1: $x_{34} = b_4 - x_{24} = 100$. Waagerecht weiter.

Für $x_{35}$:

$a_3 - x_{34} = b_5$ (300 = 300). Schritt 3: $x_{35} = a_3 - x_{34} = b_5 = 300$. ENDE

Es ist immer wichtig, dass nachdem eine Transportmenge von der Fabrik zum Warenhaus festgelegt worden ist, diese beim weiteren Vorgehen zu berücksichtigen, denn die Angebots- und Nachfragemenge verringert sich um diese festgelegte Transportmenge. So ist zum Beispiel bei der Festlegung von $x_{11} = 300$ Mengen für die weitere Betrachtung die Angebotsmenge $a_1$ um diese Menge zu reduzieren, da von Fabrik 1 diese 300 Mengen schon für den Nachfrageort 1 verplant sind. Genauso wird auch für den Nachfrageort 1 für die nachfolgenden Betrachtungen diese Menge von der Nachfragemenge $b_1$ abgezogen. Je mehr Mengen bereits festgelegt wurden, desto mehr Mengen müssen berücksichtigt werden. Zur besseren Übersicht kann man die Angebots- und Nachfragemenge auch an der Seite durchstreichen und die aktuelle Menge daneben schreiben:

Nord-West-Ecken-Verfahren Ausgangslösung

Es liegt nun eine zulässige Ausgangslösung vor. Die gesamten reduzierten Transportkosten für diese Ausgangslösung betragen:

$K_R = 300 \cdot 0 + 500 \cdot 10 + 100 \cdot 30 + 300 \cdot 0 + 500 \cdot 30 + 100 \cdot 20 + 300 \cdot 60 = 43.000$.

Hierbei handelt es sich um die Kosten der reduzierten Kostenmatrix. Diese können zum Vergleich der anderen Eröffnungsverfahren herangezogen werden. Für die anderen Eröffnungsverfahren (die nun folgen) müssen zum Vergleich der zulässigen Ausgangslösung dann aber ebenfalls die reduzierten Kosten herangezogen werden. Das Eröffnungsverfahren mit den geringsten Kosten besitzt die beste Ausgangslösung.

Die tatsächlichen Kosten (Ausgangskostenmatrix) für den obigen Transport betragen:

$K = 300 \cdot 140 + 500 \cdot 130 + 100 \cdot 170 + 300 \cdot 140 + 500 \cdot 180 + 100 \cdot 170 + 300 \cdot 190 = 330.000$.

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