Математика/5. Математическое моделирование

Пакляченко М. Ю.

Воронежский институт МВД России

Сравнительный анализ моделей систем передачи данных и транспортных систем: моделирование перераспределения потоков

 

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

Для моделирования загрузки сети используется концепция равновесного распределения потоков: состояния прямой зависимости цены путей  от загрузки системы и обратной зависимости, при котором загруженность системы будет определяться стоимостью путей [1]. Входные данные к процессу моделирования отражаются матрицами корреспонденций (количественными характеристиками структурности транспортной/информационной системы, элементы которых описывают объемы передвижений между каждой парой условных районов/каналов/магистралей). Критерием оценки путей/маршрутов при расчете является «обобщенная цена» (сумма различных факторов, главный из которых - время, выражаемых математически, на основании которых оцениваются альтернативные пути и способы передвижения).

Цель математического моделирования заключается в выборе путей / каналов, которые будут задействованы для пересылки корреспонденции между районами/узлами системы, подбор коэффициентов расщепления (долей) корреспонденции между этими путями.

В зависимости от применяемого подхода к моделированию процессов перераспределения потоков выделяют следующие типы моделей загрузки системы:

- нормативные (перераспределение формируется на основе оптимизации некоторого общесистемного критерия эффективной работы сети, например временного),

- дескриптивные (учитывают оптимизацию частных критериев для каждой корреспонденции в отдельности),

- статистические (используют аппарат усреднения основных характеристик передвижения потоков в определенном временном интервале),

- динамические (применяются в случае изменения динамики передвижений корреспонденций по длинным маршрутам в разные периоды времени, при этом объемы пересылок будут являться функциями от времени).

Наиболее востребованы модели, основанные на равновесном перераспределении потоков. Они обладают рядом особенностей, которые детально рассмотрел в своих работах Вардроп [2]:

- одинаковая ценовая политика для всех путей/каналов, соединяющих районы/узлы i  и j;

- цена незадействованного в маршруте пути/канала между районами/узлами i и j выше цены используемых путей.

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

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

Линеаризуем ( ) функцию распределения потоков на k-ом шаге ():

,                                                  (1)

тогда поиск очередного приближения с определенным направлением смещения будет осуществляться по формуле:

,                                                  (2)

где - доля/коэффициент расщепления потоков, определений которой на каждой итерации требует отдельного рассмотрения.

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

.                                               (3)

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

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

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

- определяется произвольное распределение нулевой итерации (задается условиями задачи, расчет кратчайших путей незагруженной сети);

- на основании полученной итерации по значениям потоков  пересчитываются цены всех элементов сети;

- производится нахождение кратчайших путей в соответствии с новой ценовой обстановкой;

- в результате наложения корреспонденций на кратчайшие пути рассчитываются линеаризованные потоки ( );

- поиск нового перераспределения потоков системы вычисляется как:

,                                              (4)

где - коэффициент расщепления потоков определяется решением одномерной задачи:

 ,                                                (5)

где  - функция распределения потоков, зависящая от ценовой функции   .

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

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

Важной особенностью в процессе расчета является обратная связь: матрицы корреспонденций и коэффициенты расщепления по типам передвижений зависят от обобщенных цен межрайонных передвижений, которые, в свою очередь, подчиняются  результирующей загрузке элементов сети. Для приведения "входных" и "выходных" цен в соответствие друг с другом организуется итерационный процесс вычисления матриц и загрузки (рис. 1.).

Рис. 1. Алгоритм балансного расчета перераспределения потоков системы итерационным методом

 

Литература:

1.      Моделирование транспортных потоков в крупном городе с применением к Москвской агломерации. / Алиев А.С., Стрельников А.И., Швецов В.И., Шершевский Ю.З. Автоматика и телемеханика, № 11, 2005. -  190 c.

2.      Wardrop J. G. Some theoretical aspects of road traffic research // Proc. Institution of Civil Engineers II. 1952. P. 325-378.

3.      Пакляченко М.Ю. Применение итерационных методов решения систем линейных алгебраических уравнений для анализа многоканальных систем обработки информации/Пакляченко М.Ю.; Молодежный научно-исследовательский журнал. - 2013. №12 (19).   С. 118-120.