Изменения

Как в задаче <tex>P \mid pmtn, r_i \mid L_{max}</tex> ([[PpmtnriLmax|ссылка]]) применим метод [[Вещественный_двоичный_поиск|двоичного поиска]] и сведем задачу к поиску максимального потока в сети<tex> Q \mid pmtn, r_i, d_i \mid - </tex>. Опишем алгоритм проверки Для существования допустимого расписания с <tex> L_{max} <= \le L^* </tex>. Для этого увеличим все требуется, чтобы у работы с номером <tex> i </tex> выполнялось <tex> C_i - d_i \le L^* </tex> на , что эквивалентно <tex> C_i \le d_i + L^* </tex>. Опишем алгоритм решения <tex> Q \mid pmtn, r_i, и заметимd_i \mid - </tex> при помощи сведения к задаче поиска [[Определение_сети, что _потока|максимального потока]].

Пусть <tex> t_1 \le t_2 \le ... \le t_r </tex> упорядоченная последовательность всех значений <tex>r_i</tex> и <tex>d_i+ L^*</tex>.