Modellieren mit LPs |
Jetzt wo wir beliebige LPs lösen können, wollen wir schauen, was für Probleme wir noch damit lösen können.
Das erste echte LP ist die "Stiegler Diet" (1945)
Frage: Was ist die billigste Diät (aus 77 Lebensmitteln), welche genug Kalorien und ein Minimum über 8 verschiedene Nährstoffe bietet?
- Für jedes Lebensmittel $i$ nehmen wir eine Variable $x_i \geq 0$, welche angibt, wie viel Gramm davon in die Diät kommt.
- In der Zielfunktion stehen die Kosten $c_i$ pro Gramm von Lebensmittel $i$.
- Wir wollen die Zielfunktion minimieren
- Für jeden Nährstoff $j$ ist $b_j$ die benötigte Tagesdosis in Gramm.
- Wenn $a_{ji}$ die Menge von Nährstoff $j$ in Lebensmittel $i$ ist, erhalten wir die Nebenbedingungen: \[ \sum_i a_{ji} x_i \geq b_j \qquad \forall j \]
Das Modell ist sehr ähnlich zu unserem Muffin Problem
- Stiegler konnte seiner Zeit das Problem nur Näherungsweise lösen (der Simplex Algorithmus wurde 2 Jahre später erfunden).
($39.93 pro Jahr) - 1947 berechnete ein Team aus 9 Leuten in 120 Personen Tagen die optimale Lösung mit dem Simplex
($39.69 pro Jahr) - Heute lässt sich die Lösung mit Google Sheets berechnen
- Die optimale Stigler Diät besteht aus Mehl, Leber, Kohl, Spinat und Bohnen. (Foie Linéaire à la Stigler)
Nächstes Beispiel: Wir haben 3 Muffin Fabriken mit unterschiedlichen Produktionskapazitäten in
- Bingen (3000 Stück)
- Gera (1000 Stück)
- Soltau (2000 Stück)
Für die Muffins haben wir folgende Absatzmärkte mit unterschiedlichen Bedarfen:
- Berlin (1700 Stück)
- Frankfurt (500 Stück)
- Hamburg (1500 Stück)
- Köln (800 Stück)
- München (1000 Stück)
Wir wollen die Muffins von den Fabriken zu den Absatzmärkten so transportieren, dass die Anzahl an Muffin-Kilometern minimiert wird und der Bedarf überall gedeckt wird.
Wir nehmen an, dass die Distanz zwischen Fabrik $i$ und Markt $j$ gegeben ist als $\text{distance}_{ij}$.
Welche Variablen brauchen wir?
Pro Fabrik $i$ und Markt $j$ eine Variable $x_{ij} \geq 0$, wieviele Muffins von $i$ nach $j$ transportiert werden sollen.
Zielfunktion:
\[ \min \sum_{i,j} \text{distance}_{ij} x_{ij} \]Aus einer Fabrik $i$ darf nicht mehr ausgeliefert werden, als dort produziert werden kann:
\[ \sum_j x_{ij} \leq \text{capacity}_i \qquad \forall i \]Zu einem Absatzmarkt $j$ muss mindestens soviel transportiert werden, wie dort der Bedarf ist:
\[ \sum_i x_{ij} \geq \text{demand}_j \qquad \forall j \]Das ganze Modell:
\[ \begin{aligned} \min\quad & \sum_{i,j} \text{distance}_{ij} x_{ij} \\ \text{s.t.}\quad &\sum_j x_{ij} \leq \text{capacity}_i \quad & \forall i \\ &\sum_i x_{ij} \geq \text{demand}_j \quad & \forall j \\ &x_{ij} \geq 0 \quad & \forall i,j \end{aligned} \]Neues Beispiel:
- Wir haben 23 Studierende und 5 Übungsgruppen für jeweils maximal 5 Personen
- Jede Person gibt für jede Übungsgruppe eine Präferenz zwischen 1 und 10 an.
- Wir wollen die Gruppen so zuordnen, dass die Summe der Präferenzen maximiert wird.
Welche Variablen brauchen wir?
Pro Person $i$ und Gruppe $j$ eine Variable $x_{ij} \geq 0$, ob die Person $i$ in die Gruppe $j$ geht.
Sei $p_{ij}$ die Präferenz von $i$ für Gruppe $j$
Zielfunktion:
\[ \max \sum_{i,j} p_{ij} x_{ij} \]Jede Person darf nur in genau eine Gruppe gehen:
\[ \sum_j x_{ij} = 1 \qquad \forall i \]Jede Gruppe darf nur von maximal 5 Personen gebucht werden.
\[ \sum_i x_{ij} \leq 5 \qquad \forall j \]Modifikation: Wir wollen nun dafür sorgen, dass die kleinste Präferenz maximiert wird.
Wir führen eine neue Variable $x_\text{minpref}$ für die minimale Präferenz ein.
Die neue Variable darf keine der Präferenzen übersteigen:
\[ x_\text{minpref} \leq \sum_j p_{ij} x_{ij} \qquad \forall i \]- Die neue Variable $x_\text{minpref}$ wird durch die Nebenbedingungen nicht gezwungen, den kleinsten Präferenzwert anzunehmen.
- Die Zielfunktion schiebt sie aber genau dort hin.
Allgemeiner Modellierungstrick:
Wir können das Minimum über mehrere Variablen mit einer Hilfsvariablen ermitteln, wenn diese in der Zielfunktion maximiert wird.
Analog das Maximum von mehreren Variablen, mit Minimierung in Zielfunktion.
Ähnlich: Wir haben eine Variable $x$, die potentiell negative Werte annimmt. Wir wollen den absoluten Wert $|x|$ davon minimieren:
\[ \begin{aligned} \min\quad & x_\text{abs} \\ \text{s.t.}\quad & x_\text{abs} \geq -x \\ & x_\text{abs} \geq x \end{aligned} \]Der Trick ist hier, dass für die Hilfsvariable immer eine Bedingung zieht und die andere irrelevant ist. Durch die Richtung der Zielfunktion zieht immer die richtige Bedingung.
Nächstes Beispiel: Wir suchen einen kürzesten Weg von A nach D durch ein Netzwerk von Knoten.
Natürlich können wir dieses Problem anders lösen (z.B. mit Dijkstras Algorithmus).
Als Ausgangspunkt für komplexere Modelle wollen wir das trotzdem als LP modellieren.
Wichtigste Frage: Was sind die Variablen?
Für eine Kante $ij$ von Knoten $i$ nach $j$ nehmen wir eine Variable $x_{ij} \geq 0$ die angibt, ob wir die Kante bereisen.
Wir wollen die Summe der Kantengewichte minimieren:
\[ \min 2 x_{AB} + 4 x_{AC} + 1 x_{BC} + 1 x_{CB} +\\ 3 x_{BD} + 1 x_{CD} \]
Wir müssen sicherstellen, dass wir den Knoten A verlassen:
\[ x_{AB} + x_{AC} = 1 \]
Wenn wir Knoten B betreten, müssen wir ihn auch wieder verlassen:
\[ x_{AB} + x_{CB} = x_{BC} + x_{BD} \]
Analog: Wenn wir Knoten C betreten, müssen wir ihn auch wieder verlassen:
\[ x_{AC} + x_{BC} = x_{CB} + x_{CD} \]
Optional: Wir wollen Knoten D auch wieder betreten.
\[ x_{BD} + x_{CD} = 1 \]
Warum "Optional"?
Nun können wir kürzeste Wege in beliebigen Graphen suchen.
Nächster Schritt: Was, wenn wir mehr als eine Ressource durch das Netzwerk schicken wollen?
Nun haben wir neben den Kosten je Kante auch noch Kapazitäten:
- Maximiere den Fluss von A nach D (ignoriere Kosten)
- Minimiere Kosten für eine fixe Menge an Fluss von A nach B.
Zwei unterschiedliche Ziele denkbar:
Zuerst: Maximiere Fluss von A nach D (Max Flow)
Wie zuvor nehmen wir eine Variable $x_{ij} \geq 0$ pro Kante $ij$, in der wir den Fluss von $i$ nach $j$ abbilden.
Die Nebenbedingungen funktionieren wieder so, wie bei den kürzesten Wegen: Was einen Knoten betritt, muss diesen auch wieder verlassen:
\[ x_{AB} + x_{CB} = x_{BC} + x_{BD}\\ x_{AC} + x_{BC} = x_{CB} + x_{CD} \]Ganz allgemein gilt für einen Knoten $i$:
\[ \sum_{j: i \text{ hat Kante nach } j} x_{ij} - \sum_{j: j \text{ hat Kante nach } i} x_{ji}= 0 \]"Flusserhaltung" (flow conservation)
Für jede einzelne Kante müssen wir sicherstellen, dass die Kapazität nicht überschritten wird:
\[ x_{AB} \leq 2 \quad x_{AC} \leq 3 \\ x_{BD} \leq 1 \quad x_{CD} \leq 2 \\ x_{BC} + x_{CB} \leq 5 \]
Als Zielfunktion wollen wir, dass möglichst viel Fluss den Knoten A verlässt:
\[ \max x_{AB} + x_{AC} \]
Alternativ könnten wir auch fordern dass möglichst viel bei D ankommt.
Nun wollen wir die Kosten mit einbeziehen
(Min-Cost Flow)
Minimiere die Kosten für einen Fluss von 3 Einheiten von A nach D.
Wir gehen von dem Modell gerade aus und modifizieren die Zielfunktion:
\[ \min 2 x_{AB} + 4 x_{AC} + 1 x_{BC} + 1 x_{CB} +\\ 3 x_{BD} + 1 x_{CD} \]
Analog zum kürzesten Weg.
Die Nebenbedingungen zur Flusserhaltung und zur Kantenkapazität brauchen wir nicht anfassen.
Für A oder B (oder beide) brauchen wir eine neue Bedingung:
\[ x_{AB} + x_{AC} = 3 \\ x_{BD} + x_{CD} = 3 \]
Verallgemeinerte Flusserhaltung:
\[ \sum_{j: i \text{ hat Kante nach } j} x_{ij} - \sum_{j: j \text{ hat Kante nach } i} x_{ji}= d_i \]$d_i$ ist die Differenz der Ein- und Ausflüsse des Knotens: Positiv für eine Quelle und negativ für eine Senke.
In dieser Formulierung können wir allgemein recht einfach mehrere Quellen und Senken einbauen.