Hilfe zur Klausuraufgabe Klausur Mrz 2011 (WS 2010/11)
- Ersteller uried
- Erstellt am
2a)
...
b)
D^(6)=
0 3 5 4 5
5 0 2 1 2
3 6 0 7 8
4 7 1 0 1
8 11 5 12 0
Q^(6)=
AADBD
CBDBD
CACBD
CADDD
CAEBE
c) Weg von A nach E -> Suche erfolgt rekursiv
1. Zeile aus Q^(6) lautet AADBD
Einstieg ist bei E (5. Stelle des Vektors) = D
D (4. Stelle) zeigt auf B
B (2. Stelle) zeigt auf A
A (1. Stelle) zeigt auf A
Damit ist die Strecke: A-B-D-E
Länge ist 5. Abzulesen aus D^(6) in 1. Zeile, Spalte 5
q15 = 5
...
b)
D^(6)=
0 3 5 4 5
5 0 2 1 2
3 6 0 7 8
4 7 1 0 1
8 11 5 12 0
Q^(6)=
AADBD
CBDBD
CACBD
CADDD
CAEBE
c) Weg von A nach E -> Suche erfolgt rekursiv
1. Zeile aus Q^(6) lautet AADBD
Einstieg ist bei E (5. Stelle des Vektors) = D
D (4. Stelle) zeigt auf B
B (2. Stelle) zeigt auf A
A (1. Stelle) zeigt auf A
Damit ist die Strecke: A-B-D-E
Länge ist 5. Abzulesen aus D^(6) in 1. Zeile, Spalte 5
q15 = 5
3a)
erst S4, dann S3, danach keine Verbesserung durch weiteren Standort
S3 für G1, G2, G3 mit TK = 40
S4 für G4 mit TK = 0
Fixkosten = 7
insg. also 47
3b)
Das Problem besteht darin, dass die Nachfrage = 30 Aufträge ist und die 2 Lager nur á 10 (=20) anbieten können.
Es kommt zu Kapazitätsbeschränkungen. Es ist nicht feststellbar, welchen Anteil ein Lager an der Deckung des Bedarfs der Nachfrager hat.
Der Add-Algo. geht jedoch davon aus, dass jeder Nachfrager erreichbar ist und alle Nachfragen erfüllt werden können (keine Kapazitätsrestriktionen). Für kapazitierte WLP ist der Add-A. ungeeignet.
erst S4, dann S3, danach keine Verbesserung durch weiteren Standort
S3 für G1, G2, G3 mit TK = 40
S4 für G4 mit TK = 0
Fixkosten = 7
insg. also 47
3b)
Das Problem besteht darin, dass die Nachfrage = 30 Aufträge ist und die 2 Lager nur á 10 (=20) anbieten können.
Es kommt zu Kapazitätsbeschränkungen. Es ist nicht feststellbar, welchen Anteil ein Lager an der Deckung des Bedarfs der Nachfrager hat.
Der Add-Algo. geht jedoch davon aus, dass jeder Nachfrager erreichbar ist und alle Nachfragen erfüllt werden können (keine Kapazitätsrestriktionen). Für kapazitierte WLP ist der Add-A. ungeeignet.
5.
Diese Tabu Search - Aufgaben muss ich mir immer mind. 3x durchlesen, ehe ich weiß, was "die" wollen.
a) Bewertung von f(x) = Anzahl der inzidenten Kanten; je weniger also, umso weniger Widersprüche sind vorhanden
f(x0) = 10
b) Nachbarschaftstruktur durch Austausch von zwei benachbarten "Bits", wobei immer die Null getauscht werden soll, da ja 2 Experimente wegfallen sollen
Steht eine Null an 1. Stelle wird mit letzter Stelle getauscht. Oder umgekehrt.
Auf diese Weise werden immer 2 unterschiedliche Exp. eliminiert. Allerdings komme ich aus symmetrischen Gründen auf 4 Nachbarn.
x0=011101111
x11=101101111
x12=111101110
x13=011011111
x14=011110111
c)
E=(E1,E2,...,E9), wobei Ei = {0,1} und einen Knoten (=Experiment) repräsentiert
from(x0,x11)=(01-------)
from(x0,x12)=(0-------1)
from(x0,x13)=(---10----)
to(x0,x11)=(10-------)
to(x0,x12)=(1-------0)
to(x0,x13)=(---01----)
5d)
ist viel Schreibarbeit und schenke ich mir mal jetzt
aber f(x) ist nach 3. Schritt nur noch 3
Diese Tabu Search - Aufgaben muss ich mir immer mind. 3x durchlesen, ehe ich weiß, was "die" wollen.
a) Bewertung von f(x) = Anzahl der inzidenten Kanten; je weniger also, umso weniger Widersprüche sind vorhanden
f(x0) = 10
b) Nachbarschaftstruktur durch Austausch von zwei benachbarten "Bits", wobei immer die Null getauscht werden soll, da ja 2 Experimente wegfallen sollen
Steht eine Null an 1. Stelle wird mit letzter Stelle getauscht. Oder umgekehrt.
Auf diese Weise werden immer 2 unterschiedliche Exp. eliminiert. Allerdings komme ich aus symmetrischen Gründen auf 4 Nachbarn.
x0=011101111
x11=101101111
x12=111101110
x13=011011111
x14=011110111
c)
E=(E1,E2,...,E9), wobei Ei = {0,1} und einen Knoten (=Experiment) repräsentiert
from(x0,x11)=(01-------)
from(x0,x12)=(0-------1)
from(x0,x13)=(---10----)
to(x0,x11)=(10-------)
to(x0,x12)=(1-------0)
to(x0,x13)=(---01----)
5d)
ist viel Schreibarbeit und schenke ich mir mal jetzt
aber f(x) ist nach 3. Schritt nur noch 3
- Ort
- Heidelberg
- Studiengang
- B.Sc. Wirtschaftswissenschaft
Hallo,
1 bis 3 kann ich zustimmen.
Habe bei 3 zuerst die Fixkosten von Anfang an mitgerechnet, ist aber wohl so nicht richtig. Ich rechne nochmal nach.
Bei 4 habe ich geringfügig anderes raus, rechne aber auch nochmal.
Nun zu 5. Ich habe die Aufgabe nicht so verstanden, dass man immer zwei Experimente ausschließt, sondern dass man bei jedem Schritt eines mehr ausschließt um dann eine maximale Menge widerspruchsfreier Experimente zu bekommen.
Habe also bei den Nachbarn immer eine 1 in eine 0 umgewandelt und komme nach dem 2. Schritt auf (010101011) mit f(x)=1. 3. Schritt noch nicht gemacht, weil ich mir dann doch nicht so sicher war.
1 bis 3 kann ich zustimmen.
Habe bei 3 zuerst die Fixkosten von Anfang an mitgerechnet, ist aber wohl so nicht richtig. Ich rechne nochmal nach.
Bei 4 habe ich geringfügig anderes raus, rechne aber auch nochmal.
Nun zu 5. Ich habe die Aufgabe nicht so verstanden, dass man immer zwei Experimente ausschließt, sondern dass man bei jedem Schritt eines mehr ausschließt um dann eine maximale Menge widerspruchsfreier Experimente zu bekommen.
Habe also bei den Nachbarn immer eine 1 in eine 0 umgewandelt und komme nach dem 2. Schritt auf (010101011) mit f(x)=1. 3. Schritt noch nicht gemacht, weil ich mir dann doch nicht so sicher war.
- Hochschulabschluss
- Diplom
- 2. Hochschulabschluss
- Bachelor of Science
- Studiengang
- M.Sc. Wirtschaftswissenschaft
- ECTS Credit Points
- 120 von 120
generell muß ich sagen, daß ich diese Klausur recht aufwändig und auch fehleranfällig finde.
Bei 1 ist Matrizenmultiplikation 7x7 ( auch wenn obere Dreiecksmatrix) doch viel Aufpassen angesagt.... habe 2 Anläufe gebraucht...;)
zu2 ) Triple-Algorithmus.... hänge an der Q6... da würde ich nachher noch mal explizit fragen.
zu3 ) sehe ich genauso, die fix-kosten haben eine eigene Spalte, von daher ist die Gefahr die überall mit reinzunehmen eigentlich nicht da.
zu4 )... muß ich erst mal verstehen, was im Skript steht ;)
zu5) ... f(x0) wäre bei mir 8, da x0 = 011101111 ist, d.h. im dargestellten Graphen sind 1 und 5 nicht vorhanden, macht dann nur noch 8 inzidente Kanten.
.... weiter bin ich noch nicht ;)
Bei 1 ist Matrizenmultiplikation 7x7 ( auch wenn obere Dreiecksmatrix) doch viel Aufpassen angesagt.... habe 2 Anläufe gebraucht...;)
zu2 ) Triple-Algorithmus.... hänge an der Q6... da würde ich nachher noch mal explizit fragen.
zu3 ) sehe ich genauso, die fix-kosten haben eine eigene Spalte, von daher ist die Gefahr die überall mit reinzunehmen eigentlich nicht da.
zu4 )... muß ich erst mal verstehen, was im Skript steht ;)
zu5) ... f(x0) wäre bei mir 8, da x0 = 011101111 ist, d.h. im dargestellten Graphen sind 1 und 5 nicht vorhanden, macht dann nur noch 8 inzidente Kanten.
.... weiter bin ich noch nicht ;)
- Hochschulabschluss
- Diplom
- 2. Hochschulabschluss
- Bachelor of Science
- Studiengang
- M.Sc. Wirtschaftswissenschaft
- ECTS Credit Points
- 120 von 120
hab's mal gelöscht
Die 10 bezieht sich auf die Ausgangsgrafik mit allen Kanten. Hätte vllt. besser f(x)=10 schreiben sollen.
f(x0)=8 für x0 = 011101111 ist ok.
Das wäre für mich unlogisch, denn mit diesem Ansatz kommt man immer zu f(x) = 0, spätestens wenn die letzte 1 umgewandelt wurde.
Ich bin davon ausgegangen, dass man prüfen will, bei welcher Konstellation man die wenigsten Widersprüche bei gegebener Anzahl Experimente (zB 7 gemäß Beispiel) hat.
Außerdem, wenn immer nur 1en wegfallen, wozu brauche ich dann die from- und to-Attribute?
Aber vllt. sehe ich etwas entscheidendes nicht. Wie schon gesagt, TS-Aufgaben sind nicht meine Stärke.