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 > Rangfolgeverfahren:

Zeilenfolgeverfahren

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 soll das Zeilenfolgeverfahren aufgezeigt werden. Das Zeilenfolgeverfahren ist ein Eröffnungsverfahren für Transportprobleme und hat eine zulässige Ausgangslösung zum Ergebnis. Die Vorgehensweise sei im Folgenden beschrieben:

Methode

Zeilenfolgeverfahren

Zu Beginn des Verfahrens sind alle Spalten unmarkiert. Die Iteration erfolgt von $i = 1, .., n$ ($i$ = Zeile).

1. Es wird das kleinste Element der Zeile $i$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Spaltenindex $j$ gewählt.

2. 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 $b_j = 0$, wird die Spalte $j$ markiert und die Elemente dieser Spalte für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und derselben Zeile $i$.

Ist danach $b_j \neq 0$, dann geht es weiter mit Schritt 1 und Zeile $i + 1$.

Die Vorgehensweise bei dem Zeilenfolgeverfahren ist analog zum Spaltenfolgeverfahren, nur das die Spalten durch Zeilen ersetzt werden. Es wird wieder die folgende Mengenmatrix betrachtet:

Zeilenfolgeverfahren Mengenmatrix

Die Mengenmatrix beinhaltet zu Beginn noch keine Mengenbelegung. Die Kosten der reduzierten Kostenmatrix (sofern eine Reduktion vorgenommen worden ist, sonst die Kosten der Ausgangskostenmatrix) werden die obere rechte Ecke geschrieben. Nach Anwendung des Zeilenfolgeverfahrens ergibt sich die folgenden Mengenbelegung:

Zeilenfolgeverfahren Mengenmatrix zulässige Ausgangslösung

Die Vorgehensweise zur Erreichung der obigen Mengenbelegung ist wie folgt:

Wichtig

Hinweis: Die roten Zahlen links unten stellen die Reihenfolge der Mengenbelegung dar. Die Sternchen an den Warenhäusern $j$ sind die Spaltenmarkierungen die im Laufe des Algorithmus durchgeführt worden sind.

1. Zeile:

Zunächst wird die Spalte $j = 1$ betrachtet. Hier wird das kleinste Element ausgewählt $c_{11} = 0$. Da auch $c_{14} = 0$ als kleinsten Element auftaucht wird hier das mit dem kleinsten Spaltenindex $j =1$ gewählt. Es wird dann $x_{11} = min \{900; 300 \} = 300$ gesetzt. Die neue Angebotsmenge ist dann $a_1 = 900 - 300 = 600$ und die neue Nachfragemenge $b_1 = 0$. Da $b_1 = 0$ wird die Spalte $j = 1$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 1. Zeile und sucht das kleinste Element. 

Das kleinste Element ist $c_{14} = 0$. Man setzt $x_{14} =  min \{600; 600 \} = 600$. Die neue Angebotsmenge ist dann $a_1 = 600 - 600 = 0$ und die neue Nachfragemenge $b_4 = 0$. Da $b_4 = 0$ wird die Spalte $j = 4$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 1. Zeile und sucht das kleinste Element. 

Das kleinste Element ist $c_{12} = c_{15} = 10$. Man wählt das Element mit dem kleinsten Spaltenindex $j = 2$. Man setzt $x_{12} =  min \{0; 500 \} = 0$. Die neue Angebotsmenge ist dann $a_1 = 0$ und die neue Nachfragemenge $b_2 = 500 - 0 = 500$. Da $b_2 \neq 0$ geht man als nächstes zur Zeile $i + 1 = 2$ über.

2. Zeile:

(Nicht vergessen, die markierten Spalten $j = 1$ und $j = 4$ dürfen nicht weiter berücksichtigt werden)

Es wird nun die Zeile $i = 2$ betrachtet. Es wird das kleinste Element ausgewählt $c_{23} = 0$. Die Menge wird $x_{23} = min \{800; 400 \} = 400$ gesetzt. Die neue Angebotsmenge ist dann $a_2 = 800 - 400 = 400$ und die neue Nachfragemenge $b_3 = 0$. Da $b_3 = 0$ wird die Spalte $j = 3$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 2. Zeile und sucht das kleinste Element. 

(Nicht vergessen, die markierten Spalten $j = 1$, $j = 3$ und  $j = 4$ dürfen nicht weiter berücksichtigt werden)

