Hilfe zur Klausuraufgabe Klausur Mrz 2010 (WS 2009/10)

uried · 23 Februar 2013

Aufgabe 1
F,W,W,F,F,W,F

h) <1,2> = 3; <1,3> = 4; <1,4> = 5; <1,5> = 6; <4,6> = 10
insg. 28

i)
m.E. falsch, denn ein Digraph mit mind. 2 weiteren Knoten kann Zyklen zwischen den Knoten, die keine Senke und keien Quelle sind, besitzen
zB: 1 -> 2 <--> 3 -> 4

uried · 23 Februar 2013

Aufgabe 2:

s. Aufgabensammlung des LS: B0405

Aufgabe 3:
a) Tabelle

b)
1. Schritt: sigma6 ist Minimum mit 498 -> 1. Standort ist D6
2. max. ny ist D3 für S5 (D6 bedient also S1,S2,S3,S4,S6,S7), da aber Stellplatzkapazität von D6 überschritten, muss weiterer Standort gesucht werden
3. max. ny ist D5 für S1,S4,S6,S7 (Stellplatzkap. von D5 mit 38 < 40, also ok); D6 hat Kap. von 12 < 25, auch ok und D3 hat Kap. von 12 < 30
somit Aufgabe erledigt: D3 für S5, D5 für S1,S4,S6,S7, D6 für S2, S3

ein 4. Schritt nicht nötig, aber wäre rechnerisch für D2 für S3 machbar

Aufgabe 4:
a) Vogel
A-M = 11
A-N = 54
B-K = 38
B-L = 3
B-M=36
C-L=58

b)
1. Phase SSM: ui=0,-5,-35 uj=-10, -55, -30, -15
werden danach alle red. Kosten eingetragen, finden sich keine negativen red. Kosten

folglich keine Lösungsverbesserung möglich, opt. Lösung deshalb schon erreicht?

Aufgabe 5 später

uried · 23 Februar 2013

Aufgabe 5:

a)
Station 1: 1,2,3
Station 2: 4,5
Station 3: 6,7
Station 4: 8,9
Rest (10-14) = nicht zuordenbar mit f(x0) = 11

b)
TS-Aufgabe mit wie immer hohem Verständnisproblem
Ich verstehe das so, dass Nachbarschaften so gebildet werden sollen, indem bestimmte vorgegebene Paare von Vorgängen getauscht werden sollen. Aber nicht jeder Tausch ist möglich, denn es müssen die Zwangsreihenfolgen eingehalten werden. Aber dabei spielen die Vorgangsdauern keine Rolle. Ich habe mich an das Bsp. S. 93 im Skript gehalten.
Tausch:
3-8: nach langer Überlegung bin ich der Meinung, dass es möglich ist, denn die Reihenfolge von 1 bis 14 kann eingehalten werden
{und wie Ottokarotto immer schreibt: Spoiler! :belehren:

In der Lösung in f) ist 3-8 tatsächlich getauscht}
1 2 8 4 5 6 7 3 9 10 11 12 13 14 f(x1a)=3
6-7: 1 2 3 4 5 7 6 8 9 10 11 12 13 13 f(x1b)=3
10-11: 1 2 3 4 5 6 7 8 9 11 10 12 13 14 f(x1c)=11

c) hier habe ich den erfolgreichsten Tausch (1a) genommen
2f = --3----8------
2t:= --8----3------

d) zulässig, da Positionen 3 und 8 von xk unterschiedlich zu denen in 2f sind

e) nicht zulässig, die Positionen 3 und 8 von xk sind mit denen in 2t identisch

f) f(xk) = 0 (Verteilung auf 4 Stationen möglich)

Ottokarotto · 3 März 2013

3-8: nach langer Überlegung bin ich der Meinung, dass es möglich ist, denn die Reihenfolge von 1 bis 14 kann eingehalten werden
{und wie Ottokarotto immer schreibt: Spoiler! In der Lösung in f) ist 3-8 tatsächlich getauscht}
1 2 8 4 5 6 7 3 9 10 11 12 13 14 f(x1a)=3

