Bastian Rückel Boeken

Das Ziel dieser Abhandlung ist es, eine Einteilung der 90 Vereine in der Landesliga Bayern in die fünf Staffeln zu bestimmen, so dass in jeder Staffel gleich viele Teams sind. Des Weiteren soll jedem der 90 Vereine garantiert werden, dass seine Mannschaft, an keinem Spieltag, der unter der Woche statt findet, länger als eine Stunde fahren muss. Die Fahrtzeit soll demnach an allen Wochentagsspielen höchstens 60 Minuten betragen. Diese Forderung ist vor allem deshalb sinnvoll, da die meisten Spieler und Trainer voll berufstätig sind oder studieren und bei weiten Auswärtsfahrten unter der Woche stets Probleme haben, rechtzeitig vom Arbeitsplatz bzw. von der Universität zum Spielort zu gelangen. Die Summe aller Fahrten aller Teams im Verlaufe der Saison soll aus Umweltschutzgründen und aufgrund einer Kosten- und Aufwandsminimierung für die Vereine und deren Spieler möglichst gering sein. Als mögliche Kriterien eignen sich hierbei die gesamte Fahrtstrecke bzw. die gesamte Fahrtzeit. Für die dadurch gegebene Gruppeneinteilung soll schließlich für jede der fünf Staffeln ein Spielplan konzipiert werden, der möglichst fair ist, Wünsche der Vereine berücksichtigt und an Wochenspieltagen kein einziges Spiel enthält, bei dem die Gastmannschaft länger als eine Stunde anreisen muss. In Kapitel 4 wird diese Problemstellung mit allen ihren Bedingungen nochmals aufgegriffen und als ein binäres Programm formuliert. Anschließend wird das gestellte Problem mit Hilfe von Dekompositionen gelöst.

Das Ziel dieser Arbeit liegt darin, für ein gegebenes Wassernetzwerk eine Software zu entwickeln, welche die Betriebsführung unterstützt. Dabei soll die Software Ein- und Ausschaltzeitpunkte der Pumpen, Zeitpunkte des Fremdwasserbezugs, Zeitpunkte der Nutzung des Einspeisers sowie Öffnungszeitpunkte der Klappe mit dem zugehörigen Öffnungswinkel ausgeben, so dass der stündlich wechselnde Bedarf der Verbraucher zu minimalen Kosten gedeckt wird. Die Kosten sollen aufgeschlüsselt nach Energie und Wasser berechnet werden. Zudem sollen Ganglinien für die Füllstände der vier Behälter graphisch erzeugt werden. Zulässig ist ein Fluss nur, wenn bei den Behältern minimale Füllstände nicht unterschritten und maximale Füllstände nicht überschritten werden. Kosten entstehen durch den Stromverbrauch, welcher beim Betrieb der Pumpen anfällt, sowie durch den Bezug von Wasser vom Fremdwasserlieferanten und vom Brunnen. Mit dem Fremdwasserlieferanten existiert ein Tarifvertrag, der zeitabhängig unterschiedliche Kosten für bezogenes Wasser vereinbart. Die Kosten für das Brunnenwasser sind konstant. Umsonst ist dagegen das Wasser des Einspeisers und der Quelle. Allerdings sind alle vier Möglichkeiten der Wasserbeschaffung (stündlich) in ihrer Kapazität beschränkt. Erschwert wird das Problem dadurch, dass der Optimalwert aus Gründen der Materialschonung mit möglichst wenigen Pumpenschaltungen realisiert werden soll. Druckverläufe, die dazu führen, dass das Problem mit Hilfe von Differentialgleichungen gelöst werden müssten, sollen nicht berücksichtigt werden. Neben einer Modellierung als gemischt ganzzahliges Programm bzw. als lineares Programm wird vor allem auf den Einsatz von verschiedenen Heuristiken zur Optimierung des Netzwerks eingegangen.

Gang der Untersuchung: Nach einigen einführenden Worten wird zunächst auf Grundlagen eingegangen, welche bei der späteren Bearbeitung der Mehrgüterflüsse benötigt werden. Anschließend sollen Max-Flow-Probleme, welche ein Spezialfall der Mehrgüterflüsse sind, dargestellt werden. Danach werden die Mehrgüterflüsse, welche im Folgenden auch als Multicommodity-Flows bezeichnet werden, und ihre Darstellung durch verschiedene Lineare Programme aufgezeigt. Diese stellen für die Spaltenerzeugung, reduzierten Kosten und die Dantzig_Wolfe Dekomposition, welche als geschickte Lösungsverfahren für das Multicommodity-Flow Problem aufgefasst werden können, eine geeignete Formulierung dar. Schließlich wird noch ein praxisnahes Beispiel aus dem Bereich ÖPNV beschrieben.