## Nachbestellung von Fahrradschläuchen

Eine kleine Fahrradwerkstatt verkauft neben Reparaturen vor allem Ersatzschläuche eines bestimmten Herstellers.

Der Inhaber kann den Bedarf b t an Schläuchen für die kommenden 4 Wochen t = 1,...,4 aus Erfahrung recht genau vorhersagen. Er möchte die in diesem Zeitraum benötigten Schläuche so einkaufen und lagern, dass die Gesamtkosten möglichst gering sind.

| Woche t   |   1 |   2 |   3 | 4     |
|-----------|-----|-----|-----|-------|
| b t       |  70 |  40 |  50 | 60    |
| f t       |  25 |  30 |  37 | 52    |
| c t       | 0.5 | 0.4 | 0.3 | (0.3) |

Der Großhändler hat zugesagt, dass der Einkaufspreis je Schlauch im gesamten Zeitraum gleich bleibt. Für jeden Schlauch, der nicht verkauft wird und im Lager bleibt, fallen variable Lagerkosten c t (GE je Stück und Woche) an. Vereinfachend wird angenommen, dass der Bedarf b t jeweils zu Beginn der Woche t anfällt; diese Schläuche müssen in Woche t also nicht mehr gelagert werden. Jede Bestellung beim Großhändler (jeweils zu Beginn einer Woche t) verursacht fixe Bestellkosten von f t GE. Die Lieferung kommt noch am selben Tag an und kann den Bedarf dieser Woche sofort decken. Alle Daten stehen in der Tabelle oben.

Wie viele Schläuche sollten zu Beginn jeder der 4 Wochen bestellt werden (sofern überhaupt bestellt wird), damit die Gesamtkosten minimal sind? Das Lager ist zu Beginn und am Ende des Zeitraums leer.

- a) Stellen Sie das Problem als gerichteten Graphen dar: je ein Knoten für jede Woche t = 1,...,4 (bei Bedarf zusätzlich ein Knoten für eine gedachte Periode danach) und je ein Pfeil für jede mögliche Bestellung. Verwenden Sie dabei die Optimalitätseigenschaft, dass sich eine Bestellung nur lohnt, wenn das Lager leer ist (Regenerationseigenschaft). Erklären Sie, wofür ein Pfeil steht, und geben Sie passende Pfeilbewertungen an!
- b) Lösen Sie das Problem mit dem Dijkstra-Algorithmus, indem Sie einen kürzesten Weg von der Quelle zur Senke des Graphen bestimmen!