Bin ich nicht Deiner Ansicht ( auch wenn im letzten Aufgabenteil tatsächlich eine Ähnlichkeit vorhanden ist ):
3-8 ist keine mögliche Abfolge, da die Vorgänge 6 und 3 in falscher Reihenfolge bearbeitet werden.

Die letzte AUfgabe umgeht dieses Problem dadurch, daß 673 zu 736 wird, was wiederum korrekt ist....
Lasse mich aber gerne korrigieren.

Ottokarotto · 3 März 2013

Nochmal zu Aufgabe 5) ...
wie soll man denn den Lösungsbogen interpretieren, insbesondere die Zeilen 1a-c)....? Das wäre ja ein Indiz dafür, daß von den 6 vorgegebenen Paaren nur 3 Lösungen korrekt sind???
Zeile"2" ist dann die beste der drei akzeptablen NAchbarschaftslösungen, oder?..

Also wenn das Verstehen der Aufgabe länger dauert als das Lösen.... dann gut Nacht um sechs.

uried · 3 März 2013

Ottokarotto schrieb:
Nochmal zu Aufgabe 5) ...
wie soll man denn den Lösungsbogen interpretieren, insbesondere die Zeilen 1a-c)....? Das wäre ja ein Indiz dafür, daß von den 6 vorgegebenen Paaren nur 3 Lösungen korrekt sind???
Zeile"2" ist dann die beste der drei akzeptablen NAchbarschaftslösungen, oder?..

So habe ich das verstanden...

uried · 3 März 2013

Ottokarotto schrieb:
Bin ich nicht Deiner Ansicht ( auch wenn im letzten Aufgabenteil tatsächlich eine Ähnlichkeit vorhanden ist ):
3-8 ist keine mögliche Abfolge, da die Vorgänge 6 und 3 in falscher Reihenfolge bearbeitet werden.

Die letzte AUfgabe umgeht dieses Problem dadurch, daß 673 zu 736 wird, was wiederum korrekt ist....
Lasse mich aber gerne korrigieren.

Ich vermute mal du gehst gedanklich davon aus, dass die Plätze getaucht werden. Nein, es werden nur die Abarbeitungsreihenfolgen geändert. Nach Tausch 3-8 bleibt 3 nach der 1 im Graph, wird aber nicht als 3. Vorgang, sondern als 8. abgearbeitet. Das geht.

Ottokarotto · 3 März 2013

Nach Tausch 3-8 bleibt 3 nach der 1 im Graph, wird aber nicht als 3. Vorgang, sondern als 8. abgearbeitet

...eben, aber nach der 6, die per Vorrang eigentlich nach der 3 kommen sollte...

..muß ich morgen nachschauen, bin jetzt wieder daheim und mein Geschreibsel im Büro....

uried · 3 März 2013

Ottokarotto schrieb:
...eben, aber nach der 6, die per Vorrang eigentlich nach der 3 kommen sollte...

..muß ich morgen nachschauen, bin jetzt wieder daheim und mein Geschreibsel im Büro....

Die 3 wird nach 3-8-Tausch tatsächlich in einer späteren Station abgearbeitet. Aber die Reihenfolge 8 nach 2 bleibt und 3 nach 1 bleibt auch erhalten. 6 und 8 sind nicht verbunden, folglich gibt es hier keine Reihenfolge wie im Gozintograph oder Netzplan, sind also unabhängig.
Die Zwangsreihenfolge des Graphen ist bei diesem Aufgabentyp entscheidend und nicht die zeitliche Dauer der einzelnen Vorgänge.
Im Übrigen, im Bsp. im Skript sieht man ein ähnliches "Problem": Die 4 ist in Station 2, kommt aber in der absoluten Reihenfolge noch vor 2 und 3.

Ottokarotto · 3 März 2013

aber ich beziehe mich doch auf die 6 und 3.
M.E. hat die 3 vor der 6 zu "geschehen", und das wird es doch beim 3-8 Tausch nicht mehr.....

MIJM · 3 März 2013

