Изменения
Нет описания правки
[[Файл:Figure_5.9.a.png|200px|thumb|right|Рис. 2.1 - Заменённая подсеть]]
Пусть <tex> t_1 < t_2 <...< t_r </tex> упорядоченная последовательности всех значений <tex>r_i</tex> и <tex>d_i</tex>.
Определим произвольный интервал-узел на исходной сети (Рис. 1) <tex> I_K := [t_{K-1}, t_K], \ T_K = t_K-t_{K-−1} </tex> для <tex> K = 2,..., r </tex>.
Расширим эту сеть, показанную на Рис. 1 следующим образом:
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>ν \nu = 1,. . . , s</tex> и <tex>j = 1,. . ., m</tex> существует дуга из <tex>J_{i_νi_\nu}</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).
{{Теорема
(a) Существует допустимое расписание.
(b) В расширенной сети существует поток от <tex>s </tex> до <tex>t </tex> со значением <tex>\sum\limits_{i=1}^n p_i</tex>
|proof=Равшана переводить, не мешать <tex>(b) \Rightarrow (a):</tex>:
Рассмотрим в расширенной сети поток величиной <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} \le T_Kh(A)</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>:
Предположим, что допустимое расписание существует. Для <tex>i = 1, ... , n </tex> и <tex>K = 2, ..., r</tex> пусть <tex>x_{iK}</tex> является "объемом работ", который будет выполняться на работу <tex>i</tex> в интервале <tex>I_K</tex> в соответствии с возможным расписанием. Тогда для всех <tex>K = 2, ..., r</tex> и произвольных наборов <tex>A \subseteq \{ 1, . . . , n \}</tex>, неравенство
Работа с максимальным потоком в расширенной сети занимает <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; ri r_i | CmaxC_{max}</tex> представляет собой частный случай <tex>Q | pmtn; ri r_i | LmaxL_{max}</tex>, и может быть решена более эффективно. Labetoulle, Lawler, Lenstra, и Rinnooy Kan разработали алгоритм работающий за <tex> O(n log(n) + mn) </tex> специально для этого случая.
{{Утверждение
|statement= Задача <tex>Q | pmtn | LmaxL_{max}</tex> может быть решена за <tex> O(n log(n) + mn) </tex> шагов.
|proof=
Решение <tex>Q | pmtn; ri r_i | CmaxC_{max}</tex> эквивалентно нахождению наименьшего <tex>T \ge 0</tex>, такого, что задача с допустимым временным интервалом <tex>[r_i, T] (i = 1, . . . , n)</tex> имеет решение.
С другой стороны, решение <tex>Q | pmtn | LmaxL_{max}</tex> эквивалентно нахождению такого наименьшего <tex>T \ge 0</tex>, такого, что задача с временным интервалом <tex>[0, d_i + T]</tex> или <tex>[−T, d_i]</tex> имеет решение.
}}
Таким образом, задачи <tex>Q | pmtn; ri r_i | Cmax</tex> и <tex>Q | pmtn | LmaxL_{max}</tex> симметричны.
==Источники==
