Einbeziehung von Stationen (Ausgangsmatrix)

Das Verfahren der sukzessiven Einbeziehung von Stationen wird anhand der Ausgangsmatrix dargestellt. Es kann aber ebenfalls die reduzierte Kostenmatrix herangezogen werden, es resultiert dasselbe Ergebnis. Hierzu wird die folgende Matrix mit den Umrüstungskosten $c_{ij}$ und den Produkten $i = 1,...,5$ betrachtet:

Es wird nun zunächst ein beliebiger Anfangszyklus bestimmt und die Kosten für diesen Zyklus mitangegeben:

Danach wird ein weiterer beliebiger Knoten so hinzugefügt, dass die Kosten minimiert werden. Es wird der Knoten 3 hinzugefügt. Dabei existieren zwei Möglichkeiten den Knoten 3 einzufügen:

Es wird die 1. Möglichkeit ausgewählt, weil diese geringere Kosten aufweist:

Es wird der nächsten Knoten 4 betrachtet. Hier existieren nun 3 mögliche Reihenfolgen:

Die 2. Möglichkeit mit den Kosten 140 wird ausgewählt:

Das Hinzufügen des Knoten 5 stellt den letzten Schritt dar. Die Anzahl der möglichen Reihenfolgen erhöht sich auf 4:

Die beste Reihenfolge nach dem Verfahren der sukzessiven Einbeziehung von Stationen ist anhand der Ausgangsmatrix:

Die Gesamtkosten für die Umrüstung liegen bei:

Dieses Ergebnis ist auch gleichzeitig die optimale Reihenfolge. Das Verfahren der sukzessiven Einbeziehung von Stationen führt dabei nicht immer zur optimalen Reihenfolge, sondern führt häufig zu einer zufriedenstellenden Lösung. In diesem Fall ist aber mittels dieses Verfahrens die optimale Lösung ermittelt worden. Da normalerweise (bei Anwendung dieses Verfahrens) die optimale Lösung nicht gegeben ist, weil zu viele Knoten betrachtet werden müssen, kann man natürlich auch nicht wissen, dass es sich bei der gefundenen Lösung um eine optimale Lösung handelt.