Программирование на сетях (стр. 4 из 4)

Рис. 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. Миненко С.Н., Гамазина Г.И. Экономико-математическое моделирование производственных систем. – Учебное пособие, МГИУ