355
правок
Изменения
→Доказательство
{{Утверждение
|statement=
Вышеописанный алгоритм строит оптимальное расписаниедля задачи <tex>1 \mid prec \mid f_{max} </tex>.
|proof=
<wikitex>Пусть алгоритм построил расписание, в котором работы идут в порядке $1,2,\dots,n$. Также пусть $\sigma : \sigma(1), \dots, \sigma(n)$ {{---}} оптимальное расписание. Предположим, что $\sigma(i) = i$ для $i = n, n-1, \dots, r$ и $\sigma(r - 1) \ne r-1$, причем $r$ минимальное. Тогда имеем ситуацию, изображенную на рисунке:
[[Файл:1.jpg|right]]
Мы можем поставить работу $r - 1$ сразу перед $r$ по построению. Поэтому $r - 1$ и $j$ не имеют наследников в множестве ${1,\dots,r-1}$. Теперь если мы сместим блок работ между $r-1$ и $r$ влево, поставив $r-1$ перед $r$, то время окончания каждой работы из этого блока только уменьшится, и значения соответствующих функций не увеличатся по монотонности. А, так как $f_{r-1}(p) \le f_j(p)$, где $p = \sum^{r-1}_{i=1}{p_i}$, то $f_{max}$ не увеличится. Проделывая описанное далее, мы придем к тому расписанию, который строит наш алгоритм, без ухудшения ответа.
</wikitex>
}}
