577
правок
Изменения
Нет описания правки
|proof=
Пусть <tex>S</tex> {{---}} множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа <tex>j</tex> заменила работу <tex>i</tex>, которая успевала выполниться до истечения <tex>d_i</tex>, то <tex>j</tex> так же успеет выполниться в срок, потому что <tex>d_i \leq d_j</tex>.<br>
Пусть <tex>S^*</tex> {{---}} множество работ без штрафов в оптимальном расписании.<br>Определим работы <tex>l</tex> и <tex>k</tex> следующим образом:* <tex>l</tex> {{---}} первая работа в <tex>S</tex>: <tex>l \notin S^*</tex>* <tex>k</tex> {{---}} первая работа в <tex>S^*</tex>: <tex>k \notin S</tex>Покажем, что в <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>.2. Пусть <tex>l > k</tex>.<br>
}}
