Bellman-Verfahren

Michel,

dann versuch' ich das mal mit den einfachen Antworten - Bellmann ist ja noch das einfachste Verfahren der kürzeste-Wege-Algorithmen:

1. Knoten topologisch sortieren
2. Lösungsschema wie in 852 KE1 Seite 50 aufmalen (j, dj, qj)
3. Alle Knoten, die vor dem angegebenen Startknoten liegen, kannst du gar nicht erreichen (falls nicht bei 1 gestartet werden soll...). Für die kannst du also gleich dj=unendlich, qj = 0 eintragen.
4. Für den Startknoten a schreibst du dj=0, qj=a (Ersetzen durch die richtige Nummer natürlich) rein.
5. Jetzt geht's los mit der eigentlichen Arbeit. Für alle Knoten ab der Nummer (a+1) - ich nennen den aktuellen Knoten mal j) bis zum Ende machst du folgendes:
a) Welche Vorgänger (also Pfeile, die in j rein gehen) hat der Knoten j? (wegen der topologischen Sortierung müssen diese eine kleinere Nummer als j haben)
b) Für jeden Vorgänger (nennen wir ihn mal i) addierst du das, was für den Knoten i in deinem Lösungsschema unter dj steht, und die Bewertung des Pfeils von i nach j (cij) zusammen. Die minimale dieser Summen (di + cij) schreibst du unter die Spalte dj in der Zeile j, also dem Knoten, den du gerade untersuchst. Die Nummer des Vorgängerknotens, den du gewählt hast, schreibst du unter qj auf. (Ich persönlich komme bei diesen Algorithmen schnell durcheinander, wenn einige Werte in der Lösungstabelle und andere im Graphen stehen, insofern notiere ich mir das dj zusätzlich am Knoten selbst.)
6. Wenn du bei der letzten Knotennummer angekommen bist, bist du fertig. 😉

Eigentlich ist das noch viel einfacher als es bei meiner Beschreibung klingt - aber Lösen durch Draufschauen lässt sich so schlecht in Text fassen...

Ich schreib' noch mal zur Verdeutlichung die Schritte für die ersten vier Knoten des Beispiels auf Seite 50 (s. o.) auf, den Rest kannst du dann sicher selbst:

Der Startknoten a ist der Knoten mit der Nummer 2 (das wird in der Aufgabe angegeben - gesucht sind die kürzesten Wege vom Knoten 2 zu allen anderen Knoten). Den Knoten 1 kannst du von 2 aus nicht erreichen, insofern gilt hier dj=unendlich und qj=0 (aus meiner Beschreibung oben).
Für den Startknoten a gilt (ebenfalls s. o.): dj =0 und qj = a, also 2.
Jetzt zum Knoten j = 3. Welche Vorgänger hat der Knoten Nr. 3? Das sind die Knoten 1 und 2. Also berechnest du für diese beiden Fälle die Summe aus di und cij:
a) für Vorgänger i=1: unendlich + 0 = unendlich
b) für Vorgänger i=2: 0 + 4 = 4.
4 ist kleiner als unendlich, also trägst du in die Zeile j=3 der Lösungstabelle dj=4 (die kleinste Summe) und qj = 2 (die Nummer des Vorgängers) ein.
Jetzt weiter mit Knoten Nummer 4 (einfach immer schön der Reihe nach). Vorgänger sind die Knoten 2 und 3. Als Summen ergeben sich
a) für den Vorgänger 2: 0 + 2 = 2
b) für den Vorgänger 3: 4 + 5 = 9 (die vier hast du im vorherigen Schritt ermittelt!)
Der Weg über den Vorgängerknoten 2 ist eindeutig kürzer, also notierst du in der Zeile j=4 des Lösungsschemas dj=2 und qj=2.

Und, verstanden? :auweia:
Gruß,
Sabine.

Dankeschön, jetzt hab ich's auch verstanden.

