Modulbeschreibung
Operations Research 1
Kurzzeichen:
Unterrichtssprache:
ECTS-Credits:
Leitidee:
Die Studierenden lernen Modellierungsansätze und mathematische Methoden kennen, die helfen, anspruchsvolle Optimierungsaufgaben aus der Industrie und der Betriebswirtschaft erfolgreich zu bearbeiten. Die bearbeiteten Anwendungen liegen vor allem im Operations-Management & Logistics, sind aber genauso in Service und Dienstleistung anwendbar.
Fokus liegt auf der mathematischen Modellierung von deterministischen Systemen (stochstische Problemstellungen werden in OPRE2, FS angegangen) und auf der selbstständigen Entwicklung von einfachen Algorithmen für praktische Optimierungsaufgaben. Erklärtes Ziel ist es, ausreichend Anwendungskompetenzen zu vermitteln, dass Sie sich zutrauen, die Ansätze selbstständig in der Praxis anzuweden.
Modulverantwortung:
Standort (angeboten):
Zusätzliche Eingangskompetenzen:
- Basismathematik (Umgang mit Vektoren und Matrizen)
- APROG (einfache Kontrollstrukturen (IF, FOR) in Python)
Modultyp:
Bemerkungen:
Modul ist besonders empfehlenswert für Studierende, die sich für Operations Management & Logistics interessieren und sich eventuell vorstellen könnten, ihre Bachelorarbeit in diesem Themengebiet zu machen.
Workload [h]
Vorlesung: 28
Übungen: 28
Selbststudium: 64
Total: 120
Modulbewertung:
Leistungsnachweise und deren Gewichtung
Modulschlussprüfung:
Bemerkungen zur Prüfung:
Schwerpunkt Mathematische Programmierung und Graphentheorie
Dauer: 60 Minuten, Anteil an der Note 50%
Bei der Prüfung erlaubt sind:
- closed book mit eigener Zusammenfassung auf 2 Blatt A4, beidseitig beschrieben (=4 Seiten)
-Taschenrechner (keine kommunikationsfähigen Geräte)
Während der Unterrichtsphase:
überschaubares Projekt in Kleingruppe (2 Personen) mit Schwerpunkt "Anwendung Kombinatorische Optimierung",
Anteil an der Note 50%
Leistungsnachweis über Kolloqium (im Semester):
-abzugeben: kurze Dokumentation (max. 8 Seiten Text mit Abbildungen) und Code (lauffähige Datei)
-Bewertung im Rahmen eines Kolloquiums (max. 20 min pro Gruppe, Präsentation und Fragerunde). Aus einer Nichteilnahme am Kolloqium resultiert die Projektnote 1.0.
Bewertungsart:
Gewichtung:
50% schriftliche Prüfung
50% Projekt
Bemerkungen:
Inhalte
Angestrebte Lernergebnisse (Abschlusskompetenzen):
Fachkompetenzen
Die Teilnehmenden:
-können (Operations-Research) Modelle herleiten, simulieren, analysieren, validieren und ggf. verbessern
-können gut dokumentierte Heuristiken und Algorithmen korrekt ausführen, richtig anwenden und ggf. für eigene Bedürfnisse anpassen
-lernen grosse komplexe Probleme in kleinere, überschaubarere Probleme herunterzubrechen und durch Trial-and-Error sich langsam aber sicher an wirksame Lösungen heranzutasten
Methodenkompetenzen
Die Teilnehmenden:
-können für einfache und mittelschwere Aufgabenstellungen ein adäquates mathematisches Programmierungsmodel aufstellen und mit einem Solver lösen.
-können für einfache und mittelschwere Aufgabenstellungen ein adäquates graphentheoretisches Modell aufstellen und mit bekannten Algorithmen lösen.
-können Konstruktionsheuristiken und Verbesserungsheuristiken entwickeln für Optimierungsaufgaben aus der Praxis, die zu gross sind, um mit einem Standard ILP Solver zu lösen.
Selbstkompetenzen
Die Teilnehmenden:
-gewinnen Selbstverstrauen, Mut und Kreativität in der Arbeit mit quantitativen Methoden (insbesondere im Bereich Operations-Management & Logistics).
-können die Grenzen der erlernten Methoden einschätzen.
Sozialkompetenzen
Die Teilnehmenden:
-können bei der Erstellung von Modellen effektiv zusammenarbeiten.
-können durch gezieltes Nachfragen aus unvollständigen Angaben und vagen Zielvorstellungen eine adäquate Aufgabenstellung herleiten.
Modul- und Lerninhalt:
Themen/Lernblock: Mathematische Programmierung
- Einführung: Variablen, Parameter und Indices als Bausteine für lineare Modelle mit Zielfunktion und Nebenbedingungen.
- Modelle mit binären Variablen; Modellierung von logischen Nebenbedingungen (A oder B, A und B, wenn A dann B), Sprungkosten u.v.m.
- Standard (Matrix-) Form der mathematischen Programmierungsmodelle; Optimierung mit Hilfe von open-source zugänglichen Solvern (Python); Interpretation und Validierung der Ergebnisse.
Themen/Lernblock: Kombinatorische Optimierung
- Einführung: globales Optimum, lokales Optimum, Nachbarschaft.
- Konstruktionsheuristiken & Verbesserungsheuristiken.
- Neustarts & Randomisierung.
- Umsetzung an individuellen Praxis-Beispielen: Projektarbeit in Kleinruppen. (vgl. Leistungsnachweis)
Themen/Lernblock: Graphentheorie
- Einführung: Knoten und Kanten; Pfade, Bäume und Flüsse; Kanten- und Knotenfärbungen.
- Algorithmen zur Bestimmung des kürzesten Pfades, des minimalen Spannbaums und des maximalen Flusses. Übersicht der breiten Anwendungsmöglichkeiten dieser Algorithmen.
- Umsetzung und Optimierung mit bestehenden Packages in Python.
- Das Traveling Salesman Problem und die sogenannte «kombinatorische Explosion».
Lehrmittel/-materialien:
Pflichtliteratur wie Skript, Bücher
- Folienskript
- Zusammengestellte Unterlagen
Weiterführende Literatur (Empfehlung an Studierende)
-
Winston, Wayne L., Operations Research: Applications and Algorithms., Vol. 4., Duxbury Press, 2004.
-
Holger H. Hoos & Thomas Stützle, Stochastic Local Search: Foundations and Applications, Morgan Kaufmann / Elsevier, 2004.
-
Sebastian Stiller: Planet der Algorithmen; Knaus Verlag, 2015 [Auszug] beschreibt das Konzept des Dijkstra Algorithmus anschaulich und gibt Hinweise, wie der Algorithmus in sehr umfangreichen Graphen zum Einsatz kommt (Navigationsgeräte)