Assignment Chef icon Assignment Chef
All German tutorials

Programming lesson

Operations Research mit Gurobi: Optimierung der Impfstoffverteilung am Beispiel der US Craft Beer Logistik

Lerne, wie Operations Research und Gurobi zur Optimierung von Lieferketten eingesetzt werden – am Beispiel der US-Craft-Beer-Branche. Ein praxisnahes Tutorial für Studierende der Wirtschaftsinformatik.

Operations Research Gurobi Python lineare Optimierung Transportproblem US Craft Beer Logistik Impfstoffverteilung Optimierung OR Tutorial Deutsch Gurobi Modellierung Assignment Chef Operations Research Craft Beer Supply Chain Python Gurobi Beispiel Optimierung Lieferkette Wirtschaftsinformatik Studium OR Beratung Transportkosten minimieren mathematische Modellierung

Operations Research in der Praxis: Impfstoffverteilung trifft Craft Beer

Stell dir vor, du arbeitest für ein Operations-Research-Beratungsunternehmen und dein Kunde ist Pacific Paradise, ein Unternehmen, das die Verteilung von COVID-19-Impfstoffen optimieren möchte. Klingt nach einer klassischen OR-Aufgabe? Richtig! Aber um das Konzept greifbarer zu machen, übertragen wir es auf ein aktuelles Trendthema: US Craft Beer. Warum Craft Beer? Weil die Logistik hinter der Verteilung von Hopfengetränken ähnliche Herausforderungen birgt wie die Impfstofflogistik: begrenzte Ressourcen, Kühlketten, zeitkritische Lieferungen und verschiedene Standorte.

Was ist Operations Research?

Operations Research (OR) ist die Wissenschaft der optimalen Entscheidungsfindung. Mit mathematischen Modellen und Algorithmen löst man komplexe Probleme wie Routenplanung, Lagerhaltung oder Ressourcenallokation. In diesem Tutorial lernst du, wie man ein OR-Modell mit Python und Gurobi erstellt – einem der führenden Optimierungslöser.

Das Szenario: Craft Beer Distribution

Nehmen wir an, eine US-Craft-Beer-Brauerei möchte ihre Biere an verschiedene Biergärten und Einzelhändler in Kalifornien liefern. Die Brauerei hat zwei Braustätten (San Diego und San Francisco) und drei Kunden (Los Angeles, Sacramento, Fresno). Jede Braustätte hat eine begrenzte Produktionskapazität (in Fässern), und jeder Kunde hat eine bestimmte Nachfrage. Ziel ist es, die Transportkosten zu minimieren.

Dieses Problem ist ein klassisches Transportproblem (Transportation Problem) – ein Grundpfeiler der linearen Optimierung. Es ähnelt stark der Impfstoffverteilung, bei der Impfstoffe von Lagern zu Impfzentren transportiert werden.

Mathematische Formulierung

Bevor wir programmieren, müssen wir das Problem mathematisch formulieren. Dein Chef erwartet eine allgemeine Formulierung mit Mengen, Daten, Variablen, Zielfunktion und Nebenbedingungen.

Mengen

  • I: Menge der Braustätten (Angebotsorte), z.B. {San Diego, San Francisco}
  • J: Menge der Kunden (Nachfrageorte), z.B. {Los Angeles, Sacramento, Fresno}

Daten (Parameter)

  • a_i: Angebot (Kapazität) der Braustätte i (in Fässern)
  • b_j: Nachfrage des Kunden j (in Fässern)
  • c_ij: Transportkosten pro Fass von Braustätte i zu Kunde j (in $)

Entscheidungsvariablen

  • x_ij: Anzahl der Fässer, die von Braustätte i zu Kunde j transportiert werden (kontinuierlich, >= 0)

Zielfunktion

Minimiere die gesamten Transportkosten:
Minimiere Z = Summe(i in I, j in J) c_ij * x_ij

Nebenbedingungen

  1. Angebotsbeschränkung: Für jede Braustätte i: Summe(j in J) x_ij <= a_i
  2. Nachfragebeschränkung: Für jeden Kunden j: Summe(i in I) x_ij >= b_j
  3. Nichtnegativität: x_ij >= 0 für alle i, j

Dieses Modell ist ein lineares Programm (LP). Wenn die Gesamtnachfrage gleich dem Gesamtangebot ist, spricht man von einem balancierten Transportproblem.

Implementierung mit Python und Gurobi

Jetzt wird es praktisch. Wir setzen das Modell in Python um. Stelle sicher, dass du Gurobi installiert und lizenziert hast. Der Code ist so geschrieben, dass er leicht an andere Daten angepasst werden kann – genau das, was dein Chef erwartet.

# Importiere Gurobi-Bibliothek
from gurobipy import Model, GRB, quicksum

