2.5.5. Алгоритм дефекта

В рассмотренном ранее алгоритме поиска потока минимальной стоимости предполагалось, что стоимости передачи единицы потока по каждой дуге являются неотрицательными.

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

Величина l_ij0 называетсянижней пропускной способностьюдуги(i,j).

Примеры:

1. Организаторы передвижной выставки должны определить оптимальный маршрут перемещения по нескольким городам. Известна стоимость переезда между городами и прогнозируемый доход (убытки) для каждого города. Некоторые города обязательно нужно посетить для выполнения ранее подписанных контрактов.

В сетевой модели для этой задачи каждому городу соответствует дуга со стоимостью, равной доходу (убыткам) в данном городе, нижней пропускной способностью, равной 1, если город обязательно нужно посетить, и 0 в противном случае, и пропускной способностью, равной 1. Возможным переездам между городами соответствуют дуги со стоимостью, равной стоимости переезда, нижней пропускной способностью, равной 0 и пропускной способностью, равной 1. Должны быть добавлены вершины: источник sи стокt. Для решения следует передать одну единицу потока изsвtза минимальную стоимость. Путь передачи этой единицы потока определяет оптимальный маршрут передвижения выставки.

2. Три нефтеочистительных завода могут получать неочищенную нефть из двух месторождений. Стоимость одного галлона нефти в этих месторождениях составляет 0.40$ и 0.30$ соответственно. Из обоих месторождений нефть может поставляться в неограниченном количестве, но не менее 300000 галлонов в день. Производственная мощность и затраты на ректификацию одного галлона нефти для каждого из заводов указаны в таблице.

Эти заводы должны снабжать нефтью четыре района. Во второй таблице даны затраты (в долларах) на транспортировку одного галлона нефти.

Завод	Район 1	Район 2	Район 3	Район 4
1	0.05	0.06	0.06	0.07
2	0.06	0.07	0.07	0.06
3	0.07	0.06	0.06	0.05

Суточная потребность в нефти каждого из районов и продажная цена одного галлона приведены в третьей таблице.

Район	Минимальная потребность	Максимальная потребность	Продажная цена (долл/галлон)
1	200000	250000	0.85
2	90000	175000	0.70
3	100000	175000	0.65
4	200000	350000	0.75

Поставки Переработка Транспортировка Продажа

Рис. 2.24

Для максимизации своей прибыли нефтяная компания должна поставлять в данные районы нефть при минимальных затратах на транспортировку.

Сетевая модель данной задачи приведена на рис. 2.24, первое число на дугах – стоимость ( единица – 10$), второе – нижняя пропускная способность ( в тысячах галлонов), третье – пропускная способность. Для решения задачи необходимо найти максимальный поток минимальной стоимости из вершины 1 в 14.

Для решения задачи (2.12) – (2.14) прежний алгоритм не годится по двум причинам. Во-первых, неизвестна минимальная возможная стоимость передачи единицы потока. Во-вторых, начальный нулевой поток в сети может оказаться недопустимым, то есть не удовлетворяющим условию (2.14), если есть l_ij0. Поэтому для данной задачи был разработан другой алгоритм, который носит названиеалгоритма дефекта. Перейдем к его описанию.

Добавим в сеть дополнительную дугу (t,s), соединяющую вершину-стокtи источникs,и будем предполагать, что по ней протекает поток величиныV, то есть весь поток, попадающий в стокt, возвращается по этой дуге обратно вs. Такой замкнутый поток в новом графе называетсяциркуляцией. Теперь для вершинsиtвеличины заходящего и выходящего потока равныV, поэтому может быть сформулированазадача о поиске циркуляции минимальной стоимости:

Для данного потока в сети { f_ij }величина потока изsвtпри этом равнаV=f_ts. Обе задачи о поиске потока минимальной стоимости могут быть сведены к задаче о поиске циркуляции минимальной стоимости путем подходящего выбора параметров возвратной дуги(t,s)следующим образом:

1. Если требуется найти поток заданной величины V, имеющий минимальную стоимость, то следует положитьa_ts=0, l_ts=V, C_ts=V. Любой допустимый поток тогда будет иметь величинуV.

2. Если нужно найти максимальный поток минимальной стоимости, то следует положить a_ts=-M, l_ts=0, C_ts=, гдеM– очень большое число. Добавление каждой единицы потока на дуге(t,s)приведет тогда к уменьшению суммарной стоимости наM, то есть оптимальное решение будет при максимальном потоке.

Для вершин графа введем опять стоимостные метки p(i), i=1,…,N. При поиске решения задачи (2.6) – (2.8) с помощью алгоритма Форда-Фалкерсона было видно, что потокиf_ijна дугах удовлетворяют следующим условиям:

f_ij=0 , если a_ij>p(j)-p(i),

0f_ijC_ij , если a_ij=p(j)-p(i),

f_ij=C_ij , если a_ij<p(j)-p(i).

Если обозначить q_ij=a_ij-(p(j)-p(i))= a_ij-p(j)+p(i),то в общем случае эти условия выглядят следующим образом:

f_ij=l_ij , еслиq_ij>0,(2.18)

l_ijf_ijC_ij , еслиq_ij=0, (2.19)

f_ij=C_ij , еслиq_ij<0. (2.20)

С помощью теории линейного программирования можно показать, что циркуляция в графе имеет минимальную стоимость тогда и только тогда, когда выполнены условия (2.18) – (2.20). В задаче (2.15) – (2.17), являющейся задачей линейного программирования, они представляют собой условия дополняющей нежесткости, которые являются необходимыми и достаточными условиями минимума.

