Abschlussarbeiten

Zusammenfassung: Die Grundversion des „Firefighter-Problems“ (FFP) sucht nach der „besten Vorgehensweise“, ein Feuer, das sich in einem Graphen über Kanten von Knoten zu Knoten ausbreitet, zu löschen, indem man ein oder mehrere Feuerwehrleute an die Knoten schickt. Ist ein Knoten gelöscht, bleibt das so, und die Ausbreitung des Feuers ist unterbrochen. Was genau „beste Vorgehensweise“ bedeutet, hängt von der genauen Problemstellung ab: Möglichst schneller Stillstand der Ausbreitung, möglichst viele unverbrannte Knoten etc. Je nach genauer Problemstellung ist das Problem effizient lösbar oder NP-schwer. Für die NP-schweren Fälle ist eine Modellierung als Ganzzahliges Lineares Programm (ILP) interessant: Die Untersuchung der Ganzzahligkeitslücke kann Resultate in Bezug auf Approximationsalgorithmen und andere Informationen liefern.

Aufgabe dieser Bachelorarbeit ist es, die verschiedenen Varianten des FFP vorzustellen, Beispiele für ihre Anwendbarkeit zu entwerfen und die Bedeutung und Ermittlung von Ganzzahligkeitslücken des ILP-Modells zu diskutieren. Darüber hinaus soll eine kritische Betrachtung des FFP in Zusammenhang mit der Bekämpfung der Ausbreitung von Viren vorgenommen werden. Testrechnungen auf eigenen Beispielen auf Basis der ILP-Modellierung mit verschiedenen Optionen (z. B. mit und ohne Feasibility Pump oder Ähnliches) im Lösungsprozess sollen beurteilt werden in Bezug auf Anwendungsfall und Lösungsmethode.
Abgabe: 31.07.2020

Zusammenfassung: Vernünftiges Verhalten einzelner Nationen in internationalen Verhandlungen zum Thema Klimaschutz ist ein aktuelles Problem. Im Buchbeitrag von Caleiro und Koautoren in der Literatur wird dieses Problem mit Hilfe von Spieltheorie modelliert.

Aufgabe dieser Bachelorarbeit ist es, die Spieltheorie, die für die Betrachtungen im Artikel gebraucht wird, zu erklären und die Übertragung auf den Anwendungsfall zu diskutieren. Dies soll vorwiegend mit Hilfe von eigenen Beispielen geschehen, die ggf. Stärken und Schwächen der spieltheoretischen Sichtweise aufzeigen.
Abgabe: 31.01.2020

Zusammenfassung: In der Spieltheorie wird der Erfolg der Mitspielenden traditionell in Form einer Auszahlung gemessen. Manchmal führt dies zu unerwünschten Effekten, wenn nämlich nur die Platzierung wichtig ist. Soetwas kann man sich im Sport bei großen Wettbewerben gut vorstellen. Um hier eine theoretische Untersuchungsgrundlage zu schaffen, haben Brandt und Koautoren in der Literatur Ranking Games (RG) eingeführt.

Aufgabe dieser Bachelorarbeit ist es, das Konzept von RG zu erklären, Beispiele aus dem Sport dafür zu betrachten und die Theorie im Sportkontext zu interpretieren. Ferner sollen für ganz konkrete Beipiel-Sport-RGs ganz konkrete Gleichgewichte mit den im Artikel angegebenen Methoden berechnet und interpretiert werden.
Abgabe: 31.01.2020

Zusammenfassung: Optimierte Fahrzeugeinsatzplanung (engl: Vehicle Routing Problem (VRP)) wird in verschiedensten Anwendungsfällen benötigt. Beispiele sind Rundtouren eines Handlungsreisenden (das klassische TSP), Pakete einsammeln und ausliefern, Einsatzplanung von Pannenhilfefahrzeugen, Robotereinsatzplanung, Winterdienst, . . .

Der Anwendungsfall dieser Bachelorarbeit scheint bislang wenig erforscht: Sicherheitsdienste. Die Besonderheit: die berechneten Touren sollten nicht leicht vorhersagbar sein. Häufigere Besuche desselben Ortes sollten möglich sein und zeitlich nicht zu nah aufeinanderfolgen. Eine Möglichkeit: Man berechnet nicht nur einen Routenplan sondern mehrere und wählt kurz vor der Anwendung einen davon zufällig aus. Dafür muss man ein Modell haben, das eine geeignete Menge von Routenplänen generiert.

Aufgabe dieser Bachelorarbeit ist es, ein Modell auf Basis der Gemischt-Ganzzahligen Linearen Optimierung (MILP) für eine VRP-Tourenplan-Menge zu entwickeln, dass die Belange eines Sicherheitsdienstes beachtet. Mindestens eine neue Klasse von Nebenbedingungen und/oder Kostenfaktoren muss einem klassischen VRP-Modelle auf Basis einer fundierten Diskussion hinzugefügt werden. Die Gestalt optimaler Lösungen soll anhand von konstruierten Beispielen und Testrechnungen bewertet werden.
Abgabe: 31.01.2020

Zusammenfassung: Im Problem Online-Searching versucht man in einem Graphen einen bestimmten Zielknoten zu finden. Den Sucherfolg bemerkt man erst, wenn man den Zielknoten erreicht. Das sogenannte Cow-Path Problem ist ein Spezialfall: Eine Kuh sucht ein Loch im Zaun und kann links oder rechts beginnen zu suchen und nach beliebieger Zeit auch umkehren. Ziel ist eine Online-Strategie, die, egal wo das Loch sich befindet, immer nur einen möglichst kleinen konstanten Faktor der Entfernung des Lochs vom Startpunkt laufen muss. Jaillet und Stafford haben dieses Problem in der Literatur auf Bäumen untersucht. Fleischer und Koautoren haben in der Literatur einige der Resultate verbessert.

Aufgabe dieser Bachelorarbeit ist es, Anwendungsfälle (z. B. Evakuierungsprobleme) von Online-Searching zu identifizieren und die aus der Theorie generierten Handlungsempfehlungen kritisch im Anwendungsfall zu bewerten.
Abgabe: 31.01.2020

Zusammenfassung: Man möchte einen Baumstamm in einem durch eine polygonale Mauer begrenzten Gelände vollständig herumdrehen. Wie lang kann der Baumstamm höchstens sein? Aufgabe dieser Bachelorarbeit ist es, theoretischen Überlegungen und Computer-Experimente zu Algorithmen vorzunehmen, die uns der Lösung dieser Frage (in idealisierter Form) näher bringen. Das Problem selbst ist bislang offen, so dass jede Form von Fortschritt erwünscht ist. Teil der Aufgabe ist eine saubere formalmathematische Formulierung und die Untersuchung von (vereinfachten) Spezialfällen und Beispielen in diesem formalen Rahmen. Hierbei sind Aspekte der Mathematik (Geoemtrie in der Ebene) und Informatik (Optimierungsprobleme, Entscheidungsprobleme, Komplexität) einzubringen sowie praktische Fähigkeiten (Computerprogrammierung). Die formalen Details der Aufgabenstellung finden sich in der Anlage.
Abgabe: 31.08.2019

Zusammenfassung: Das Guaranteed Service Model (GSM) ist ein Optimierungsmodell zur Bestimmung von garantierten Service-Zeiten in Liefernetzen zur Erreichung eines vorgegebenen Servie-Grads bei stochastischer Nachfrage. Davon kann man unter anderem Sicherheitsbestände ableiten, die ausreichend sind, um diesen Service-Grad zu erreichen.

Zur Lösung des GSM auf divergenten Netzen existieren zwei konkurrierende Ansätze: Dynamic Programming (DP), angewandt in der Literatur, und Mixed Integer Linear Programming (MILP). Bei komplizierten Liefernetzen und Nachfragen kann die Lösung des GSM über die MILP-Technik auf- wendig werden, was für eine stochastische Erweiterung SGSM des GSM noch amplifiziert wird.

Aufgabe dieser Bachelor-Arbeit ist es, für den Anwendungsfall in der Literatur beide Lösungsmethoden zu vergleichen und Empfehlungen abzuleiten.
Abgabe: 31.07.2018

