577
правок
Изменения
→Доказательство корректности
#:Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:<br>
#::<tex>(a)</tex> Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geqslant d_k</tex>, то мы можем заменить <tex>k</tex> на <tex>k^*</tex> в <tex>S^*</tex>, сохранив условие, что <tex>S^*</tex> не содержит опаздывающих работ. Следовательно, множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что противоречит построению <tex>S</tex>.
#::<tex>(b)</tex> Пусть <tex>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | \mid j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.
}}
