Построение математической модели

Математическую модель данной задачи строим в виде сети. Пусть пользователи (S^/, S^//) связаны через 5 серверов (узлы сети) каналами связи (дуги). Пусть также известен объем информации, который каждый канал способен пропускать в единицу времени (пропускные способности - числа над дугами).

Тогда исходная задача может быть формализована в виде сетевой модели, представленной на рисунке 4.8:

Условно примем требование однонаправленности информационного потока в заданной сети, например S^/®S^// (оптимальная схема передачи информации S^//®S^/, очевидно, будет такой же).

Данная задача может быть решена как задача о максимальном потоке. Воспользуемся алгоритмом Форда-Фалкерсона отыскания максимального потока в сети.

Решение:

Находим произвольный ориентированный путь, соединяющий узлы S^/ и S^//.

1) S^/®1®3®2®S^//.

Выбираем минимальную пропускную способность из всех пропускных способностей дуг, входящих в выбранный путь: a₁ = min{10, 7, 6, 8} = 6.

Это и есть величина потока, пропущенного по данному пути. Записываем a₁=6 над дугами, входящими в этот путь, в скобках, а за скобками записываем оставшуюся пропускную способность как разность между пропускной способностью на предыдущем шаге и величиной пропущенного потока a₁=6.

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

Процесс решения данной задачи представлен ниже, а иллюстрирован на рисунке 4.9.

2) S^'®4®5®S^'', a₂ = min{4, 10, 13} = 4;

3) S^'®1®2®S^'', a₃ = min{4, 5, 2} = 2;

4) S^'®3®S^'', a₄ = min{2, 2} = 2.

После четвертого шага алгоритм заканчивает свою работу, так как больше нет путей, связывающих узлы S^/ и S^//.

Величина максимального потока:

r _max= a₁+a₂+a₃+a₄= 6+4+2+2= 14,

а сам максимальный поток (оптимальное решение задачи) представлен на рисунке 4.10:

Над дугами записаны величины потока, пропущенного по каждой из них.

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

максимальный объем информации, который может быть передан в единицу времени через данную информационную сеть с рабочей станции S^/ на рабочую станцию S^// (или в обратном направлении), равен 14 единицам объема информации.