Hilfe zur Klausuraufgabe Klausur Sep 2009 (SS 2009)

U

uried

Studiengang
M.Sc. Wirtschaftswissenschaft
Aufgabe 1:

a) F, 2 ist Senke und erreicht keinen anderen Knoten
b) W
c) F, in wegen dürfen keine Knoten doppelt vorkommen
d) F, da Zyklen in G
e) W

Rest folgt
 
Aufgabe 2:

ist hier gut gelöst; habe keine Einwendungen

Aufgabe 3:

Center-Probleme -> sind im Skript sehr stiefmütterlich behandelt

a) zuerst ein Schock, als ich die Tab. sah, aber zum Glück kein Median-Problem
der minimale Maximumwert der Zeilen ist E mit 150

b) .... {verworfen}

Aufgabe 4:

ui = 2,3,5
uj = 0,0,-1

Kosten:
1. Wert = Restkosten, 2. Wert= red. Kosten
1-1' : 0,0
1-2' : 3,3
1-3' : 5,4
2-1' : 0,0
2-2' : 2,2
2-3' : 1,0
3-1' : 1,1
3-2' : 0,0
3-3' : 4,3

b)
Zuordnung gemäß ungar. M. (Netzwerktechnik)
1-1'
2-3'
3-2'
also alle sind m.E. bereits zugeordnet, eine Flussänderung deshalb nicht nötig

Somit erscheint mir der letzte Satz der Aufg. 4b) verwirrend. Zur Überprüfung habe ich deshalb schnell mal das Tableau-Verf. der Ungar. M.
angewandt:
nach Kostenred. komme ich bereits tatsächlich auf (*=UN):
* 3 4
0 2 *
1 * 3
Hier gibts m.E. nichts mehr zu tun.

Lösung: 1-1', 2-3', 3-2'

Aufgabe 5:
Gemisch aus TS und genet. Algo.

a) Summe der 10 Gewichte = 7500 kg; da jeder LKW max. 2500 kg zuladen darf, also 3 Fahrten mind. nötig
b) Bandbreitenalgo.; 5 Fahrten
ci) wie Crossover beim Bandabgleich: Punkt (=Obj.) festlegen, ab dem Crossover durchgeführt wird; danach die Objekt des 1. Elternteils bis zum festgelegten Pkt. übernehmen und den Rest vom 2. Elterenteil ab dem Punkt auffüllen, aber derart, dass nur die Objekte verwendet werden, die bisher noch nicht verwendet wurden (dabei die Reihenfolge strikt vom Crossoverpunkt bis zum Ende und danach, wenn nötig, von vorn einhalten); der 2. "Nachfahre" wird genauso erzeugt
cii) weitere Crossover: 1-Pkt.-Crossover oder Mehr-Pkt.-Crossover (striktes Vertauschen ab best. Punkten)
ungeeignet, da Oj. doppelt vorkommen können

ciii) und civ)

Eltern, Fitness, k, Nachkomme, Fitness
1 2 3 4 5 6 7 8 9 10, 3/5, 6, 1 2 3 4 5 6 10 9 8 7, 3/5
10 9 8 7 6 5 4 3 2 1, 3/5, 6, 10 9 8 7 6 5 1 2 3 4, 3/5
3 7 1 4 5 8 2 10 9 6, 3/4, 4, 3 7 1 4 2 9 8 6 5 10, 1 (3/3)
4 7 1 3 2 9 8 6 5 10, 3/4, 4, 4 7 1 3 5 8 2 10 9 6, 3/5

zu iv) Fitness = opt. Anzahl der Fahrten / tatsächliche Anzahl an Fahrten = 3 / tatsächliche Anzahl an Fahrten
also Fitness = 1 ist optimal
 
Zitat:
Aufgabe 3:
Center-Probleme -> sind im Skript sehr stiefmütterlich behandelt
a) zuerst ein Schock, als ich die Tab. sah, aber zum Glück kein Median-Problem
der minimale Maximumwert der Zeilen ist E mit 150

Wie kommst du auf 150?

Ansonsten bei der Klausur nichts anderes herausbekommen.
Habe nur noch Probleme bei der ungarischen Methode. Kann die reduzierten Kosten, die ui und die uj bestimmen, aber das mit der Zuordnung klappt noch nicht so. Aber es sind ja noch ein paar Tage Zeit. :-):wall::-)
 
Super das mit dem Lesen. Habe doch tatsächlich Median statt Center gemacht.
Habe mich noch gewundert wegen der vielen Werte. Halleluja.
Also auf ein Neues.
 
Hallo zusammen,
ich grübele gerade über 3b und c)...
Mit a bin ich einverstanden, 1-zentrums-Problem, Ort mit minimalen Radius.

