Kursangebot | Operations Research 1 | MODI-Methode

Operations Research 1

MODI-Methode

Definition der MODI-Methode

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.

Vorgehen bei der MODI-Methode

In diesem Abschnitt soll anhand der Ausgangslösung des Matrixminimumverfahrens die Vorgehensweise der MODI-Methode veranschaulicht werden. 

Methode

Hier klicken zum Ausklappen

MODI-Methode

1. Die Kosten der belegten Felder der Ausgangslösung werden in eine neue Matrix -übernommen. Diese erhällt die Kopfzeile und die Vorspalte .

2. Die Werte und werden wie folgt bestimmt durch und . Die Werte innerhalb der Matrix werden bestimmt durch .

3. Es wird nun eine neue Differenzmatrix gebildet, indem die neue -Matrix von der alten Matrix abegzogen wird. Die Werte der Differenzmatrix werden also wie folgt bestimmt: .

4. Ergeben sich innerhalb der Differenzmatrix , 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.

Beispiel für die MODI-Methode

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


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

2. Schritt: Der Wert wurde festgelegt. Es können nun die anderen Werte und bestimmt werden durch: . 

Es kann zunächst der Wert bestimmt werden, da und . Und mit ergibt sich dann, . Einsetzen der Werte ergibt . Danach mit . Nach diesem Prinzip werden alle Werte durch Umstellen der Gleichung bestimmt.

3. Schritt: Erstellung einer neuen Differenzmatrix, indem die Werte der obigen -Matrix von den Werten der Ausgangsmatrix abgezogen werden:

4. Schritt: Es ist ersichtlich, dass in der Differenzmatrix ein Wert kleiner als Null vorhanden ist. Es gilt . 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 . 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:

Es wird dann eine Umverteilung der Mengen vorgenommen. Es wird die minimale Menge auf dem Feld mit -1 ausgewählt, hier . Diese wird mit dem Startfeld 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:

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

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

Lösung mit MODI-Methode

Die gesamten minimalen Transportkosten ergeben sich zu:

.

Lerne erfolgreich mit unseren Online-Kursen

This browser does not support the video element.

Sichere dir jetzt das kompakte Wissen mit unserem Vollzugriff Komplettpaket für Ingenieurstudenten


  • Alle Lernmaterialien komplett mit 494 Videos, 5120 interaktiven Übungsaufgaben und 3108 Lerntexten
  • Günstiger als bei Einzelbuchung nur 14,90 € mtl. bei 1 Monaten Mindestvertragslaufzeit
Jetzt entdecken

This browser does not support the video element.

Einzelkurs: Operations Research 1


  • Die besten Lernmaterialien: 77 Texte, 184 Abbildungen, 13 Videos und 42 Übungsaufgaben.
Jetzt entdecken