Summe der Wartezeiten beim Arzt minimieren

Question

würde mich freuen, wenn ihr mir bei der folgenden Aufgabe helfen könntet:

Es seien n Patienten im Wartezimmer beim Arzt. Zu jeder der n Patienten (P₁, ... , P_n) ist die jeweilige Behandlungszeit (t₁, ... , t_n) bekannt. In welcher Reihenfolge müssen die Patienten behandelt werden, damit die Summe der Wartezeiten aller zu behandelnden Patienten minimal wird? Beweisen Sie Ihre Vermutung.

Die Antwort ist mir durch Probieren schnell klar geworden: Die Patienten müssen in aufsteigender Reihenfolge bzgl. Ihrer Behandlungszeit behandelt werden.

Aber wie kann ich das beweisen? Wir sollen das mit Widerspruch machen.

Vielen Dank für jegliche Hilfe und LG,
Fehlerteufel

Answer 1

Hi,

wenn die Wartezeiten aufsteigend sortiert sind, d.h. wenn gilt \( t_1 \le t_2 \le ... \le t_n \) ist die Gesamtwartezeit
$$ T = \sum_{j=2}^n \sum_{i=1}^{j-1} t_i = \sum_{i=1}^{n-1} (n-i)t_i $$
Tauscht  man zwei Patienten gegeneinander aus, also den \( \text{l'ten} \) gegen den \( \text{k'ten} \) mit \( k > l \) verändert sich die Gesamtwartezeit um den Betrag
$$ (n-l)t_k + (n-k)t_l - (n-l)t_l - (n-k)t_k = (t_k-t_l)(k-l) > 0 $$ weil beide Faktoren \( \ge 0 \) sind.
Damit ist gezeigt, dass eine Änderung in der Patientenreihenfolge gegenüber der aufsteigend Sortierten Reihenfolge immer eine Vergrößerung der Gesamtwartezeit zur Folge hat.