TODO: Verweis auf Literatur Sioshansi Branch and Bound Cutting Planes, Implementierung mit SciPy und PuLP, keine Schattenpreise
TODO: Beispiele
Betrachten wir ein Busunternehmen, das eine optimale Personaleinsatzplanung erstellen möchte. Der Bedarf an Bussen variiert, wie in folgender Abbildung dargestellt, aufgrund der Kundennachfrage von Stunde zu Stunde:
import numpy as np
from scipy.optimize import linprog
import matplotlib.pyplot as plt
periods = np.arange(0, 24, 4)
buses = np.array([4, 8, 10, 7, 12, 4])
plt.figure(figsize=(5, 3))
plt.bar(periods, buses, width=4,
color='lightgray', align='edge')
plt.xticks(periods)
plt.xlabel('Tageszeit')
plt.ylabel('Bedarf an Bussen')
plt.grid(True)
Beispielsweise müssen vier Busse von Mitternacht bis 4 Uhr im Einsatz sein, während acht Busse von 4 bis 8 Uhr fahren müssen. Wir gehen davon aus, dass die Nachfrage jeden Tag die gleiche ist.
Sie sollen bestimmen, wie viele Fahrer für jede Startzeit bei Bedarfsdeckung einzuplanen sind. Fahrer arbeiten in 8-Stundenschichten, die um 0, 4, 8, 12, 16 oder 20 Uhr beginnen. Zum Beispiel kann ein Fahrer ab 0 Uhr einen Bus bis 8 Uhr fahren. Ein Fahrer, der um 20 Uhr zu arbeiten beginnt, fährt die letzten vier Stunden des Tages und die ersten vier Stunden des nächsten Tags. Das Ziel besteht darin, die Anzahl der eingesetzten Fahrer und somit die Kosten zu minimieren. Beachten Sie, dass, obwohl ein Fahrer für einen Zeitraum von acht Stunden eingesetzt werden kann, es nicht erforderlich ist, dass er für den gesamten Zeitraum einen Bus fährt. Er könnte auch für vier Stunden innerhalb seines Zeitraums pausieren.
Eine zulässige Entscheidung für dieses Problem besteht darin, 8 Fahrer zum Zeitpunkt 0, 10 Fahrer zum Zeitpunkt 8 und 12 Fahrer zum Zeitpunkt 16 einzusetzen. Diese Entscheidung deckt alle Anforderungen ab und verwendet insgesamt 30 Fahrer, ist aber nicht optimal. Das Problem besteht darin, die kleinst mögliche Anzahl an Fahrern zu finden.
Lösen Sie das LP in Python.
TODO: Aufgaben