264
правки
Изменения
Нет описания правки
<tex dpi = "200" >1 \mid r_i, p_i = 1 \mid \sum f_i</tex>
Для каждой работы задана монотонно неубывающая функция <tex>f_i</tex>. Необходимо минимизировать <tex> \sum f_i, </tex> где каждая <tex>f_i</tex> считается на значении времени завершения выполнения задания с номером <tex>i</tex>.
==Решение==
{{Лемма
|id=lemma1
|statement= Существует Пусть значения <tex>t_i</tex> вычислены приведенным выше алгоритмом. Тогда существует оптимальное расписание <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>t_{j+1}</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>r_i = 0.</tex> Заданы функции <tex>f_i</tex>: <tex>f_1(t) = t^2 </tex> <tex>f_2(t) = t^3 </tex> <tex>f_3(t) = \mathrm{e} ^ t </tex> Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях: <tex>\begin{tabular}{c||ccc}$t_i$ $\backslash$ i & 1 & 2 & 3 \\\hline\hline0 & 1 & 1 & $\mathrm{e}$ \\1 & 4 & 8 & $\mathrm{e} ^ 2$ \\2 & 9 & 27 & $\mathrm{e} ^ 3$\\\hline\end{tabular} </tex> В результате будет выбрано расписание, в котором сначала будет идти третья, затем вторая, а затем первая работа. ==См. также ==
* [[Классификация задач]]
* [[1precpmtnrifmax|<tex>1 \mid prec, pmtn, r_i \mid f_{\max}</tex>]]
