Изменения
→Доказательство корректности
== Доказательство корректности ==
Докажем две леммы:
{{Лемма
|id=lemma1
|statement= В оптимальном расписании на каждом станке работы выполняются в порядке неубывания.
|proof= Пусть это не так. Заметим что каждая работа даёт вклад в <tex>\sum C_{i}</tex> равный <tex>p_{i} \cdot (b_{i} + 1)</tex>. Тогда поменяем местами две работы которые нарушают порядок невозрастания. Заметим что <tex>\sum C_{i}</tex> уменьшилась. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}}
{{Лемма
|id=lemma2
|statement= В оптимальном расписании количество выполненных работ на любых двух станках отличается не более чем на <tex>1</tex>.
|proof= Пусть это не так. Как было отмечено в предыдущей лемме, каждая работа даёт вклад в <tex>\sum C_{i}</tex> равный <tex>p_{i} \cdot (b_{i} + 1)</tex>. Найдём два станка количество работ на которых отличается больше чем на <tex>1</tex>. Пусть это станки <tex>x</tex> и <tex>y</tex>. Причём на стнаке <tex>x</tex> выполняется больше работ. Тогда если отправить первую с начала работу со станка <tex>x</tex> на станок <tex>y</tex> то <tex>\sum C_{i}</tex> уменьшится на разность количества работ на станках <tex>x</tex> и <tex>y</tex>. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие.}}
{{Теорема
|id=theorem1
|statement= Алгоритм <tex>P \mid \mid \sum C_{i}</tex> строит оптимальное расписание.
|proof= Пусть это не так и оптимальное расписание отличается от расписания построенного алгоритмом. Заметим что расписание построенное алгоритмом удовлетворяет обеим леммам. Тогда можно воспользоваться одной из них чтобы улучшить оптимальное раписание. Следовательно {{---}} оптимальное расписание не оптимально. Противоречие. }}
