Operations Research I: Lineare Programmierung
	Vorlesung im Sommersemester 2015
	Dozent: Peter Becker
	Studiengang: Bachelor Informatik, 4. Semester, Wahlpflicht

Vorlesungsankündigung

Unterlagen zur Vorlesung

1. Einführung Operations Research

   • Vorbemerkungen
   • Einführung
   • Weitere Quellen:
     • Wikipedia: Operations Research
     • Wikipedia: Lineare Optimierung
     • Wikipedia: Transportproblem
     • Wikipedia: Rucksackproblem
     • Wikipedia: Facility Location Problem (Standortplanung)

2. Mathematische Grundlagen

   • Dimension, Basis, Rang, Lineare Gleichungssysteme, Determinante
   • Algorithmen zur Lösung linearer Gleichungssysteme
   • Weitere Quellen:
     • Wikipedia: Körper
     • Wikipedia: Vektorraum
     • Wikipedia: Rang
     • Wikipedia: Lineares Gleichungssystem
     • Wikipedia: Permutation
     • Wikipedia: Permutationsgruppe
     • Wikipedia: Symmetrische Gruppe
     • Wikipedia: Fehlstand
     • Wikipedia: Signum
     • Wikipedia: Determinante
     • Wikipedia: Cramersche Regel
     • Wikipedia: Elementarmatrix
     • Wikipedia: Gaußsches Eliminationsverfahren
     • Wikipedia: Gauß-Jordan-Algorithmus

3. Grundlagen der linearen Programmierung

   • Lineares Programm, Grafische Lösung, Normalformen
   • Geometrie linearer Programme
   • Basislösungen
   • Weitere Quellen:
     • Wikipedia: Lineares Programm
     • Wikipedia: Umgebung
     • Wikipedia: Offene Menge
     • Wikipedia: Abgeschlossene Menge
     • Wikipedia: Rand
     • Wikipedia: Kompakte Menge
     • Wikipedia: Extremwertsatz
     • Wikipedia: Konvexe Menge
     • Wikipedia: Extremalpunkt
     • Wikipedia: Polytop
     • Wikipedia: Polyeder

4. Simplexalgorithmus

   • Primaler Simplexalgorithmus
   • Dualer Simplexalgorithmus, Vermeidung von Zyklen
   • Weitere Quellen:
     • Wikipedia: Simplex-Verfahren

5. Dualität

   • Konzept der Dualität
   • Dualitätssätze
   • Zweiphasen-Simplexalgorithmus
   • Weitere Quellen:
     • Wikipedia: Dualität in der Linearen Optimierung

6. Softwarewerkzeuge für die Lineare Programmierung

   • GNU Linear Programming Kit
   • Beispiele:
     • Beispiel 6.1
     • Beispiel 6.2
   • Weitere Quellen:
     • Homepage GNU Linear Programming Toolkit (GLPK)
     • GLPK Reference Manual
     • Für die Installation des GLPK unter OS X empfehle ich MacPorts.

7. Transport- und Zuordnungsprobleme

   • Transportproblem, Eröffnungsverfahren
   • Stepping-Stone-Methode
   • u-v-Methode, Zuordnungsproblem
   • Weitere Quellen:
     • Wikipedia: Transportproblem
     • Wikipedia: Stepping-Stone-Methode
     • Wikipedia: Umladeproblem
     • Wikipedia:Netzwerk-Simplexmethode
     • Wikipedia: Bipartiter Graph
     • Wikipedia: Zuordnungsproblem
     • Wikipedia: Ungarische Methode

Übungen

• Aufgabenblatt 1

  • Modell zu Aufgabe 2
  • Modell zu Aufgabe 3

• Aufgabenblatt 2

  • Lösungen zu den Aufgaben 1 bis 3
  • Source-Code zu Aufgabe 4

• Aufgabenblatt 3

  • Lösungen zu den Aufgaben 1 bis 3
  • Source-Code zu Aufgabe 4

• Aufgabenblatt 4

  • Lösung zu Aufgabe 1 (a)
  • Lösung zu Aufgabe 1 (b)
  • Lösung zu Aufgabe 1 (c)
  • Lösung zu Aufgabe 2 (a) (GeoGebra)
  • Lösung zu Aufgabe 2 (c) (GeoGebra)
  • Lösung zu den Aufgaben 3 und 4

• Aufgabenblatt 5

• Aufgabenblatt 6

  • Lösung zu Aufgabe 1 (a)
  • Lösung zu Aufgabe 1 (b)
  • Lösung zu Aufgabe 1 (c)
  • Lösung zu Aufgabe 2
  • Lösung zu Aufgabe 3 (a)
  • Lösung zu Aufgabe 3 (b)

• Aufgabenblatt 7

  • Lösung zu Aufgabe 1
  • Lösung zu Aufgabe 2

• Aufgabenblatt 8

  • Lösung zu Aufgabe 1 (a)
  • Lösung zu Aufgabe 1 (b)

• Aufgabenblatt 9

Literatur

Softwarewerkzeuge

• GNU Linear Programming Toolkit (GLPK)
• lp_solve Open Source LP-Solver
• LINGO von LINDO Systems Inc., Trial Versionen verfügbar
• Gurobi Optimizer Der zur Zeit wohl beste kommerzielle LP-Solver.
• IBM ILOG CPLEX Weit verbreiteter LP-Optimizer von IBM.