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

Для построения матрицы нового потока X¹ к соответствующим элементам x_ij ⁰ матрицы XP⁰ прибавляется найденное значение , после чего возвращаются к п. 2 алгоритма, и т.д. до получения максимального потока.

Прибавим величину к элементам x₁₂ ⁰ = 1, x₂₄ ⁰ = 0 и x₄₆ ⁰ = 2, обозначающим ненасыщенный путь (по всем остальным ребрам величина потока не изменится). Приходим к матрице нового потока X¹ (см. табл. 1.5), мощность которого равна 7 ед. Этот поток вновь надо исследовать на оптимальность, т. е. вернуться к п. 2 алгоритма. Вновь составляем матрицу R – X¹ (см. табл. 1.5), а по ней – списки вершин, достижимых из истока I по ненасыщенным путям:

Из этих списков видно, что сток 6 снова в подмножестве A, а путь, ведущий в него, состоит из ненасыщенных ребер (1, 2), (2, 4), (4, 5), (5, 6). Новый поток X² , (его матрица представлена в табл. 1.6, получается преобразованием потока X¹ , если увеличить на потоки по указанным ребрам найденного ненасыщенного пути. Мощность нового потока X² составляет 9 ед. Для исследования этого потока составляется матрица R – X² (табл. 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 вершин, достижимых из истока по ненасыщенным ребрам. Значит поток X² максимален. Нанесем его на сеть с указанием направления потоков по отдельным ребрам (см. рис. 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 – X² , если своевременно заметить, что потоки по ребрам (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).

Заключение

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

Список использованной литературы

1. Акулич Н.А. Математическое программирование в примерах и задачах. – М.: Высшая школа, 2003.

2. Иозайтис В.С., Львов Ю.А. Экономико-математическое моделирование производственных систем. – М.: Высшая школа, 2000.

3. Миненко С.Н., Гамазина Г.И. Экономико-математическое моделирование производственных систем. – Учебное пособие, МГИУ