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 [21.02.2019 00:53] (aktuell) – angelegt Suyooo | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | **LKOpt - Schriftliche Prüfung (10ECTS)** | ||
+ | **Dozent:** Dieter Weninger | ||
+ | |||
+ | **Erlaubte Hilfsmittel: | ||
+ | |||
+ | **Zeit:** 90 Minuten | ||
+ | |||
+ | Zeitlich ist die Klausur sehr knapp bemessen - lieber einmal mehr nochmal die abgeschriebenen Werte prüfen bevor man die Hälfte durchstreichen und nochmal rechnen muss (wie ich, der die falsche Basis im Simplex benutzt hat...) | ||
+ | |||
+ | Die Algorithmen und wichtigen Sätze passen gut auf zwei Seiten, besonders wenn man die Sortier- und Graphalgorithmen aus AuD noch gut kennt und nur die Unterschiede aufschreiben muss. Die dritte Seite habe ich genutzt, um die Lösungen einiger Übungsaufgaben aufzuschreiben - allerdings brauchte ich diese nicht. Besser wäre es gewesen, auch die Sätze, die auf den Übungsblättern bewiesen wurden, mitzunehmen. Es gibt keine " | ||
+ | |||
+ | Ich habe versucht, die Aufgabenstellungen so genau wie möglich wiederzugeben - ist natürlich kaum machbar, aber ich denke, dass die hier beschriebenen Probleme ähnlich genug zu denen aus der Prüfung sind. | ||
+ | |||
+ | Notiz am Rande: LKOpt bietet auch eine 5 ECTS-Prüfung an (entweder nur lineare oder nur kombinatorische Optimierung), | ||
+ | |||
+ | Meinen Lösungsvorschlag habe ich auf einer seperaten Seite abgelegt, damit man nicht aus Versehen darüber liest: [[pruefungen/ | ||
+ | |||
+ | ==== 1) Flüsse ==== | ||
+ | **a)** Maximalflussproblem mit Augmentierende-Wege-Algorithmus. Angeben des augmentierenden Wegs, Flusswertes und Zeichnen des Residualgraphen nach jedem Schritt. Zum Schluss Fluss und minimalen Schnitt angeben. | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **b)** Minimalkosten-Flussproblem mit Kreislöschungs-Algorithmus. Angeben der Flusskosten, | ||
+ | |||
+ | {{: | ||
+ | |||
+ | ==== 2) Modellierung ==== | ||
+ | **a)** Einfaches Problem modellieren: | ||
+ | | | ||
+ | |N1|100|100|50|150|200|300| | ||
+ | |N2|150|80|50|300|200|---| | ||
+ | |N3|50|90|50|300|200|---| | ||
+ | |Kosten|400|200|300|1000| | | | ||
+ | |||
+ | **b)** Duales Problem für das Problem aus a) aufstellen. | ||
+ | |||
+ | **c)** Zu beweisen: der optimale Zielfunktionswert beträgt 500. Den benötigten Satz angeben. | ||
+ | |||
+ | ==== 3) Simplex ==== | ||
+ | {{: | ||
+ | |||
+ | **a)** Zulässige Menge zeichnen. Optimallösung markieren. | ||
+ | |||
+ | Für die folgenden Aufgaben war die Standardform des Problems gegeben: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **b)** Primaler Simplex. Start mit B=(1,3), x_B = (3,3). Stoppt im Pricing der 2. Iteration. | ||
+ | |||
+ | **c)** Dualer Simplex. Start mit B = (1,4), z_N = (0.5,0.5). Stoppt im Pricing der 2. Iteration. | ||
+ | |||
+ | ==== 4) Graphen ==== | ||
+ | {{: | ||
+ | |||
+ | Gegeben ist ein einfacher, zusammenhängender Graph G=(V,E) (Bild oben). Ein Kantengraph K(G) = (V', | ||
+ | |||
+ | **a)** K(G) für obiges G zeichnen. | ||
+ | |||
+ | **b)** Zu beweisen: Für jede Kante e = (v,w) in G gilt: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Folgendes Lemma darf für den Beweis verwendet werden: Wenn G einfach ist, ist auch K(G) einfach. | ||
+ | |||
+ | **c)** Zu beweisen: Wenn G eulersch ist, ist auch K(G) eulersch. | ||
+ | |||
+ | **d)** Zu begründen: Die Gegenrichtung von c) gilt im Allgemeinen nicht. | ||
+ | |||
+ | ==== 5) Verständnis ==== | ||
+ | **a)** Dijkstra auf folgendem Graph ausführen. Distanzlabels und Vorgängerstruktur müssen erkennbar sein, und der besuchte Knoten soll markiert werden. | ||
+ | |||
+ | {{: | ||
+ | |||
+ | **b)** Zu begründen: das Minimalkostenflussproblem kann verwendet werden, um **(i)** das Kürzeste-Wege-Problem, | ||
+ | |||
+ | **c)** Gegeben ist Graph G: | ||
+ | |||
+ | {{: | ||
+ | |||
+ | Basissystem und Kreissystem von M(G) sowie M*(G) angeben. | ||
+ | |||
+ | **d)** Wahr/ | ||
+ | * Falls die Menge der zulässigen Lösungen für das primale Problem leer ist, ist das duale Problem unbeschränkt. | ||
+ | * Wenn das duale Problem eine endliche Optimallösung hat, hat auch das primale Problem eine endliche Optimallösung | ||
+ | * Wenn das duale Problem unbeschränkt ist, ist auch das primale Problem unbeschränkt. | ||
+ | * Wenn das primale Problem unbeschränkt ist, hat das duale Problem keine zulässige Lösung |