Hilfe zur Klausuraufgabe Klausur Sep 2011 (SS 2011)

Ottokarotto · 18 Februar 2013

Hat da jemand eine Idee zur Vorgehensweise?

Im Kopf kann man sich schon eine Lösung basteln, .... aber das ist nicht gewollt

.

Ich scheitere gerade an den folgenden Überlegungen:
1) es gibt "beliebig viele" Gleise, aber wie unterscheide ich die Plätze, derer es ja zwei pro Gleis gibt. Es macht einen Unterschied, ob ich von links komme, und auf den rechten Platz fahre, oder von links und gleich links stehen bleibe.
2) wie kann ich in die Färbungsfrage den Faktor "Zeit" unterbringen....? brauche ich das überhaupt?

Das Ampel-Problem aus dem Skript fand ich "schöner" ;)

Grüße

Ottokarotto · 18 Februar 2013

antworte mir mal selber:
wenn man die Kanten als: "Züge kommen sich paarweise in die Quere" modelliert käme ich auf einen Graphen dergestalt:
Adjazenzmatrix =
000110
001001
010110
101001
101001
010110

da kommt man auch sehr schnell auf eine minimale Einfärbung von K_1= AFC und K_2= BED.... ABER:
Pro Gleis dürfen ja nur 2 Züge stehen, deswegen ist das keine korrekte Lösung.
Also muß man als weitere Beschränkung hinzunehmen, daß die Mächtigkeit der Farbmenge <= 2 ist, also braucht man um 3 Farben à Zwei Knoten umzufärben im Sinne von Simulated Annealing, noch eine vierte Farbe, quasi als Dummy...

In der Klausur scheinen sich hierbei einige die Zähne dran ausgebissen zu haben :panik:

MIJM · 19 Februar 2013

Adjazenzmatrix habe ich auch so.
C. A,B auf Gleis 1 zulässig; C,D auf Gleis 2 und E,F auf Gleis 3 nicht zulässig.
Auf dem Lösungsbogen soll man immer nur mit Gleis 1 bis 3 arbeiten. "Erzeugen Sie Nachbarlösungen durch beliebiges Umfärben eines solchen Knotens, der durch eine Kante mit einem Knoten gleicher Farbe verbunden ist."
Also färbe ich bei Gleis 1 nichts um, die sind ja nicht verbunden.
Also hab ich D mit E getauscht. Ist zulässige Lösung. Ergibt: A,B + C,E + D,F.
Da dabei D mit F verbunden ist, habe ich E mit F getauscht, auch zulässige Lösung.
Ergibt: A,B + C,F + D,E; und das funktioniert.

MIJM · 19 Februar 2013

Zu den restlichen Aufgaben dieser Klausur.

1.a.
0110
1001
0000
0010

b. e1 von 1 nach 2 e2 von 2 nach 4 e3 von 4 nach 2 e4 von 4 nach 3
e5 von 4 nach 5 e6 von 3 nach 1 e7 von 1 nach 3

c. Minimalgerüst mit Kruskal: (1,2) (4,7) (2,4) (3,5) (1,3) (4,5) (5,6) mit Kantenlänge = 15

d. (n-1) x c

2. a. 1,2 mit 15 1,3 mit 9 1,4 mit 12 1,5 mit 17 1,6 mit 16 1,7 mit 19 1,8 mit 23 1,9 mit 23 1,10 mit 20
Ergibt in Summe 154
b. 1-Median-Problem; reine km - Ersparnis beträgt bei mir 154 - 75 = 79 km.

3. a. imaginären Abnehmer N einplanen; RIE liefert 1,0 Mio Reifen an WOB, da Transportkosten dort minimal;
Transportkosten von K nach IN auf unendlich setzen.
b. RIE nach WOB 1,0 Mio à 3 GE = 3 Mio GE
FD nach IN 0,7 à 3 = 2,1 Mio GE
FD nach S 0,8 à 2 = 1,6 Mio GE
K nach S 0,1 à 6 = 0,6 Mio GE
K nach WOB 0,1 à 3 = 0,3 Mio GE = 7,6 Mio GE

Bis denn. Schöne Woche.

Ottokarotto · 19 Februar 2013

Hallo MIJM.
das kann ich "natürlich" nicht unwidersprochen hinnehmen ;)
bei 1c hast Du Dir einen schönen "Kreis" eingehandelt... 1,2,4,5,3,1 - die Verbindung (4,5) ist überflüssig, und deswegen sind die Transportkosten auch nur = 11.

2 habe ich noch nicht gemacht.

Bei 3) komme ich "streng nach Vogel" auf 8,8 als Transportkosten, was unbestreitbar schlechter ist als Deins ;)
Wie argumentierst Du im Sinne von Vogel, daß Du RIE nach WOB komplett abdeckst?..... ( im Sinne der Vorgaben ist das schon klar, aber wie bekommst Du das mit Vogel in Einklang? )

Gruß

uried · 19 Februar 2013

MIJM schrieb:
...
FD nach IN 0,7 à 3 = 2,1 Mio GE
FD nach S 0,8 à 2 = 1,6 Mio GE
...

Das geht nicht. FD hat nur eine Liefermenge von 0,8. Zzgl. evtl. eine fiktive Menge von max. 0,3.

Die Aufgabenstellung ist leicht verworren: Mal steht Fulda und Köln, dann wieder HU und Fürstenwalde...

Frage: Wieso setzt du die Transportkosten von K nach IN auf unendlich und nicht die Liefermenge auf 0? Die Liefermenge von RIE nach WOB setzt du doch auch gleich auf 1,0. Ich bin mir noch nicht so recht schlüssig.

