Задачи для самостоятельного решения

↑

⇐ ПредыдущаяСтр 7 из 11Следующая ⇒

Задачи для самостоятельного решения

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

a)

b)

c)

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

Дана сеть G = (V,E) , на каждой дуге eÎE задана пропускная способность с(e) > 0 и удельная стоимость d(e) , выделен источник s и сток t. Если в сети имеется поток f , то его стоимость определяется как

Задача о потоке минимальной стоимости состоит в поиске допустимого потока f , имеющего заданную величину m и минимальную стоимость S( f ).

Граф модифицированных стоимостей G_f = ( V_f , E_f ) имеет V_f = V. Множество дуг E_f  строятся по следующему правилу:

1) если eÎE  и f ( e ) = 0 , то дуга e строится в G_f  с той же пропускной способностью c_f (e) = c(e) и стоимостью d_f (e) = d(e);

2) если e = ( x , y ) Î E и f (e) = c(e) , то в G_f  строится обратная дуга

     c пропускной способностью                     и удельной стоимостью

;

3) если e = ( x , y ) Î E  и 0 < f (e) < c(e) , то в G_f  строятся две дуги

                    с

Легко показать, что каждому простому ориентированному пути в сети G_f , ведущему из источника в сток, соответствует увеличивающая цепь в сети G .

Удельной стоимостью пути (или цикла) в сети будем называть сумму удельных стоимостей входящих в него дуг.

Критерием оптимальности потока фиксированной мощности является следующее утверждение. Допустимый поток f в сети G имеет минимальную стоимость среди всех допустимых потоков той же величины в том и только том случае, когда в графе G_f нет контуров с отрицательной удельной стоимостью.

Алгоритм Басакера - Гоуэна. На каждом шаге алгоритма находится наиболее дешевый (по удельной стоимости) ориентированный путь из s в t в графе модифицированных стоимостей G_f. Этому пути соответствует увеличивающая цепь минимальной удельной стоимости в сети G. Затем по этой цепи пропускается максимальный поток, который можно добавить к имеющемуся потоку f .

Шаг 1.В сети G пропускаем нулевой поток f. Его величина γ(f ) и стоимость S(f) равны нулю.

Шаг 2. Строим граф модифицированных стоимостей G_f.

Шаг3. Если в G_f нет ни одного ориентированного пути из s в t, то мощность потока f  не может быть увеличена, и задача не имеет решения. В противном случае среди всех путей из s в t в графе G_f находим путь с минимальной удельной стоимостью. Обозначим его P_f.

Шаг4. В исходной сети G определяем неориентированную цепь Р, соответствующую пути P_f. Для всех дуг е из цепи Р вычисляем числа ε(е): на прямых дугах ε(е) = с(е) – f(e), а на обратных дугах ε(е) = f(е). Затем находим  ε= min [ ε(e), m – γ(f) | еÎ P ].На прямых дугах цепи Р увеличиваем поток f на ε, а на обратных дугах уменьшаем поток f на ε. При этом величина потока увеличивается на ε.

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

Алгоритм Басакера - Гоуэна имеет смысл применять только к таким сетям G, в которых нет контуров отрицательной удельной стоимости. Выполнение или невыполнение этого условия можно проверять с помощью алгоритма Форда-Беллмана или алгоритма Флойда.

Для поиска самого дешевого пути из s в t в графе G_f (шаг 3 алгоритма Басакера - Гоуэна) тоже можно использовать алгоритмы Форда-Беллмана и Флойда.

Пример. Построить в следующей сети поток величиной m = 3 с минимальной стоимостью. Пропускные способности дуг указаны в квадратных скобках, стоимости без скобок, величина потока в круглых скобках.

Пропускаем поток  f(e) = 0 , eÎE . Строим граф модифицированных стоимостей. Он будет совпадать с исходной сетью. Находим наиболее дешевый простой путь из s в t. Он состоит из дуг (s,a) , (a,b) , (b,t)  и имеет удельную стоимость равную 3. Соответсвующая цепь в исходной сети дает ε = min [3, 1, 4, 3 – 0] = 1 . Все дуги цепи прямые. Увеличиваем поток по дугам на единицу. Получим новый поток в сети величины 1. Мощность потока меньше 3. Поэтому строим граф модифицированных стоимостей.

Находим путь из источника в сток с минимальной удельной стоимостью. Он состоит из дуг (s,a) , (a,t) и имеет удельную стоимость равную 3. В исходной сети для соответсвующая цепи получим ε = min [3–1, 2, 3–1] = 2. Увеличиваем поток по дугам (s,a), (a,t) на 2. Величина нового потока равна 3.

Необходимая величина потока достигнута. Искомый поток построен. Его стоимость S( f ) = 9 .

Алгоритм Клейна.Его сущность заключается в том, что вначале нужно найти какой-нибудь поток  f величины т, а затем последовательно уменьшать его стоимость, перестраивая вдоль имеющихся циклов с отрицательной удельной стоимостью. При этих перестройках величина потока f будет сохраняться. В тот момент, когда циклы с отрицательной удельной стоимостью исчезнут, поток f станет оптимальным.

Шаг 1. Находим любой допустимый поток f величины М (f) = т.

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

Шаг 2. Строим граф модифицированных стоимостей G_f. Если в нем нет контуров с отрицательной удельной стоимостью, то задача решена: построенный поток f имеет минимальную стоимость среди потоков величины т. В противном случае находим в графе G_f контур Р_f с отрицательной удельной стоимостью (например, с помощью алгоритма Флойда).

Шаг3. В исходной сети G определяем неориентированный цикл Р, соответствующий контуру Р_f. Все дуги еÎ Р разбиваются на два класса: прямые, для которых еÎ Р_f, и обратные, для которых ēÎ P_f - (где ē – дуга, противоположная е) . Вычисляем ε = min [ ε(e) | еÎ P},  где ε (е ) = с (е) - f (е ) на прямых дугах и ε (е ) = f (е) на обратных дугах.

Шаг4. На прямых дугах цикла Р увеличиваем поток f на ε, а на обратных дугах цикла Р уменьшаем поток f на ε. Переходим к шагу 2.

Пример. Построить в следующей сети поток величиной m=3 с минимальной стоимостью. Пропускные способности дуг указаны в квадратных скобках, стоимости без скобок, величина потока в круглых скобках.

В сети уже имеется поток величины 3. Строим граф модифицированных стоимостей.

Находим контур с отрицательной удельной стоимостью: (s,a), (a,t), (t,b), (b,s) . Ему соответсвует цикл (s,a), (a,t), (b,t), (s,b) в исходной сети. Вычисляем ε = min [3 – 1, 2 – 0, 4 – 3, 2] = 1. На дугах (s,a), (a,t) увеличиваем поток на 1, на дугах (b,t), (s,b) уменьшаем на 1. Получим сеть с новым потоком.

Для нового потока строим граф модифицированных стоимостей.

t

Опять находим контур с отрицательной удельной стоимостью: (s,a), (a,t), (t,b), (b,s) . Ему соответсвует цикл (s,a), (a,t), (b,t), (s,b) в исходной сети. Вычисляем ε = min [3 – 2, 2 – 1, 4 – 2, 2-1] = 1. На дугах (s,a), (a,t) увеличиваем поток на 1, на дугах (b,t), (s,b) уменьшаем на 1. Получим сеть с новым потоком.

Строим граф модифицированных стоимостей.

t

s

В графе отсутствуют контуры с отрицательной удельной стоимостью. Следовательно, построенный поток оптимален. Его стоимость S( f ) = 9 .

Познавательные статьи:



Психологические особенности спортивного соревнования

Приготовление дезинфицирующих растворов различной концентрации

Занятость населения и рынок труда

Социальный статус семьи и её типология