577
правок
Изменения
→Доказательство корректности
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>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \cdots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \cdots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \cdots < i_r</tex>.<br>[[Файл:Sh.jpg|250px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leq i_u</tex>. Тогда <tex>w_{k_{i_v}} \geq w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга.
}}