uried · 19 Februar 2013

So, nochmal Aufg. 3
a)
-fiktiver Abnehmer mit 0,3
-Kosten FW-IN auf sehr hohen Wert (unendlich oder größer als alle anderen TK)
- Kosten RIE - alle anderen auf Null (hier habe ich mich sehr schwer getan, Null ist die einzige sinnvolle Möglichkeit, die ich gesehen habe)
b) In der Reihenfolge gemäß VAM:
1. RIE-IN = 0,7 (Korrektur!)
2. RIE-WOB = 0,3
3. HU - S = 0,8
4. FW-S = 0,1
5. FW-WOB = 0,8
6. Rest: FW = 0,3
gesamt = 8,3

HU = FD und FW = K

uried · 19 Februar 2013

MIJM schrieb:
Adjazenzmatrix habe ich auch so.
C. A,B auf Gleis 1 zulässig; C,D auf Gleis 2 und E,F auf Gleis 3 nicht zulässig.
Auf dem Lösungsbogen soll man immer nur mit Gleis 1 bis 3 arbeiten. "Erzeugen Sie Nachbarlösungen durch beliebiges Umfärben eines solchen Knotens, der durch eine Kante mit einem Knoten gleicher Farbe verbunden ist."
Also färbe ich bei Gleis 1 nichts um, die sind ja nicht verbunden.
Also hab ich D mit E getauscht. Ist zulässige Lösung. Ergibt: A,B + C,E + D,F.
Da dabei D mit F verbunden ist, habe ich E mit F getauscht, auch zulässige Lösung.
Ergibt: A,B + C,F + D,E; und das funktioniert.

Ich denke, es muss in jedem Schritt nur ein Knoten umgefärbt werden. Du beschreibst einen Tausch, also Umfärben von je 2 Knoten pro Schritt. Soll das wirklich so richtig sein?

Ich habe: 1. C nach III und danach 2. E nach II (Austausch in 2 Schritten)

Ottokarotto · 20 Februar 2013

uried schrieb:
b) In der Reihenfolge gemäß VAM:
1. RIE-IN = 0,4
2. RIE-WOB = 0,3
3. HU - S = 0,8
4. FW-S = 0,1
5. FW-WOB = 0,8
6. Rest: FW = 0,3
gesamt = 8,3

HU = FD und FW = K

Hi,
jetzt sehe ich aber bei Dir nicht die Vollauslastung in RIE, hier komme ich nur auf 0,7 Absatz
btw. wir müssen unterschiedliche Exemplare haben, weil bei mir stimmen die Städtenamen - HU und FW kommen nicht vor....

MIJM · 20 Februar 2013

Hallo und guten Morgen,

zu 1.c. Kreise erkennen können ist so eine Sache. Jetzt sehe ich es auch.
Manchmal sehe ich auch schon bunte Kreise vor lauter Aufgaben rechnen.

zu 3. Habe einfach angenommen, RIE liefert alles an WOB, da dort Transportkosten am kleinsten. Geht aber im Sinne von Vogel nicht. RIE kann ja auch an IN und S liefern und bekommt so alles weg. Also wie uried meint, Kosten auf Null setzen ist schlüssig. Dann werden
die als erstes geliefert.
Ergebnis ist bei mir auch 8,3 Mio Gesamtkosten. Nur ist RIE nach IN 0,7.

zu 4. Ich hab doch auf jedem Gleis nur Platz für 2 Züge. Wenn ich also C nach III gebe, dann sind auf Gleis III 3 Züge.
Also habe ich mich für direkten Tausch entschieden.

Bis denn

uried · 20 Februar 2013

Ottokarotto schrieb:
Hi,
jetzt sehe ich aber bei Dir nicht die Vollauslastung in RIE, hier komme ich nur auf 0,7 Absatz
btw. wir müssen unterschiedliche Exemplare haben, weil bei mir stimmen die Städtenamen - HU und FW kommen nicht vor....

Schreibfehler: RIE - IN = 0,7

Komisch, wahrscheinlich ist meine Klausur schon etwas älter. Du hast wahrscheinlich eine korrigierte Fassung.

uried · 20 Februar 2013

MIJM schrieb:
Hallo und guten Morgen,

zu 1.c. Kreise erkennen können ist so eine Sache. Jetzt sehe ich es auch.
Manchmal sehe ich auch schon bunte Kreise vor lauter Aufgaben rechnen.

zu 3. Habe einfach angenommen, RIE liefert alles an WOB, da dort Transportkosten am kleinsten. Geht aber im Sinne von Vogel nicht. RIE kann ja auch an IN und S liefern und bekommt so alles weg. Also wie uried meint, Kosten auf Null setzen ist schlüssig. Dann werden
die als erstes geliefert.
Ergebnis ist bei mir auch 8,3 Mio Gesamtkosten. Nur ist RIE nach IN 0,7.

zu 4. Ich hab doch auf jedem Gleis nur Platz für 2 Züge. Wenn ich also C nach III gebe, dann sind auf Gleis III 3 Züge.
Also habe ich mich für direkten Tausch entschieden.

Bis denn

Das Problem mit dem Tausch wurde auch im Studienservice disskutiert. Aber in der Aufgabe steht m.E. (habe sie jetzt nicht greifbar), dass immer nur ein Knoten umgefärbt werden soll. Andererseits hast du damit recht, dass nicht 3 Züge zusammen auf einem Gleis stehen können.
Hm, hängt wahrscheinlich davon ab, welche Ansicht der LS vertritt.