577
правок
Изменения
→Доказательство корректности
В противном случае найдем такую работу <tex>i_t</tex> с наименьшим <tex>t</tex>, что никакая работа <tex>i_v</tex>, где <tex>v > t</tex>, не превосходит <tex>i_t</tex>, причем <tex>i_t < l</tex>. По определению это значит, что после того, как работа <tex>i_t</tex> будет добавлена в <tex>S</tex>, ни одна работа <tex>i \leq i_t</tex> не будет удалена из этого множества. Так как <tex>i_t < l</tex>, то по определению <tex>l</tex> все работы, которые на момент добавления <tex>i_t</tex> находятся в <tex>S</tex>, так же должны принадлежать <tex>S^*</tex>. Покажем, что это приведет нас к противоречию.<br>
Пусть <tex>S_t</tex> {{---}} множество <tex>S</tex> после удаления <tex>k_{i_t}</tex> и добавления <tex>i_t</tex>. Рассмотрим два случая:<br>
а). Если <tex>k^* = k_{i_t} > k</tex>, то есть <tex>d_{k^*} \geq 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>k^* < k</tex>. Тогда все работы из <tex>S_t \cup \{k\}</tex> могут быть выполнены в срок, так как <tex>S_t</tex> и <tex>k</tex> принадлежат <tex>S^*</tex>. Более того, все работы из множества <tex>\{j \in S_t | j < k\}</tex> могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество <tex>S_t \cup \{k^*\}</tex> не содержит работ со штрафами, что является противоречием.
}}
