355
правок
Изменения
→Доказательство
<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}$. Теперь если мы сместим блок работ между Пусть $p_{r-1}$ и $p_j$ есть времена, в которые выполняются работы $r-1$ и $j$ влево. Теперь, поставив если мы поменяем работы $r-1$ перед и $rj$местами, то время окончания каждой работы из этого блока только уменьшится, и значения соответствующих функций ответ не увеличатся по монотонностиухудшится. АДействительно, так как $f_j(p_{r-1}) \le f_j(p_j)$ и $f_{r-1}(pp_j) \le f_j(pp_j)$, где а значения соответствующих функций для работ между $p = \sum^{r-1}_{i=1}{p_i}$, то и сам $f_{max}j$ также не увеличится. Проделывая эти действия далееизменятся, мы придем к тому расписанию, который строит наш алгоритм, без ухудшения ответапоэтому после перестановки ответ не ухудшится.
</wikitex>
}}
