Изменения
→Алгоритм решения
==Алгоритм решения==
[[Файл:Figure_5.9.ab.png|200px500px|thumb|right|Рис. 2.1 - Заменённая подсетьРасширение сети]]
Как в задаче [[PprecriLmax|<tex>P \mid pmtn, r_i \mid L_{max}</tex>]] сведем задачу к поиску потока сети. Также будем использовать бинарный поиск.
Определим произвольный интервал-узел на исходной сети (Рис. 1) <tex> I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </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>.
что и является искомым неравенством.
}}
==Время работы==
