Экономико-математическое моделирование / Курсовая работа: Программирование на сетях

Курсовая работа: Программирование на сетях

Построенное разбиение является разрезом A/B. По условию разбиения для любой вершины существует путь из истока в i, состоящий из ненасыщенных ребер, а для любой вершины такого пути нет. Отсюда следует, что любое ребро (i,j) разреза A/B будет насыщенным (иначе j принадлежало бы A), т.е. xij = rij. Просуммируем все эти равенства по всем и всем и получим

(1.6)

В этом равенстве слева – величина X потока через разрез, справа – пропускная способность R разреза A/B. Из равенства (1.6) по теореме Форда - Фалкерсона следует, что поток X = {xij} является максимальным.

Рассмотрим случай 2. Если то существует путь из ненасыщенных ребер, ведущий из истока в сток. По ребрам этого пути можно пропустить дополнительный поток величиной , где минимум берется по всем ребрам, входящими в этот путь. Потоки xBijB по всем остальным ребрам остаются без изменения. В результате мощность суммарного потока возрастет на величину и это будет новый поток X = {xBijPB 1P }.

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

1. Построить некоторый начальный поток XP0P = {xBijPB 0P }.

2. Найти подмножество A вершин, достижимых из истока I по ненасыщенным ребрам. Если в этом процессе сток S не попадет в подмножество A, то построенный поток максимальный и задача решена. Если же сток S попал в A, то перейти к п. 3 алгоритма.

3. Выделить путь из истока I в сток S, состоящий из ненасыщенных ребер, и увеличить поток xBij B по каждому ребру этого пути на величину , где минимум берется по ребрам (i,j) упомянутого пути. Это означает, что будет построен новый поток XP1P = {xBijPB 1P }. После этого надо вернуться к п. 2 данного алгоритма.

Замечание: при выполнении п. 3 алгоритма на каждом шаге по крайней мере одно из ненасыщенных раннее ребер становится насыщенным. Поскольку число ребер в сети конечно, то через конечное число шагов максимальный поток будет построен.

Разберем на примере предложенный алгоритм.

Рис. 1.10

На рис. 1.10 изображена сеть с истоком I в вершине (1) и стоком в вершине (6). В скобках проставлена пропускная способность ребер в прямом и обратном направлении. В табл. 1.2 показана матрица пропускных способностей сети.

В соответствии с п. 1 алгоритма сформируем на сети первоначальный поток XP0P . В этом потоке по пути 1 – 3 – 5 – 6 перемещаются 2 ед., поскольку ограничивает величину потока ребро (3, 5); по пути 1 – 2 – 5 – 6 перемещается 1 ед., лимитирующим является ребро (2, 5); по пути 1 – 4 – 6 – 2 – 2 ед., и ребро (1, 4) становится насыщенным. Матрица потока представлена на табл. 1.3.

Мощность потока XP0 P рассчитаем по формуле (1.4).

f = xB12B + xB13 B + xB14B = xB46B + xB56B = 1 + 2 + 2 = 2 + 3 = 5.

Таблица 1.2

i/j 1 2 3 4 5 6
1 0 7 4 2 0 0
2 3 0 8 4 1 0
3 6 8 0 0 2 0
4 5 9 0 0 8 4
5 0 5 2 3 0 5
6 0 0 0 6 7 0

Таблица 1.3

i/j 1 2 3 4 5 6
1 0 1 2 2 0 0
2 -1 0 0 0 1 0
3 -2 0 0 0 2 0
4 -2 0 9 0 4 0
5 0 -1 -2 0 0 3
6 0 0 0 -2 -3 0

Для выполнения п. 2 алгоритма рассчитаем матрицу R – XP0P , приведенную в табл. 1.4. Элементы (rij – xij 0 ) этой матрицы позволяют судить о насыщенности ребер сети. Нулевые элементы соответствуют насыщенным ребрам, ненулевые – ненасыщенным. С помощью матрицы R – XP0P можно сформировать подмножество A вершин, в которое можно попасть из истока I, двигаясь только по ненасыщенным путям, выделить их (если поток XP0 P не максимален) и с их помощью увеличить мощность потока.

Таблица 1.4

i/j 1 2 3 4 5 6
1 0 3 2 2 0 0
2 -3 0 0 2 1 0
3 -2 0 0 0 2 0
4 -2 -2 0 0 0 4
5 0 -1 -2 0 0 3
6 0 0 0 -4 -3 0

Таблица 1.5

i/j 1 2 3 4 5 6
1 0 6 2 0 0 0
2 4 0 8 4 0 0
3 8 8 0 0 0 0
4 7 9 0 0 8 2
5 0 6 4 3 0 2
6 0 0 0 8 10 0

Вершины подмножества A выделяют постепенно, начиная с истока I. Для этого просматривают первую строку матрицы R – XP0 P ( в общем случае строку I) и выписывают номера вершин iB1B , iB2B , …, iBkB , соответствующих ненулевым элементам стоки. Это и будут вершины, в которые можно попасть из истока, перемещаясь по ненасыщенным ребрам. Запишем выявленные вершины в виде списка

Далее рассматривают каждую из вершин iBk B полученного списка и составляют для нее свой список аналогичным образом. При этом вершины, встречающиеся в прежних списках, повторно не выписываются.

Если в этом процессе сток S не встретится, то поток максимален и задача решена; если же, напротив, при составлении очередного списка в нем появится сток S, то поток не максимален и его мощность можно увеличить. Для этого выделяют ненасыщенный путь из истока в сток. Построение ненасыщенного пути из I в S начинают с последнего ребра этого пути. Этим ребром будет (iBn -1B , S), где iBn -1 B – вершина, в список которой попал сток S. Далее находят ребро (iBn -2B , iBn -1B ), где iBn -2B - вершина, в список которой попала вершина iBn -1B , и т.д., пока не встретится ребро (I, iB1B ), которым начинается искомый ненасыщенный путь.

В данном примере I = 1, S = 6. Построим подмножество A, начиная с вершины. В табл. 1.4 в первой строке ненулевые элементы стоят во втором и третьем столбцах. Следовательно, запишем .

Последовательно составляем списки вершин 2 и 3. Во второй строке матрицы три элемента отличны от нуля: 4, 8, 4. Цифры 4 и 8 соответствуют вершинам 7 и 3, которые уже вошли в подмножество A, поэтому эти вершины повторно в списки не включаем. В четвертом столбце цифра 4 встречается впервые, поэтому включаем ее в список вершины . Переходим к вершине 3. В третьей строке матрицы R – XP0 P ненулевым элементам соответствуют вершины 1 и 2, которые уже встречались в списках. Значит, список вершины 3 будет пустым: … Аналогичным образом составляется список вершины . Повторим полученный набор списков:

(1.7)

Просматривая списки, замечаем что сток (вершина 6) попал в подмножество A. Значит поток XP0 не максимален и существует путь из истока в сток, состоящий из ненасыщенных ребер.

Перейдем к п. 3 алгоритма – выделению ненасыщенных ребер пути из истока в сток и преобразованию имеющегося потока в новый поток большей мощности. В списке (1.7) последним ребром (in -1 , S) является (4, 6), ребром (i Bn -2B , i Bn -1B ) – ребро (2, 4), ребром (I, iB1B ) – ребро (1, 2). Найденный путь по ненасыщенным ребрам из истока 1 в сток 6 пройдет через вершины 1, 2, 4 и 6.

К-во Просмотров: 334
Бесплатно скачать Курсовая работа: Программирование на сетях