Hilfe zur Klausuraufgabe Nachbesprechung Klausur Sep 2008 (SS 2008)

Ottokarotto · 1 März 2013

In loser Reihenfolge:
Aufgabe 1)
a) Verfahren wäre Dijkstra, Grund: "kürzeste-Wege"
b) Kosten von 78
c) Minimalgerüst berücksichtigt nicht, daß die jeweiligen Strecken vom Ausgangspunkt zum Endpunkt addiert werden. Ein willkürlich gewähltes Minimalgerüst ( Kantenwerte von 29 ) hätte aber Kosten von 89.

Aufgabe 3)
S1 und S5 mit Gesamtlieferkosten von 100 ( 50 + 10 + 15 + 25 )

Aufgabe 4)
Gesamtkosten von 3924
als 4*90 + 8 *36 + 66 * 2 + 66* 4 + 24 * 10 + 18 * 8 + 84 * 16 + 96 * 12

uried · 1 März 2013

1a)
Ford wäre auch möglich, bei Bellmann bin ich mir nicht so sicher, da Bellmann für zyklenfreie Netzwerke angewendet wird. Das Netzwerk hat m.E. Zyklen.

b) ok, kommt auch bei Ford raus
c) Ergänzung: Beim Minimalgerüst sind alle Knoten über die kostengünstigsten Kanten erreichbar, sodass die Gesamtlänge aller Kanten minimal ist. Es berücksichtigt nicht, wie Ottokarotto schon schrieb, die kostengünstigsten (=kürzesten) Wege vom Ausgangsknoten Z zu jeden anderen Knoten. Nicht jeder kürzeste Weg von Z zu jedem anderen Knoten verläuft auf einem Minimalgerüst.

Aufgabe 3)
Du hast also auch die fixen Kosten bei Ermittlung der Diff. nyi unberücksichtigt gelassen? Ich war mir da nicht so sicher. Steht das irgendwo, dass man es so macht?
100 habe ich auch: S1 versorgt K1 mit 15, K2 mit 20 und K5 mit 15, Kfix=10 und S5 versorgt K mit 5 und K4 mit 10, Kfix = 25.

Aufgabe 6:
W
W
F (deterministisch oder probabilistisch; S.67)
F
W

uried · 1 März 2013

Aufgabe 2:

a) und b)
Pfeil, red. Kosten, Zustand, K
<Q,1>, 3, L-,9
<Q,2>,-1,K+,1
<1,3>,1,L,0
<1,4>,-1,K+,4
<2,1>,8,L,0
<2,3>,-2,K,0
<2,4>,5,L-,10
<3,5>,3,L+,1
<3,6>,5,L-,10
<4,3>,1,L,0
<4,5>,-1,K+,2
<4,6>,0,B-,1
<5,S>,0,B,0
<6,5>,12,L-,24
<6,S>,4,L-,16
<S,Q>,5,L,0

uried · 1 März 2013

Aufgabe 5:
eine vielseits geliebte Aufgabe mit Färbungsproblem und Tabu Search-Verfahren

Mein Kommentar dazu:
a) war relativ leicht darzustellen, ok
b) Hätte man nicht deutlich schreiben können: Färbe Knoten I mit "Mo", II mit "Die" usw.
Nach langem Überlegen habe ich auch die Aufgabe verstanden.
i) Anzahl der Kanten ,die Knoten gleicher Farbe verbinden (kommt häufig dran); gesucht ist Minimum
ii) Nachbarschaftsbegriff: Verschieben einer Farbe in die Nachbarschaftsmenge
in FR sind 2 Knoten (V und VI), also wird 1a) V nach DO und dann 1b) nach MO verschoben und dann 1c) VI nach DO und dann 1d) nach MO - also insgesamt 4 Nachbarschaftslösungen (Funktionswerte: 1a=1, 1b=1, 1c=0, 1d=0)
iii) hier gibts verschiedene Varianten, spare ich mir an dieser Stelle

Die vollständige Lösung gibst unter B0301 in der Aufgabensammlung. Habe ich leider erst entdeckt, als ich bei b iii) war und ich nach geeigneten from-Attr. gesucht habe. Darauf wird in der Lösung nicht eingegangen.

Ottokarotto · 3 März 2013

zu 2)

Sysiphus läßt grüßen..... :panik:

... gibt's da Eselbrücken?
..wenn man das Skript nicht mitnehmen dürfte, wäre ich bei so einer Aufgabe hoffnungslos aufgeschmissen!

MIJM · 3 März 2013

Hallo Leute,