Zusammenfassung: Zur Abfederung der Nachfragevariabilität in Liefernetzwerken werden als Puffer Lager eingesetzt. Einen großen Einfluss auf die erwarteten Gesamtkosten hat die Festlegung der Sicherheitslagerbestände. Ein dafür vorgeschlagener Modellierungsansatz ist das Guaranteed Service Model (GSM): Statt direkt Sicherheitsbestände zu bestimmen, werden garantierte Servicezeiten für jeden Lieferanten ermittelt, aus denen sich geeignete Sicherheitslagerbestände berechnen lassen. Im Grundmodell sind die Lieferzeiten (gerechnet ohne Auslieferungsverzögerungen) deterministisch angenommen. In der Literatur wurden die Konsequenzen stochastischer Lieferzeiten analysiert und festgestellt, dass das GSM dadurch zu einem nicht-konvexen, sehr komplizierten Optimierungsproblem wird. Auf der anderen Seite wurde in der Literatur ein Ansatz aus der gemischt-ganzzahligen Programmierung (MILP) zur Lösung des GSM vorgeschlagen, in den sich möglicherweise durch zusätzliche binäre Variablen und Nebenbedingungen stochastische Lieferzeiten integrieren lassen, wenn man nur endlich viele Szenarien von Lieferzeiten untersucht (ähnlich wie in der Literatur). Aufgabe in dieser Bachelorarbeit ist es, zu erklären, was die Schwierigkeit der stochastischen Lieferzeiten im GSM ausmacht und ob man evtl. mit MILP-Methoden für lineare Nachfragenschranken und (wenige) endlich viele Szenarien stochastische Lieferzeiten logisch konsistent behandeln kann.
Abgabe: 31.07.2018

In der klassischen Lagerhaltungstheorie, die mit Markovschen Entscheidungsproblemen modelliert wird, gibt es keine Kapazitätsbeschränkungen. Manchmal sind aber Lager- und/oder Produktionskapazitäten beschränkt. In der Literatur wird gezeigt, dass man die beschränkten Kapazitäten durch Nachfrage-Vorabinformationen in gewisser Weise ausgleichen kann, so dass die wesentliche Struktur der Optimalkostenfunktion (Konvexität) gegenüber der Problemstellung ohne Kapazitätsbeschränkungen erhalten bleibt.

Aufgabe dieser Bachelorarbeit ist es, diese Zusammenhänge genau zu erklären und mit eigenen Beispielen zu illustrieren.
Abgabe: 31.01.2018

Das Nierenaustauschproblem (KEG, kidney exchange problem) entsteht bei der Zuordnung von Nierenspendern zu Patienten: Wenn spendenbereite Angehörige von Patienten aus medizinischen Gründen nicht als Spender in Frage kommen, dann können von verschiedenen Spender-Patienten-Paaren die Spender ausgetauscht werden, so dass die Transplantation in den neuen Paarungen möglich ist. Tauscht man die Spender aus zwei Spender-Patienten-Paaren, so kann man die maximal erreichbare Menge von Transplantationen durch die Lösung eines Matchingproblems effizient berechnen. Erlaubt man auch längere Austausch-Zykel mit einer Obergrenze auf die Zykel-Länge, so wird das Problem NP-schwer. Daher versucht man u. a. mit Hilfe von Ganzzahliger Linearer Optimierung (ILP) optimale Lösungen zu erreichen. Hierzu gibt es einen Ansatz in der angegebenen Literatur, in dem ein direktes Modell verglichen wird mit einem Modell, dass vom Handlungsreisendenproblem inspiriert ist.

Aufgabe dieser Bachelorarbeit ist es, die Modelle aus der angegebenen Literatur zu erklären und ihr Verhalten anhand von selbst konstruierten instruktiven Beispielen zu vergleichen.
Abgabe: 31.12.2017

Üblicherweise wird die Steuerung eines Warenlagers auf Basis stochastischer Informationen über eine unsichere Nachfrage mit Hilfe von Markovschen Entscheidungsproblemen (MDP) optimiert. Es gibt aber auch eine andere Quelle von Unsicherheit: Zukünftige Preise. In manchen Branchen mit stark volatilen Preisen (z. B. manche Rohstoffmärkte) kann diese Quelle der Unsicherheit sehr wichtig sein.

Eine Art der Betrachtung von Unsicherheiten ist die Online-Optimierung. In diesem Fall werden Online-Algorithmen mit bestmöglicher Kompetitivität gesucht. Werden also die Tagespreise für Material zwischen einem Minimalpreis und einem Maximalpreis jeden Tag neu bekannt gegeben ohne stochastische Vorabinformation, dann muss ein Online-Algorithmus jeden Tag über die Nachbestellung von Material entscheiden, ohne zukünftige Preise zu kennen. Dies ist eine Erweiterung des Economic Order Quantity-Modells (EOQ) und wurde von Larsen und Wøhlk (2010) untersucht.

Aufgabe dieser Bachelorarbeit ist es, Lagerhaltungspolitiken, die unter dem Blickwinkel der kompetitiven Analyse gut sind, zu vergleichen mit typischen Politiken, die unter dem MDP-Blickwinkel gut sind. Hierzu sollen vor allem Beispiele entworfen werden, bei denen sich Unterschiede und Gemeinsamkeiten deutlich zeigen. Sollte es keine substanziellen Unterschiede geben, ist nach einer Begründung dafür zu suchen.
Abgabe: 30.09.2017

Der Q-learning Algorithmus für Markovsche Entscheidungsprobleme ist mit der Wertiteration für Markovsche Entscheidungsprobleme verwandt. Anstatt die Kostenfunktion einer bestimmten Politik zu approximieren, werden Q-Faktoren, die mit der Optimalkostenfunktion verknüpft sind, approximiert. Dieser Algorithmus wurde für einen adaptiven Spieler in einer Umgebung, die sich nach festen Übergangswahrscheinlichkeiten entwickelt in der angegebenen Literatur beschrieben. Littman hat diesen Ansatz auf Zwei-Personen Markov Spiele übertragen und einen minimax-Q learning Algorithmus für zwei adaptive Spieler entwickelt. Dieser Algorithmus wird auf in der Arbeit beispielhaft auf ein stark vereinfachtes Markov Spiel für Fußball angewendet.

Aufgabe dieser Bachelorarbeit ist es, ein stark vereinfachtes Modell für Beachvolleyball als Markov Spiel zu entwickeln und den minimax-Q learning Algorithmus darauf anzuwenden. Dabei sollen verschiedene Rechenexperimente mit Spielen gegen unterschiedlich trainierte Gegner durchgeführt werden.
Abgabe: 31.07.2017

Optimale Diplomatie ist best-mögliche Art und Weise, in einer Reihe von Meetings eine Meinung zu vertreten, um am Ende möglichst viele Unterstützer zu gewinnen. Formell wurde dieses Problem in der Literatur aufgebracht und erste Untersuchungen durchgeführt. Grundlage ist die Hegselmann-Krause-Dynamik (HK-Dynamik) auf Basis des sogenannten "Bounded-Confidence"-Konzepts. In einer populärwissenschaftlichen Darstellung wurde das Konzept anhand der Meinungsdynamik im Kinofilm "12 angry men" (deutscher Verleihtitel: "Die zwölf Geschworenen") plastisch gemacht. Der Artikel endet damit, dass die Dynamik im Film nicht vollständig durch die im Artikel eingenommene eindimensional Sichtweise erklärt werden könne. Für die plausible Behauptung wurde jedoch bislang keine stichhaltige Argumentation vorgelegt. Ferner ist offen, ob die Dynamik im Film ("Wer stimmt in der soundsovielten Abstimmung für was?") nicht vielleicht durch mehrdimensionale Meinungsräume als formale Instanz einer kontrollierten Meinungsdynamik darstellbar ist.

Aufgabe dieser Bachelorarbeit ist es, diese Fragen ergebnisoffen zu untersuchen und die Ergebnisse angemessen zu dokumentieren.
Abgabe: 31.07.2017

