Изменения

:Рассмотрим в расширенной сети поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от <tex>J_i</tex> до <tex>I_K</tex>. Заметим, что <tex>\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i</tex>. Достаточно показать, что для каждого подмножества <tex>A \subseteq \{ 1, . . . , n \}</tex> выполняется

:<tex>\sum\limits_{i \in A} x_{iK} \leqslant T_Kh(A)</tex> ,где <tex>h(A) =

:Это означает, что условие <tex>\sum\limits_{i \in A} p_i \leqslant Th(A), \forall A \subseteq \{ 1, ... , n \}</tex> выполняется и требования к обработке <tex>x_{1K}, . . . , x_{nK}</tex> могут быть запланированы как <tex>I_K</tex> для <tex>K = 2, . . . , r</tex>. Рассмотрим подсеть в расширенной сети в подмножестве <tex>A</tex> и соответствующие части потока. Фрагмент частичного потока, который проходит через <tex>(K, j)</tex> ограничен

:<tex>\min \{ j(s_j −- s_{j + 1})T_K, |A|(s_j - s_{j+1})T_K \} = T_K(s_j - s_{j+1}) \min \{ j, |A| \}</tex>.

:Таким образом, мы имеем

:То, что равенство <tex>(*)</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>S_m = h(A)</tex>.

:В противном случае

:<tex>\sum\limits_{j = 1} \min \{ j, |A| \}(s_j - s_{j + 1}) = s_1 - s_2 + 2s_2 - 2s_3 + 3s_3 - ... + (|A| - 1)s_{|A| - 1} -\ </tex>:<tex>(|A| - 1)s_{|A|} + |A|(s_{|A|} - s_{|A| - 1} - ... - s_m + s_m - s_{m + 1}) = S_{|A|} = h(A)</tex>.

<tex>(a) \Rightarrow (b):</tex><br>:Предположим, что допустимое расписание существует. Для <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>, неравенство

:<table align = center>