Hilfe zur Klausuraufgabe Klausur Mrz 2009 (WS 2008/09)

Studiengang
M.Sc. Wirtschaftswissenschaft
Aufgabe 1:

a) F (schwacher Zusammenhang ist notwendige, aber keine hinreichende Bed. für gerichtetes Gerüst, vgl. S. 20)
b) W
c) F (vollständige Digraphen sind nie bipartit)
d) W
e) W [S(1,3) und R(2,5,4)]

Aufgabe 2:

a)
Anfangsflussstärke = 7
1. Fluss: 1-4-7-8 mit +5
2. Fluss: 1-2-6-8 mit +1

b) Kapazität = 13
min. (1,8)-Schnitt = C<A,B> mit A = { 1,2,3,4} und B = { 5,6,7,8}
my(C<A,B>) = 13


Aufgabe 3:
a)
Standort B beliefert A und B
Standort D beliefert C,D,E

b) und der Rest folgt noch
 
3b)
Diesbzgl. wurden schon im Studienservice verschiedene Ansätze disk.
Mir leuchtet nur folgender ein:

1. Die gewichtete Entfernungsmatrix ausfüllen wie in a) mit Ausnahme der Felder, in denen die Entfernung >60 km. Dort einen hinreichend großen Wert eintragen, damit die Kosten für diesen Standort so hoch werden, dass es unlukrativ ist, diesen anzufahren. Ich habe 100.000 gewählt.
2. Jetzt den "normalen" Add-Alg. Man kommt wieder auf D als 1. Standort und anschließend B als 2.

Es geht aber auch einfacher:
Es muss nicht in jeder Zeile sigma errechnet werden. Sobald man sieht, dass in einer Zeile mehr als 1 Standort mit > 60 km, kann diese Zeile unbeachtet bleiben (hier B,C und E), denn die können nie minimales Sigma enthalten. Bei den anderen nur die "normalen" gewichteten Entf. addieren (also nicht die mit 100T angesetzten) und erhält den 1. Standort D (Minimales Sigma).
2. Wert geht noch schneller: Standort D hat den Maximalwert 100T bei B. Die Diff. zur Zeile B ist mind. 100T (100T-0). Den Rest braucht man nicht mehr untersuchen, da keine andere Differenz einen Wert >=100T erreichen kann. Also hat man schon B als 2. Standort.
3. Tab.fuß ausfüllen - fertig - wohl fühlen. :-)


Aufgabe 4a)

Wahrscheinlich ist hier gefordert, dass zuerst alle Werte mit 6 multipliziert werden. Das habe ich mir gespart, es kommt das gleiche Ergebnis raus, wenn man zum Schluss alle cij*xij mit 6 mult. (k.A., wie der LS das sieht)

ges. TK = 5520

b) cij pro Feld LiKj zweimal errechnen: cij * 6 und cij * 8.
Danach die Matrix-Min.-M. : oberer Wert pro Feld mit max. 20
1. L3K1=20 (6€)
2. L1K3=20 (6€)
3. L3K1=45 (8€)
4. L2K3=20 (6€)
5. L1K3=80 (8€)
6. L3K3=5 (8€)
7. L2K2=20 (6€)
8. L2K2=20 (8€)

ges. TK=6635
 
Aufgabe 5:

a)
Grafik als Text leider nicht darstellbar
b)
Grafik als Text leider nicht darstellbar
8 ist Ziel (Z)

c)

g = bereits zurückgelegter Weg (Kästchen zählen) zB S->1 ist 1
h = Entfernung zum Ziel als "Luftlinie hor. durch alle Hindernisse"

d) erster erreichter Knoten in Z ist 8 über S-1-3-6-8 (Wert=22)
aber besser bewertet ist S-1-3-7-10 (Wert=24, da der Weg länger ist)

Was ist nun die bessere Lösung? Ich denke der 1., denn es ist nach dem ersten Erreichen eiens Knoten in Z gefragt.
 
Aufgabe 1
okay
Aufgabe 2
minimaler Schnitt hat bei mir Kapatität 16
Aufgabe 3
a ebenso, b noch nicht gemacht
Aufgabe 4
ebenso
Aufgabe 5
noch nicht
 
Aufgabe 2: der Ford-Fulkerson-Algorithmus und ich haben sich noch nicht ganz verstanden. Ich komme auf einen minimalen Schnitt von 12. Die erste Augmentierung um 5 habe ich gefunden. Eine weitere sehe ich nicht, da m.E. alle Flüsse im "Mittelteil" ausgeschöpft sind. Wo ist mein Denkfehler?
 
Zurück
Oben