Изменения

<tex>I_K</tex> - произвольный интервал узел на рисунке, обозначим через <tex> J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> набор предшественников узла <tex>I_K</tex>. Тогда замененная нами подсеть определяется как <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex>, которая показана на рисунке 52.9 (а), расширение 1; Расширение сети показано на рисунке 5.9 (б).{{TODO | t = ДОБАВИТЬ_Рисунок 52.9: Расширение сети2.}}

Расширенная подсеть строится путем добавления к вершинам <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> with capacity с емкостью <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> with capacity с емкостью <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> (см. рисунок 5.21). Сеть построена таким образом, называется расширенной сетью.

[[Файл:Figure_5.9.b.png|400px|thumb|right|Рис. 2.2]]Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности. Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Получается алгоритм со сложностью <tex>O (mn^3(log(n) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.

Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Это дает <tex>\varepsilon</tex>-приближении алгоритм со сложностью <tex>O (mn^3(log(n) + log(1 / \varepsilon) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, ограничен <tex>n \max\limits_{i=1}^{n}p_i</tex>, при <tex>s_1 = 1</tex>.  Потому что (5.10) справедливо для всех К частичной работы с требования к обработке Xik могут быть запланированы в ИК с уровнем алгоритма. Задача <tex>Q | pmtn; ri | Cmax</tex>, которая представляет собой частный случай <tex>Q | pmtn; ri | Lmax</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, and Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.{{Утверждение|statement= Задача <tex>Q | pmtn | Lmax</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов. Это вытекает из следующих соображений:|proof= Решение <tex>Q | pmtn; ri | Cmax</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что проблема задача с "временными окнами " <tex>[гr_i, тT] (г i = 1, ..., пn) имеет возможности решение.  С другой стороны, решение <tex>Q | pmtn | Lmax</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, что проблема с временными окнами [0, D + T] или с временными окнами [-T, ди] имеет допустимое решение.