|
Пусть [math]S[/math] — множество работ, вычисленное с помощью алгоритма. Тогда все работы, находящиеся в этом множестве, будут выполнены в срок, то есть штраф за них налагаться не будет, так как если работа [math]j[/math] заменила работу [math]i[/math], которая успевала выполниться до истечения [math]d_i[/math], то [math]j[/math] так же успеет выполниться в срок, потому что [math]d_i \leqslant d_j[/math].
Пусть [math]S^*[/math] — множество работ без штрафов в оптимальном расписании.
Определим работы [math]l[/math] и [math]k[/math] следующим образом:
- [math]l[/math] — первая работа в [math]S[/math]: [math]l \notin S^*[/math]
- [math]k[/math] — первая работа в [math]S^*[/math]: [math]k \notin S[/math]
Покажем, что в [math]S^*[/math] работа [math]k[/math] может быть заменена работой [math]l[/math] без увеличения значения целевой функции. Рассмотрим два случая:
- Пусть [math]l \lt k[/math].
- То, что [math]k[/math] не принадлежит множеству [math]S[/math], значит, что либо на некотором шаге появилась опаздывающая работа [math]j[/math], которая заменила [math]k[/math], либо работа [math]k[/math] опаздывала и [math]w_k[/math] было меньше [math]\min\limits_{i \in S}w_i[/math], и поэтому она не была добавлена. В любом случае в это время работа [math]l[/math] уже принадлежала [math]S[/math]. Во втором случае очевидно, что [math]w_k \leqslant w_l[/math]. То же неравенство выполняется и в первом случае, так как на этапе замены мы выбрали [math]k[/math], а не [math]l[/math]. Следовательно, мы не ухудшим целевую функцию заменой [math]k[/math] на [math]l[/math].
- Пусть [math]l \gt k[/math].
- Замена работы [math]k[/math] в [math]S^*[/math] на работу [math]l[/math] не противоречит условию, что за все работы в этом множестве штраф налагаться не будет, так как [math]k[/math] выполнялась в срок, а [math]d_k \leqslant d_l[/math] и все работы выполняются одинаковое количество времени. Следовательно, [math]l[/math] так же будет выполнена в срок. Осталось доказать, что [math]w_k \leqslant w_l[/math].
- Пусть работа [math]k_{i_0} = k[/math] была заменена работой [math]i_0[/math], а так же [math]k_{i_1} \ldots k_{i_r}[/math] — последовательность работ из [math]S[/math], каждая из которых была на некотором шаге заменена работой [math]i_1 \ldots i_r[/math] соответственно. Тогда [math]i_0 \lt i_1 \lt \ldots \lt i_r[/math].
 Рис. 1. [math]i_v[/math] превосходит [math]i_u[/math]. - Будем говорить [math]i_v[/math] превосходит [math]i_u[/math], где [math]u \lt v[/math], если [math]k_{i_v} \leqslant i_u[/math]. Тогда [math]w_{k_{i_v}} \geqslant w_{k_{i_u}}[/math], так как когда мы вставляли работу [math]i_u[/math] мы выбрали для замены [math]k_{i_u}[/math], то есть ее вес был минимальным среди всех работ, находившихся на тот момент в [math]S[/math], включая [math]k_{i_v}[/math]. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг друга согласно их номерам.
- Если из последовательности [math]i_0 \lt i_1 \lt \ldots \lt i_r[/math] можно выделить подпоследовательность [math]j_0 = i_0 \lt j_1 \lt \ldots \lt j_s[/math] со свойствами:
- [math]j_{v + 1}[/math] превосходит [math]j_v[/math], где [math]v \in [0 \ldots s - 1][/math]
- [math]j_{s - 1} \lt l \leqslant j_s[/math] ,
- то [math]w_l \geqslant w_{k_{j_s}} \geqslant \ldots \geqslant w_{k_{j_0}} = w_k[/math], что доказывает теорему.
- В противном случае найдем такую работу [math]i_t[/math] с наименьшим [math]t[/math], что никакая работа [math]i_v[/math], где [math]v \gt t[/math], не превосходит [math]i_t[/math], причем [math]i_t \lt l[/math]. По определению это значит, что после того, как работа [math]i_t[/math] будет добавлена в [math]S[/math], ни одна работа [math]i \leqslant i_t[/math] не будет удалена из этого множества. Так как [math]i_t \lt l[/math], то по определению [math]l[/math] все работы, которые на момент добавления [math]i_t[/math] находятся в [math]S[/math], так же должны принадлежать [math]S^*[/math]. Покажем, что это приведет нас к противоречию.
- Пусть [math]S_t[/math] — множество [math]S[/math] после удаления [math]k_{i_t}[/math] и добавления [math]i_t[/math]. Рассмотрим два случая:
- [math](a)[/math] Если [math]k^* = k_{i_t} \gt k[/math], то есть [math]d_{k^*} \geqslant d_k[/math], то мы можем заменить [math]k[/math] на [math]k^*[/math] в [math]S^*[/math], сохранив условие, что [math]S^*[/math] не содержит опаздывающих работ. Следовательно, множество [math]S_t \cup \{k^*\}[/math] не содержит работ со штрафами, что противоречит построению [math]S[/math].
- [math](b)[/math] Пусть [math]k^* \lt k[/math]. Тогда все работы из [math]S_t \cup \{k\}[/math] могут быть выполнены в срок, так как [math]S_t[/math] и [math]k[/math] принадлежат [math]S^*[/math]. Более того, все работы из множества [math]\{j \in S_t \mid j \lt k\}[/math] могут быть выполнены без опозданий. Таким образом, мы снова приходим к тому, что множество [math]S_t \cup \{k^*\}[/math] не содержит работ со штрафами, что является противоречием.
|
