 |
Optimierungsprobleme finden sich überall:
Gemein haben die Probleme, dass aus einer Vielzahl an Lösungen eine beste ausgewhält werden soll. Zum Glück, lassen sich all dies sind Fragen mit Methoden der mathematische Optimierung lösen. Dazu müssen in einem ersten Schritt die Fragestellung mathematisch Formuliert werden, danach die Eigenschaften von optimalen Lösungen analysiert werden, um effiziente Lösungsalgorithmen zu generieren. Und wie dies funktioniert sollt ihr in dieser Nachmittags AG lernen. |
OptiQuest ist eine neue Nachmittags AG, die aus einer Kooperation mit der RWTH Aachen und dem Schülerlabor CAMMP am Einhard Gymnasium entstanden ist. In der AG werdet ihr lernen, was mathematische Optimierung bedeutet und wie man mithilfe von verschiedenen effizienten Algorithmen typische und auch untypische Probleme lösen kann. In einem Jahr wirst du verstehen wofür MIP steht, was ein minimal aufspannender Baum ist und wie vielfältig Algorithmen sein können.
Das Programm der AG besteht insgesamt aus vier Teilen. Im ersten Teil werden wir erste Optimierungsprobleme und ihre mathematischen und algorithmischen Eigenschaften kennenlernen. Danach lernen wir die ganzzahlige Programmierung kennen, mir der viele Optimierungsprobleme gelöst werden können. In Teil 3 seid ihr dran und werdet euer eigenes Optimierungsprojekt lösen. Der letzte Teil behandelt noch mal vertiefende Kenntnisse zu Algorithmen.
Wenn wir dich neugierig gemacht haben, schau hier nach, wie du dich anmelden kannst.
Wir freuen uns auf dich!
| Name | OptiQuest Nachmittags AG |
| Wo? | Einhard Gymnasium, Raum 203-204 |
| Wann? | Dienstags, 14.00 - 15.30 Uhr |
| Für wen? | Klassenstufe 10 bis Q2 |
| Starttermin: | 24.09.2024 |
| Endtermin: | 09.07.2025 |
| Anmeldungsdeadline: MM | 02.09.2024 |
| Ansprechpartnerin: | Janina Gerke  |
Falls dich die AG interessiert und du in der Stufe 10 bis Q1 bist, schreibe uns bis zum 02.09.2024 eine Mail mit folgenden Informationen:
Wir melden uns bei dir bis zum 02.09.2024, ob du an der AG teilnehmen kannst.
Das Programm besteht aus vier Teilen und läuft über das gesamt Schuljahr 2024/2025.
Hier lernst du die grundlegenden Optimierungsprobleme aus der diskreten Optimierung kennen, mathematische Eigenschaften der optimalen Lösungen und Algorithmen, um die Probleme optimal zu lösen.
Themen: Euler-Touren, minimal aufspannende Bäume, kürzestes Wege, maximale Matchings, Optimalitätskriterien, Dijkstra-Algorithmus, Algorithmus von Prim
Ganzzahlige Optimierung ist ein mächtiges Werkzeug, um eine vielzahl an Optimierungsproblemen zu modellieren und im Anschluss zu lösen. Hier lernen wir die wichtigsten Techniken dazu kennen.
Themen: Lineare Programme, ganzzahlige Programme, Branch and Bound, Knapsack Problem, Simplex Algorithmus, Facility Location
Optimierungsprobleme sind überall zu finden. In diesem Teil geht es darum, dass ihr euer eigenes Problem mathematische Modelliert, lösen lasst und am Ende die Lösung interpretiert.
Themen: Optimierungskreislauf, mathematisches Formulieren, Analysieren, Lösungsalgorithmen entwickeln, Analysieren, Präsentireen
Nicht immer können wir optimale Lösungen berechnen. Hier lernen wir allgemeine Techniken kennen, wie man guten Lösungen erhält.
Themen: Greedy Algorithmen, Lokale Suche, P vs. NP, Traveling Salesperson Problem, Matroide, Minimum Cost Flow, Approximationsalgoirthmen
Apothekennotdienste stellen eine durchgängige Versorgung mit Arzneimitteln sicherstellen. Das Ziel der Planung besteht darin, täglich einem Teil der Apotheken 24-Stunden Dienste zuzuweisen, sodass eine angemessene Versorgung gewährleistet und gleichzeitig die Belastung der Apotheken minimiert wird.
In vielen Gebieten Deutschlands wird der Apothekennotdienst noch händisch geplant, was viel Zeit in Anspruch nimmt und das Finden eines "optimalen" Plans praktisch ausschließt. Das liegt daran, dass während der Planung viele komplexe Entscheidungen getroffen werden müssen. Alleine in Aachen gibt es 2(74*365) Möglichkeiten den Notdienst für 74 Apotheken in einem Jahr mit 365 Tagen zu planen. Das entspricht ungefähr 108130 Möglichkeiten, also eine gigantische Zahl mit 8130 Stellen. Zum Vergleich: die Anzahl der Atome im Universum wird auf eine Zahl mit etwa 84 bis 89 Stellen geschätzt.
Um den besten Notdienstplan zu finden, können wir also nicht alle Pläne ausprobieren, sondern müssen clevere Algorithmen einsetzen. Hier kommt die Mathematische Optimierung ins Spiel, die sich damit beschäftigt, wie optimale Lösungen für praktische Probleme effizient berechnet werden können. Ein mächtiges Werkzeug der Mathematischen Optimierung ist die Ganzzahlige Lineare Programmierung. Diese werden wir in diesem Workshop kennenlernen und nutzen, um die Notdienstplanung mathematisch zu modellieren und einen optimalen Plan zu berechnen.
Wir wollen den Apothekennotdienst einer Region mit fünf Orten und neun Apotheken für einen Zeitraum von einer Woche planen. An jedem Wochentag müssen Notdienste an Apotheken vergeben werden. Dabei sollten einige Nebenbedingungen beachtet werden.
|
|
Im Beispiel sollen die Nebenbedingungen so lauten:
Aufgabe: Finde einen Notdienstplan für 6 Tage der alle Bedingungen erfüllt und möglichst wenig Dienste verteilt. Wenn du Lust hast, schicke uns deine Lösung zu.
Die Nachmittags AG OptiQuest ist eine Zusammenarbeit des Einhard Gymnasiums, der Kombinatorischen Optimierungsgruppe der RWTH Aachen und dem CAMMP Schülerlabor. Teilnehmen kann jeder, der Interesse an Mathematik hat und in den Stufen 10 bis Q1 ist.
| Einhard | |||
 |
Janina Gerke Lehrkraft für Mathematik und Informatik gerke@einhard-gymnasium.de |  |
Sebastian Zacharias Lehrkraft für Biologie und Chemie zacharias@einhard-gymnasium.de |
| a | |||
| RWTH Aachen | |||
 |
Christina Büsing Professorin für Kombinatorische Optimierunga buesing@combi.rwth-aachen.de |  a |
Anna-Maria Fischbach Hiwi im CAMMP Schülerlabor anna-maria.fischbach@rwth-aachen.de |
 |
Elena Stammen Mitarbeiterin im CAMMP Schülerlabor stammen@combi.rwth-aachen.de |
