51
правка
Изменения
→Корректность алгоритма
# <tex>\max \{W_{k - 1} (s, e), W'_k (s, e)\} \leqslant W^*_k (s, e)</tex>
#: Так как <tex>U_{k - 1} (s, e) \subseteq U_k (s, e)</tex>, то <tex>W_{k - 1} (s, e) = W^*_{k - 1} (s, e) \leqslant W^*_k (s, e)</tex>. Кроме того, если <tex>W'_k (s, e) > 0</tex>, то существует такое время <tex>s' \mid \max \{r_k, s + p\} \leqslant s' \leqslant \min \{d_k, e\} - p</tex>, что:
#:<tex>W'_k (s, e) = w_k + W_{k - 1} (s, s') + W_{k - 1} (s', e) = w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e) \leqslant W^*_k (s, s'e)</tex>
#:
#: Неравенство выполняется, так как <tex>w_k + W^*_{k - 1} (s, s') + W^*_{k - 1} (s', e)</tex> - суммарный вес расписания, состоящего из:
