Hilfe zur Klausuraufgabe Klausur Mrz 2008 (WS 2007/08)

Ottokarotto

Ottokarotto

Ort
Am Fuße der Schwäbischen Alb
Hochschulabschluss
Diplom
2. Hochschulabschluss
Bachelor of Science
Studiengang
M.Sc. Wirtschaftswissenschaft
ECTS Credit Points
120 von 120
Fange mal an, kann aber gerne auch von anderen fortgesetzt werden.

1)
ungerichtet: nur i)
gerichtet: alle außer i)
schwach zusammenhängend: ii), iv) bis vi)
stark zusammenhängend: nur iii)
zyklenfrei: ii), v), vi) ( ist i) zyklenfrei, da ungerichtet?.... )
Baum: v) und vi)
bipartit: nur i) ( da bei bipartit nur für einfache graphen definiert ist.)

b)
Adjazenmatrix:
0111
0000
0000
0000
Inzidenzmatrix
1 1 1
-1 0 0
0 -1 0
0 0 -1
 
Ottokarotto schrieb:
...
1
zyklenfrei: ii), v), vi) ( ist i) zyklenfrei, da ungerichtet?.... )
...
bipartit: nur i) ( da bei bipartit nur für einfache graphen definiert ist.)
...
Zum Vergrößern anklicken....

ungerichtete Graphen haben keine Zyklen, nur Kreise, dehalb ist E) i) gar nicht zu beantworten
- hier würde ich eine Bemerkung hinschreiben, denn keine Markierung heißt, hier ist ein Zyklus (was falsch ist) -

[gilt übrigens auch für C) i) und D) i)]

G) i), ii), vi)
 
Aufgabe 2:

a) Ausgangsfluss = 10 (in Quelle 0 gehen 10 raus und in Senke 10 kommen kumulativ 10 an)
b)
0-4-5-9-10 mit Stärke 3
0-1-6-10 mit Stärke 2
0-2-3-8-7-10 mit Stärke 2
Gesamtfluss also 17
c) minimaler (0,10)-Schnitt = max. Fluss = Kapaz. von 17 und ist C(A,B) mit A={0,2] und B={1,3...10}
Kontrolle: Addition der Phi von <0,1>,<2,1>,<2,3>,<2,5>,<2,4>,<0,1> = 17

Aufgabe 3:
B0501

Aufgabe 4:
a) nach 2 Iterationen: P-D, A-B, B-C, C-A, D-P
b) die ungar. Methode ist für Zuordnungsprobleme, was hier eigentlich nicht vorliegt, denn hier geht es um Routenplanung (Salesman-Probl.)
Außerdem werden hier zwei Routen (PDP und ABCA) erzeugt. Der Arzt will/muss jedoch alle Patienten in einer Route besuchen.
Lösung:Optimierung der provisorischen Zwischenlösung mittels Branch & Bound (siehe Opt.methoden des OR)
Vorgehen: kleineren Zyklus P-D-P aufbrechen und 2 neue Probleme definieren und das mit der kleineren Schranke lösen (ist nicht Gegenstand dieses Moduls)
 
Ergänzung zu 4b)
zur Generierung eines Zykluses aus 2 Zyklen eines TSP muss i.A. mit einer Verschlechterung der Fahrzeiten gerechnet werden.
hier ist es so, dass nach Lösung von a) eine Fahrzeit von 44 min vorliegt
nach Lösung von b) komme ich auf den Zyklus: P-A-B-C-D-P mit 48 min
(Wen es interessiert: Ich habe die Fahrt P-D auf unendl. gesetzt und danach die ungar. Methode erneut angesetzt; Resultat ist, dass die UN bei PD und CA weggefallen und dafür bei PA und CD dazugekommen sind. Als duale Lös. ändert sich u1 von 17 auf 21, wodurch wieder die primale und die duale lös. übereinstimmen.)
 
Aufgabe 5:
a) Knoten = Projekte A...H; Kanten = Konflikt zwischen den Projekten bei der Mitarbeiterzuordnung, da Mitarbeiter an beiden Projekten beteiligt ist
b) die Menge der mit einer Farbe gefärbten Knoten = zu Projektgruppe zusammengefasste Projekte, die gleichzeitig durchgeführt werden können (kein Mitarbeiter arbeitet zur gleichen Zeit an mehr als einem Projekt dieser Projektgruppe mit)
c) Ziel: möglichst wenig Projektgruppen (= wenig verschiedene Färbungen); da jede Projektgruppe bestimmte Zeit ( 1 Wo.) in Anspruch nimmt, bedeuten wenig Farben einen möglichst geringen Zeitaufwand
d) ..., A-E (K1) sowie G-H (K4) sind zulässig und B-D (K2) sowie C-F (K3) sind nicht zulässig, da verbunden
e)
1. Iteration: falt=2 fneu=3 delta=1 T=5 e^(-1/5)=0,819 0,819<0,9 keine Akzeptanz
2. IS (akt. Lösung wie im 1. IS): B aus K2 nach K3 falt=2 fneu=1 delta=-1 Akzeptanz (T=2.5, aber nicht benötigt)
3. IS : F aus K3 nach K2 falt = 1 fneu=0 delta=-1 Akzeptanz (T=1.25 aber nicht benötigt)

Lösung: K1={A,E}; K2={D,F}; K3={B,C}; K4={G,H}

Anmerkung: Diese Lösung ist nicht optimal, da nur die Zulässigkeit hergestellt wurde. Eine Minimierung der Färbungen wurde nicht durchgeführt.
Eine mögliche Weiterführung wäre bspw. D nach K4 und dann F nach K1. Somit entfällt Farbe K2. :-)
 
nochmal zur Aufgabe 4:
eine ähnliche Aufgabe ist in der Aufgabensammlung: B0902 b) Habe ich gerade erst entdeckt. :sleeping:
 
wobei die B0902 die ungarische Methode ja nur im Ansatz verwendet,
wenn's dann um BT und NBT geht uswusf... sehe ich persönlich recht schnell alt aus ;)... aber es gibt ja hoffentlich Teilpunkte!! :freuen:
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben