ZU DEN KURSEN!

Operations Research 2 - Beispiel: Vollständige Enumeration (Reduktion der Matrix)

Kursangebot | Operations Research 2 | Beispiel: Vollständige Enumeration (Reduktion der Matrix)

Operations Research 2

Beispiel: Vollständige Enumeration (Reduktion der Matrix)

Anwendungsbeispiel: Vollständige Enumeration beim TSP

Vollständige Enumeration

Die obige Matrix stellt eine Maschine dar mit den Produkten $i = 1, 2, 3, 4, 5$. Die Kosten $c_{ij}$ sind gegeben für die Umrüstung der Maschine von z.B. Produkt 3 auf Produkt 1 mit 32 Geldeinheiten (GE). Gesucht wird diejenige Reihenfolge mit minimalen Umrüstungskosten.

Da hier die Matrix gegeben ist, muss kein Graph gezeichnet werden. Es wird zunächst die obige Matrix angepasst, indem alle unerwünschten Verknüpfungen bzw. nicht vorhanden Verknüpfungen (Hauptdiagonale) und alle deutlich abweichenden Kosten (hier: 180) mit $c_{ij} = \infty$ belegt werden:

Vollständige Enumeration


Es ist außerdem sinnvoll eine Matrixreduktion vorzunehmen, bevor mit der vollständigen Enumeration begonnen werden kann. Hierzu wird das kleinste Element einer Zeile von allen anderen Elementen dieser Zeile subrahiert:

Vollständige Enumeration Matrixreduktion

In der linken Zeile sind in den Klammern die kleinsten Elemente der Zeile aufgeführt (der Übersicht halber). Die Summe aller kleinsten Elemente ergibt dann die Reduktionskonstante:

Methode

$k_R = 162$     Reduktionskonstante


Es kann nun mit dem Verfahren der vollständigen Enumeration begonnen werden (siehe folgenden Abschnitt).