Die Beurteilung der Ähnlichkeit von Musikstücken spielt eine große Rolle in der Zuordnung der tatsächlichen Urheberschaft von Musikstücken. Um Urteile wenigstens teilweise auf objektive Fakten zu stützen, wird nach mathematischen Klassifikationssystemen gesucht. Ein neuerer Ansatz nutzt Ganzzahlige Lineare Modelle (ILP). Für ein Beispielmusikstück wird sein Stil wie folgt durch die zulässige Menge eines ILP beschrieben: Für das Beispielmusikstück werden die verschiedenen musikalischen Dimensionen (Harmonie, Melodie, Rhythmus, ...) in Binärwerte kodiert, und zwar für verschiedene zeitliche Auflösungen. Aus diesen Werten werden Statistiken ermittelt, von denen man denkt, dass sie wichtig sind für den musikalischen Eindruck. Alle Stücke mit denselben oder ähnlichen Statistiken werden als ähnlich im Stil aufgefasst. Im speziellen Ansatz wird das durch lineare Gleichungen und Ungleichungen in den Binärvariablen ausgedrückt.

Ziel dieser Bachelorarbeit ist es, dieses ILP-System auf eine Reihe von (vereinfachten) Musikstücken auszuprobieren und ein paar Fragen dazu zu klären.
Abgabe: 31.07.2017

Üblicherweise wird optimale Lagerhaltung in diskreter Zeit (z. B. tägliche Nachbestellmöglichkeit) modelliert mit Markovschen Entscheidungsproblemen (MDP), um die Unsicherheiten (vor allem der Nachfrage) mathematisch abzubilden. Für einfache Spezialfälle kennt man optimale Politiken, die auch in komplizierteren Umgebungen wegen ihrer einfachen Struktur bevorzugt angewendetet werden, sogar wenn sie bekanntermaßen suboptimal sind. Es gibt aber auch eine Alternative zur Behandlung der Unsicherheiten: Robuste Optimierung (RO). In dieser Arbeit soll ein Ansatz aus der RO zur optimalen Lagerhaltung anhand von selbst entwickelten instruktiven Beispielen mit den Resultaten der MDP-Methoden verglichen werden.
Abgabe: 31.07.2017

In der Produktionplanung kann man mit Hilfe der Linearen Programmierung (LP) Produktionsmengen mit maximalem Deckkungsbeitrag bei gegebenen Ressourcenbeständen ausrechnen. Aber nur, wenn man alle Daten tatsächlich genau kennt. Ist Unsicherheit im Spiel, dann muss man Optimierungsmethoden für unsichere Optimierungsprobleme anwenden wie stochastische Optimierung oder robuste Optimierung. Eine Alternative, die auch die Unsicherheit bei der Formulierung der Wünsche des Anwenders mit berücksichtigen kann, ist die Methode Fuzzy-Linear-Programming (FLP). Hierbei wird die Zugehörigkeit eines Punktes zur zulässigen Menge nicht scharf sondern durch eine parametrisierbar schwammige Mitgliedschaftsfunktion dargestellt.

Ziel dieser Bachelorarbeit ist es, die Lösungsvorschläge von FLP für ein konkretes Produktionsplanungsbeispiel zu ermittlen und mit den Lösungsvorschlägen von LP zu vergleichen, wenn Unsicherheiten auftreten.
Abgabe: 30.06.2017

Im Ganzladungs-Güterverkehr ("Full Truckload") wird der ganze LKW für nur eine Lieferung verwendet. Bei großen Entfernungen sind manchmal auch bei kürzest-möglichen Transportrouten lange Pausen und damit nutzlose Standzeiten der (teuren) Fahrzeuge unvermeidlich. Im ILAN-Projekt der FH Erfurt wird untersucht, wie eine Gruppe von Kleinspediteuren Lieferungen kooperativ transportieren können, so dass möglichst viele Fahrer jeden Abend wieder zu Hause sind. Das geht zum Beispiel dadurch, dass sich die Spediteure die Ladungen auf gemeinschaftlich genutzten Trailern übergeben, so dass die Zugmaschinen jedes Spediteurs nur eine halbe Tagesfahrt entfernt vom eigenen Depot unterwegs sind.

In der Literatur wurde dazu ein Modell entwickelt: Möglichst viele Lieferungen sollen kooperativ transportiert werden, ohne dass Leerfahrten entstehen. Das ist ein Matching-Problem mit einer Set-Covering-Bedingung. Im Artikel wird das Problem mit einem ad-hoc-Algorithmus gelöst. Die Rechenzeiten sind problematisch für viele Lieferungen. In einer Bachelorarbeit wurden Gemischt-Ganzzahlige Modelle (MILP) entwickelt, die sich mit Standard-Software wesentlich schneller lösen lassen. Allerdings offenbaren Testrechnungen, dass das Optimierungspotenzial wegen des starren Ansatzes nicht so groß ist wie gewünscht.

Aufgabe dieser Bachelorarbeit ist es, die starren Regeln des originalen Kooperationsansatzes an geeigneten Stellen zu flexibilisieren. Die größte Flexibilisierung entsteht dadurch, dass die einzelnen Transporte nicht notwendig entlang kürzester Routen laufen müssen. Es kann besser sein, die Routen genau so zu planen, dass der Nutzen der Kooperation am größten wird. Hierfür soll ein integriertes MILP entwickelt werden und anhand von Beispieldaten getestet werden.
Abgabe: 28.02.2017

In der Literatur finden sich Ansätze, wie touristische Touren optimiert werden können. Dabei geht es nicht in erster Linie um kürzeste Wege sondern auch um schönste. Ein Modellansatz stützt sich auf das Orienteering-Problem (OP).

Aufgabe dieser Bachelorarbeit ist es, die Modelle zum OP auf Basis Gemischt-Ganzzahliger Linearer Programmierung (MILP) zu erklären, mathematische Standard-Methoden zu ihrer Lösung zu skizzieren und die Modelle beispielhaft auf Spaziergänge über die Landesgartenschau Bayreuth anzuwenden.
Abgabe: 15.12.2016

Das Kürzeste-Wege-Problem mit Ressourcenbeschränkungen (engl.: Shortest-Path Problem with Resource Constraints, SPPRC) fragt nach einem kürzesten Weg unter der Nebenbedingung, dass auf dem Weg der Resourcenverbrauch einer oder mehrerer Resourcen ein gegebenes Budget jeweils nicht übersteigt. Das SPPRC ist bekanntermaßen NP-schwer, kann aber mit einem pseudopolynomialen Dynamic-Programming-Algorithmus gelöst werden. In einer klassischen Arbeit hat Hassin ein polynomiales Approximationsschema (PTAS) vorgestellt: Für jede konstant vorgebene Optimalitätslücke existiert ein Algorithmus, der in Polynomialzeit das SPPRC innerhalb dieser Lücke löst.

In dieser Arbeit soll der Hintergrund des SPPTW und das PTAS von Hassin erklärt werden und eine Anwendung des SPPRC im Bereich der touristischen Routenplanung (z. B. Radfahren, Landesgartenschau) diskutiert werden.
Abgabe: 31.10.2016

Patiententransporte in Krankenhäusern erfordern eine sorgfältige Planung, damit Wartezeiten sowohl für Patienten als auch für Behandelnde möglichst vermieden werden. Hierzu gibt es auch Ansätze auf Basis mathematischer Optimierung. Oftmals werden heuristische Ansätze den exakten Methoden vorgezogen, da es sehr schwierig ist, sich auf Modelle zu verständigen, die die Wünsche der Agierenden in einem Krankenhaus genau abbilden. Ein solcher, auf Meta-Heuristiken basierender Ansatz wurde in der Literatur entwickelt und implementiert. Es stellt sich die interessante Frage, ob die verwendete Heuristik in bestimmten Fällen zu stark suboptimalen Lösungen führen kann, oder ob „in aller Regel“ die Optimalitätslücke klein ist.

Aufgabe dieser Bachelorarbeit ist es, für das Modell in der Literatur auf ausgewählten Beispielinstanzen die heuristische Lösungsqualität mit dem exaktem Optimalwert zu vergleichen.
Abgabe: 30.09.2016

Beim Gütertransport auf der Straße unterscheidet man zwischen Aufträgen mit Full-Truckload (jede Lieferung nimmt einen ganzen LKW in Anspruch, wie zum Beispiel bei Umzugsunternehmen) und Less-Than-A-Truckload (eine Lieferung wird im LKW mit anderen zusammengepackt, wie zum Beispiel bei Paketdiensten). Wird der ganze LKW für nur eine Lieferung verwendet und geht die Fahrt sehr weit, so muss der Fahrer seine Ruhezeiten unterwegs einschieben. Das (teure) Fahrzeug ist in der Zeit unproduktiv. Daher wird im ILAN-Projekt der FH Erfurt untersucht, wie eine Gruppe von Kleinspediteuren Lieferungen kooperativ transportieren können, so dass möglichst viele Fahrer jeden Abend wieder zu Hause sind. Das geht zum Beispiel dadurch, dass sich die Spediteure die Ladungen auf gemeinschaftlich genutzten Trailern übergeben, so dass die Zugmaschinen jedes Spediteurs nur eine halbe Tagesfahrt entfernt vom eigenen Depot unterwegs sind.

