Глава 22, Потоки в сетях

22.5. Потоки минимальной стоимости

Нет ничего удивительного в том, что конкретная задача о максимальном потоке име­ет несколько решений. Это обстоятельство дает нам право задать вопрос, можем ли мы ввести дополнительные критерии с целью выбора какого-то одного из них. Например, вполне понятно, что существует некоторое множество решений задач определения пото­ков в сети с единичной пропускной способностью ребер, представленной на рис. 22.22; возможно, по тем или иным причинам мы предпочитаем решение, использующее наи­меньшее число ребер, или решение, предусматривающее построение кратчайших путей, возможно, мы хотим знать, существует ли решение, использующее непересекающиеся пути. Эти задачи сложнее, чем стандартные задача о максимальном потоке, они охваты­ваются более общей моделью, известной как задача о потоке с минимальной стоимостью (minicost flow problem).

Как и в случае задачи о максимальном потоке, существуют различные эквивалентные способы постановки задачи о потоке с минимальной стоимостью. В этом разделе мы под­робно рассмотрим стандартную постановку этой задачи, а различные сведения к другим задачам мы обсудим в разделе 22.7.

В частности, мы воспользуемся моделью максимального потока с минимальной стоимос­тью (mincost-maxflow model): мы вводим понятие типа ребра, которое означает стоимость ребра, выраженную целым числом, используем стоимость ребра для определения стоимо­сти потока естественным образом, а затем ставим задачу определения максимального по­тока с минимальной стоимостью. Как станет ясно из дальнейшего, мы не только полу­чим эффективный алгоритм решения этой задачи, но и построим модель решения этой задачи, получившую широкое применение.

Определение 22.8. Стоимость потока (flow cost) через ребро в транспортной сети со стоимостями ребер есть произведение потока в этом ребре и стоимости. Стоимость (cost) потока есть сумма стоимостей потоков в ребрах этого потока.

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

Максимальный поток с минимальной стоимостью. Пусть задана транспортная сеть, ребра которой наделены стоимостями, найти такой максимальный поток, стоимость ко­торого меньше стоимости любого другого максимального потока.

Рисунок 22.40 служит иллюстрацией различных максимальных потоков в транспорт­ной сети со стоимостями, в том числе и максимальный поток с минимальной стоимос­тью. Разумеется, вычисление минимальной стоимости по трудоемкости не уступает вычис­лению максимального потока, с которым мы имели дело в разделах 22.2 и 22.3. И в самом деле, стоимость добавляет новое измерение, которое привносит новые трудноразрешае­мые проблемы. Но даже если это так, то мы можем справиться с этими трудностями с

Часть 5, Алгоритмы на графах

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

Другие многочисленные задачи сводятся к задаче о максимальном потоке минималь­ной стоимости. Например, следующая постановка задачи представляет интерес, поскольку она охватывает задачу о распределении товаров, которую мы изучали в начале данного раздела.

Допустимый поток минимальной стоимости. Напомним, что мы определяем поток в сети, содержащей вершины с весами (запас, если вес положительный, и спрос, если вес отрицательный) как допустимый (feasible), если сумма весов вершин отрицательна и раз­ность между притоком в каждую вершину и истечением из нее равна нулю. Задача зак­лючается в том, чтобы в такой сети найти допустимый поток минимальной стоимости.

Для описания сетевой модели решение задачи о допустимом потоке минимальной сто­имости мы для краткости используем термин распределительная сеть (distribution network) для обозначения " транспортной сети с заданными пропускными способностями и стоимо­стями ребер и весами запаса или спроса в вершинах".

В приложениях, осуществляющих распределение товаров, вершины с запасом соот­ветствуют складам, вершины со спросом — розничным торговым точкам, ребра — мар­шрутам перевозок, величины запаса или спроса соответствуют количеству поставляемо­го и получаемого материала, а пропускные способности ребер - числу и грузоподъемности грузовых машин, курсирующих на том или ином маршруте. Естествен­ной интерпретацией стоимости каждого ребра может служить стоимость перевозки еди­ницы товара по этому ребру (стоимость пробега грузовой машины при перевозке единицы товара по соответствующему маршруту). Если задан поток, то стоимость потока через то или иное ребро составляет некоторую часть стоимости продвижения потока по всей сети, которую мы можем приписывать этому ребру. Если задано количество материала, кото­рый должен быть доставлен по некоторому заданному ребру, то мы можем вычислить стоимость доставки, умножив стоимость доставки единицы товара на его количество. Выполняя такое вычисление для каждого ребра и складывая полученные произведения, мы получим общую стоимость доставки товара, которую мы намерены минимизировать.

РИСУНОК 22.40. МАКСИМАЛЬНЫЕ ПОТОКИ В ТРАНСПОРТНЫХ СЕТЯХ С РЕБРАМИ, НАДЕЛЕННЫМИ СТОИМОСТЯМИ

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