Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » 1) Flüsse   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

pruefungen:nebenfach:mathematik:linkomopt2019-02-loesung [21.02.2019 01:53] (aktuell)
Suyooo angelegt
Zeile 1: Zeile 1:
 +**Lösungsvorschlag** zur [[pruefungen/​nebenfach/​mathematik/​linkomopt2019-02|WS 2018/​2019-Prüfung LKOpt (10 ECTS)]]
  
 +==== 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,​1,​3,​4,​2,​s.
 +
 +==== 2) Modellierung ====
 +**a)** x_1 ... x_4: Anteil in Tonnen der Grundstoffe G_1 ... G_4
 +
 +{{:​pruefungen:​nebenfach:​mathematik:​lkopt_2019_2primal.png?​nolink|}}
 +
 +(Die zweite Bedingung kann natürlich auch mit ≤ geschrieben werden, aber so ist es einfacher für die Dualisierung)
 +
 +**b)** ​
 +
 +{{:​pruefungen:​nebenfach:​mathematik:​lkopt_2019_2dual.png?​nolink|}}
 +
 +**c)** Anscheinend war es nötig, hier eine Lösung ohne Simplex zu finden - in diesem Fall wäre das x*=(0,​2.5,​0,​0). Die Aufgabe in der Prüfung war ähnlich, man musste einen einzelnen der Grundstoffe für die "​Mischung"​ verwenden. Dann kann man mit dem Satz des komplementären Schlupfs argumentieren:​ x*_2 > 0, also muss duale Ungleichung 2 exakt erfüllt werden. Ungleichungen 1, 3 und 4 sind strikt erfüllt, also sind y*_1, y*_3 und y*_4 = 0. Nun können wir also mit der 2. dualen Ungleichung (-100 y_2 = 200) die duale Lösung bestimmen: y* = (0,-2,0,0). Diese erfüllt alle dualen Ungleichungen,​ ist damit zulässig und laut dem Satz optimal.
 +
 +==== 3) Simplex ====
 +**a)**
 +
 +{{:​pruefungen:​nebenfach:​mathematik:​lkopt_2019_3zeichnung.png?​nolink|}}
 +
 +**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,​0,​1/​3,​1/​3)^T
 +2. Iteration:
 +  * BTRAN: x_B = (1/3, 1/3)^T
 +  * Pricing: Simplex terminiert
 +
 +==== 4) Graphen ====
 +**a)** ​
 +
 +{{:​pruefungen:​nebenfach:​mathematik:​lkopt_2019_4kantengraph.png?​nolink|}}
 +
 +**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,​3,​4},​{1,​3,​4},​{1,​2,​4},​{1,​2,​3}},​ fancyC = <​nowiki>​{{1,​2,​3,​4}}</​nowiki>,​ fancyB* = {{1},​{2},​{3},​{4}},​ fancyC* = {{1,​2},​{1,​3},​{1,​4},​{2,​3},​{2,​4},​{3,​4}}
 +
 +**d)** falsch/​wahr/​falsch/​wahr