In der Literatur wurde dazu ein Modell entwickelt: Möglichst viele Lieferungen sollen kooperativ transportiert werden, ohne dass Leerfahrten entstehen. Das ist ein Matching-Problem mit einer Set-Covering-Bedingung. Im Artikel wird das Problem mit einem ad-hoc-Algorithmus gelöst. Die Rechenzeiten sind in vielen Fällen problematisch für viele Lieferungen.

Aufgabe dieser Bachelorarbeit ist es, die Aufgabe mit einem geeigneten Gemischt-Ganzzahligen Programm (MILP) zu modellieren und mit einem Standard-Löser (z. B. SCIP) zu lösen. Die Lösungen und die Rechenzeiten sollen mit dem Verfahren aus der Originalarbeit verglichen werden. Erweiterungen des MILP auf Kapazitäten und anderen Nebenbedingungen und Zielfunktionen sollen diskutiert werden.
Abgabe: 30.09.2016

Abgabe: 31.08.2016

Abgabe: 31.07.2016

Das Performance-Potential-Metamodell modelliert die Wechselwirkung zwischen Belastung und Leistung unterschiedlichster Systeme in der Sportphysiologie. Es wurde ursprünglich von Jürgen Perl entwickelt und wird aktuell in den Sportwissenschaften angewandt und weiterentwickelt. Die Systemdynamik des ursprünglichen Modells besitzt Nichtlinearitäten, weshalb im bisherigen Lösungsansatz heuristische Verfahren verwendet werden.

Aufgabe dieser Bachelorarbeit ist es, das Modell mit den Methoden der ganzzahligen linearen Optimierung zu analysieren. Dabei soll die Systemdynamik des Performance-Potential-Metamodells als ganzzahliges lineares Programm modelliert werden oder begründet werden warum dies nicht möglich ist. Gefundene Optimallösungen von Beispielinstanzen sollen mit Ergebnissen der heuristischen Verfahren verglichen werden. Die Unterschiede zwischen den beiden Ansätzen sollen deutlich werden.
Abgabe: 31.07.2016

Nach der Einrichtung einer Bahnlinie müssen die Haltepunkte festgelegt werden. Gerade im ländlichen Raum ist es aber gar nicht offensichtlich, wo die besten Stellen dafür sind. In der Literatur gibt es Mathematische Modelle, deren Optimallösungen Vorschläge für die Festlegung solcher Haltepunkte gemäß verschiedenen Kriterien generieren.

Aufgabe dieser Bachelor-Arbeit ist es, diese Ansätze zu sammeln und einen ausgewählten Ansatz auf ein selbst definiertes Haltepunktplanungsproblem der Region Bayreuth anzuwenden. Beispielsweise können die tatsächlichen Haltepunkte an einer existierenden Bahnstrecke mal auf ihre Qualität in einem der mathematischen Modelle geprüft werden.
Abgabe: 31.07.2016

Die optimierte Planung von nationalen Sportligen (DFL, DBL) wird heutzutage mit modernen mathematischen Methoden durchgeführt. Ein interessantes verwandtes Problem ist die Planung von Turnieren mit mehreren Austragungsorten (z. B. Beachvolleyball-Felder auf einer Urlaubsinsel). Auch diese Problemstellung kann man mit graphentheoretischen Methoden und diskreter Optimierung angreifen.

Aufgabe dieser Bachelorarbeit ist es, die mathematische Modellierung und Optimierung eines Turniers mit mehreren Austragungsorten zu erklären und auf ein von den Bayreuther Sportwissenschaftlern im Sommer 2016 veranstaltetes Beachvolleyball-Turnier anzuwenden.
Abgabe: 31.07.2016

Um eine Mountainbike-Route automatisch zu berechnen, müssen viel mehr Aspekte berücksichtigt werden als beim Navigieren mit Autos auf Straßen. Nicht die schnellste/kürzeste Strecke ist gesucht, sondern die genussreichste. Ferner ist bei besonders attraktiven Single-Trails aus Wanderkarten die Befahrbarkeit zum Tourzeitpunkt oft nicht bekannt. Nutzt eine geplante Tour so einen Trail, so kann die Gesamttour wegen Schiebe-/Tragepassagen viel unattraktiver sein als gedacht.

Aufgabe dieser Bachelorarbeit ist es, möglichst einfache robuste und/oder stochastische Optimierungs-Modelle für die Berechnung einer besten Mountainbike-Route von A nach B zu entwickeln, die mit alltäglichen Anforderungen logisch kompatibel sind. Dabei sollen Erkenntnisse aus dem Bereich der robusten und/oder stochastischen Optimierung beachtet und bewertet werden. Die Unterschiede zur Kfz-Navigation sollen deutlich werden.
Abgabe: 31.12.2015

Markovsche Entscheidungsprobleme (MDP) modellieren optimale Handlungsstrategien für sequentielles Entscheiden unter Unsicherheit. Manchmal ist eine vollständige Information über alle Übergangswahrscheinlichkeiten nicht verfügbar oder entsprechende statistische Schätzungen sind sehr unzuverlässig. Man ist also damit konfrontiert, dass eine berechnete Politik unter anderen als den Modellbedingungen zum Einsatz kommt. Um zu erreichen, dass die angewendete Politik in einer Situation mit veränderten Wahrscheinlichkeiten nicht zu schlecht abschneidet, kann man Konzepte der robusten Optimierung auf die Berechnung optimaler Politiken für MDPs anwenden.

Im Bereich der Sportspielforschung können Übergangswahrscheinlichkeiten für MDP-Modelle tatsächlich nur grob geschätzt werden. Aufgabe dieser Bachelorarbeit ist es daher, für ein einfaches Sportspiel-MDP eine robuste Politik zu berechnen und ihre erwartete Performance mit einer nicht robusten optimalen Politik numerisch zu vergleichen.
Abgabe: 30.09.2015

Eine wesentliche Teilaufgabe in der Agrarplanung ist die Folgende: Welche Nutzpflanze soll auf welchem Teil der verfügbaren Ackerfläche angebaut werden? In einfachen Modellen der Linearen Programmierung (LP) wird angenommen, dass der Ertrag pro Fläche für jede Pflanze im Voraus bekannt ist. In der Realität schwankt dieser Flächenertrag aber. Eine Methode, damit umzugehen, ist die Stochastische Lineare Programmierung (SLP).

Ziel dieser Arbeit ist es, für eine Fallstudie das Verbesserungspotenzial von SLP gegenüber LP in Anbetracht unsicherer Ertragsdaten zu ermitteln.
Abgabe: 31.07.2015

Das Webcaching-Problem fragt nach der besten Vorschrift, wie ein Webbrowser heruntergeladene Dokumente in einem Cache zwischenspeichern soll, um zukünftige Anforderungen mit weniger Wartezeit bedienen zu können. Man unterscheidet dabei, ob der Webserver für die angeforderten Dokumente genau in der Reihenfolge der Anfragen die Cache-Entscheidung (Cachen: ja/nein, wenn ja, welches Dokument ersetzen) treffen soll oder ob eine Umsortierung (Pipelining) in gewissem Rahmen möglich ist (Webcaching mit Umsortierung, kurz WCRP: the webcaching-with-reordering problem). Ferner ist wichtig, ob ein Zugriff stets über den Cache erfolgen muss (wie bei der Speicherverwaltung eines Betriebssystems) oder ob ein Dokument auch unter Umgehung des Cache (bypassing) angezeigt werden kann.

Ziel dieser Bachelorarbeit ist es, die Resultate der Literatur zur kompetitiven Analyse vorzustellen und mit eigenen Überlegungen zu erweitern. Zum Beispiel: Was bringt Lookahead im Vergleich zum Standard-Paging? Wie wirkt sich Bypassing auf die bekannten Standard-Paging-Resultate der kompetitiven Analyse aus?
Abgabe: 31.07.2015

