Internetseite von Dr. rer. nat. Markus Herrich

Mathematisches Seminar Lineare Optimierung und Anwendungen

für Studierende des Lehramtes an Gymnasien und Berufsbildenden Schulen (Module MN-SEGY-MAT-SEM bzw. MN-SEBS-MAT-SEM)


Umfang der Lehrveranstaltung: 2 SWS

Zeit und Raum: Do 5.DS im Raum WIL/C104

Inhalt:
Bei einem Optimierungsproblem geht es darum, eine Zielgröße, die von einer oder mehreren Entscheidungsvariablen abhängt, zu minimieren oder zu maximieren. Das heißt, es sind Werte für die Entscheidungsvariablen gesucht, für die die Zielgröße so klein wie möglich oder so groß wie möglich ist. Dabei müssen die Entscheidungsvariablen allerdings noch gewisse Nebenbedingungen, meistens durch Ungleichungen und/oder Gleichungen beschrieben, einhalten.
Charakteristisch für ein lineares Optimierungsproblem ist, dass zwischen Zielgröße und Entscheidungsvariablen ein linearer Zusammenhang besteht und außerdem die Nebenbedingungen ausschließlich durch lineare Ungleichungen und/oder Gleichungen definiert werden.
Nachdem wir im ersten Vortrag einige Grundbegriffe eingeführt und einige praktische Probleme, die sich als lineare Optimierungsprobleme modellieren lassen, kennengelernt haben, beschäftigen wir uns im zweiten Vortrag mit graphischen Verfahren zur Lösung von (kleinen) linearen Optimierungsproblemen. Außerdem beschäftigen wir uns mit der Frage nach der Anzahl optimaler Lösungen eines linearen Optimierungsproblems. Danach werden wir mit der Fourier-Motzkin-Elimination ein erstes rechnerisches Verfahren zur Lösung von linearen Optimierungsproblemen kennenlernen, werden aber auch sehen, dass dieses bei größeren Problemen unpraktikabel ist.
Anschließend beweisen wir den Hauptsatz der linearen Optimierung, der besagt, dass es ausreichend ist, nur endlich viele Punkte aus dem zulässigen Bereich (mit gewissen Eigenschaften) zu betrachten, um eine optimale Lösung des linearen Optimierungsproblems zu finden. Diese Aussage macht sich das Simplexverfahren zunutze - eines der wichtigsten Verfahren der linearen Optimierung, mit dem wir uns ausführlich auseinandersetzen werden.
Als Anwendung werden wir uns mit der Transportoptimierung befassen. Wir werden sehen, dass es sich bei einem Transportproblem in der Tat um ein linaeres Optimierungsproblem handelt, sodass zu seiner Lösung pronzipiell das Simplex-Verfahren verwendet werden könnte. Es wird sich aber herausstellen, dass aufgrund der speziellen Struktur des linearen Optimierungsproblems angepasstere Verfahren zweckmäßiger sind, weil sie einen geringeren Aufwand erfordern.
Zu guter Letzt wollen wir uns noch zwei Beispiele für Software, mit der sich lineare Optimierungsprobleme lösen lassen, anschauen.

Literatur:
Als Literatur werden wir ausgewählte Abschnitte der folgenden Lehrbücher verwenden:
  • Dempe, S., Unger, T.: Lineare Optimierung. Vieweg + Teubner, Wiesbaden, 2010. (Kapitel 1-4)
  • Geiger, C., Kanzow, C.: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, Berlin, 2002. (Abschnitt 3.1.1)
  • Koop, A., Moock, H.: Lineare Optimierung. Eine anwendungsorientierte Einführung in Operations Research. Springer, Berlin, 2008. (Kapitel 5 und 9)
Die relevanten Abschnitte wurden allen in der 1. Veranstaltung als Kopien zur Verfügung gestellt. Zumindest die ersten beiden genannten Lehrbücher sind auch in der SLUB ausleihbar.

Vortragsthemen und Zeitplan:
Es sind Vorträge zu den folgenden Themen geplant.
  1. Motivation, Grundbegriffe, Modellierung (am 26.10.2017)
  2. Graphische Lösung von linearen Optimierungsproblemen (am 02.11.2017)
  3. Die Fourier-Motzkin-Elimination - ein erstes rechnerisches Verfahren zur Lösung linearer Optimierungsprobleme (am 09.11.2017)
  4. Normalform und zulässige Basislösungen eines linearen Optimierungsproblems (am 16.11.2017)
  5. Hauptsatz der linearen Optimierung (am 23.11.2017)
  6. Das Simplexverfahren (in vektorieller Form) (am 30.11.2017)
  7. Tableauform des Simplexverfahrens (am 07.12.2017)
  8. Zwei-Phasen-Simplexverfahren, Entartung (am 14.12.2017)
  9. Das klassische Transportproblem: Definition und Aussagen zur Lösbarkeit (am 04.01.2018)
  10. Basislösungen eines Transportproblems, Bestimmung einer ersten zulässigen Basislösung (am 11.01.2018)
  11. Stepping-Stone-Verfahren zur Lösung eines Transportproblems (am 18.01.2018)
  12. Ein schnelleres Verfahren zur Lösung eines Transportproblems (am 25.01.2018)
  13. Lineare Optimierung mit mehreren Zielfunktionen (am 01.02.2018)
  14. Lösung von linearen Optimierungsproblemen mit dem Excel-Solver und mit der MATLAB-Funktion "linprog" (am 01.02.2018, ausnahmsweise in der 6.DS)