Logik in der Informatik
PD Dr. Louchka Popova-Zeugmann

Vorlesung Lineare Optimierung

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

Aktuelles

Die Vorlesungen und Übungen vom 10.1.2019 bis 18.1.2019 fallen wegen Krankheit aus.

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

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

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

Informationen zum Vorlesungsbetrieb

Zeiten und Raum: V: mittwochs 9:30 - 11:00 Rudower Chaussee 26, Raum 0'313; donnerstags 9:30 - 11:00 Rudower Chaussee 26, Raum 0'313; Ü: mittwochs 11:15 - 12:45 Rudower Chaussee 26, Raum 0'313; donnerstags 11:15 - 12:45 Rudower Chaussee 26, Raum 0'313
Dozent: PD Dr. Louchka Popova-Zeugmann
Tutor: Arsen Hnatiuk

Ü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: 31.10.2018, vor der Vorlesung

Hausaufgabenblatt 2: als pdf-File, Abgabe: ~~7.11.2018,~~ 8.11.2018, vor der Vorlesung (s. auch unter "Aktuelles")

Hausaufgabenblatt 3: als pdf-File, Abgabe:14.11.2018, vor der Vorlesung

Hausaufgabenblatt 4: als pdf-File, Abgabe:21.11.2018, vor der Vorlesung

Hausaufgabenblatt 5: als pdf-File, Abgabe: 28.11.2018, vor der Vorlesung

Hausaufgabenblatt 6: als pdf-File, Abgabe: 5.12.2018, vor der Vorlesung

Hausaufgabenblatt 7: als pdf-File, Abgabe: 12.12.2018, vor der Vorlesung

Hausaufgabenblatt 8: als pdf-File, Abgabe: 19.12.2018, in dem Briefkasten gegenüber von R. 425 im Haus III, 4. Etage, in der Zeit 9:00 bis 11:00

Aufgaben für 19.12.2018 und 20.12.2018 als pdf-File.

Hausaufgabenblatt 9: als pdf-File, Abgabe: 23.1.2019, vor der Vorlesung

Hausaufgabenblatt 10: als pdf-File, Abgabe: 30.1.2019, vor der Vorlesung

Hausaufgabenblatt 11: als pdf-File, Abgabe: 6.2.2019, vor der Vorlesung

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:

22. Februar 2019, und beim Bedarf noch am 25. Februar 2019.

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: Mi 30. Jan 14:39:34 CET 2019
L. Popova-Zeugmann