In der Literatur wird ein Markovsches Entscheidungsproblem (MDP) definiert, das die strategischen Entscheidungen während eines Tennis-Ballwechsels modelliert. Zur Lösung wird ein statistisches Lernverfahren (Monte-Carlo-Baumsuche) angewendet, weil Übergangswahrscheinlichkeiten schwer zu bestimmen sind. Damit erhält man Politiken und Schätzungen für die Gewinnwahrscheinlichkeit. Allerdings ist das MDP nicht so groß, dass es ausgeschlossen wäre, zunächst alle Wahrscheinlichkeiten zu schätzen und dann eine optimale Politik zu bestimmen.

Aufgabe dieser Bachelorarbeit ist es, das in der Literatur angegebene MDP bei gegebenen Wahrscheinlichkeiten direkt mit den üblichen mathematischen Verfahren zu lösen oder präzise zu beschreiben, warum das nicht geht.
Abgabe: 31.07.2015

Modeartikel werden manchmal im Herstellungsland bereits als Sortimente mit unterschiedlichen Konfektionsgrößen vorverpackt. Ein Lot-Typ bestimmt dabei, wieviele Teile in welcher Größe sich in so einem Paket (= Lot) befinden. Das Lot-Type-Design-Problem (LDP) fragt nach der besten Auswahl von Lot-Typen zur Belieferung von Filialen mit gegebener erwarteter Nachfrage nach Größen. Nun sind im Liefer- und Abverkaufsprozess Unsicherheiten zu erwarten. Zum Beispiel sind die erwarteten Nachfragen nur Schätzungen, und die tatsächliche Lieferung des Herstellers stimmt manchmal nicht genau mit der Bestellung beim Hersteller überein.

Ziel dieser Bachelorarbeit ist es, das LDP zu robustifizieren bzgl. geeigneter Datenunsicherheitsmengen und die Ergebnisse zu diskutieren.
Abgabe: 31.07.2015

Angenommen, für einen Tanzball sollen gemischte Tanzpaare zusammengestellt werden. Es ist durch nicht-negative Gewichte (= Spaßfaktoren) bekannt, wieviel Spaß es den möglichen Paaren machen würde, miteinander zu tanzen. Dann kann man durch ein gewichtsmaximales Matching eine "gesamtspaßmaximale" Zusammenstellung von Tanzpaaren für den Ball berechnen. Nun ist nicht jeder Mensch an jedem Tag gleichgut "drauf". Dies äußert sich beim Tanzpaar-Problem darin, dass die Spaßfaktoren stochastisch sind. So kann ein Tanzpaar an einem Tag eine Menge gute Laune versprühen und an einem anderen sich nur zanken. Man kann also die Spaßfaktoren als stochastisch ansehen. Das Ziel besteht darin, eine Tanzpaarzusammenstellung zu finden mit dem maximalen erwarteten Gesamtspaß. Dies ist ein einstufiges stochastisches bipartites Matching-Problem (SBMP). Nehmen wir nun an, es ist erlaubt, einige Tanzpaare erst am Ball-Abend zusammenzustellen, wenn die Stimmungslage bereits bekannt ist. Für die Vorab-Zuordnung bekommt man einen deterministischen Spaßfaktor abhängig vom Paar. Nach der Zuordnung am Ball-Abend gibt es die dann realisierten stochastischen Spaßfaktoren hinzu, weil nun klar ist, wer in welcher Stimmung ist und wer in nun aufgebrezelter Form wem wie gut gefällt. Dies führt auf ein zweistufiges stochastisches bipartites Matching-Problem mit Kompensation (SBMP2).

Ziel dieser Arbeit ist es, für das SBMP zu klären, ob der Wert der stochastischen Lösung (VSS) Null ist (Erwartungswert-Äquivalenz). Ferner sollen Beispielinstanzen des SBMP und des SBMP2 bei endlichen Verteilungen mit Hilfe von Szenario-Sampling und Szenario-Reduktion gelöst werden. Hierbei soll eine fundierte Szenario-Reduktion in Bezug auf die Lösungsqualität verglichen werden mit dem willkürlichen Weglassen von Szenarien.
Abgabe: 31.07.2015

In der Philosophie und in den Sozialwissenschaften untersucht man künstliche Gesellschaften. In solchen künstlichen Gesellschaften gibt es absichtlich stark vereinfachte Interaktionsmodelle, die man mit Mathematik und/oder Computer-Experimenten untersuchen kann. Entstehen dabei nicht-triviale Effekte, so hat man damit sehr grundsätzliche Strukturen identifiziert, die solche Effekte hervorrufen können. Findet man die Effekte auch in einer realen Gesellschaft vor, so ist dies ein Hinweis darauf, dass die einfache Struktur eine substantielle Rolle in der realen Gesellschaft spielen könnte. Ein seit einigen Jahren vielfach betrachtetes Modell für die dynamische Entwicklung von Meinungen ist die sogenannte Bounded-Confidence-Dynamik (BC). In der einfachsten Variante besteht der Meinungsraum aus dem reellen Einheitsintervall. Nach einer (diskreten) Runde Meinungsaustausch bilden sich die neuen Meinungen durch Durschschnittsbildung mit allen anderen Meinungen, die nicht weiter als ε ∈ [0, 1] (der Konfidenzradius) entfernt sind. Durch kontrollierte Meinungsäußerungen kann man die dynamische Entwicklung in eine gewünschte Richtung bewegen. Mathematisch wurde dieses Konzept für BC erstmals als Optimalsteuerungsproblem in der grundlegendsten Form präsentiert. Hier ging man davon aus, dass ein globaler Planer die Meinungsäußerungen von einem oder mehreren Agenten steuert. Gibt es zwei oder mehr Spieler, die jeweils einen oder mehrere Agenten unabhängig voneinander, und mit eigenen Zielen, steuern können, so verlässt man das Gebiet der Optimalsteuerung und landet in der Spieltheorie.

Aufgabe dieser Bachelorarbeit ist es, erste spieltheoretische Untersuchungen zur Bounded-Confidence-Dynamik anzustellen. Das allgemeine Problem wurde bereits in der Literatur kurz beschrieben. Für Spezialfälle und kleine Anzahlen an Agenten bzw. Runden sollten sich theoretische und computerunterstützte Ergebnisse finden lassen.
Abgabe: 31.07.2015

Wie soll ein Regal mit 40 Komponenten-Behältern auf 4 Ebenen eingerichtet werden, damit eine Montagekraft bei den erwarteten Montagearbeiten am ergonomischsten und schnellsten arbeiten kann? Aufgabe dieser Bachelorarbeit ist es, diese Frage in Zusammenarbeit mit der Firma Wibond Informationssysteme mit Hilfe mathematischer Optimierungsverfahren zu lösen. Details der Aufgabenstellung finden sich im Anhang des Kooperationspartners.

Ziel der Bachelorarbeit ist es, geeignete mathematische Modelle und Verfahren zu identifizieren, die zu einer besseren Regal-Einrichtung in der Praxis führen. Gütegarantien für Lösungsvorschläge sind erwünscht.
Abgabe: 30.06.2015

Beim Laserschweißproblem mit festen Touren (LSP-T) in der angegebenen Literatur teilen sich Industrieroboter gewisse Ressourcen. Beispiele hierfür sind gemeinsam genutzte Laserquellen für die Bearbeitung von Schweißnähten oder Ressourcen zur Kollisionsvermeidung. Wenn zwei Roboter gleichzeitig mit derselben Laserquelle schweißen wollen oder gleichzeitig in einen kritischen Bereich fahren, in dem es zu einer Kollision zwischen Ihnen kommen kann, so liegt ein Ressourcenkonflikt vor. Das Ziel des LSP-T besteht darin, die Roboter so zu synchronisieren, dass keine Ressourcenkonflikte auftreten und der Makespan minimal ist.

Das LSP-T ist ein wichtiges Subproblem in einem Branch-and-Bound Algorithmus zur Lösung des kompletten LSP, bei dem zusätzlich noch die Robotertouren bestimmt werden müssen. In der aktuellen Implementierung wird dazu ein gemischt ganzzahliges Modell verwendet. Während die meisten Instanzen innerhalb einer Sekunde gelöst werden können, gibt es auch welche, bei denen CPLEX auch nach Tagen noch keinen Optimalitätstest führen kann.

