Die Reduktion der Kostenmatrix ist sinnvoll für
- das Nord-West-Ecken-Verfahren (Eröffnungsverfahren),
- die Rangfolgeverfahren (Eröffnungsverfahren),
- die Stepping-Stone-Methode (Optimierungsverfahen).
- die MODI-Methode (Optimierungsverfahren).
Merke
Die Matrixreduktion muss aber nicht unbedingt angewendet werden, d.h. man kann alle Verfahren auch ohne vorherige Matrixreduktion anwenden. Für das Vogelsche Approximationsverfahren (Eröffungsverfahren) sollte keine reduzierte Kostenmatrix verwendet werden.
Methode
Die Reduktion der Kostenmatrix erfolgt in mehreren Schritten:
- Das kleinste Element der Kostenmatrix wird von allen anderen Elementen subtrahiert.
- Das kleinste Elemente einer Spalte der Kostenmatrix wird von allen anderen Elemente dieser Spalte subtrahiert.
- Wenn nicht mindendestens ein Element in jeder Zeile Null wird, dann wird das kleinste Element dieser Zeile von allen anderen Elementen dieser Zeile subtrahiert. Am Ende muss also jede Zeile mindestens ein Element mit dem Wert Null beinhalten.
Es wird nun die Kostenmatrix herangezogen und die Reduktion dieser vorgenommen:
Zunächst wird das kleinste Element
Als nächstes wird das kleinste Element der Spalten (außer die Spalte mit Null) betrachtet und dieses von den anderen Elementen der jeweiligen Spalte abgezogen:
Da bereits in allen Zeilen der Wert Null auftaucht, ist die Reduktion der Kostenmatrix abgeschlossen. Für die folgenden Eröffnungsverfahren wird diese reduzierte Kostenmatrix herangezogen (außer für das Vogelsche Approximationsverfahren). Die Reduktion der Kostenmatrix ist kein muss, allerdings erleichert es die spätere Berechnung der Kosten.
Weitere interessante Inhalte zum Thema
-
Oxidation und Reduktion, Oxidations- und Reduktionsmittel
Vielleicht ist für Sie auch das Thema Oxidation und Reduktion, Oxidations- und Reduktionsmittel (Donator-Akzeptor-Prinzip) aus unserem Online-Kurs Anorganische Chemie für Ingenieure interessant.
-
Einbeziehung von Stationen (Ausgangsmatrix)
Vielleicht ist für Sie auch das Thema Einbeziehung von Stationen (Ausgangsmatrix) (Kombinatorische Optimierung) aus unserem Online-Kurs Operations Research 2 interessant.
