Gegeben sei die Matrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1,...,5$.
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:
$1 - 3$
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
$K = 34 + 38 + 32 + 39 + 36 = 179$.
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.