In der angegebenen Literatur wurde gezeigt, dass das LSP-T NP-schwer ab 3 Roboter ist. Hierfür wurde jedoch ein pseudo-polynomialer Algorithmus sowie darauf aufbauend ein fully polynomial approximation scheme (FPTAS) angegeben. Dies wurde bisher jedoch nie implementiert oder getestet.
In dieser Bachelorarbeit soll versucht werden, die schwierigen LSP-T Instanzen optimal bzw. approximativ zu lösen
Abgabe: 31.09.2012

Zusammenfassung: Auktionen werden verwendet, um beim Verkauf von Gütern Preise zu erzielen, die die Bezahlbereitschaft ("wahrer Preis") möglicher Kaufender voll ausnutzen. Hierbei muss beachtet werden, dass ein Mechanismus zum Einsatz kommt, bei dem es für die Interessierten gut ist, ihren wahren Preis zu offenbaren. Beim Verkauf von Rechten an digitalen Gütern sind die Reproduktionskosten des Gutes nahe Null. Auf der anderen Seite ist eine A-Priori-Verteilung der wahren Preise nicht immer zuverlässig zu schätzen. Solche braucht man aber für sogenannte Bayes’sche Auktionen. Eine Alternative wurde daher von Goldberg, Hartline, Karlin, Saks und Wright in der Literatur mit dem Konstrukt der Kompetitiven Auktionen eingeführt.

Aufgabe dieser Masterarbeit ist es, das Konzept und die Theorie der kompetitiven Auktionen zu erklären und mit den Bayes’schen Auktionen zu vergleichen. Ferner soll ein beliebiger, möglichst realitätsnaher Anwendungsfall diskutiert werden, in dem Vorteile der kompetitiven Auktionen zum Tragen kommen könnten. Dies soll durch Simulationsrechnungen untermauert werden
Abgabe: 30.04.2020

Zusammenfassung: Das Maximum-Scatter Traveling Salesman Problem (MSTSP) in der Literatur fragt nach einer Rundreise, die alle Knoten eines Graphs jeweils genau einmal besucht und deren kürzeste Kante möglichst lang ist. Motiviert ist das Problem z. B. aus der Fertigungstechnik, wenn direkt aufeinander folgende Arbeitsschritte an einem Werkstück nicht zu nah beieinander ausgeführt werden sollen. Wegen dieser Motivation sind besonders euklidische Instanzen von Interesse. In einer aktuellen Arbeit in der Literatur wurden für sogenannte doubling metrics in beliebiger Dimension (diese verallgemeinern die euklidische Metrik) effiziente (aber nach Aussage der Autoren unpraktikable) Approximationsschemata gefunden. Auf der anderen Seite konnten in der Literatur für vollständige Graphen auf regulären Gitterpunkten (Gitter-MSTSP) in Dimension zwei und drei optimale und beinahe optimale Touren identifizert werden. Aufgabe dieser Masterarbeit ist es, zu untersuchen, ob die unpraktikablen Approximationsschemata von Kozma und Mömke in der Literatur für Gitter doch umsetzbar sind und ob sie ähnliche Touren liefern wie die von Hoffmann, Kurz und Rambau in der Literatur.
Abgabe: 29.02.2020

Zusammenfassung: Jeder Industriezweig hat seine eigenen Anforderungen an eine Lagernetzbestandsplanung (engl.: Multi-Echelon Inventory Control, MEIC). Charakteristika für die High-Tech-Zulieferindustrie sind lange Lieferzeiten für eine große Anzahl an Rohstoffen und mächtige Kunden (z. B. Automobilkonzerne) mit hohen Anforderungen an kurze Lieferzeiten. Das bedeutet, dass im vom Zulieferer kontrollierten Teil der Supply-Chain die Lieferzeiten von groß nach klein "transformiert" werden müssen mit den entsprechenden Konsequenzen für die Lagerbestandsplanung. Häufig anzutreffen sind Lagerplanungssysteme basierend auf "Enterprise Resource Planning"-Software (ERP). Diese verwenden zwar die Netzstruktur des Gesamtsystems im Detail, berücksichtigen aber nicht direkt die Unsicherheit der Nachfrage. Der andere Extremfall in der Praxis ist die verteilte Verwendung von stochastischer Lagermanagement-Optimierung für jedes Lager einzeln.

Aufgabe dieser Masterarbeit ist es, auf Basis der Literatur zu MEIC ein für diesen Industriezweig passendes Modellierungskonzept zu identifizieren und am Beispiel eines konkreten Lagernetzes umzusetzen. Um die Relevanz verschiedener Einflussfaktoren besser einzuschätzen, soll das Testnetz strukturell einem echten solchen Netz möglichst ähnlich sein. Hierfür steht Dr. Cornelius Schwarz von der Frenzelit GmbH (Bad Berneck) als Gesprächspartner zur Verfügung. Besonders interessant ist es, in wie weit ein Ansatz auf Basis von stochastischer Optimierung sich in einen bestehenden ERP-Kontext integrieren lässt (z. B. Formate von Input-Daten und Output-Daten) und welche Probleme damit überwunden werden können.

Ziel ist es unter anderem, mit verschiedenen Modellrechnungen und Beispielbetrachtungen zu ermitteln, ob sich die modell-optimale Positionierung von Sicherheitsbeständen im Netz für bestimmte Parameterbereiche auch durch einfache Handlungsregeln (näherungsweise) umsetzen ließe. Ferner ist es interessant, das Optimierungspotenzial gegenüber einer nicht vernetzten Lagerbestandsoptimierung oder einfachen Geschäftsregeln abhängig von Modellparametern zu quantifizieren.

Als erster Ansatz soll ein Modell auf Basis des Guaranteed-Service-Modells (GSM) oder einer Erweiterung davon, z. B. des Stochastic GSM (SGSM), entwickelt werden, die sich als Stochastisches Mixed Integer Linear Program (SMILP) formulieren lassen. Eine Literatur-Recherche soll Alternativen identifizieren, die ggf. anstelle des (S)GSM-Ansatzes verfolgt werden können.
Abgabe: 31.08.2019

Optimale Diplomatie in einem Kommittee bezeichnet die Präsentation einer Meinung, repräsentiert durch eine Zahl im Einheitsintervall, in einer gegebenen Anzahl von Sitzungen, so dass in der Hegselmann-Krause-Dynamik der Meinungen der Kommittee-Mitglieder am Ende möglichst viele Kommittee-Mitglieder Meinungen in einem vorgebenen Meinungsintervall haben. Das statische Optimierungsproblem der optimalen Diplomatie ist selbst für kleine Instanzen sehr schwer zu lösen. In vielen Fällen des Kampagnen-Problems, einer Benchmark-Instanz aus der Literatur, liefert die sogenannte „Strongest-Guy“-Heuristik aber sehr gute Lösungen. Die augenblickliche Umsetzung durch eine Spezialimplementierung ist nicht sehr flexibel und braucht für große Instanzen viel Rechenzeit. Es wäre daher interessant, die Strongest-Guy-Heuristik mit einem gemischt-ganzzahligen linearen Modell (MILP) zu lösen, da sie sich dann leichter mit Variablenfixierungen, anderen Nebenbedingungen und Kostenmodellen kombinieren ließe.
Abgabe: 28.02.2019

Zusammenfassung: Mit Hilfe von Prozessmodellen können wiederkehrende Abläufe in Unternehmen und Behörden systematisch dokumentiert werden. Hat man zwei Prozessmodelle, z. B. für den Immatrikulationsprozess zweier Universitäten, so ist es interessant, inwiefern die tatsächlichen Prozesse ähnlich sind. Dazu versucht man die Aktivitäten des einen Modells möglichst passgenau auf die Aktivitäten des anderen Modells bijektiv abzubilden. Während bis vor kurzem hauptsächlich Bijektionen zwischen einzelnen Aktivitäten untersucht wurden, hat Baumann in der Literatur nun zum ersten Mal einen Ansatz ausgearbeitet, in dem Bijektionen von beliebigen Teilmengen einzelner Aktivitäten als Grundlage verwendet werden. Damit ist es möglich, auch die Ähnlichkeit von Prozessen aufzudecken, in deren Modellen das Vorgehen in unterschiedlicher Weise in Aktivitäten aufgeteilt worden ist. Um die passgenaueste Abbildung zwischen Teilmengen zu finden, wurde ein Ganzzahliges Lineares Programm (ILP) genutzt, dessen Lösung aber für große Prozessmodelle sehr schwierig ist.

