3622
правки
Изменения
м
→Доказательство оптимальности алгоритма
Доказательство проведём по индукции. Очевидно, что для одной вершины алгоритм построит оптимальное расписание. Пусть теперь он может составить оптимальную последовательность назначенных работ числом меньше <tex> n </tex>. Пусть также работы <tex> i, j </tex> {{---}} работы, которые объединятся на первом шаге алгоритма. Тогда оптимальное расписание <tex> R </tex> можно представить следующим образом:
<tex> \pi \colon \pi (1), ...\ldots, \pi (k), i, j, \pi (k + 3), ...\ldots, \pi (n) </tex>
После объединения работ <tex> i </tex> и <tex> j </tex> в одну расписание <tex> R' </tex> примет такой вид:
<tex> \pi ' \colon \pi (1), ...\ldots, \pi (k), I, \pi (k + 3), ...\ldots, \pi (n) </tex>
где <tex> I = \{i, j\}, ~w(I) = w(i) + w(j), p(I) = p(i) + p(j)</tex>. Обозначим за <tex> f_n(\pi ), ~f_{n-1}(\pi ') </tex> целевые функции для последовательностей <tex> \pi </tex> и <tex> \pi ' </tex> соответственно. Тогда
Теперь разделим обе части равенства <tex> (*) </tex> на <tex> w(i)w(j) </tex>. Получим, что расстояние между целевыми функциями равно
<tex dpi = 150> -\fracdfrac{p(j)}{w(j)} = -\fracdfrac{1}{q(j)} </tex>
Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.
