3622
правки
Изменения
м
→Доказательство
Вышеописанный алгоритм строит оптимальное расписание для задачи <tex>1 \mid prec \mid f_{max} </tex>.
|proof=
[[Файл:1.jpg]] <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$ и $j$ местами, то ответ не ухудшится. Действительно, $f_j(p_{r-1}) \leqslant f_j(p_j)$ и $f_{r-1}(p_j) \leqslant f_j(p_j)$, а значения соответствующих функций для работ между $r-1$ и $j$ не изменятся, поэтому после перестановки ответ не ухудшится.
</wikitex>
