2.5.3. Алгоритм поиска потока минимальной стоимости

Рис. 2.20

В задаче о поиске потока минимальной стоимости рассмотрим сначала случай, когда все стоимости a_ijАлгоритм решения задачи (3.6) – (3.8) для этого случая построить сравнительно несложно. Пусть для некоторой сети заданы пропускные способности дугC_ijи стоимости передачи единицы потокаa_ij, источникsи стокt , все данные являются целочисленными. Требуется найти максимальный поток минимальной стоимости изsвt. Введем в рассмотрение стоимостные метки узловp(i), которые будут при выполнении алгоритма равны стоимости, за которую поток может быть передан изsвi. Еслиa_ijто минимально возможная стоимость потока в сети равна нулю, поэтому на первом шаге всеp(i)=0. За нулевую стоимость поток может быть передан изsвt, если есть увеличивающая цепь, состоящая из дуг, для которыхa_ij. Для всех узлов, для которых таких цепей нет, следует увеличить стоимостные метки и затем попытаться найти поток большей стоимости. Например, для графа на рис.3.10 (первое число на дуге – стоимость, второе – пропускная способность,s=1, t=4) за нулевую стоимость поток не может быть передан из вершины 1 даже в соседние вершины 2 и 3, тем более – в 4. Значит, меткиp(i)вершин 2, 3 и 4 должны быть увеличены на единицу. После этого будетp(1)=0,p(2)=1, а стоимость передачи единицы потока по дуге(1,2)равна 1, так что есть возможность передать 3 единицы потока из вершины 1 в 2 за стоимость, равнуюp(2)=1, а метки вершин 3 и 4 следует увеличить еще на 1, и так далее, пока не найдется увеличивающая цепь изsвt. Таким образом, увеличивающими и уменьшающими дугами будут те дуги, для которыхa_ij=p(j)-p(i), и множестваIиRувеличивающих и уменьшающих дуг должны определяться следующим образом:

I = { (i,j) : a_ij=p(j)-p(i), f_ij<C_ij } (2.10)

R = { (i,j) : a_ij=p(j)-p(i), f_ij>0 } (2.11)

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

Шаг 1. Положить для всех i,j=1…N f_ij=0, p(i)=0.

Шаг 2. Определить множества дуг IиRпо правилам (2.10) – (2.11).

Шаг 3. Найти при данных множествах I, Rмаксимальную увеличивающую цепь. Если она есть, то провести увеличение потока и перейти к шагу 2.

Шаг 4. (Увеличивающая цепь не найдена) Если разрез, определяемый множеством вершин X, полученным при поиске увеличивающей цепи, является насыщенным, то СТОП: найден максимальный поток минимальной стоимости. Иначе для вершинiXположитьp(i)равнымp(i)+1и перейти к шагу 2.

Рис. 2.21

В таблице приведены результаты работы алгоритма для графа на рис. 2.20, в последнем столбце – пропускная способность увеличивающей цепи. Конечный результат приведен на рис 2.21. Максимальный поток в сети равен 4 единицам.

Если требуется найти поток заданной величины V, то в алгоритме следует ввести соответствующее условие остановки в шаге 3.

Пример. (Модель производственного планирования Смита и Джонсона). Фирма должна удовлетворить спрос на продукцию в течение трех периодов. В каждом периоде продукция может выпускаться в рабочее и сверхурочное время. Заданы следующие исходные данные:

Стоимость хранения единицы продукции на складе в течение одного периода равна 1. Уровень запасов в начале первого периода составляет 15 единиц. Определить производственный план фирмы так, чтобы минимизировать затраты.

Рис. 2.22

Данная задача может быть сформулирована как задача о поиске максимального потока минимальной стоимости. Сетевая модель представлена на рис. 2.22. Дуги (11,12)соответствуют первому периоду: наличие на них потока вf_ijединиц означает, что в первый период должно быть произведеноf_ijединиц продукции в рабочее время (верхняя дуга) и в сверхурочное время (нижняя дуга), дуги(21,22)соответствуют второму периоду, дуги(31,32)– третьему. Введен узел – источникs, дуга(s,12)включена ввиду наличия на складе 15 единиц продукции. Дуги(12,22)и(22,32)означают возможность хранения продукции на складе до конца второго и третьего периодов, дуги(12,t),(22,t)и(32,t)соответствуют реализации продукции в конце первого, второго и третьего периодов. Для решения задачи в этой сети следует найти максимальный поток минимальной стоимости. На рис. 2.22 приведен конечный результат работы алгоритма. В первый период следует произвести 75 единиц продукции в рабочее время. Вместе с имеющимися на складе это составит 90 единиц. Из них 60 нужно реализовать в первом периоде, а 30 оставить на складе. Во втором периоде следует произвести 100 единиц в рабочее время и 10 в сверхурочное, реализовать 80, 60 оставить на складе. Наконец, в третий период нужно произвести 60 единиц в рабочее время и 20 в сверхурочное, и реализовать их вместе с 60 единицами, хранившимися на складе. Суммарные затраты при этом равны a_ijf_ij = 5990. Насыщенный разрез включает дуги(12,t),(22,t)и(32,t), то есть спрос на продукцию может быть полностью удовлетворен.