Das kleinste Element ist $c_{25} = 10$. Man setzt $x_{25} =  min \{400; 300 \} = 300$. Die neue Angebotsmenge ist dann $a_2 = 400 - 300 = 100$ und die neue Nachfragemenge $b_5 = 0$. Da $b_5 = 0$ wird die Spalte $j = 5$ markiert. Die Elemente dieser Spalte dürfen nicht weiter berücksichtigt werden. Man verbleibt bei der 2. Zeile und sucht das kleinste Element. 

(Nicht vergessen, die markierten Spalten $j = 1$$j = 3$$j = 4$ und $j = 5$ dürfen nicht weiter berücksichtigt werden)

Das kleinste Element ist $c_{22} = 40$. (Alle anderen Element dürfen nicht berücksichtigt werden). Man setzt $x_{22} =  min \{100; 500 \} = 100$. Die neue Angebotsmenge ist dann $a_2 = 0$ und die neue Nachfragemenge $b_2 = 500 - 100 = 400$. Da $b_2 \neq 0$ geht man als nächstes zur Zeile $i + 1 = 3$ über.

3. Zeile:

(Nicht vergessen, die markierten Spalten $j = 1$$j = 3$$j = 4$ und $j = 5$ dürfen nicht weiter berücksichtigt werden)

Es wird die Zeile $i = 3$ betrachtet. Es wird das kleinste Element ausgewählt $c_{32} = 0$ (ist das einzige Element, welches ausgewählt werden darf). Die Menge wird $x_{32} = min \{400; 400 \} = 400$ gesetzt. Die neue Angebotsmenge ist dann $a_3 = 0$ und die neue Nachfragemenge $b_2 = 0$. 

Das Verfahren endet hier, da alle Zeilen abgearbeitet worden sind und $m + n - 1 = 3 + 5 - 1 = 7$-Basisvariablen bestimmt worden sind. 

Die gesamten reduzierten Kosten ergeben sich zu:

$K_R = 300 \cdot 0 + 0 \cdot 10 + 100 \cdot 40 + 400 \cdot 0 + 400 \cdot 0 + 600 \cdot 30 + 300 \cdot 0 = 4.000$.

Merke

Im Gegensatz zum Nord-West-Ecken-Verfahren ist diese zulässige Ausgangslösung um einiges besser, da die reduzierten Kosten $K_R$ geringer sind. 

Die tatsächlichen Transportkosten betragen:

$K = 300 \cdot 140 + 0 \cdot 130 + 100 \cdot 160 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 291.000$.

Merke

Das Spaltenfolgeverfahren und das Zeilenfolgeverfahren führen nicht immer zu den selben Transportkosten!

Alternative Vorgehensweise

Es existiert noch eine alternative Vorgehensweise für die Durchführung des Zeilenfolgeverfahrens. Dies soll im folgenden aufgezeigt werden.

Methode

Zeilenfolgeverfahren (alternative Vorgehensweise)

Zu Beginn des Verfahrens sind alle Spalten unmarkiert. Die Iteration erfolgt von $i = 1, .., n$ ($i$ = Zeile).

1. Es wird das kleinste Element der Zeile $i$ ausgewählt. Bei mehreren gleich kleinen Elemente, wird das Element mit dem kleinsten Spaltenindex $j$ gewählt.

2. 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 $b_j = 0$, wird die Spalte $j$ markiert und die Elemente dieser Spalte für die weiteren Betrachtungen nicht weiter berücksichtigt. Es geht dann weiter mit Schritt 1 und der nächsten Zeile $i + 1$.

Nachdem alle Zeilen betrachtet worden sind, fängt das Verfahren wieder bei der 1. Zeile an. Dies wird solange durchgeführt, bis alle $m + n - 1$-Basisvariablen gefunden sind. 

Bei dieser Vorgehensweise verbleibt man nicht in der Zeile, wenn $b_j = 0$, sondern schreitet immer von einer Zeile zur nächsten. Das ganze wiederholt sich solange, bis die $m + n -1$-Basisvariablen gefunden sind. Nach dieser Vorgehensweise ergibt sich die folgenden Mengenbelegung:

Zeilenfolgeverfahren alternative Vorgehensweise

Bei dieser Vorgehensweise sind die gesamten reduzierten Kosten:

$K_R = 300 \cdot 0 + 0 \cdot 10 + 100 \cdot 40 + 400 \cdot 0 + 400 \cdot 0 + 600 \cdot 0 + 300 \cdot 0 = 4.000$

Die tatsächlichen Transportkosten betragen:

$K = 300 \cdot 140 + 0 \cdot 130 + 100 \cdot 160 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 291.000$.

Merke

Die beiden Zeilenfolgeverfahren führen nicht immer zu den selben Transportkosten!

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