Instituts-Logo Logik in der Informatik
PD Dr. Louchka Popova-Zeugmann 		Humboldt-Logo

Vorlesung Lineare Optimierung

Aktuelles  Einführung  Skripte  Logbuch  Vorlesungsbetrieb  Übungen  Aufgaben  Prüfung Literatur

Aktuelles

Um die Vorlesung besuchen zu können, müssen Sie sich neben Agnes auch in Moodle anmelden. Der Einschreibeschlüssel wird Ihnen über Agnes mitgeteilt. Zu jeder Vorlesungsstunde wird es eine kurze Einleitung als Video in Moodle geben. Darüber hinaus werden die Seiten im Skript angegeben, die zu der jeweiligen Vorlesung gehören.

Übungen finden zu den angegebenen Zeiten statt, allerdings in Form von Frage und Antwort im Forum in Moodle. Es steht Ihnen frei, wann Sie Ihre Fragen stellen. Zu den Übungszeiten werden sie zeitnah beantwortet. Neben den schriftlichen Übungsaufgaben werden Ihnen Aufgaben zum selbstständigen Üben bereitgestellt.

Die Übungsaufgaben werden über Moodle eingereicht. Bitte bilden Sie Zweier- oder Dreiergruppen.

Einführung

Inhalt:  Die Optimierung beschäftigt sich mit der Findung der besten Lösung(en) eines Problems. Die LO untersucht Probleme, bei denen die Gesamtheit aller Lösungen durch lineare (Un-)Gleichungen und das Ziel als eine bzw. mehrere lineare Funktionen gegeben sind. Angewand in technischen, betriebs- und volkswirtschaftlichen Zusammenhängen, dient die bereits in der Planung eingesetzte Optimierung dazu, knappe Ressourcen so effektiv wie möglich zu verwenden bzw. ein gewünschtes Ergebnis mit möglichst geringem Ressourcenverbrauch zu erreichen. In dieser Vorlesung werden wir die klassischen Lösungsverfahren kennenlernen: Simplexmethode, duale Simplexmethode, Methode der Potentiale zur Lösung der klassischen Transportaufgabe, sowie die Grundidee des polynomialen Algorithmus von Chatchijan der eingeschriebenen Ellipsoide. Die entwickelten Verfahren werden wir auch zur Lösung von 1-parametrischen LO-Aufgaben, verschiedenen Transportaufgaben und zur Lösung von Aufgaben aus der Spieltheorie anwenden.


Skripte und Manuskripte

Beispiel zur 1. Vorlesung vom 21.4.2020

Definition Skalarprodukt

Das Skript zur Vorlesung: als pdf-File.

1. Anhang: Anmerkung zum Beweis des Lemmas 3, Kapitel 1 (als Manuskript): pdf-File oder als Skript pdf-File (mit Dank an Lucas Emmerich für die Erstellung der tex-Version).
2. Anhang: Gomory-Schnitt: pdf-File.
3. Anhang: Zur Ellipsoidenmethode (als Manuskript): pdf-File.
4. Anhang: Beweis des Satzes 2 aus dem Kapitel 5 (als Manuskript): pdf-File.

Logbuch

Im Logbuch finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Räume
V: montags      11:00 - 13:00   Rudower Chaussee 26,  Raum 1'303
    dienstags      15:00 - 17:00   Rudower Chaussee 26,  Raum 1'303
Ü: montags       09:00 - 11:00   Rudower Chaussee 26,  Raum 1'303

Dozentin
PD Dr. Louchka Popova-Zeugmann

Übungsaufgaben

Es wird regelmäßig Übungsaufgaben geben, deren erfolgreiche Bearbeitung (mindestens 50% der Punkte) Voraussetzung für den Scheinerwerb und die Zulassung zur Prüfung ist.

Hausaufgabenblatt   1: als pdf-File, Abgabe: 04.05.2020, 9:00 Uhr
Hausaufgabenblatt   2: als pdf-File, Abgabe: 11.05.2020, 9:00 Uhr
Hausaufgabenblatt   3: als pdf-File, Abgabe: 18.05.2020, 9:00 Uhrr
Hausaufgabenblatt   4: als pdf-File, Abgabe: 25.05.2020, 9:00 Uhr
Hausaufgabenblatt   5: als pdf-File, Abgabe: 02.06.2020, 9:00 Uhr
Hausaufgabenblatt   6: als pdf-File, Abgabe: 08.06.2020, 9:00 Uhr
Hausaufgabenblatt   7: als pdf-File, Abgabe: 15.06.2020, 9:00 Uhr
Hausaufgabenblatt   8: als pdf-File, Abgabe: 22.6.2020, 9:00 Uhr: fakultativ
Hausaufgabenblatt   9: als pdf-File, Abgabe: 22.6.2020, 9:00 Uhr
Hausaufgabenblatt 10: als pdf-File, Abgabe: 29.06.2020, 9:00 Uhr
Hausaufgabenblatt 11: als pdf-File, Abgabe: 06.07.2020, 9:00 Uhr; Die Lösungen sind in Moodle zu finden.
Hausaufgabenblatt 12: als pdf-File, Abgabe: 17.07.2020, 9:00 Uhr; fakultativ

Prüfung

Für die Zulassung zur Prüfung müssen mindestens 50% der Punkte in den Übungaufgaben erworben werden. Die Prüfung ist mündlich und dauert 30 Minuten.

Prüfungsthemen   als pdf-File.

Prüfungstermine:     

20.08.2020, und beim Bedarf noch am 21.08.2020.
   
19.10.2020, und beim Bedarf noch am 20.10.2020.

Literatur

[PZ]
 Popova-Zeugmann, Skript zur Vorlesung, HUB, 2012
[F]
 R. Fletcher, Practical Methods of Optimisation, John Wiley & Sons-Verlag, 2te Auflage, 1995
[M]
 P. Morris, Introduction to  Game Theory, Springer-Verlag, 1994


Last modified:   Mo   6 Jul 2020 15:10:56   CEST 2020
L. Popova-Zeugmann