# Daten (Beispiel)
angebot = {"San Diego": 100, "San Francisco": 150}
nachfrage = {"Los Angeles": 80, "Sacramento": 70, "Fresno": 100}
kosten = {
    ("San Diego", "Los Angeles"): 2.5,
    ("San Diego", "Sacramento"): 3.0,
    ("San Diego", "Fresno"): 4.0,
    ("San Francisco", "Los Angeles"): 3.5,
    ("San Francisco", "Sacramento"): 2.0,
    ("San Francisco", "Fresno"): 3.0
}

# Mengen
I = list(angebot.keys())
J = list(nachfrage.keys())

# Modell erstellen
m = Model("CraftBeerTransportation")

# Entscheidungsvariablen
x = {}
for i in I:
    for j in J:
        x[i, j] = m.addVar(lb=0, vtype=GRB.CONTINUOUS, name=f"x_{i}_{j}")

# Zielfunktion
m.setObjective(quicksum(kosten[i, j] * x[i, j] for i in I for j in J), GRB.MINIMIZE)

# Angebotsbeschränkungen
for i in I:
    m.addConstr(quicksum(x[i, j] for j in J) <= angebot[i], name=f"Angebot_{i}")

# Nachfragebeschränkungen
for j in J:
    m.addConstr(quicksum(x[i, j] for i in I) >= nachfrage[j], name=f"Nachfrage_{j}")

# Optimierung
m.optimize()

# Ergebnisse ausgeben
if m.status == GRB.OPTIMAL:
    print(f"Optimale Gesamtkosten: ${m.objVal:.2f}")
    for i in I:
        for j in J:
            if x[i, j].X > 0:
                print(f"{i} -> {j}: {x[i, j].X} Fässer")
else:
    print("Keine optimale Lösung gefunden.")

Erklärung des Codes

  • Modell initialisieren: Model("CraftBeerTransportation") erstellt ein neues Optimierungsmodell.
  • Variablen hinzufügen: Mit addVar werden die Entscheidungsvariablen definiert. lb=0 setzt die untere Grenze auf 0, vtype=GRB.CONTINUOUS bedeutet, dass die Variablen kontinuierlich sind (wir können auch Fässer als ganze Zahlen modellieren, aber für dieses Beispiel reichen kontinuierliche).
  • Zielfunktion: setObjective definiert die zu minimierende Kostenfunktion.
  • Constraints: addConstr fügt die Angebots- und Nachfragebeschränkungen hinzu.
  • Optimierung: m.optimize() löst das Modell. Der Status wird überprüft und die Ergebnisse werden ausgegeben.

Erweiterung: Zusätzliche Constraints

In der Realität kommen oft zusätzliche Anforderungen hinzu, z.B. Mindestliefermengen, Kapazitätsbeschränkungen pro Route oder zeitliche Fenster. Dein Könnte verlangen, dass jede Braustätte mindestens 20% ihres Angebots an einen bestimmten Kunden liefern muss. So fügst du das hinzu:

# Mindestlieferung von San Diego an Los Angeles: 10 Fässer
m.addConstr(x["San Diego", "Los Angeles"] >= 10, name="MinLieferung_SD_LA")

Oder du möchtest, dass die Transportkosten pro Route nicht über 4 $ pro Fass liegen:

# Kostenbeschränkung: Nur Routen mit Kosten <= 4 $/Fass dürfen genutzt werden
for i in I:
    for j in J:
        if kosten[i, j] > 4:
            m.addConstr(x[i, j] == 0, name=f"Verbot_{i}_{j}")

Dein Bericht für den Chef

Dein Chef erwartet zwei Python-Dateien: eine mit dem Grundmodell und eine mit Erweiterungen. Zusätzlich eine mathematische Formulierung. Achte darauf, dass der Code gut kommentiert ist und die Variablennamen auf die Formulierung verweisen. Verwende LaTeX für die Formeln, um einen professionellen Eindruck zu hinterlassen.

Präsentation für den Kunden

Im zweiten Teil des Assignments erstellst du eine 7-minütige Videopräsentation. Zeige, wie du die Optimierungsergebnisse interpretierst. Welche Engpässe gibt es? Wie wirken sich zusätzliche Constraints auf die Kosten aus? Nutze Diagramme aus Gurobi (z.B. mit m.write("model.lp") und importiere sie in Excel).

Tipps für die Bestnote

  • Formuliere das Problem zunächst allgemein, dann spezifisch für die gegebenen Daten.
  • Teste dein Modell mit verschiedenen Daten, um die Robustheit zu zeigen.
  • Erkläre, warum lineare Optimierung für dieses Problem geeignet ist und wo die Grenzen liegen.
  • Verbinde das Beispiel mit aktuellen Trends: Die Craft-Beer-Branche wächst rasant und viele Brauereien nutzen OR für ihre Logistik.

Fazit

Operations Research mit Gurobi ist ein mächtiges Werkzeug, um reale Probleme zu lösen – sei es die Verteilung von Impfstoffen oder von Craft Beer. Mit diesem Tutorial hast du die Grundlagen gelernt, um dein eigenes Optimierungsmodell zu erstellen. Viel Erfolg bei deinem Assignment!