Beispielmodell mit Implementierung

In der Vorlesung haben Sie das folgende Modell schon kennengelernt. Darunter finden Sie auch eine Implementierung in Python. Bitte lesen Sie den Text noch einmal durch und stellen Sie sicher, dass Sie die Überführung in Python verstehen und das Programm auch auf Ihrem PC läuft.

Auf den nächsten Seiten werden dann einige Verständnisfragen gestellt. Sie können alle durch genaues Hinsehen und Überlegen lösen. Probieren Sie aber auch aus, die Implementierung zu ändern, um Ihre Vermutungen zu bestätigen.

Modell

Betrachten sie das folgende Beispiel eines Warehouse Location-Problems:

Für die Belieferung von drei Kunden stehen zwei potenzielle Lagerstandorte zur Verfügung. Die folgende Tabelle enthält die Lagerkapazitäten und Fixkosten der Standorte.

Lagerstandort 1 2

Fixkosten [GE]

5

6

Kapazitäten [ME]

8

9

Die Kunden weisen unterschiedliche Bedarfe auf. Kunde 1 benötigt 5 ME, Kunde 2 benötigt 3 ME und Kunde 3 benötigt 7 ME.

Die Transportkosten [GE/ME] von den Standorten zu den Kunden unterscheiden sich und sind der folgenden Tabelle zu entnehmen.

Lager↓  | Kunden →
 1 2 3

1

9

6

7

2

7

3

6

Das dazugehörige Problem ist einmal allgemein und enumeriert formuliert:


Implementierung

Eine mögliche Implementierung finden Sie hier:
  • Implementierung 1 (Ausführliche Kommentare, inklusive enumeriertem Modell)
  • Implementierung 2 (Kurze, übersichtliche Implementierung, am besten verändern Sie dieses Modell für die Testfragen)
Tipp zum Arbeiten mit dem allgemeinen Modell
Nachdem Sie ein Modell in Gurobi definiert haben, können Sie mit model.write("wlp-modell.lp") sich das Modell ausgeben lassen.(Gurobi schreibt eine Datei mit dem gegebenen Namen in das Verzeichnis, wo Sie das Programm ausführen. Sie können sie mit jedem Editor öffnen). Dies kann besonders hilfreich sein, wenn Sie für ein allgemeines Modell das enumerierte sehen wollen. Vergleichen Sie das untenstehende Model mit dem enumerierten von oben. Bedenken Sie, dass Python immer von 0 anfängt zu zählen, also modelliert x[0,0]  \( x_{11} \). Einige Gleichungen werden von Gurobi umgeschrieben, etwa gilt offensichtlich \( x_{11} + x_{12} + x_{13} - 8 y_1 \leq 0 \Leftrightarrow x_{11} + x_{12} + x_{13} \leq 8 y_{1} \)  und x[0,0] + x[0,1] + x[0,2] - 8 y[0] <= 0 modelliert also \( x_{11} + x_{12} + x_{13} - 8 y_1 \leq 0 \)).

Das LP Format ist ein generelles Format, das von diversen Solvern verwendet werden kann. Für mehr Informationen lesen Sie bitte die Gurobi Dokumentation↗ (letzter Zugriff 09.11.2022).
```\ Model WLP Vorlesung allgemein
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize (Zielfunktion)
  9 x[0,0] + 6 x[0,1] + 7 x[0,2] + 7 x[1,0] + 3 x[1,1] + 6 x[1,2] + 5 y[0]
   + 6 y[1]
Subject To (Nebenbedingungen)
 R0: x[0,0] + x[0,1] + x[0,2] - 8 y[0] <= 0
 R1: x[1,0] + x[1,1] + x[1,2] - 9 y[1] <= 0
 R2: x[0,0] + x[1,0] = 5
 R3: x[0,1] + x[1,1] = 3
 R4: x[0,2] + x[1,2] = 7
Bounds (Variablen Definition)
Binaries (Variablen Definition)
 y[0] y[1]
End
```
あなたは 93% のレッスンを完了しました。
93%