Программирование на сетях
Для
построения
матрицы нового
потока X1
к соответствующим
элементам xij0
матрицы
XP0
прибавляется
найденное
значение
,
после чего
возвращаются
к п. 2 алгоритма,
и т.д. до получения
максимального
потока.
Прибавим
величину
к элементам
x120
= 1, x240
= 0 и x460
= 2, обозначающим
ненасыщенный
путь (по всем
остальным
ребрам величина
потока не изменится).
Приходим к
матрице нового
потока X1
(см. табл. 1.5), мощность
которого равна
7 ед. Этот поток
вновь надо
исследовать
на оптимальность,
т. е. вернуться
к п. 2 алгоритма.
Вновь составляем
матрицу R
– X1
(см. табл. 1.5), а по
ней – списки
вершин, достижимых
из истока I
по ненасыщенным
путям:
![]()
Из
этих списков
видно, что сток
6 снова в подмножестве
A,
а путь, ведущий
в него, состоит
из ненасыщенных
ребер (1, 2), (2, 4), (4, 5), (5, 6).
Новый поток
X2,
(его матрица
представлена
в табл. 1.6, получается
преобразованием
потока X1,
если увеличить
на
потоки по указанным
ребрам найденного
ненасыщенного
пути. Мощность
нового потока
X2
составляет
9 ед. Для исследования
этого потока
составляется
матрица R
– X2
(табл. 1.8), а по ней
– списки.
(1.8)
Таблица 1.6
|
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
5 |
2 |
2 |
0 |
0 |
|
2 |
-5 |
0 |
0 |
4 |
1 |
0 |
|
3 |
-2 |
0 |
0 |
0 |
2 |
0 |
|
4 |
-2 |
-4 |
0 |
0 |
2 |
4 |
|
5 |
0 |
-1 |
-2 |
-2 |
0 |
5 |
|
6 |
0 |
0 |
0 |
-4 |
-5 |
0 |
Таблица 1.7
|
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
4 |
2 |
0 |
0 |
0 |
|
2 |
6 |
0 |
8 |
2 |
0 |
0 |
|
3 |
8 |
8 |
0 |
0 |
0 |
0 |
|
4 |
7 |
11 |
0 |
0 |
8 |
0 |
|
5 |
0 |
6 |
4 |
3 |
0 |
2 |
|
6 |
0 |
0 |
0 |
10 |
10 |
0 |
По спискам (1.8) видно, что сток 6 не попал в подмножество A вершин, достижимых из истока по ненасыщенным ребрам. Значит поток X2 максимален. Нанесем его на сеть с указанием направления потоков по отдельным ребрам (см. рис. 1.11).
Таблица 1.8
|
i/j |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
4 |
2 |
0 |
0 |
0 |
|
2 |
6 |
0 |
8 |
2 |
0 |
0 |
|
3 |
8 |
8 |
0 |
0 |
0 |
0 |
|
4 |
7 |
11 |
0 |
0 |
8 |
0 |
|
5 |
0 |
6 |
4 |
3 |
0 |
2 |
|
6 |
0 |
0 |
0 |
10 |
10 |
0 |

Рис. 1.11
Можно было бы и не строить матрицу R – X2, если своевременно заметить, что потоки по ребрам (4, 6) и (5, 6) равны их пропускным способностям, т.е эти ребра насыщены (см. табл. 1.7 и 1.8).
Используя списки (табл. 1.8) выделим подмножества A и B, на которые оказалось разбитым множество всех вершин: A = {1, 2, 3}, B = {4, 5, 6}. Теперь можно выписать ребра, образующие разрез A / B минимальной пропускной способности: (1, 4), (2, 4), (2, 5), (3, 5).
Заключение
Как говорилось выше, теория графов, теория сетей имеют широкое и разнообразное применение. К задаче о максимальном потоке можно, например, свести задачу об оптимальном назначении, хотя такая задача относится к задаче целочисленного программирования и может быть решена соответствующими методами. К задаче о максимальном потоке можно свести транспортную задачу на минимизацию времени перевозок.
Список использованной литературы
Акулич Н.А. Математическое программирование в примерах и задачах. – М.: Высшая школа, 2003.
Иозайтис В.С., Львов Ю.А. Экономико-математическое моделирование производственных систем. – М.: Высшая школа, 2000.
Миненко С.Н., Гамазина Г.И. Экономико-математическое моделирование производственных систем. – Учебное пособие, МГИУ