Aufgabe dieser Masterarbeit ist es, mit ILP-Standard-Methoden die (approximative) Lösung des Prozess-Modell-Matching-ILP zu beschleunigen bzw. für große Modelle erst zu ermöglichen.
Abgabe: 31.01.2019

In der Standard-Literatur zu Markovschen Entscheidungsproblemen(MDP) (Bertsekas 2000; Puterman 1994) werden numerische Verfahren für die Berechnung der Optimalkostenfunktion (OKF) eines stationären MDP mit unendlichem Horizont und endlichen Zustands- und Kontrollräumen besprochen. Bei einem dieser Verfahren, der Wertiteration (WI), kann man nicht in endlicher Zeit erwarten, die exakte OKF zu erhalten. Die Iterierten konvergieren aber gegen die OKF, und so kann man nur mit Hilfe von Fehlerschranken, die während der Ausführung der WI berechnet werden können, sinnvoll entscheiden, wann man die WI abbricht. Für diskontierte Probleme gibt es solche Fehlerschranken, für stochastische Kürzeste-Wege-Probleme (SSP) sind die Fehlerschranken der Lehrbuchliteratur kaum sinnvoll berechenbar.

In einer recht aktuellen Arbeit von Hansen (2017) werden nun solche Fehlerschranken für das SSP angegeben. Aufgabe dieser Masterarbeit ist es, diese neuen Fehlerschranken zu erklären und mit denen in der Lehrbuchliteratur zu vergleichen. Ferner sollen das gesamte WI-Verfahren dann verglichen werden mit dem Verfahren der Linearen Programmierung (LP). Gibt es Instanzen/Klassen von Instanzen, in denen WI der LP-Methode überlegen ist oder umgekehrt?
Abgabe: 31.10.2018

Die Kapazitätsplanung von großen Produktionsstätten muss auf Basis von unsicheren Zukunftsinformationen erfolgen. Gewünscht ist eine "robuste" strategische Planung der Kapazitäten für die nächsten Jahre, d. h. eine Planung, die für möglichst viele Szenarien handhabbare operative Produktionsplanung ermöglicht. In der angegebenen Literatur wurde dazu ein Konzept entwickelt, dass robuste Migrationspfade auf Basis von Markovschen Entscheidungsproblemen und nachgelagerten statistischen Schätzungen indentifiziert.

Aufgabe dieser Masterarbeit ist zu prüfen, in wie weit das Ausgangsproblem vollständig als Mathematisches Programm modelliert werden kann. Ansätze aus der Kapazitätserweiterungsplanung mit mehrstufigen stochastischen Programmen sollen hierzu als Ansatz dienen.
Abgabe: 31.07.2018

Markovsche Entscheidungsprobleme (MDP) werden im Gegensatz zu Markov-Ketten im Sport seltener angewendet. Für Tennis und für Beach-Volleyball gibt es jedoch erste Ansätze. Der Beach-Volleyball-Ansatz ist dahingehend neu, dass zwei MDP zur Modellierung genutzt werden: Ein grobes zur Modellierung einer wichtigen Strategiefrage, das strategische MDP (s-MDP), und ein feines, das gameplay-MDP (g-MDP) zur Simulation der Übergangswahrscheinlichkeiten des s-MDP.

Aufgabe dieser Masterarbeit ist es, das Konzept aus der angegebenen Literatur auf Tennis anzuwenden, zu testen und zu diskutieren, welche Vor- und Nachteile es gegenüber der Methode aus der angegebenen Literatur hat.
Abgabe: 31.01.2018

Energienetzbetreiber müssen auf verschiedene Einspeise- und Lastszenarien (im Folgenden kurz Szenarien) vorbereitet sein. Die Szenarien entstehen durch die Entscheidungen der Energieerzeuger und -konsumenten, die Energie in das Netz einspeisen und aus dem Netz entnehmen. Vor allem die Einspeisungen aus regenerativen Quellen unterliegen großen Schwankungen, die schlecht vorhersehbar sind, da z. B. das Wetter eine Rolle spielt. Die Endnachfrage lässt sich demgegenüber ganz gut prognostizieren. Es wird angenommen, dass die Steuerung aller aktiven Netzkomponenten so geschehen soll, dass ein Gesamtsystemoptimum erreicht wird. Der optimale Betrieb von Kraftwerken und Speicheranlagen bei gegebener Endkunden-Nachfrage wird dabei durch Varianten des Unit-Commitment-Problems (UCP) modelliert. Ein Joint-Market-Modell (JMM) fasst die UCPs aller Erzeuger eines gesamten Netzes zusammen. Die Einspeisungen und Entnahmen und die davon abhängigen, für das Gesamtsystem optimalen Aktionen der großen Energieerzeuger induzieren schließlich ein Energietransport-Szenario, dem das Netz gewachsen sein muss. Letztendlich würde man gern viele Szenarien generieren, um erstens systemrelevante Komponenten zu identifizieren und zweitens das Netz für viele mögliche Situationen fit zu machen. Das Ziel dieser Arbeit ist es zu untersuchen, ob schärfere Modellierungen von einzelnen UCP-Restriktionsgruppen helfen können, die beim Anwendungspartner TenneT vorhandenen JMM-Modelle (TenneT-JMM) auf Basis Gemischt-Ganzzahliger Optimierung (MILP) schneller zu lösen.
Abgabe: 31.01.2018

Seit der Dissertation von Pfeiffer werden immer mehr Abläufe in Sportspielen mit Hilfe von Markov-Ketten simuliert. Man will damit die Sensitivität von Erfolg in Bezug auf Übergangswahrscheinlichkeiten (Pass kommt an oder nicht, Schuss kommt auf das Tor oder nicht, ...) abschätzen. Allerdings kann man damit nicht direkt optimale Spielstrategien charakterisieren. Neuer ist die Verwendung von Markovschen Entscheidungsproblemen (MDP) zur Bestimmung von optimalen Strategien. In dieser Arbeit soll ein Ansatz aus der Literatur für eine interessante strategische Frage im Fußball umgesetzt werden. Da bereits eine Master-Arbeit für die Frage ”Tikitaka oder Kick-and-Run“ vergeben wurde, soll durch Absprache mit der anderen Kandidatin eine Dopplung vermieden werden. Eine mögliche Frage, die hier untersucht werden soll, ist: Wann und wen sollte man in welcher Spielsituation für wen einwechseln? Ziel ist es, unter der Annahme, dass notwendige Daten erhoben werden können, fundierte Strategieempfehlungen zu geben.
Abgabe: 31.12.2017

Das Stochastic Guaranteed Service Model (SGSM) ist ein zweistufiges stochastisches ganzzahliges lineares Programm mit Kompensation (SILP) zur Opimierung der Sicherheitsbestände in mehrstufigen Lagernetzen. Es erweitert das Guaranteed Service Model (GSM), das beschränkte Nachfrage und feste Transportzeiten voraussetzt. Das SGSM erlaubt beliebige Nachfragen und stochastische Transportzeiten. Zusätzliche Handlungsoptionen zur Kompensation von hoher Nachfrage und verzögerter Lieferung sind Outsourcing und/oder beschleunigte Lieferung, wofür Extra-Kosten angerechnet werden.

Das SGSM ist in einem Punkt mathematisch nur eine Approximation: Die Nachfrage in vorgeschalteten Lagern hängt in Wahrheit von den Entscheidungen der nachgeschalteten Lager ab. Nutzt ein nachgeschaltetes Lager Outsourcing, so kommt dieser Teil der Nachfrage bei den vorgeschalteten Lagern nie an. Daher wird die tatsächlich exogene Endkundennachfrage nicht einfach propagiert. Im SGSM werden für alle Lager exogene Nachfrageverteilungen angesetzt. Dies ist eine Approximation. Die Approximation funktionierte in einer Fallstudie mit zwei Stufen sehr gut. Wie sieht es aber bei mehreren Stufen aus?

Aufgabe dieser Masterarbeit ist es, für vielstufige Lagernetzen herauszufinden, welchen Effekt im SGSM die Ersetzung der tatsächlich endogenen Nachfragen durch exogene Nachfrageverteilungen in vorgeschalteten Lagern hat und wie man das SGSM ggf. modifizieren kann, um den Effekt zu kontrollieren.
Abgabe: 31.10.2016

