1302
правки
Изменения
→Алгоритм: Лемма 4.6
б) Если <tex>I \sim J</tex> и <tex>q(I) = q(J)</tex>, то <tex>\pi'</tex> тоже оптимальное расписание.
|proof=
а) Пусть <tex>f = \sum w_i C_i</tex>. Так как <tex>\pi</tex> {{---}} оптимальное расписание, то <tex>f(\pi) \le f(\pi')</tex>. Таким образом:
<tex>0 \le f(\pi') - f(\pi) = w(I) p(J) - w(J) p(I)</tex> Поделим на <tex>p(I)p(J)</tex>: <tex>q(I) = w(I) / p(I) \ge w(J) / p(J) = q(J) </tex> б)Если <tex>q(I) = q(J) </tex>, то <tex>f(\pi) = f(\pi') </tex>, следовательно расписание <tex>\pi'</tex> тоже оптимально.
}}
