Gegeben sei die Matrix mit den Umrüstungskosten
Man geht nun wie folgt vor. Beginnend bei dem Produkt 1 wird nun das Produkt gesucht, welches als nächstes umgerüstet wird. Dabei werden die kleinsten Umrüstungskosten gewählt. Das Produkt 3 mit 34 GE besitzt die geringsten Umrüstungskosten:
Danach wird von Produkt 2 ausgehen derjenige Nachfolgerknoten mit den geringsten Umrüstkosten gewählt usw.
Es ergibt sich die folgende Reihenfolge:
Die Kosten sind demnach:
Methode
Im Abschnitt Vollständige Enumeration lag das Optimum bei 172 GE. Es ist also eine Abweichung von 7 GE zum Optimum gegeben.
Weitere interessante Inhalte zum Thema
-
Dijkstra-Algorithmus
Vielleicht ist für Sie auch das Thema Dijkstra-Algorithmus (Greedy-Algorithmus) aus unserem Online-Kurs Operations Research 1 interessant.
-
Beträge
Vielleicht ist für Sie auch das Thema Beträge (Grundlagen: Mengenlehre und reelle Zahlen) aus unserem Online-Kurs Analysis und Lineare Algebra interessant.