Sysiphus stimmt.
Muss einen Knick in der Optik haben, denn immer beim ersten Rechnen vertue ich mich an irgendwelchen Stellen, B, B- oder B+ und so, + statt - bei den reduzierten Kosten; muss mich einfach besser konzentrieren. Aber zum Glück muss man das Zeug ja nicht auswendig lernen.
Aufgabe 2 okay
Aufgabe 1 habe ich auch mit Ford gemacht und Ergebnis 78.
Aufgabe 4 auch 3924
Aufgabe 6 auch WWFFW
Aufgabe 3 habe ich was anderes, muss nochmal nachschauen. Habe bei Berechnung von sigma die Fixkosten weggelassen, wie bei anderen Aufgaben auch. Oder muss ich sie doch dazurechnen?

uried · 3 März 2013

MIJM schrieb:
Aufgabe 3 habe ich was anderes, muss nochmal nachschauen. Habe bei Berechnung von sigma die Fixkosten weggelassen, wie bei anderen Aufgaben auch. Oder muss ich sie doch dazurechnen?

Das ist eine gute Frage. So richtig weiß ich mit den Fixkosten bei dem Add-Alg. noch nicht umzugehen.
Im Studienservice wurde es auch jedesmal anders gemacht.

Habe gerade noch mal nachgeschaut: in der Klausur 9/2011 wurde auch mit Fixkosten gerechnet, wenn auch nur ein Standort ermittelt werden sollte. Jedenfalls habe ich dort für die Fixkosten bei Ermittlung von ny auch die Differenz gebildet und nicht wie bei dieser subtrahiert. Tja, Fragen über Fragen...

Hier ist das mit den Fixkosten ganz gut erklärt, aber ob's stimmt?
http://studienservice.de/thema/28891/#post-644924

MIJM · 4 März 2013

Zu der Aufgabe in 9/2011: da habe ich die ny garnicht gebildet, da Ergebnis aus 2a - sigma von B6 in 2b die Ersparnis bringt.

Und wenn ich hier die Fixkosten bei ny mitrechnen würde, müsste ich ja immer die Fixkosten vom dem Standort mit den günstigsten Fixkosten nehmen und das geht ja nicht. Außerdem bekomme ich bei der Aufgabe Standort S1 als erstes raus, okay.
Aber als zweites bekomme ich Standort 3 und das wird am Ende teurer, aber ich weiß nicht wo ich meinen Fehler habe. Das ny bei S3 ist bei mir 60 und das ny bei S5 ist 50, also gibt es die größere Ersparnis bei S3.

uried · 4 März 2013

MIJM schrieb:
...

Und wenn ich hier die Fixkosten bei ny mitrechnen würde, müsste ich ja immer die Fixkosten vom dem Standort mit den günstigsten Fixkosten nehmen und das geht ja nicht. Außerdem bekomme ich bei der Aufgabe Standort S1 als erstes raus, okay.
Aber als zweites bekomme ich Standort 3 und das wird am Ende teurer, aber ich weiß nicht wo ich meinen Fehler habe. Das ny bei S3 ist bei mir 60 und das ny bei S5 ist 50, also gibt es die größere Ersparnis bei S3.

Ich habe (deshalb oben meine Frage) die Fixkosten gleich von der Ersparnis abgezogen, also ny (eigentlich eta, ich habe immer ny geschrieben

) = sigma_j - dkj - fix, auf deutsch: eta pro Zeile ermitteln und die Fixkosten subtrahieren.
Grund: Eine Ersparnis der Transportkosten ist nur sinnvoll, wenn diese größer als die Fixkosten dieses Standorts sind. Ohne den Abzug der Kfix komme ich auch auf S3 als 2. Standort (eta=60). Aber die Kfix sind 55, zu hoch wie du schon geschrieben hast.
Subtrahiere ich die Kfix von eta, ist mein größtes eta bei S5 mit 25. Die ges. Kfix sind nun mit S1 und S5 als Zulieferstandorte nur 35 und die TK sind 65.

MIJM · 5 März 2013

Klingt gut.

Alisha · 31 August 2014

Eine Frage zu Aufgabe 2:
Bei der Übungsaufgabe auf der LS-Seite war der Aufgabentyp kein Problem. Wenn ich jetzt die reduzierten Kosten ausrechnen möchte, komme ich allerdings auf andere Ergebnisse als alle anderen (habe ein Fremdskript zu Hause und da sind auch andere Lösungen).
Von der Notation her steht doch über einem Strich: minimaler Fluss / maximaler Fluss / Kosten und unter dem Strich der aktuelle Fluss, oder? Von daher hätte ich doch bei der Berechnung der reduzierten Kosten z.B. für <0, 1>: 4 - 0 + 3 = 7. Oder irre ich mich da?

Edit: Wenn man mal einen Blick in den Lösungsbogen werfen würde, sieht man, dass die Kosten unten stehen... wer ändert denn die Notation? *grrr* Frage hat sich also erledigt

Hilfe zur Klausuraufgabe Nachbesprechung Klausur Sep 2008 (SS 2008)

Tutorin und Forenadmin