Hallo ihr beiden,
hatte jetzt auch die letzten zwei Tage Zeit zu rechnen.
Aufgabe 5
Habe auch zuerst gedacht, 3 und 8 kann man nicht tauschen, geht aber wohl doch, da man die 6 von der 2 ausgehend erreichen kann und später die 3 von der 1 aus.
Dann hört man nach dem Tausch von 3-8, 3-4 und 6-7 auf, da die ersten drei schon in Ordnung sind.
from(--3----8------) to(--8----3------).
Da aber die Lösung durch tauschen von 6-7 auch die ZF=3 hat, kann man vielleicht auch die nehmen, oder muss man die erste gefundene Lösung mit der kleinsten Zielfunktion nehmen?
Letzter Aufgabenteil auch ZF=0 und damit optimal.

Aufgabe 1
unschlüssig bei e. Rest okay.

Restliche Aufgaben auch so.
Gruß

uried · 3 März 2013

MIJM schrieb:
Hallo ihr beiden,
hatte jetzt auch die letzten zwei Tage Zeit zu rechnen.
Aufgabe 5
Habe auch zuerst gedacht, 3 und 8 kann man nicht tauschen, geht aber wohl doch, da man die 6 von der 2 ausgehend erreichen kann und später die 3 von der 1 aus.
Dann hört man nach dem Tausch von 3-8, 3-4 und 6-7 auf, da die ersten drei schon in Ordnung sind.
from(--3----8------) to(--8----3------).
Da aber die Lösung durch tauschen von 6-7 auch die ZF=3 hat, kann man vielleicht auch die nehmen, oder muss man die erste gefundene Lösung mit der kleinsten Zielfunktion nehmen?

Ich denke, es ist egal, welche der beiden Nachbarschaftslösungen mit ZF=3 genommen wird. Man könnte auch die andere nehmen.

uried · 3 März 2013

MIJM schrieb:
Aufgabe 1
unschlüssig bei e

Dieser Digraph kann m.E. nicht stark zusammenhängend sein, da nicht jeder Knoten von jedem anderen aus erreichbar ist. Z.B. von knoten 2 ist kein anderer zu erreichen.

Ottokarotto · 4 März 2013

Dieser Digraph kann m.E. nicht stark zusammenhängend sein, da nicht jeder Knoten von jedem anderen aus erreichbar ist. Z.B. von knoten 2 ist kein anderer zu erreichen.

sehe ich genauso - für stark zusammenhängend Teilgraphen muß ein Zyklus exisitieren, denn sonst wäre nicht jedes i von jedem j, und jedes j von jedem i aus zu erreichen. Hier ist 2 eine Senke und 1 eine Quelle, deswegen auch kein Zyklus, und deswegen ist der Graph auch nicht stark zusammenhängend. Ich sehe außer den Knoten an sich auch keine starke Zusammenhangskomponenten, weil es überhaupt keinen Zyklus gibt. Also auf die Frage nach den starken Zusammenhangskomponenten wären nur die Knoten zu nennen ( was hier aufgrund der Fragestellung aber gar nicht verlangt ist ).

Ottokarotto · 4 März 2013

Noch mal zu 5b) Tausch von 3 - 8:
Ich bleibe dabei, daß es kein erlaubter Tausch ist!
2,3 und 4 haben Vorrang vor 6. Ich sehe die Mehrfachpfeile als UND und nicht als ODER.
Wenn ich 3 und 8 Tausche ist m.E. nicht die 8 das Problem, denn solange die nach der 2 und vor der 12 kommt ist alles im grünen Bereich.
Aber die 6 kommt vor der 3 und das ist laut Vorrangsgraphen eben gerade nicht erlaubt.

In der allerletzten Vorrangsreihenfolge: 12845736.... wird genau diesem Umstand Rechnung getragen.

Aus dem gleichen Grund ist für mich auch der Tausch 4 - 9 nicht erlaubt. 123956784... 9 käme nach drei, verlangt aber erst eine Abarbeitung von 6...
3-4 kann ich ohne Probleme tauschen, die beiden Schritte hängen nicht wirklich voneinander ab, selbe Argumentation für 6-7 und 10-11

