577
правок
Изменения
→Доказательство корректности
Покажем, что в <tex>S^*</tex> работа <tex>k</tex> может быть заменена работой <tex>l</tex> без увеличения значения целевой функции. Рассмотрим два случая:<br>
1. Пусть <tex>l < k</tex>.<br>
То, что <tex>k</tex> не принадлежит множеству <tex>S</tex>, значит, что либо на некотором шаге появилась опаздывающая работа <tex>j</tex>, которая заменила <tex>k</tex>, либо работа <tex>k</tex> опаздывала и <tex>w_k</tex> было меньше <tex>\min\limits_{i \in S}w_i</tex>, и поэтому она не была добавлена. В любом случае в это время работа <tex>l</tex> уже принадлежала <tex>S</tex>. Из этого следуетВо втором случае очевидно, что <tex>w_k \leq w_l</tex>, во втором . То же неравенство выполняется и в первом случае очевидно, почему, а в первом {{---}} потому что так как на этапе замены мы выбрали <tex>k</tex>, а не <tex>l</tex>. Следовательно, мы не ухудшим целевую функцию заменой <tex>k</tex> на <tex>l</tex>.<br>
2. Пусть <tex>l > k</tex>.<br>
Замена работы <tex>k</tex> в <tex>S^*</tex> на работу <tex>l</tex> не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как <tex>k</tex> выполнялась в срок, а <tex>d_k \leq d_l</tex> и все работы выполняются одинаковое количество времени. Следовательно, <tex>l</tex> так же будет выполнена в срок. Осталось доказать, что <tex>w_k \leq w_l</tex>. <br>
* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \cdots s - 1]</tex>
* <tex>j_{s - 1} < l \leq j_s</tex> ,
то <tex>w_l \geq w_{k_{j_s}} \geq \cdots \geq w_{k_{j_0}} = w_k</tex>, что доказывает теремутеорему.<br>
}}
