Изменения
→Алгоритм решения
Расширим сеть, показанную на Рис. 1 следующим образом:
<tex>I_K</tex> - произвольный интервал-узел. Обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>, тогда замененная нами подсеть(Рис. 2.1) определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>. Расширение сети показано на Рис . 2.2.
Cчитаем, что станки индексируются в порядке невозрастания скоростей <tex> s_1 \ge s_2 \ge . . . \ge s_m </tex>, кроме того <tex>s_{m+1} = 0</tex>.
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>. При <tex>j = 1,..., m </tex>, есть дуги от <tex>(K, j)</tex> до <tex>I_K</tex> с емкостью <tex> j(s_j - s_{j+1}) T_K </tex> и для всех <tex>ν = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_ν}</tex> в <tex>(K, J)</tex> с емкостью <tex> (s_j - s_{j+1}) T_K </tex>.
Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги из <tex>s</tex> в <tex>J_i</tex> емкостью <tex>p_i</tex> и дуги из <tex>I_K</tex> в <tex>t</tex> емкостью <tex>S_mT_K</tex> (смРис. рисунок 1).
{{Теорема
}}
[[Файл:Figure_5.9.b.png|500px|thumb|right|Рис. 2.2 - Расширение сети]]
==Время работы==