Aus dem Grund hätte ich dann als 1a) 3-4 mit f(x)=11; 1b) 6-7 mit f(x)=3 und 1c) 10-11 mit f=10

und nun: haut mich ;)

uried · 4 März 2013

Ottokarotto schrieb:
Noch mal zu 5b) Tausch von 3 - 8:
Ich bleibe dabei, daß es kein erlaubter Tausch ist!
2,3 und 4 haben Vorrang vor 6. Ich sehe die Mehrfachpfeile als UND und nicht als ODER.
Wenn ich 3 und 8 Tausche ist m.E. nicht die 8 das Problem, denn solange die nach der 2 und vor der 12 kommt ist alles im grünen Bereich.
Aber die 6 kommt vor der 3 und das ist laut Vorrangsgraphen eben gerade nicht erlaubt.

In der allerletzten Vorrangsreihenfolge: 12845736.... wird genau diesem Umstand Rechnung getragen.

Aus dem gleichen Grund ist für mich auch der Tausch 4 - 9 nicht erlaubt. 123956784... 9 käme nach drei, verlangt aber erst eine Abarbeitung von 6...
3-4 kann ich ohne Probleme tauschen, die beiden Schritte hängen nicht wirklich voneinander ab, selbe Argumentation für 6-7 und 10-11

Aus dem Grund hätte ich dann als 1a) 3-4 mit f(x)=11; 1b) 6-7 mit f(x)=3 und 1c) 10-11 mit f=10

und nun: haut mich ;)

Nein, Scherz.
Deine Argumentation zu 3-4, 6-7 und 10-11 sind ok. Die sind ohne Diskussion möglich. Auch 8-11, denke ich.
Aber ich verstehe nicht, wieso 3-8 nicht möglich sein soll. Und-Oder-Bez. gilt m.E. nicht, denn mit UND wäre nur Nachbarschaftstausch möglich.
Mal alle Schritte notiert:
1 - 2 - 8 (1. Zeile), gehe in 3. Z. : 4, gehe in 4. Z.: 5; zu 6 in Z. 2, 7 in Z. 4, 3 in Z.2, Hm, ich gebe zu, es sieht schon merkwürdig aus.
Aber mit meiner Behauptung, es gelten auch ODER-Bez., würde es funktionieren. Also weiter: 9 nach der 6 in Z. 2, 10 in Z.3 ....
Vllt. hätte ich in der Klausur 3-4, 6-7 und 10-11 gewählt. Und: f) verleitet zu glauben, dass es zulässig ist.

Ottokarotto · 4 März 2013

Also ich interpretiere die Vorgangsfolge unter Einhaltung des Vorranggraphen folgendermaßen:
Links von der 6 MUSS die 1234 stehen, rechts von der 6 MUSS die 9 10 12 13 14 stehen.
Deswegen darf die 8 Links von der 6 stehen, aber die 3 darf nicht rechts davon stehen.

Am Beispiel 11:
Links von der 11 MUSS 1 4 5 7 stehen, Rechts davon MUSS 13 14 stehen, die 12 z.Bsp darf stehen wo sie will ( bezogen auf die 11 natürlich nur ).

uried · 4 März 2013

Klingt einleuchtend, das wäre doch mal ein Anfrage beim Lehrstuhl wert.

Ottokarotto · 4 März 2013

ist halt nur blöd, daß diese Klausur nicht zu den offiziellen VOrbereitungsklausuren zählt ....

uried · 4 März 2013

zu Aufgabe 2 bzw. B0405 der Aufgabensammlung

Wieso steht in der Tabelle in d) in der Spalte des 2. IS, dass die Flüsse von O->H und B->O jeweils die Stärke 2 haben?
Ich denke, es müsste 1 heißen, weil der Fluss von A kommt und dort schon nur 1 hat.

Und noch etwas anderes: Ich habe die Flüsse unter c) schon anders, allerdings mit gleichem Endergebnis. Dadurch ist meine Tabelle unter d) auch anders. Stellt sich die Frage: Gibt es eine Vorschrift, einen bestimmten Fluss zu bevorzugen bzw. zuerst zu nehmen? Wie gesagt, das Endergebnis ist ja immer gleich.