Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » 1) Flüsse (Übersicht)
no way to compare when less than two revisions
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
— | pruefungen:nebenfach:mathematik:linkomopt2019-02-loesung [21.02.2019 00:53] (aktuell) – angelegt Suyooo | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | **Lösungsvorschlag** zur [[pruefungen/ | ||
+ | ==== 1) Flüsse ==== | ||
+ | **a)** Zwei Augmentierungen nötig, z.B. s,1,3,t und s,2,4,t. Maximaler Flusswert 5, minimaler Schnitt W = {s,1,2,4}. | ||
+ | |||
+ | **b)** Eine Augmentierung nötig, mit negativem Kreis s, | ||
+ | |||
+ | ==== 2) Modellierung ==== | ||
+ | **a)** x_1 ... x_4: Anteil in Tonnen der Grundstoffe G_1 ... G_4 | ||
+ | |||
+ | {{: | ||
+ | |||
+ | (Die zweite Bedingung kann natürlich auch mit ≤ geschrieben werden, aber so ist es einfacher für die Dualisierung) | ||
+ | |||
+ | **b)** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **c)** Anscheinend war es nötig, hier eine Lösung ohne Simplex zu finden - in diesem Fall wäre das x*=(0, | ||
+ | |||
+ | ==== 3) Simplex ==== | ||
+ | **a)** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **b)** 1. Iteration: | ||
+ | * BTRAN: y = (0, -1)^T | ||
+ | * Pricing: z_N = (-1, 1)^T, x_2 betritt Basis | ||
+ | * FTRAN: w = (2, 3)^T | ||
+ | * Ratio-Test: γ = 1, x_3 verlässt Basis | ||
+ | * Update: x = (1,1,0,0)^T | ||
+ | 2. Iteration: | ||
+ | * BTRAN: y = (-1/3, -1/3)^T | ||
+ | * Pricing: z_N = (1/3, 1/3)^T, Simplex terminiert | ||
+ | |||
+ | **c)** 1. Iteration: | ||
+ | * BTRAN: x_B = (3/2, -3/2)^T | ||
+ | * Pricing: x_4 verlässt Basis | ||
+ | * FTRAN: w = (-1/2, 1)^T, α_N = (3/2, 1/2) | ||
+ | * Ratio-Test: γ = 1/3, x_2 betritt Basis | ||
+ | * Update: z = (0, | ||
+ | 2. Iteration: | ||
+ | * BTRAN: x_B = (1/3, 1/3)^T | ||
+ | * Pricing: Simplex terminiert | ||
+ | |||
+ | ==== 4) Graphen ==== | ||
+ | **a)** | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **b)** Da der Graph einfach ist, kann es keine Schlingen oder parallele Kanten geben. Also sind die einzigen Kanten, die mit v und w inzident sind, e selbst und alle Kanten, die mit e einen Endknoten gemeinsam haben. Wir können die Anzahl der Kanten, die einen gemeinsamen Endknoten haben, über deg_G(v) + deg_G(w) erhalten. Dies zählt aber e selbst mit, weshalb 2 abgezogen wird. | ||
+ | |||
+ | **c)** Ein Graph ist eulersch genau dann wenn alle Knotengrade gerade sind. Da die Aussage aus b) für alle Knoten in K(G) gilt und deg_G(v) sowie deg_G(w) gerade sind, sind auch alle Knotengerade in K(G) gerade. Daher ist also K(G) auch eulersch. | ||
+ | |||
+ | **d)** Alle deg_G(v) können einen ungeraden Grad haben - dann ist G nicht eulersch, aber K(G) schon. Ein Gegenbeispiel ist beispielsweise K_4. | ||
+ | |||
+ | ==== 5) Verständnis ==== | ||
+ | **a)** | ||
+ | |||
+ | |**s**|**1**|**2**|**t**| | ||
+ | |__0__|∞|∞|∞| | ||
+ | | |__2__|5|∞| | ||
+ | | | |__3__|5| | ||
+ | | | | |__4__| | ||
+ | |Endergebnis|||| | ||
+ | |0|2|3|4| | ||
+ | |Vorgänger|||| | ||
+ | |-|s|1|2| | ||
+ | |||
+ | **b)** Entspricht Übungsaufgabe 4 von Blatt 8 1-zu-1: Für das Kürzeste-Wege-Problem setzen wir alle Kantenkapazitäten auf 0, den Bedarf an s auf 1 und an t auf -1, alle anderen 0. Für das Maximalflussproblem bilden wir das Problem auf eine Zirkulation ab: alle Bedarfe sind 0 und eine Kante von t zu s wird eingeführt. Nun müssen nur noch die Kosten aller Kanten auf -1 gesetzt werden. | ||
+ | |||
+ | **c)** fancyB = {{2, | ||
+ | |||
+ | **d)** falsch/ |