3622
правки
Изменения
→Доказательство оптимальности алгоритма
<tex> \pi ' \colon \pi (1), ..., \pi (k), I, \pi (k + 3), ..., \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>f_n(\pi ) - f_{n-1}(\pi ') \\ = w(i)p(i) + w(j)(p(i) + p(j)) - (w(i) + w(j))(p(i) + p(j)) = -w(i)p(j) ~\ (*)</tex>
Следовательно, расписание <tex> R </tex> будет оптимальным тогда и только тогда, когда расписание <tex> R' </tex> будет оптимальным. А по предположению индукции наш алгоритм составит оптимальное расписание для последовательности <tex> \pi ' </tex>.
Это расстояние минимально (по модулю), так как мы выбирали работу <tex> j </tex> с максимальным значением <tex> q(j) </tex>. Из этих утверждений и следует оптимальность построенного алгоритмом расписания.
}}
== Литература ==
* P. Brucker. Scheduling Algorithms (2006), 5th edition, стр. 73 - 78
