32
правки
Изменения
→Динамика
|definition = <tex>\forall t_u, t_v \in \Theta, u <= v, \forall k = 1, \dots ,n:</tex>
#<tex>U_k(t_u, t_v) = \{J_i \mid i < k ; t_u <= r_i < t_v\};</tex>
#<tex>W_k(t_u, t_v, m)</tex> - максимальный вес <tex>Z \subset U_k(t_u, t_v), |Z| = m</tex> такой, что <tex>m \in (1, \dots ,n)</tex> и <tex>JPS</tex> от <tex>Z</tex> разрешимо и заканчивается до <tex>t_v</tex>. Если такое <tex>Z</tex> существует, будем говорить, что <tex>Z</tex> реализует <tex>W_k(t_u, t_v, m)</tex>. Если же такого <tex>Z</tex> не существуетнет, то <tex>W_k(t_u, t_v, m) = - \infty.</tex>}}
{{Лемма
Теперь рассмотрим случай, когда <tex>r_k \in [t_u, t_v)</tex>. Сначала докажем, что <tex>W_k(t_u, t_v, m) \geqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
* <tex>W_{k-1}(t_u, t_v, m) > \geqslant W'_k</tex>
*:Так как <tex>U_{k-1}(t_u, t_v) \subseteq U_k(t_u, t_v)</tex>, то <tex>W_{k-1}(t_u, t_v, m) \leqslant W_k(t_u, t_v, m)</tex>.
*:# <tex> p \cdot (m_2 + 1) = t_y - t_x</tex>,
*: Очевидно, что <tex>U_{k-1}(t_u, t_x), U_{k-1}(t_x, t_y)</tex> и <tex>U_{k-1}(t_y, t_v)</tex> не пересекаются. Следовательно, <tex>JPS</tex> подмножеств, которые реализуют <tex>W_{k-1}(t_u, t_x, m_1), W_{k-1}(t_x, t_y, m_2)</tex> и <tex>W_{k-1}(t_y, t_v, m_3)</tex>, поставленные друг за другом дадут правильное расписание для <tex>m-1</tex> работ взятых из <tex>U_{k-1}(t_u, t_v)</tex>. Более того, у нас достаточно места чтобы вставить работу <tex>J_k</tex> в промежуток между <tex>t_x</tex> и <tex>t_y</tex>. Это возможно, так как <tex>p \cdot (m_2 + 1) = t_y - t_x</tex> и ровно <tex>m_2</tex> работ распределено для <tex>U_{k-1}(t_x, t_y)</tex>. Таким образом <tex>W'_k \leqslant W_k(t_u, t_v, m)</tex>.
Докажем неравенство <tex>W_k(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>. Положим <tex>Z</tex> реализует <tex> W_k(t_u, t_v, m)</tex>.
* <tex>J_k \notin Z</tex>. Тогда <tex>W_k(t_u, t_v, m) = W_{k-1}(t_u, t_v, m) \leqslant \max(W_{k-1}(t_u, t_v, m), W'_k)</tex>.
* <tex>J_k \in Z</tex>.
}}
