Для любого <tex>k = 0, \dots, n</tex> и для любого <tex>s, e \in T \mid s \leqslant e</tex>, выполняетсяравенство: <tex>F_k (s, e) = F^*_k (s, e)</tex>.
|proof=
PROOFБудем полагать, что равенство верно для <tex>k - 1</tex> (очевидно, равенство выполнится при <tex>k = 0</tex>). Если <tex>r_k \notin [s - p, e)</tex>, тогда <tex>U_k(s - p, e) = U_{k - 1}(s - p, e)</tex> что подразумевается в равенстве. Теперь нужно показать, что а) <tex>F^{*}_k(s, e) \leq F^{'}_k(s, e)</tex>; б) <tex>F^{'}_k(s, e) \leq F^{*}_k(s, e)</tex> при <tex>r_k \in [s - p, e)</tex>. а) Полагаем, что <tex>F^{'}_k</tex> ограничена. Тогда существует <tex>t_k \in T</tex> такая, что <tex>max{s, t_k} \leq t_k \leq e - p</tex>, при которой <tex>F^*_k(s, e) = F_{k - 1}(s, t_k) + F_{k-1}(t_k + p, e) + f_k(t_k + p) = F^*_{k-1}(s, t_k) + F^*_k-1(t_k + p, e) + f_k(t_k + p) \geq F^*_k(s, e).</tex> б) Полагаем, что <tex>F^{*}_k</tex> ограничена. Среди всех оптимальных расписаний, возвращающих <tex>F^{*}_k(s, e)</tex> выберем оптимальное расписание <tex>S</tex>, соответствующий вектор времён окончания работ которого <tex>(C_{i_1}, C_{i_2}, ... , C_{i_l})</tex> минимален при условии, что <tex>i_1 \leq i_2 \leq \dots \leq i_l</tex> в лексикографическом порядке. Пусть <tex>t_k \in T</tex> — время начала работы <tex>k</tex> в расписании <tex>S</tex>. Тогда <tex>F^{*}_k(s, e) = \sum\limits_{j \in U_k(s - p, e)}{f_j(C_j)} = \sum\limits_{j \in U_k(s - p, t_k)}{f_j(C_j)} + \sum\limits_{j \in U_k(t_k, e)}{f_j(C_j)} + f_k(t_k + p) \geq F_{k-1}(s, t_k) + F_{k-1}(t_k + p, e) + f_k(t_k + p) \geq F^{'}_k(s, e).</tex> Чтобы проверить первое неравенство, нужно показать, что все работы <tex>U_{k-1}(s - p, t_k)</tex> записаны в <tex>S</tex> в пределах интервала <tex>[s, t_k]</tex>, а все работы <tex>U_{k-1}(t_k, e)</tex> — в пределах <tex>[t_k + p, e]</tex>. Докажем первое утверждение (второе доказывается аналогично). Полагаем, что существует работа <tex>j</tex> такая, что <tex> s - p \leq r_j \leq t_k</tex>, начинающаяся в расписании <tex>S</tex> позже, чем работа <tex>k (t_j > t_k)</tex>. Поменяв местами <tex>k</tex> и <tex>j</tex>, получим оптимальное расписание <tex>S'</tex> такое, что <tex>v = |S'| - |S| = f_j(t_k + p) + f_k(t_j + p) - f_j(t_j + p) - f_k(t_k + p) = (f_j - f_k)(t_k + p) - (f_j - f_k)(t_j + p)</tex>, где <tex>|S|</tex> — объективное значение расписания <tex>S.</tex> <tex>j < k</tex> подразумевает <tex>v \leq 0</tex>, так как <tex>f_j - f_k</tex> не убывает по условию. Таким образом, <tex>S'</tex> также является оптимальным, несмотря на то, что это противоречит лексикографической минимальности расписания <tex>S</tex>.
