|
Diskrete Optimierung I (DiskOpt I)5 ECTS (englische Bezeichnung: Discrete optimization I)
(Prüfungsordnungsmodul: Diskrete Optimierung I)
Modulverantwortliche/r: Alexander Martin Lehrende:
Andreas Bärmann
Start semester: |
WS 2019/2020 | Duration: |
1 semester | Cycle: |
jährlich (WS) |
Präsenzzeit: |
45 Std. | Eigenstudium: |
105 Std. | Language: |
Deutsch |
Lectures:
-
-
Diskrete Optimierung I
(Vorlesung, 2 SWS, Andreas Bärmann, Wed, 10:00 - 12:00, H12)
-
Tutorial zu Diskrete Optimierung I
(Übung, 1 SWS, Andreas Bärmann, Wed, 14:00 - 16:00, Übung 5 / 01.254-128)
Empfohlene Voraussetzungen:
Lineare Algebra, Kombinatorische Optimierung
Inhalt:
Die Vorlesung behandelt theoretische und praktische Grundlagen zur
Lösung schwieriger gemischt-ganzzahliger linearer Optimierungsprobleme
(MIPs). Zunächst werden Kerndefinitionen der NP-Vollständigkeit behandelt und einige der bekannten NP-vollständigen Probleme vorgestellt. Im Bereich der Polyedertheorie werden die Grundlagen der Seitenstruktur konvexer Polyeder behandelt. Darauf aufbauend werden Schnittebenenverfahren sowie Branch-and-Cut Verfahren zur Lösung von MIPs gelehrt. Abschließend studieren wir einige klassische Probleme der Diskreten Optimierung wie das Rucksack-Problem, das Traveling-Salesman-Problem oder das Set-Packing-Problem.
Lernziele und Kompetenzen:
Die Studierenden
verfügen über grundlegende theoretische Erkenntnisse zur Lösungemischt-ganzzahliger linearer Optimierungsprobleme (MIPs),
können MIPs mittels verfügbarer Standard Software lösen.
Literatur:
- Vorlesungsskript zu diesem Modul
Conforti, Cornuéjols, Zambelli: Integer Programming, Springer 2014
B. Grünbaum, Convex Polytopes, Springer, 2003
B. Korte, J. Vygen: Combinatorial Optimization, Springer 2005
G. L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization, Wiley 1994
A. Schrijver: Theory of Linear and Integer Programming, Wiley 1986
L.A. Wolsey: Integer Programming, Wiley 1998
G. Ziegler, Lectures on Polytopes, Springer, 1995
Bemerkung:
- Wahlmodul: Master Mathematik, Technomathematik und Wirtschaftsmathematik
Kern-/Forschungsmodul Master Mathematik Studienrichtung „Modellierung, Simulation, Optimierung“, Master Technomathematik Studienrichtung „Optimierung“, Master Wirtschaftsmathematik Studienrichtung „Optimierung und Prozessmanagement“
Organisatorisches:
Neben der Vorlesung werden Übungen angeboten, in denen die
Studierenden von einem Übungsgruppenleiter betreut werden. Anhand von
Präsenz- und Hausaufgaben werden wesentliche Lerninhalte geübt. Bis WS 14/15 hieß das Modul "Theoretische Grundlagen der Diskreten Optimierung"!
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Mathematik (1. Staatsprüfung für das Lehramt an Gymnasien)
(Po-Vers. 2019w | NatFak | Mathematik (1. Staatsprüfung für das Lehramt an Gymnasien) | Module Fachwissenschaft Mathematik | Wahlpflichtbereich Angewandte Mathematik | Diskrete Optimierung I)
Dieses Modul ist daneben auch in den Studienfächern "Mathematik (Master of Science)", "Technomathematik (Master of Science)", "Wirtschaftsmathematik (Master of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Diskrete Optimierung I (Prüfungsnummer: 59251)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 15, benotet, 5 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- Erstablegung: WS 2019/2020, 1. Wdh.: WS 2019/2020
1. Prüfer: | Andreas Bärmann |
|
|
|