Изменения

Для решения этой задачи, мы должны найти множество <tex>S</tex> работ, которые успеваем выполнить до дедлайна. Значит нам надо минимизировать: <tex>\sum\limits_{ i \notin S } {w_{i}}</tex>. Будем решать эту задачу с помощью [[Динамическое_программирование|динамического программирования]] с использованием утверждений из решения задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i d_{i} \mid - </tex>]].

Пусть <tex>h^S</tex> {{---}} вектор соответствующий множеству <tex>S</tex> из задачи [[Opij1di|<tex> O \mid p_{i,j} = 1, d_i \mid - </tex>]]. Тогда, для добавления работы <tex>i</tex> в множество <tex>S</tex> должно выполняться неравенство: <tex>m \cdot (d_i d_{i} - m) - ( km k m - \sum\limits_{j = 1}^m {h^S(d_i d_{i} - m + j)})+x(d_id_{i}) \geqslant m</tex>, где <tex>k=|S|</tex> и <tex>x(d_id_{i})</tex> {{---}} количество периодов времени <tex>t</tex> со свойствами: <tex>d_i d_{i} - m + 1 \leqslant t \leqslant d_id_{i}</tex> и <tex>h^S(t) < m</tex>. Чтобы проверить это неравенство, нам нужно посчитать <tex>m</tex> чисел <tex>h^S(t)</tex>, <tex>t=d_i d_{i} - m + 1, \ldots, d_id_{i}</tex>. Для этого определим переменные:

<tex>k_jk_{j} = \begin{cases} h^S(d_i d_{i} - m + j) & j \in \{1 , \ldots , m\} \\

<tex>l_j=\begin{cases}1 & j \in \{1 , \ldots , m\}\text{; } k_j k_{j} < m \\

Тогда можно заметить, что <tex>x(d_id_{i})=\sum\limits_{j = 1}^m {l_jl_{j}}</tex>, так как <tex>l_j l_{j} = 1</tex> если <tex>1 \leqslant j \leqslant m</tex> и <tex>h^S(d_i d_{i} - m + j) < m</tex> или <tex>d_i d_{i} - m + 1 \leqslant d_i d_{i} - m + j \leqslant d_id_{i}</tex> и <tex>h^S(d_i d_{i} - m + j) < m</tex>. Следовательно можно упростить исходное неравенство: <tex>m \cdot (d_i d_{i} - m) - (km k m - \sum\limits_{j = 1}^m {k_jk_{j}}) + \sum\limits_{j = 1}^m {l_jl_{j}} \geqslant m</tex> или <tex>m \cdot (d_i d_{i} - m - k)+ \sum\limits_{j = 1}^m {(k_j k_{j} + l_jl_{j})} \geqslant m</tex>.

Для динамического программирования определим <tex>f_if_{i} (k , k_1 k_{1} , \ldots , k_mk_{m})</tex> {{---}} минимальное значение целевой функции для расписания работ <tex>i , i+1 , \ldots , n</tex>, позволяющее выполнить работы из множества <tex>S</tex> без опоздания, где <tex>k = |S|, S \subseteq \{1, \ldots , i - 1\}</tex> и <tex>k_jk_{j}=h^S(d_i d_{i} - m + j)</tex>, где <tex>j = 1, \ldots , m</tex>, то есть <tex>f_if_{i} (k, k_1k_{1}, \ldots , k_mk_{m}) = \min\limits_{S: |S| = k, S \subseteq \{1, \ldots , i - 1 \}}(\sum\limits_{j = i}^n {w_jU_jw_{j} U_{j}})</tex>.

Пусть <tex>p = d_{i + 1} - d_id_{i}</tex>, тогда определим рекуррентное выражение для <tex>f_if_{i} (k, k_1k_{1}, \ldots , k_m)</tex>:

<tex>f_if_{i} (k, k_1k_{1}, \ldots , k_mk_{m})=\begin{cases}f_{i + 1}(k, k_{1 + p},k_{2 + p}, \ldots, k_{m + p}) + w_iw_{i}, & m\cdot (d_i d_{i} - m - k)+ \sum\limits_{j = 1}^m {(k_j k_{j} + l_jl_{j})} < m \text{ } (1)\\\min(f_{i + 1}(k, k_{1 + p}, k_{2 + p}, \ldots , k_{m + p}) + w_i w_{i} ; f_{i + 1}(k + 1, k_{1 + p} + l_{1 + p},k_{2 + p} + l_{2 + p}, \ldots ,k_{m + p} + l_{m + p})), & m\cdot (d_i - m - k) + \sum\limits_{j = 1}^m {(k_j k_{j} + l_jl_{j})} \geqslant m \text{ }(2)\\

c начальным условием: <tex>f_{n + 1}(k, k_1k_{1}, \ldots , k_mk_{m}) = 0 </tex> для <tex>k, k_1k_{1}, \ldots , k_m k_{m} = 0, 1, \ldots , m</tex>.

Если выполняется неравенство <tex>(1)</tex>, то мы не можем добавить работу <tex>i</tex> в множество <tex>S</tex> и поэтому <tex>f_if_{i} (k, k_1 k_{1} \ldots , k_mk_{m}) = f_{i + 1}(k, k_{1 + p}, k_{2 + p}, \ldots, k_{m + p}) + w_iw_{i}</tex>.

Если выполняется неравенство <tex>(2)</tex>, тогда мы может добавить работу <tex>i</tex> в множество <tex>S</tex> или не добавлять. Если мы добавим работу <tex>i</tex>, то <tex>f_if_{i} (k, k_1k_{1}, \ldots , k_mk_{m}) = f_{i + 1}(k + 1,k_{1 + p} + l_{1 + p},k_{2 + p}+l_{2 + p}, \ldots ,k_{m + p}+l_{m + p}) \text{ } (3)</tex>. Если мы не добавим работу <tex>i</tex>, то по аналогии с первым случаем <tex>f_if_{i} (k, k_1k_{1}, \ldots , k_mk_{m}) = f_{i + 1}(k, k_{1 + p},k_{2 + p}, \ldots, k_{m + p}) +w_i w_{i} \text{ } (4)</tex>. Так как <tex>f_if_{i} (k, k_1k_{1}, \ldots , k_mk_{m}) = \min(\sum\limits_{j = i}^n {w_jU_jw_{j} U_{j}})</tex>, то нам надо взять минимум из значений <tex>(3)</tex> и <tex>(4)</tex>.

Ответ на задачу будет находиться в <tex>f_1f_{1} (0, 0, \ldots , 0)</tex>.