Сведение к задаче о потоке минимальной стоимости

ти минимизирует поток в фиктивном ребре и тем самым увеличивает поток до макси­мального в исходной сети. В силу этого обстоятельства, все задачи, рассмотренные в раз­деле 22.4, которые сводятся к задаче о максимальном потоке, сводятся также и к задаче о потоке минимальной стоимости. Это множество задач, помимо прочих, включает зада­чи о двудольном сочетании, о допустимых потоках и о минимальном сечении.

Однако больший интерес представляет тот факт, что мы можем проверить возмож­ность использования свойств полученных нами алгоритмов решения задачи о потоке ми­нимальной стоимости для разработки новых общих алгоритмов решения задачи о макси­мальном потоке. Мы уже отмечали, что общий алгоритм вычеркивания циклов, применяемый при решении задачи о максимальной потоке минимальной стоимости, по­зволяет получить общий алгоритм вычисления аугментальных путей для задачи о макси­мальном потоке. В частности, такой подход приводит к реализации, которая находит ауг­ментальные пути без поиска в сети (см. упражнения 22.133 и 22.134). С другой стороны, этот алгоритм может строить аугментальные пути с нулевым потоком, в связи с чем его рабочие характеристики трудно оценить (см. раздел ссылок).

Задача о максимальном потоке минимальной стоимости носит более общий характер, нежели задача поиска кратчайшего пути. Это утверждение следует из возможности ее све­дения к другой задаче.

Свойство 22.29. Задача о кратчайшем пути с единственным источником (в сетях, в ко­торых нет отрицательных циклов) сводится к задаче о допустимых потоках минималь­ной стоимости.

Доказательство: Пусть дана задача поиска кратчайшего пути с единственным источни­ком (сеть и исток в вершине s), требуется построить транспортную сеть с теми же вер­шинами, ребрами и стоимостями ребер и наделить ребра неограниченной пропускной способностью. Добавьте новую вершину истока с ребром, ведущим в s и имеющим стоимость ноль и пропускную способность V— 1, а также новую вершину стока с реб­рами, ведущими из всех других вершин и имеющими нулевые стоимости и пропуск­ные способности, равные 1. Это построение представлено на рис. 22.51.

Решим задачу о допустимом потоке минимальной стоимости на этой сети. При необ­ходимости удалим из решения все циклы с тем, чтобы получить решение с остовным деревом. Это остовное дерево непосредственно соответствует остовному дереву крат­чайших путей в исходной сети. Подробное доказательство этого факта оставляем чи­тателям на самостоятельную проработку (см. упражнение 22.128). ■

Таким образом, все задачи, рассмотренные в разделе 21.6, которые сводятся к задаче поиска кратчайших путей в сети с единственным источником, также сводятся к задаче о потоке минимальной стоимости. Это множество задач включает задачу календарного пла­нирования работ с конечными сроками завершения и с разностными и прочими ограни­чениями.

Как мы убедились при изучении задач о Максимальном потоке, имеет смысл проана­лизировать во всех подробностях работу сетевого симплексного алгоритма при решении задачи поиска кратчайших путей с использованием приведения, описанного в свойстве 22.29. В этом случае данный алгоритм поддерживает остовное дерево с корнем в истоке, во многом напоминая алгоритмы на базе поиска, которые рассматривались главе 21, од­нако потенциалы и приведенные стоимости дают дополнительную гибкость при разработке методов выбора следующего ребра для включения в дерево.

Поток в ребре u-v преобразованной сети привносит в стоимость составляющую fx, a поток в ребре v-u исходной сети - составляющую -cx + fx. Первый член этого выра­жения не зависит от потока, следовательно, стоимость любого потока в преобразован­ной сети равна стоимости соответствующего потока в исходной сети плюс сумма про­изведений пропускных способностей на стоимости всех ребер с отрицательными стоимостями (они, естественно, представлены отрицательными числами). Поэтому любые потоки минимальной стоимости в преобразованной сети являются потоками минимальной стоимости в исходной сети. ■

Это сведение одной задачи к другой показывает, что мы можем сосредоточить свое внимание только на положительных стоимостях, однако в общем случае на практике мы не удосуживаемся делать это, поскольку полученные в разделах 22.5 и 22.6 реализации имеют дело исключительно с остаточными сетями и без труда выполняют обработку от­рицательных стоимостей. Важно иметь в своем распоряжении некоторую нижнюю грани­цу стоимостей в ряде контекстов, но эта граница не должна быть нулевой (см. упражне­ние 22.145).

Далее мы покажем, что, как это делалось в случае задачи о максимальном потоке, при желании можно было бы ограничиться рассмотрением ациклических сетей. Более того, можно было бы также предположить, что ребра не имеют ограничений на пропускную способность (не существует верхней границы величину потока в таких ребрах). Комби­нация этих двух вариантов приводит к следующим классическим формулировкам задачи о потоках минимальной стоимости.

Транспортная задача. Решим задачу о потоке минимальной стоимости для двудольной распределительной сети, все ребра которой направлены из вершины с запасом в верши­ны со спросом и обладают неограниченной пропускной способностью. Как уже было показано в начале данной главы (см. рис. 22.2), обычно эта задача моделирует распреде­ление товаров из складов (вершины с запасом) в розничные торговые точки (вершины со спросом) по каналам распределения (ребра) с конкретной стоимостью поставки еди­ницы товара.

Свойство 22.31. Транспортная задача эквивалентна задаче о потоке с минимальной сто-имоетъю.

Доказательство: Пусть задана транспортная задача, мы можем решить ее, присваивая каждому ребру пропускную способность, более высокую, чем значения запаса или спроса вершин, которые оно соединяет, и решая возникающую при этом задачу на­хождения допустимого ребра минимальной стоимости на построенной в процессе ре­шения этой задачи распределительной сети. Поэтому нам всего лишь достаточно ус­тановить, что решение стандартной задачи сводится к решению транспортной задачи.

Для разнообразия, опишем новое преобразование, которое линейно только на разре­женных сетях. Построение, подобное тому, что мы использовали при доказательстве свойства 22.16, позволяет установить этот результат для неразреженных сетей (см. уп­ражнение 22.148).

Пусть дана стандартная распределительная сеть с V вершинами и Е ребрами, постро­им для транспортной задачи двудольную сеть с V вершинами запаса, Е вершинами спроса и 2Е ребрами следующим образом. Для каждой вершины исходной сети вклю­чим в двудольную сеть вершину с величиной запаса или спроса, равной соответству-