Таким образом, задача будет решена, если удастся найти циркуляцию {f_ij}и стоимостные меткиp(i), удовлетворяющие условиям (2.16) – (2.20).

Идея алгоритма дефекта состоит в следующем. Пусть для дуг сети определены потоки f_ij, удовлетворяющие условию (2.16), а для вершин – стоимостные меткиp(i). Например, в начале они все могут быть равны нулю. При этом условия (2.17) – (2.20) могут быть не выполнены. Для каждой дуги определяется величинадефекта. Дефект равен нулю, если условия (2.17) – (2.20) выполнены, и положителен в противном случае. Если в сети есть дуги с положительным дефектом, выбирается одна из них(i,j), и для нее делается попытка устранить дефект. Для этого поток на дуге должен быть или увеличен, или уменьшен. Если поток требуется увеличить, то это можно сделать в том случае, если такое же количество единиц потока возможно передать по остальным дугам сети, не увеличивая их дефекта. Если изjвi имеется увеличивающая цепь, то увеличение потока на(i,j)производится, в противном случае происходит изменение метокp(i). Если же поток на(i,j)нужно уменьшить, то производится поиск увеличивающей цепи изiвj, чтобы направить его другим путем. Оптимальное решение будет найдено, если дефекты всех дуг удастся сделать равными нулю. Однако в сети с положительными нижними пропускными способностями допустимый поток может вообще не существовать.

Определим понятие дефекта дуги. Во втором столбце таблицы приводятся девять различных случаев состояния дуги, для каждого из которых в третьем столбце определяется величина дефекта. Как и ранее, вводятся множества IиRдуг, на которых можно увеличивать и уменьшать поток. В последнем столбце – максимальное количество единицv_ij, на которое может быть увеличен (для дуг изI) или уменьшен (R) поток.

Теперь можно привести описание алгоритма дефекта.

Шаг 1. Положить f_ij=0, i,j=1,…,N, q(i)=0, i=1,…,N.

Шаг 2. Для всег дуг сети вычислить дефект K_ij. Если все они равны нулю, то СТОП: найден поток минимальной стоимости.

Шаг 3. Определить множества дуг IиR. Выбрать дугу(i,j),для которойf_ij<l_ij, если такой нет – то любую дугу с положительным дефектом. Если она принадлежитI, то на следующем шаге считать вершинуjисточникомs, аi– стокомt, еслиR– считатьiисточникомs, аj– стокомt.

Шаг 4. Найти максимальную увеличивающую цепь из sвt. Если ее нет, то перейти к шагу 5. Иначе провести увеличение потока вдоль цепи, но не более, чем наv_stединиц. Соответственно изменить поток на дуге(s,t)(увеличить, если она из множестваI, уменьшить, если изR). Перейти к шагу 2.

Шаг 5. Пусть X– множество вершин, определяющее разрез при поиске увеличивающей цепи на шаге 4,tX. Определить множества дуг:A₁ = { (i,j): iX, jX, q_ij>0, f_ij<C_ij }A₂ = { (i,j): jX, iX, q_ij<0, f_ij>l_ij}

Вычислить:

Если , то СТОП: если поток допустимый, то найдено решение, в противном случае допустимый поток не существует. Иначе для всехiXположитьp(i)равнымp(i)+и перейти к шагу 2.

На первом шаге устанавливаются начальные нулевые значения потока и стоимостных меток, на втором вычисляются дефекты дуг. На третьем шаге определяется принадлежность каждой дуги множествам IиR, и выбирается дуга, для которой далее будет сделана попытка уменьшить дефект, причем в первую очередь следует выбирать те дуги, для которых не выполнено ограничение (2.17). Дуга с положительным дефектом всегда принадлежит либо множествуI, либоR, но не обоим сразу. Чтобы устранить дефект, поток на дуге(i,j)надо увеличить (если она принадлежитI) или уменьшить (если она принадлежитR). В первом случае поток должен быть “возвращен” обратно изjвi, во втором – передан изiвjкаким-либо другим путем. В обоих случаях для этого на шаге 4 ищется увеличивающая цепь. Если она есть, то поток на ней и на дуге(i,j)изменяется так, чтобы максимально уменьшить или совсем устранить деефект на этой дуге. Если же увеличивающей цепи нет, то на шаге 5 происходит изменение стоимостных метокp(i).A₁– множество прямых дуг разреза,_- минимальное количество единиц, на которое следует увеличить все меткиp(i)вершин, не принадлежащихX, чтобы какая-либо из них вошла в множествоX. Аналогично,A₂- множество обратных дуг разреза,_- минимальное количество единиц, на которое следует увеличить все меткиp(i)вершин, не принадлежащихX, чтобы какая-либо из них вошла в множествоX.

Поставки Переработка Транспортировка Продажа

Рис. 2.25

На рис. 2.25 приведен результат работы алгоритма дефекта для задачи примера 2 (п.2.5.5.). В сеть добавлена возвратная дуга (14,1)с стоимостью–100(большое числоM=100), нижней пропускной способностью0и пропускной способностьютак как требуется найти максимальный поток минимальной стоимости. Следует заметить, что конечные стоимостные метки зависят от порядка выбора дефектных дуг на шаге 3, и поэтому могут отличаться на константу от меток на рис. 2.25.