Fand das nur unmöglich erklärt im Skript (wie einiges andere auch).
Mit anderen Sachen hatte ich viel weniger Probleme (Tripel-Alg. oder Kilter), da diese viel ausführlicher erläutert werden.

Naja, danke nochmal!

In diesem Zusammenhang habe ich allerdings auch eine Frage! In Kurs 852 Übungsaufgabe 3.3 steige ich nicht hinter die Lösung. Das Aufstellen der Formel und der Bellmann ist mir klar, aber vielleicht kann mir da einmal jemand nahe bringen!

Danke schon einmal!

Ja, die fand' ich auch verwirrend. So halbwegs hab' ich das jetzt verstanden - obwohl ich nie im Leben selbst anhand der Aufgabenstellung darauf gekommen wäre, wie man dieses Problem durch eine Graphen lösen kann...

Ein Pfeil von i nach j bedeutet, dass die zu Beginn des Jahres i angeschaffte Maschine zu Beginn des Jahres j verkauft und durch einen neue ersetzt wird. Die Bewertung des Pfeils ergibt sich nach der in der Musterlösung angegebenen Formel als
Kosten der Anschaffung im Jahr i - Verkaufswert der alten Maschine + Betriebskostensumme für die Jahre i bis (j-1).
Gesucht ist nun der kürzeste Weg vom Jahr 1 (Knoten 1) zum Ende des Jahres 5 (Knoten 6). Alle Pfeile, die in diesem kürzesten Weg enthalten sind, bedeuten, dass zu Beginn von j neu investiert wurde.

Für den kürzesten Weg <1,3,6> sind die Pfeile <1,3> sowie <3,6> enthalten. D. h., man schafft die Maschine zu Beginn des ersten Jahres an, betreibt diese dann während des ersten und zweiten Jahres und schafft zu Beginn des dritten Jahres (Knoten 3) eine neue an. Die wird dann wieder am Ende des fünften Jahres (Knoten 6) verkauft.

Gruß,
Sabine.

P.S.: Jetzt packe ich mal meinen Koffer und mache mich auf den Weg nach Düsseldorf, insofern hört ihr vor der Klausur nichts mehr von mir.
Viel Erfolg alle zusammen!

skdo schrieb:

Ja, die fand' ich auch verwirrend. So halbwegs hab' ich das jetzt verstanden - obwohl ich nie im Leben selbst anhand der Aufgabenstellung darauf gekommen wäre, wie man dieses Problem durch eine Graphen lösen kann...

Ein Pfeil von i nach j bedeutet, dass die zu Beginn des Jahres i angeschaffte Maschine zu Beginn des Jahres j verkauft und durch einen neue ersetzt wird. Die Bewertung des Pfeils ergibt sich nach der in der Musterlösung angegebenen Formel als
Kosten der Anschaffung im Jahr i - Verkaufswert der alten Maschine + Betriebskostensumme für die Jahre i bis (j-1).
Gesucht ist nun der kürzeste Weg vom Jahr 1 (Knoten 1) zum Ende des Jahres 5 (Knoten 6). Alle Pfeile, die in diesem kürzesten Weg enthalten sind, bedeuten, dass zu Beginn von j neu investiert wurde.

Für den kürzesten Weg <1,3,6> sind die Pfeile <1,3> sowie <3,6> enthalten. D. h., man schafft die Maschine zu Beginn des ersten Jahres an, betreibt diese dann während des ersten und zweiten Jahres und schafft zu Beginn des dritten Jahres (Knoten 3) eine neue an. Die wird dann wieder am Ende des fünften Jahres (Knoten 6) verkauft.

Gruß,
Sabine.

P.S.: Jetzt packe ich mal meinen Koffer und mache mich auf den Weg nach Düsseldorf, insofern hört ihr vor der Klausur nichts mehr von mir.
Viel Erfolg alle zusammen!

Zum Vergrößern anklicken....

