ZU DEN KURSEN!

Operations Research 2 - Einbeziehung von Stationen (Ausgangsmatrix)

Kursangebot | Operations Research 2 | Einbeziehung von Stationen (Ausgangsmatrix)

Operations Research 2

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:

Verfahren der sukzessiven Einbeziehung von Stationen Kostenmatrix

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

Reihenfolge            Kosten           
$1 - 2 - 1$ 72

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:

Nr.  Reihenfolge           Kosten 
1      $1 - 2 - 3 - 1$      110
2      $1 - 3 - 2 - 1$      $\infty$

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

Reihenfolge            Kosten           
$1 - 2 - 1$ 72
$1 - 2 - 3 - 1$    110

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

Nr. Reihenfolge                Kosten   
1      $1 - 2 - 3 - 4 - 1$  150
2      $1 - 2 - 4 - 3 - 1$ 140
3      $1 - 4 - 2 - 3 - 1$ 146

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

Reihenfolge                           Kosten           
$1 - 2 - 1$ 72
$1 - 2 - 3 - 1$    110
$1 - 2 - 4 - 3 - 1$    140

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

Nr.  Reihenfolge                         Kosten      
1      $1 - 2 - 4 - 3 - 5 - 1$             184
2      $1 - 2 - 4 - 5 - 3 - 1$           172
3      $1 - 2 - 5 - 4 - 3 - 1$           179
4      $1 - 5 - 2 - 4 - 3 - 1$           182

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

Methode

$1 - 2 - 4 - 5 - 3 - 1$         beste Reihenfolge (Verfahren der sukzessiven Einbeziehung von Stationen)


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

Methode

$K = 172 GE$.


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. 

Merke

Das Verfahren der sukzessiven Einbeziehung von Stationen liefert bessere Ergebnisse als das Verfahren des besten Nachfolgers.