Изменения
→Алгоритм решения
Таким образом, мы имеем
<tex>\sum\limits_{i \in A} x_{iK} \ge T_K \sum\limits_{j = 1}^m(s_j − s_{j+1}) \min \{ j, |A| \} = T_Kh(A)</tex>. <tex>(5.9*)</tex>
То, что равенство <tex>(5.9*) </tex> справедливо, может рассматриваться как следствие. Если <tex>|A| > m</tex>, то
<tex>\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - 3s_4 + ... + ms_s - ms_{m+1} =\ </tex>
Предположим, что допустимое расписание существует. Для <tex>i = 1, ... , n </tex> и <tex>K = 2, ..., r</tex> пусть <tex>x_{iK}</tex> является "объемом работ", который будет выполняться в интервале <tex>I_K</tex> в соответствии с нашим возможным расписанием. Тогда для всех <tex>K = 2, ..., r</tex> и произвольных наборов <tex>A \subseteq \{ 1, . . . , n \}</tex>, неравенство
<tex>\sum\limits_{i \in A} x_{iK} \le T_Kh(A)</tex> <tex> (5.10**)</tex>
выполняется. Кроме того, для <tex>i = 1, . . . , n</tex> у нас <tex>p_i = \sum\limits_{K = 2}^r s_{iK}</tex>. Остается показать, что можно отправить <tex>x_{iK}</tex> от <tex>J_i</tex> до <tex>I_K</tex> <tex>(i = 1, . . . , n; K = 2, . . . , r)</tex> в расширенной сети. Такой поток существует, если <tex>\forall A \subseteq \{ 1, . . . , n \}</tex> и <tex>K = 2, . . . , r</tex> значение <tex>\sum\limits_{i \in A} x_{iK}</tex> ограничено величиной минимального среза части сети с истоками <tex>J_i(i \in A)</tex> и стоком <tex>I_K</tex>. Тем не менее, это значение
<tex>T_K\sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})</tex>
Используя <tex>(5.10**) </tex> и правую часть <tex>(5.9*)</tex>, получаем
<tex>\sum\limits_{i \in A} x_{iK} \le T_K h(A) = T_K \sum\limits_{j = 1}^m \min \{ j, |A| \}(s_j - s_{j+1})</tex>
