Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

Задача о максимальном потоке на сети. Метод форда-фалкерсона

Постановка задачи о максимальном потоке на сети.

На сети, что задается графом (I,U), где I — множество вершин, U — множество дуг, с определенной на ней функцией пропускных способностей rij ((і,j) — дуга с U), зафиксированные две вершины — i1 и in. Вершина i1 (источник) имеет интенсивность d, вершина in (стек) — интенсивность d, все другие вершины нейтральные. Нужно найти максимальную интенсивность источника d, при которой сеть допускает поток. Поток, что отвечает такому максимальному значению интенсивности d*, называется максимальным потоком, а именно значение d*величиной этого потока.

Алгоритм Форда-Фалкерсона применяется для построения максимального потока на сети из заданной начальной вершины-источникав заданную конечную вершину-сток.

Будем считать, что вершиной-источником является 1-я вершина, вершиной-стоком — вершина с номером n.

Входные данные.

Для работы алгоритма необходимо задать следующую информацию:

1. Число вершин сети.

2. Матрицу смежности С, элементы которой сіjопределяются соотношениями:

сij=1, если существует дуга (і,j);

сij=0, если дуга (і,j) отсутствует.

3. Величины rijпропускных способностей дуг (і,j).

4. Начальный поток на сети, то есть величины xij, которые удовлетворяют условия:

a) 0xijrij;

b) Для произвольной вершины (кроме первой и последней) поток, что входит в вершину, равняется потоку, что выходит из нее.

Изложение алгоритма Форда-Фалкерсона.

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

В каждой итерации можно выделить два этапа.

Этап 1 (этап выставления отметок).

1. В каждый момент времени каждая вершина может находиться в одном из трех положений:

а) не обозначенная;

б) обозначенная, но не рассмотрена;

в) обозначена и рассмотрена.

Общий вид отметки j-ївершины: [i+j], или [и,j], где и — номер некоторой обозначенной вершины, при просмотре которой была обозначена вершина j. Вершина 1 всегда обозначена и имеет отметку [1+1], где 1 равное +  (бесконечности).

2. Просмотр произвольной обозначенной вершины j заключается в следующем:

a) произвольная необозначенная вершина k, для которой существует дуга (j,k) и имеет место неравенство xjk<rjk, получает отметку вида [j+k], где

k=min {j, rjk xjk};

б) произвольная необозначенная вершина k, для которой существует дуга (k,j) и имеет место условие xkj>0, получает отметку вида [j,k], где

k=min {j, xkj}.

3. Процесс выставления отметок заканчивается в одном из двух случаев:

а) вершина с номером n обозначена;

б) условие а) не выполняется, но ни одну вершину больше пометить нельзя.

В первом случае переходим к этапу изменения потока на сети. Во втором — до определения минимального разреза сети и максимального потока.

Этап 2 (этап изменения потока).

Поток в сети изменяется на величину n согласно правила.

Если вершина n имеет отметку [k+n], где k — номер некоторой вершины, то xkn=xkn+n. Если отметка имеет вид [k,n], то xnk=xnkn. Переходим к вершине с номером k. Если отметка вершины k имеет вид [j+k], то xjk=xjk+n; если она равняется [j,k], то xkj=xkjn. Подобные действия продолжаем до тех пор, пока не будет достигнута начальная вершина. В этом случае все старые отметки вытираем и возвращаемся к первому этапу.

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

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

Величина максимального потока ровная суммарной пропускной способности минимального разреза.

Программное обеспечение.

Обучающий модуль, с помощью которого задача о максимальном потоке на сети Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗМО.

Задание.

Решить методом Форда-Фалкерсона задачи о максимальном потоке на сети, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи, в каждой из которых сеть задается матрицами смежности C и пропускных способностей R. Во всех задачах источником считается вершина 1, а стоком — вершина 6.

1)

0

1

1

0

0

0

0

10

18

0

0

0

0

0

0

0

1

1

0

0

0

0

14

1

C =

0

1

0

1

0

0

,

R =

0

10

0

17

0

0

;

0

1

0

0

1

1

0

9

0

0

22

12

0

0

0

0

0

1

0

0

0

0

0

18

0

0

0

0

0

0

0

0

0

0

0

0

2)

0

1

1

0

0

0

0

11

33

0

0

0

0

0

0

1

1

0

0

0

0

14

4

0

C =

0

1

0

1

1

0

,

R =

0

5

0

15

23

0

;

0

0

0

0

0

1

0

0

0

0

0

23

0

0

0

1

0

1

0

0

0

11

0

22

0

0

0

0

0

0

0

0

0

0

0

0

3)

0

1

1

1

0

0

0

20

21

22

0

0

0

0

1

1

1

0

0

0

5

13

14

0

C =

0

0

0

0

1

1

,

R =

0

0

0

0

12

28

;

0

0

1

0

1

1

0

0

12

0

11

10

0

0

0

0

0

1

0

0

0

0

0

17

0

0

0

0

0

0

0

0

0

0

0

0

4)

0

1

1

1

0

0

0

5

19

27

0

0

0

0

0

0

1

1

0

0

0

0

17

15

C =

0

1

0

0

1

1

,

R =

0

23

0

0

7

8

;

0

1

1

0

1

0

0

5

12

0

11

0

0

0

0

0

0

1

0

0

0

0

0

28

0

0

0

0

0

0

0

0

0

0

0

0

5)

0

1

1

1

1

0

0

24

33

6

12

0

0

0

1

1

1

0

0

0

10

15

7

0

C =

0

0

0

1

1

1

,

R =

0

0

0

11

15

17

;

0

0

0

0

1

1

0

0

0

0

12

26

0

0

0

0

0

1

0

0

0

0

0

25

0

0

0

0

0

0

0

0

0

0

0

0

6)

0

1

1

1

1

0

0

19

16

8

18

0

0

0

1

1

0

0

0

0

20

1

0

0

C =

0

0

0

0

1

1

,

R =

0

0

0

0

32

42

.

0

0

1

0

0

1

0

0

45

0

0

2

0

0

0

1

0

1

0

0

0

31

0

20

0

0

0

0

0

0

0

0

0

0

0

0

Ответы:

1) d* = 28. 2) d* = 44. 3) d* = 55. 4) d* = 51. 5) d* = 68. 6) d* = 61.

Лабораторная работа 9.