Der Add-Algorithmus führt Dich aber z.Bsp. auf einen Standort wie Siegen im zweiten Schritt, und das ist mit Verlaub allein anschaulich eine ganz schlechte Entscheidung. ( wenn man von Siegen nach Köln fährt ist das halt länger als von Olpe nach Köln ).

Ich versuche mir gerade das Problem als Set-Covering-Location Problem vorzustellen, dann käme ich anschaulich auf Zentren wie zBsp. Köln, Hamm und Essen. Der Add-Algo liefert aber eben im ersten Schritt ein richtiges Zentrum, von dem aus alles gleich schlecht erreichbar ist, das ist aber doch m.E. gar nicht nötig, denn wir wollen ja gleichmäßig verteilen....

Wenn man argumentieren würde:
Die am weitesten entlegenen Orte müssen erreicht werden: dann wäre Aachen von Köln erreichbar,
Paderborn von Hamm und Bochholt von Duisburg.
Wenn jetzt diese Mindestradien alle anderen Standorte abdecken, wäre m.E. eine optimale Lösung gefunden.... oder nicht? ;)
 
Meine Lösung ist ( nach der oben beschriebenen intuitiven ) Vorgehensweise:
DU -> BH, D, DU, E, W
HAM -> BI, DO, HA, HAM, MS, PB
K -> AC, BN, K, OE, SI
Ich habe hierbei Gesamtkilometer von 707.

Die Lösung oben hat ( wenn ich mich nicht vertippert habe ): 799
 
Aufgabe 3 b und c verworfen (Beitrag #2). Hat hier jemand eine Idee?
 
Wenn man den Text genau liest, wird Essen nicht als vorgegeben betrachtet
In welchen drei Städten soll.... gebaut werden
Zum Vergrößern anklicken....
.
d.h. im ersten Schritt muß der Add-Algo auf ein Set-Covering-Location-Prob umgemodelt werden, dann bei Teil c) werden die beiden zusätzlichen Standorte berechnet.

Es wird ja ganz explizit auf den Algorithmus 5.1 im Skript abgestellt, und verbal könnte man argumentieren, daß in der Erreichbarkeitsmatrix gewisse Verbindungen von vorneherein gestrichen werden, weil die Entfernung Aachen-Paderborn keinen wirklich sinnvollen Beitrag leistet.
Wenn man als zusätzliches Argument den Abstand der Randorte zum nächstgelegen Ort + X als obere Schranke nimmt ( also z.Bsp. alle Entfernungen < 100 km ) könnte man den Add nochmal als 3-Median-Problem angehen.... ( mache ich gleich mal ;) )
 
Hm, das ist die größe Entfernung zwischen 2 Orten ohne Zwischenort. Aber was sagt uns das...?
Nehme ich das als Mindestentfernung und gehe 93 km von Siegen aus, komme ich nicht mal nach Köln, aber nach Hagen. Von hagen nach Aachen sind es dann wieder mehr als 93. 93 ist zu wenig.

Ja, Rechnen müsste man können. Si - K sind 92, geht doch. Also müsste man gedankliche Kreise um Hamm machen mit r=93. Dann sich zwei weitere Punkte suchen auf dem kreisbogen und sehen, ob alles abgedeckt ist.
 
Habe mir zum Center-Problem nochmals Gedanken gemacht. Bevor ich meinen Algorithmus kurz beschreibe, noch ein Anmerkung dazu: Wieso muss gem. b) überhaupt der Add-Algorithmus angewendet werden, wenn er auch nicht in a) angewandt wird. Anhand der Tabellen setzt der LS aber voraus, dass in b) ein eta ausgerechnet werden soll. Bei Center-Problemen geht es m.E. aber nur um die kürzesten Entfernungen der am weitesten entfernten Orte.
Jetzt mein Algo., gleich bezogen auf die Aufgabe:

1. zwei Orte mit den größen Entfernungen zueinander ermitteln (AC und PB)
2. dritten am weitesten entfernten Ort ermitteln: für jeden Ort der Tabelle die Summe der Entfernungen zu AC und zu PB bilden; die größe Summe hat BH
3. die minimalen Entfernungen von jedem Ort zu den 3 Centern ermitteln; damit wird jeder Ort zu einem der 3 Centern zugeordnet (=Teilmenge des p-Centers)
4. für jede Teilmenge das Zentrum ermitteln: entweder wie Aufgabe a) mittels minimales Entfernungsmaximum oder mittels Add-Algor.
5. jedes Centrum der Teilmengen ist ein Ort der gesuchten p-Centren

Leider weichen die Ergebnisse in 4. in Abhängigkeit der Methode ab:
mittels Add-Algo. komme ich auf DO, E und K
und mittels min. Maximum auf DU, HAM und K

Aber wie schon gesagt, die Tabelle in b) gibt ein eta vor, folglich gilt dann wohl DO für BI, DO, Ha, HAM, MS, PB
K für OE, K, Si, Bn, Ac und E für HB, E, DU, D, W.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben