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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки России

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Брянский государственный университет имени академика И.Г. Петровского

Физико-математический факультет

Кафедра алгебры

Направление «Информационные технологии»

Творческая работа

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

Выполнили: студенты 3 курса ФМФ

Овчаров Б.С., Прокудин А.В.

Свентицкий Е.И., Свентицкий П.И.

Научный руководитель:

К. ф.-м. н. М.М. Сорокина

Брянск 2012



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

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

(1)

где - поток по дуге при ограничениях:

1.

2. Для начальной вершины

- уравнение истока

3. Для конечной вершины

- уравнение стока

4. Для любой другой вершины

- условие сохранения потока

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

Модификация сети допускается только определенного порядка. Пусть - исходная сеть, S - множество вершин, U - множество ребер, - множество весов (пропускных способностей дуг), D - набор стоимостей пересылки единичного потока из в вдоль дуги .

Модификация относительно данного потока сеть строится следующим образом.

1. , т.е. число и набор вершин в модифицированной сети не изменяется.

2. , где - некоторое множество фиксированных дуг. Таким образом, после модификации число дуг сети увеличивается.

3. Если и , то дуга включается в множество V. При этом полагается . Этот пункт применяется только к дугам, по которым проходит поток , относительно которой происходит модификация сети.

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

.

5. Для всех насыщенных дуг и полагают

Это довольно сложный и «длительный» алгоритм. Нахождение кратчайшего пути как в исходной, так особенно в модифицированной сети может потребовать использование алгоритма Белмана-Мура. Кроме того, решение типичных учебных задач требует три-четыре интерполяции алгоритма.

Пример 1

Пусть матрицами и заданы пропускные способности дуг сети и стоимости транспортировки единичного потока вдоль всех дуг.

Требуется:

1) построить максимальный поток от к и указать минимальный разрез, отделяющий от

2) построить поток величины , имеющий минимальную стоимость, здесь […] - целая часть числа.

Построим рисунок соответствующей сети (рис. 1); первое число на дугах - стоимость транспортировки единичного потока вдоль этой дуги, второе - пропускная способность дуги.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 1

Найдём максимальный поток от вершины к вершине по алгоритму Форда-Фалкерсона.

Этап 1

Путь Увеличиваем поэтому поток до 11 единиц, ребро станет насыщенным. Второй возможный путь

Поток по этому пути будет равен 10 единицам. Дуга станет насыщенной. Третий путь, по которому возможен ненулевой поток, - это путь Здесь По этому пути можно увеличить поток лишь на единицу, при этом дуга станет насыщенной. Больше путей нет.

Этап 2

Рассмотрим маршруты с противоположными рёбрами. Маршрут Поток можно увеличить на две единицы на дуге . Эта дуга станет насыщенной. Тогда потоки по этому маршруту будут такими Больше маршрутов нет. Поток максимален. На рисунке 2 на дугах графа стоят две цифры: первая - пропускная способность дуги, вторая - поток на дуге (насыщенные дуги выделены). Теперь можно сделать несоклько разрезов, например, отделяя исток и сток. И по разрезу I, и по разрезу II поток одинаков

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 2

Построим теперь поток величины

единиц

По рассмотренному алгоритму для этого надо построить кратчайший путь от к на графе Этот граф изображён на рисунке 3; веса всех дуг в нём положительны, можно использовать алгоритм Дейкстры.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис. 3

Этап 1.

Шаг 1

1-я итерация.

Шаг 2

={x₁,x₂}, d(x₁)=min(?, 0^*+9),

d(x₂)=min(?, 0^*+10)=10.

Шаг 3

Min (9,10,?,?)=9^*=d(x₁), =x₁.

Шаг 4. =t? Нет. Переход на начало второго шага.

2-я итерация

Шаг 2. ={x₂,x₃}, d(x₂)=min(10, 9^*+12)=10,

d(x₃)=min(?, 9^*+9)=18.

Шаг 3

min(10,18,?,?)=10^*=d(x₂), =x₂.

Шаг 4

=t? Нет

3-я итерация

Шаг 2

={x₃,x₄,t}, d(x₃)=min(18, 10^*+7)=17,

d(x₄)=min(?, 10+9)=19, d(t)=min(?,10+13)=23.

Шаг 3

min(17,19,23)=17^*=d(x₃), =x₃.

Шаг 4

=t? Нет

Переход на начало второго шага

4-я итерация

Шаг 2

={x₄}, d(x₄)=min(19, 17^*+14)=19.



Шаг 3

min(19,23)=19^*=d(x₄), =x₄.

Шаг 4

=t? Нет

Переход на начало второго шага

5-я итерация

Шаг 2

={t}, d(t)=min(23, 19^*+9)=23.

Шаг 3

min(23)=23^*=d(t), =t.

Шаг 4

=t? Нет

Переход. Конец первого этапа

Этап 2

Кратчайший путь здесь очевиден, это путь

µ₁^*=(s,x₂)-(x₂,t)

Максимальный поток по этому пути



ц_max=с_min(µ₁^*)=min(11,17)=11

Так как и=18, то ц_max< и; требуется модификация сети.

Положим ц(s,x₂)= ц(x₂,t)=11 и ц (x_i,x_j)=0 для остальных дуг. Тогда по третьему пункту правил модификации сети включим обратные дуги (x₂,s) и (t,x₂). При этом (x₂,s)=11, (x₂,s)=-10, (t,x₂)=17, (t,x₂)=13. По четвертому пункту правил характеристики всех дуг, где нет потока, останутся без изменений, для дуг потока ц=11, т.е. только для дуги (x₂,t), изменятся характеристики (x₂,t)=13, (x₂,t)=17-11=6. По пятому пункту правил для насыщенной дуги (s,x₂)(s,x₂)=0, (s,x₂)=?. В результате имеем новую сеть G=(S,U,D)(рис. 4). Необходимо найти кратчайший путь между s и t в этой сети. Так как теперь есть дуги с отрицательным весом, следует применить алгоритм Беллмана-Мура.

минимальний оптимальный поток сеть

Рис. 4

Этап 1

d(s)=0, d(x₁)=d(x₂)= …=d(t)=?, Q={s}.

1-я итерация.

Шаг 2

=s, Q=Ш, ={x₁,x₂},

d(x₁)=min(?,0+9)=9,

9<??

Да, корректировка очереди. Q={x₁},

d{x₂}=min(?,0+?)=?,

?<?? Нет, корректировка очереди не проводится

Шаг 3

Q=Ш? Нет

2-я итерация.

Шаг 2

=x₁, Q=Q\{x₁}=Ш, ={x₂,x₃},

d(x₂)=min(?,9+12)=21,

21<?? Да, корректировка очереди. Q={x₂},

d{x₃}=min(?,9+9)=18,

18<?? Да, корректировка очереди. Q={x₂,x₃}.

Шаг 3

Q=Ш? Нет

3-я итерация.

Шаг 2

=x₂, Q={x₃}, ={s,x₃,x₄},

0<0? Нет, корректировка очереди не проводится,

d(x₃)=min(18,21+7)=18,

18<18? Нет

d{x₄}=min(?,21+9)=30,

30<?? Да, корректировка очереди. Q={x₃,x₄},

d{t}=min(?,21+13)=34,

34<?? Да, корректировка очереди. Q={x₃,x₄,t}.

Шаг 3

Q=Ш? Нет.

4-я итерация

Шаг 2

=x₃, Q={x₄,t}, ={x₄},

d(x₄)=min(30,18+13)=30,

30<30? Нет, очередь не корректируется.

Шаг 3

Q=Ш? Нет

5-я итерация

Шаг 2

=x₄, Q={t}, ={t},

d(t)=min(34,30+9)=34,

34<34? Нет, очередь не корректируется.

Шаг 3



Q=Ш? Нет

6-я итерация

Шаг 2

=t, Q=Ш, =Ш.

Шаг 3

Q=Ш? Да. Конец первого этапа алгоритма Беллмана-Мура

Итак, кратчайший путь найден. Это путь

=(s, x₁)-(x₁,x₂)-(x₂,t)

Его вес

d()=9+12+13=34

ц_max=c_min()=min(13, 11, 6)=6

Общий поток по двум уже рассмотренным путям

ц_общ=11+6=17<18=и,

т. е. требуется еще одна модификация сети

Положим опять ц(s,x₁)=ц(x₁,x₂)=ц(x₂,t)=6, ц(s,x₂)=11 и , ц(x_i,x_j)=0 для остальных дуг. По третьему пункту правил включаем обратные дуги (x₁,s), (x₂,x₁), (t,x₂), причем последняя дуга уже присутствует. Полагаем (x₁,s)=6, (x₁, s)=-9, (x₂,x₁)=6, (x₂,x₁)=-12, (t,x₂)=17, (t,x₂)=-13. По четвертому пункту правил все ненасыщенные дуги, где нет потока остаются без изменений, кроме дуг с потоком (x₁,s), (x₁,x₂). Здесь (s,x₁)=13-6=7, (s,x₁)=9, (x₁,x₂)=11-6=5, (x₁,x₂)=12. По пятому пункту правил для насыщенной дуги (x₂,t) (x₂,t)=0, (x₂,t)=?. В полученной после второй модификации сети G=(S,U,D) необходимо найти кратчайший путь между вершинами s и t. Так как опять имеются отрицательные веса, то снова придется применить алгоритм Беллмана-Мура (рис. 5).

Этап 1

Шаг 1

d(s)=0, d(x₁)=d(x₂)= …=d(t)=?, Q={s}.

Шаг 2

=s, Q=Ш, ={x₁, x₂}.

d(x₁)=min(?, 0+9)=9, 9<?? Да. Q={x₁},

d(x₂)=min(?,0+?)=?.

Шаг 3

Q?. Переход на второй шаг.

2-я итерация

Шаг 2

=x₁, Q=Ш.

={s, x₁, x₂}, d(s)=min{0, 9-9}=0,

0<0? нет корректировки очереди,

d(x₂)=min(?, 9+12)=21, 21<?? Да. Q={x₂},

d(x₃)=min(?, 9+9)=18, 18<?? Да. Q={x₂, x₃},

Шаг 3

Q?Ш. Переход на второй шаг.

3-я итерация

Шаг 2

=x₂, Q={x₃}, ={s, x₁, x₃, x₄, t},

d(s)=min{0, 21-10}=0, нет корректировки очереди,

d(x₁)=min{9, 21-12}=9, нет корректировки очереди,

d(x₃)=min{18, 21+7}=18, нет корректировки очереди,

d(x₄)=min{?, 21+9}=30, Q={x₃, x₄},

d(t)=min{?, 21+?}=?, нет корректировки очереди,

Шаг 3

Q?Ш. Переход на второй шаг.

4-я итерация

Шаг 2

=x₃, Q={x₄}, ={x₄},

d(x₄)=min{30, 18+14}=30, нет корректировки очереди,

Шаг 3

Q?Ш.

5-я итерация

Шаг 2

=x₄, Q=Ш, ={t}.

Шаг 3

Q?Ш.

6-я итерация

Шаг 2

=t, Q=Ш, =Ш.

Шаг 3

Q?Ш

Конец первого этапа. Критический путь найден.

=(s,x₁) - (x₁,x₂) - (x₂,x₄) - (x₄,t)

Его вес



d() = 9 + 12 + 9 + 9 = 34

ц_max=c_min()=min(7,5,13,10)=5

Таким образом, по этому пути можно пустить поток в пять единиц. Тогда общий поток будет

ц_общ=17+5=22>и=18

Для того чтобы сформировать поток требуемой величины и=18, необходимо по пути направить поток величиной всего в одну еденицу.

Тогда ц(s,x₁)=7, ц(x₁,x₂)=7, ц(x₂,x₄)=1, ц(x₄,t)=1. Кроме того два предыдущих потока дали ц(s,x₂)=11, ц(x₂,t)=17. Таким образом, минимальная стоимость всего потока и=18 равна

(x_i,x_j)•ц(x_i,x_j)=9•7+12•7+10•11+13•17+9•1+9•1=496.

Размещено на Allbest.ru