ZU DEN KURSEN!

Operations Research - Reduktion der Kostenmatrix

Kursangebot | Operations Research | Reduktion der Kostenmatrix

Operations Research

Reduktion der Kostenmatrix

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

Hier klicken zum Ausklappen

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

Hier klicken zum Ausklappen

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:

Transportproblem Beispiel Kostenmatrix


Zunächst wird das kleinste Element $c_{ij}$ der Matrix herangezogen. Dieses ist 120. Es wird nun das kleinste Element von allen anderen Elemente in der Matrix abgezogen (die Angebots- und Nachfragemengen sind davon nicht betroffen):

Reduktion der Kostenmatrix Beispiel


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:

Reduktion der Kostenmatrix Beispiel


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.