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)

Beispiel: Vollständige Enumeration beim TSP

Die obige Matrix stellt eine Maschine dar mit den Produkten . Die Kosten 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 belegt werden:


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:

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

    Reduktionskonstante


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

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 501 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 2


  • Die besten Lernmaterialien: 60 Texte, 60 Abbildungen, 13 Videos und 25 Übungsaufgaben.
Jetzt entdecken