In der Philosophie und in den Sozialwissenschaften untersucht man künstliche Gesellschaften. In solchen künstlichen Gesellschaften gibt es absichtlich stark vereinfachte Interaktionsmodelle, die man mit Mathematik und/oder Computer-Experimenten untersuchen kann. Entstehen dabei nicht-triviale Effekte, so hat man damit sehr grundsätzliche Strukturen identifiziert, die solche Effekte hervorrufen können. Findet man die Effekte auch in einer realen Gesellschaft vor, so ist das ein Hinweis darauf, dass die einfache Struktur eine substantielle Rolle in der realen Gesellschaft spielen könnte.Zum Beispiel werden seit vielen Jahren Modelle für die dynamische Entwicklung von Meinungen untersucht. Ein Modell für Meinungen in einem metrischen Raum (z. B. das reelle Einheitsintervall) ist die Bounded-Confidence-Dynamik (BC). Nach einer Runde Meinungsaustausch bilden sich die neuen Meinungen durch Durchschnittsbildung mit allen anderen Meinungen, die nicht weiter als ε ≥ 0 (der Konfidenzradius) entfernt sind. Diplomatie entsteht dadurch, dass man durch kontrollierte Meinungsäußerung die Entwicklung von Meinungen in eine gewünschte Richtung befördern kann. Mathematisch wurde dieses Konzept für BC erstmals als Optimalsteuerungsproblem in der grundlegensten Form präsentiert. Ein entsprechendes Benchmark-Kampagnen-Problem zeigt die Schwierigkeit auf, optimale Steuerungen zu finden.

Aufgabe dieser Masterarbeit ist es, eigene Überlegungen anzustellen zu folgenden Erweiterungen des Optimalsteuerungsproblems in der Literatur: Was ändert sich, wenn ε dem Diplomaten unbekannt ist? Wie schlecht kann eine Kampagne werden, wenn sie optimal für ein ε ist, in der Realität sich ε' ≠ ε als zutreffend herausstellt? Ist es schlimmer, wenn ε kleiner ist als erwartet, oder ist es umgekehrt schlimmer? Wird es schlimmer, wenn alle ein individuelles ε haben?
Abgabe: 31.01.2016

Das Thema dieser Masterarbeit stammt aus der theoretischen Informatik aus dem Gebiet der formalen Sprachen. In der Theorie der formalen Sprachen spielt die Operation der Konkatenation L.L' zweier Sprachen L und L' (aneinanderhängen) eine ähnliche Rolle wie die Multiplikation für natürliche Zahlen. Für eine Sprache A kann man analog zu natürlichen Zahlen die Frage nach einer nicht-trivialen Faktorisierung stellen: Ist A die Konkatenation zweier nicht-trivialer Sprachen? (Eine triviale Faktorisierung ist immer A.ε, wobei ε die leere Sprache bezeichnet, genau wie p = 1 · p immer eine triviale Faktorisierung einer natürlichen Zahl ist.) Dieses Faktorisierungsproblem ist also eine Art "Primzahltest" für formale Sprachen und wird als Primality Problem (PP) bezeichnet. Die Sprache A wird als deterministischer endlicher Automat gegeben. Nachdem in der Literatur gezeigt wurde, dass das PP PSPACE-vollständig ist, kann man dieselbe Frage auch für spezielle Sprachenklassen stellen, z. B. für die Klasse der Baumsprachen. Man vermutet, dass PP für Baumsprachen EXPTIME-vollständig ist.

Aufgabe dieser Masterarbeit ist es auszuarbeiten, ob und wenn ja wie die Beweismethode in in der Literatur erweitert werden kann, so dass die Komplexität des PP für Baumsprachen geklärt werden kann.
Abgabe: 29.01.2016

Wenn ein neues Land der Europäischen Union oder einem anderen Verbund beitritt, kommt es häufig zu politischen Diskussionen über die Verteilung der Stimmgewichte. Über den Zusammenhang zwischen Bevölkerungsgröße und einem angemessenen Machtanteil ist man sich mehr oder weniger einig und sieht eine Machtzuteilung, die proportional zur Quadratwurzel der Bevölkerung ist, als „fair“ an. Aber dass Macht nicht proportional zum Stimmgewicht ist, sieht man an folgendem kleinen Beispiel. Wir betrachten drei Länder A, B und C mit Stimmgewichten 6, 3 und 2. Obwohl Land B immerhin noch die Hälfte der Stimmen von Land A hat, haben bei einer 50 %-Mehrheitsregelung die Länder B und C keinerlei Macht. Land A kann alle Entscheidungen alleine treffen. Für verwickeltere Situationen gibt es mehrere sogenannte Machtindizes, mit denen man eine reelle Zahl als Maß für die Macht eines Landes ausrechnen kann. Hat man sich einmal auf einen geeigneten Machtindex geeinigt, so kann man die offensichtliche Frage nach einer gerechten Verteilung der Stimmgewichte als mathematisches Optimierungsproblem formulieren. Es gilt, die Abweichung zwischen dem sich aus der Bevölkerungsanzahl ergebenden, gerechten Machtanteil und der sich aus den Stimmgewichten ergebenden, tatsächlichen Macht zu minimieren. Für den Penrose-Banzhaf Index (PBI) wurde die Approximierbarkeit von Machtverteilungen durch gewichtete Abstimmungsregeln beispielsweise in der Literatur untersucht. Im Rahmen dieser Masterarbeit sollen die verwendeten Methoden auf andere Machtindizes, wie beispielsweise dem Shapley-Shubik Index oder dem Nucleolus, übertragen werden.
Abgabe: 15.09.2015

In vielen Produkten sind informationsverarbeitende Systeme integriert. Die enorme Steigerung der Performanz und Flexibilität dieser Systeme begünstigt dabei den Anstieg der Komplexität. So werden durch Steuerungen letzlich auch Aktionen durchgeführt, welche Personen in der Umgebung potentiell Schaden zufügen können. Das Themengebiet der Sicherheit beschäftigt sich mit der Fragestellung, welche Maßnahmen getroffen werden müssen, damit aus einem unerwarteten Verhalten des betrachteten Systems keine Gefahrensituation entstehen kann. Diese sogenannten Sicherheitsfunktionen werden i.d.R. durch sichere Messaufnehmer, Kommunikationseinrichtungen, Steuerungen bzw. Aktoren realisiert. Häufig kommen hier kostenintensive redundante Hardware-Strukturen zum Einsatz. Moderne Steuerungen verwenden arithmetische Codes zur Fehleraufdeckung. Als deterministische Kriterien zur Bewertung der Fehleraufdeckung werden beispielsweise die arithmetische Distanz und die minimale Hamming Distanz betrachtet. In Sicherheitsnachweisen müssen die entsprechende Werte gegenüber unabhängigen Gutachtern (TÜV, IFA, ...) nachgewiesen werden.

Im Rahmen dieser Masterarbeit soll untersucht werden, wie die Bestimmung der Hamming Distanz bei arithmetischen Codes als ganzzahliges lineares Programm formuliert und mit den zugehörigen Methoden gelöst werden kann.
Abgabe: 31.07.2015

In einem von der Oberfrankenstiftung geförderten Forschungsprojekt wurden Methoden für die Universitätskursstunden- und -raumplanung (UCTP) entwickelt. Die Aufgabe der Raumzuweisung bei gegebener Terminplanung ist schon für sich allein genommen unter praktischen Nebenbedingungen nicht unbedingt einfach zu bewältigen, da es sich wegen der Restriktionen nicht immer um ein klassisches Assignment Problem (AP) handelt. Hierbei müssen den bereits mit Terminen versehenen wöchentlichen Sitzungen der Kurse Räume zugewiesen werden, so dass einem Raum zu jeder Zeit maximal eine Sitzung zugewiesen wird und so dass die Anforderungen der Sitzungen an den Raum erfüllt werden. Ferner kann es noch Restriktionen zu Entfernungen o. ä. geben. Interessante Einblicke bzgl. praxisrelevanter Restriktionen geben die Regeln und Instanzen der International Timetabling Competition in der angegebenen Literatur.

Ziel der Diplomarbeit ist es, herauszufinden, welche Varianten des AP in einer praxisrelevanten Raumplanung eine Rolle spielen und welchen Komplexitätsstatus die entsprechenden Modelle haben.
Abgabe: 08.07.2014