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

MODI-Methode

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]

Ein weiteres Optimierungsverfahren neben der Stepping-Stone-Methode stellt die MODI-Methode dar. Auch hier wird zunächst eine zulässige Ausgangslösung benötigt, damit mittels MODI-Methode eine optimale Lösung ermittelt werden kann. In diesem Abschnitt soll anhand der Ausgangslösung des Matrixminimumverfahrens die Vorgehensweise der MODI-Methode veranschaulicht werden. 

Methode

MODI-Methode

1. Die Kosten $c_{ij}$ der belegten Felder der Ausgangslösung werden in eine neue Matrix $z_{ij}$-übernommen. Diese erhällt die Kopfzeile $v_j$ und die Vorspalte $u_i$.

2. Die Werte $v_j$ und $u_i$ werden wie folgt bestimmt durch $v_1 := 0$ und $u_i + v_j = c_{ij}$. Die Werte innerhalb der Matrix werden bestimmt durch $z_{ij} = u_i + v_j$.

3. Es wird nun eine neue Differenzmatrix $\triangle z_{ij}$ gebildet, indem die neue $z_{ij}$-Matrix von der alten Matrix abegzogen wird. Die Werte der Differenzmatrix werden also wie folgt bestimmt: $\triangle z_{ij} = c_{ij} - z_{ij}$.

4. Ergeben sich innerhalb der Differenzmatrix $\triangle z_{ij} < 0$, so ist eine Verbesserung der Ausgangslösung möglich. Bei mehreren negativen Werte, wird der betragsmäßig kleinste Wert gewählt. Es wird dann die Ausgangslösung betrachtet und der Zyklus von diesem Feld aus wie bei der Stepping-Stone-Methode (vorheriger Abschnitt) durchgeführt. Die minimale Menge auf dem Feld mit -1 wird dann mit dem betrachteten Feld getauscht. Alle weiteren Felder des Zyklus müssen dann mit dieser Menge verrechnet werden (Addition bei +1, Subtraktion bei -1).

5. Das Verfahren beginnt nun wieder bei Schritt 1. Es liegt die Optimallösung vor, wenn alle Elemente der Differenzmatrix positiv sind.

Die Vorgehensweise soll anhand der Ausgangslösung nach dem Matrixminimumverfahren durchgeführt werden:

MODI-Methode Ausgangslösung


1. Schritt:
Es werden zunächst die Kosten der belegten Felder in eine neuen Matrix übernommen:

MODI-Methode 1

2. Schritt: Der Wert $v_1 = 0$ wurde festgelegt. Es können nun die anderen Werte $v_j$ und $u_i$ bestimmt werden durch: $v_j + u_i = c_{ij}$. 

MODI-Methode 2

Es kann zunächst der Wert $u_1$ bestimmt werden, da $v_1 = 0$ und $z_{11} = 0$. Und mit $v_1 + u_1 = z_{11}$ ergibt sich dann, $u_1 = z_{11} - v_1$. Einsetzen der Werte ergibt $u_1 = 0 - 0 = 0$. Danach $v_2$ mit $v_2 = z_{12} - u_1 = 10 - 0 = 10$. Nach diesem Prinzip werden alle Werte durch Umstellen der Gleichung $u_i + v_j = z_{ij}$ bestimmt.

3. Schritt: Erstellung einer neuen Differenzmatrix, indem die Werte der obigen $z_{ij}$-Matrix von den Werten $c_{ij}$ der Ausgangsmatrix abgezogen werden:

MODI Methode 3

4. Schritt: Es ist ersichtlich, dass in der Differenzmatrix ein Wert kleiner als Null vorhanden ist. Es gilt $\triangle z_{21} = -20$. Es kann also eine Verbesserung der Ausgangslösung erfolgen. Dies geschieht, indem wie bei der Stepping-Stone-Methode ein Zyklus gesucht wird, beginnen bei dem Feld mit dem negativen Wert, also bei $x_{21}$. Dabei dürfen danach nur belegte Felder angesteuert werden und es muss immer ein Richtungswechsel (waagerecht, senkrecht, waagerecht usw.) stattfinden. Am Ende muss der Zyklus wieder am Startfeld enden:

MODI Methode Zyklus

Es wird dann eine Umverteilung der Mengen vorgenommen. Es wird die minimale Menge auf dem Feld mit -1 ausgewählt, hier $x_{22} = 100$. Diese wird mit dem Startfeld $x_{21}$ getauscht. Danach werden die Mengen auf dem Pfad angepasst. Für alle Mengen mit dem Zusatz +1 wird die Menge hinzuaddiert und für alle Mengen mit dem Zusatz -1 subtrahiert. Es ergibt sich dann die neue Basislösung:

MODI Methode neue Basislösung

Danach werden die Schritte 1-4 wiederholt durchgeführt. Es wird im Folgenden nur die Differenzmatrix angegeben:

MODI-Methode 4

Da keine negativen Werte mehr in der Differenzmatrix vorhanden sind, ist die oben gegeben Lösung optimal. 

Die gesamten minimalen Transportkosten ergeben sich zu:

$K = 200 \cdot 140 + 100 \cdot 150 + 100 \cdot 130 + 400 \cdot 120 + 400 \cdot 140 + 600 \cdot 150 + 300 \cdot 130 = 289.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