264
правки
Изменения
Нет описания правки
|id=lemma1
|statement= Существует оптимальное расписание <tex>S</tex> в котором все <tex>n</tex> задач распределены по всем временам <tex>t_i (i = 1\ldots n)</tex>, которые выбирает приведенный выше алгоритм.
|proof= Предположим, что в некоторое оптимальное расписание <tex>S</tex> входят времена <tex> t_1 \ldots t_j, </tex> где <tex> j < n</tex> и из всех возможных оптимальных расписаний мы возьмем то, у которого <tex>j</tex> будет максимально возможное для этого расписания. Из того, как в алгоритме выбирались значения для <tex>t_i</tex> следует, что <tex>t_{j + 1}</tex> {{---}} минимальное возможное время, большее <tex>t_j,</tex> , в которое вообще можно начать выполнять какое-нибудь из оставшихся заданий. Если во время <tex>t_{j+1}</tex> в расписании <tex>S</tex> не выполняется никакого задания, то какое-то задание, которое могло бы выполнится в момент времени <tex>t_{j+1}</tex> выполняется в <tex>S</tex> позднее. Значит оно может быть перемещено в нашем расписании <tex>S</tex> на время <tex>t_{j+1}</tex> без увеличения целевой функции. Таким образом, наше новое расписание тоже будет оптимальным. Получили противоречие с максимальностью <tex>j</tex>. Значит из всех оптимальных расписаний нам подходят только те, в которых <tex>j = n</tex>.
}}
Заметим, что в полученном расписании будут интервалы в которые машина будет работать без остановки, и будут периоды простоя.
Для того, чтобы найти это оптимальное расписание, сведем к задаче о назначения следующим образом:
<tex>V_1=\left \{ 1,\ldots,n \right\}</tex>
<tex>V_2=\left \{ t_1,\ldots,t_n \right\}</tex>
<p>
<tex>
c_{ij} =
\left \{\begin{array}{ll} f_i(t_j + 1), & r_i \le t_i \\
\infty, & otherwise
\end{array} \right.
</tex>
</p>