Soweit so gut, aber ich komme irgendwie nicht auf die Gewichtung der Pfeile. Bspw. für den Pfeil <1,4): 105-30+30=105 in der Lösung steht aber 100! 105 ist der Anschaffungswert im Jahr 4, 30 ist der Verkaufswert der Anlage im Jahre Ende 3 und insgesamt sind doch 30 Betriebskostenstunden aufgelaufen! Grrr

Falls es noch interessiert (kam ja leider nicht dran... das hätte ich gekonnt...):

i = 1, j = 4; mit Einsetzen in die Formel in der Musterlösung:
c14 = B1 - S3 + (C1 + C2 + C3)
c14 = 100 - 30 + (5 + 10 + 15) = 100 - 30 + 30 = 100

Sieht für mich so aus, als ob du nur ganz am Anfang statt B1 B4 genommen hättest?

skdo schrieb:

Falls es noch interessiert (kam ja leider nicht dran... das hätte ich gekonnt...):

i = 1, j = 4; mit Einsetzen in die Formel in der Musterlösung:
c14 = B1 - S3 + (C1 + C2 + C3)
c14 = 100 - 30 + (5 + 10 + 15) = 100 - 30 + 30 = 100

Sieht für mich so aus, als ob du nur ganz am Anfang statt B1 B4 genommen hättest?

Zum Vergrößern anklicken....

Man was bin ich benagelt! Ich habe es wohl leider aus der falschen Brille gesehen. Allerdings ist mir der Praxisbezug noch ein wenig fremd. c14 bedeutet ja, was passiert mit einer Maschine angeschafft in t=1, wenn diese in t=4 ersetzt wird. Die Wahl des Bi kann dann meiner Meinung nach nicht der Wiederbeschaffungswert in t=1 sein, sondern in t=4! Weil zu diesem Zeitpunkt möchte ich schließlich ersetzen. Wie dem auch sei, danke Dir!

HeikoEH schrieb:

Man was bin ich benagelt! Ich habe es wohl leider aus der falschen Brille gesehen. Allerdings ist mir der Praxisbezug noch ein wenig fremd. c14 bedeutet ja, was passiert mit einer Maschine angeschafft in t=1, wenn diese in t=4 ersetzt wird. Die Wahl des Bi kann dann meiner Meinung nach nicht der Wiederbeschaffungswert in t=1 sein, sondern in t=4! Weil zu diesem Zeitpunkt möchte ich schließlich ersetzen. Wie dem auch sei, danke Dir!

Zum Vergrößern anklicken....

....Ok! Ein Gegenargument gegen diese Sichtweise wäre natürlich, daß in der Aufgabe nicht von WBZ sondern AK´s!

Viele Grüße
Heiko

Frage von mir zum Beispiel 3.2 auf Seite 49 KE 1 852

Im Absatz 2 heißt es lapidar: "Da Knoten 1 vom Startknoten a=2[/COLOR] aus ..."
Ich habe jetzt 1 Stunde lang versucht in der KE und im Netz herauszufinden, wie ich auf "a=2" komme. Ich habe das Gefühl, dies muss in der Aufgabenstellung vorgegeben sein. Könnt ihr das bestätigen?

Auch in Übungsaufgabe 3.2 auf Seite 46 selbiger KE soll in a) der Startknoten bestimmt werden. Ich hab folgende Denkkette: qj soll ein Wegeknoten (und somit Vorgänger auf dem kürzesten Weg von a nach j sein. Wenn a=3 und j=3, dann ist doch 3 kein Vorgänger von 3.
Und da ich das nicht verstehe, verstehe ich auch nciht, warum man das aus der Tabelle ablesen kann...

Für Denkanstöße oder auch grobe Schubser, bin ich dankbar.

1. Der Startknoten wird in der Aufgabenstellung vorgegeben.
2. Alles Definitionsfrage - der Algorithmus ist halt so definiert, dass man den Startknoten a dran erkennt, dass qj = j gilt. Bei anderen Verfahren wird manchmal gar kein qj für den Startknoten angegeben.
Beide Informationen entnehme ich der Beschreibung des Algorithmus auf Seite 48.