Разработка имитационной модели транспортной сети (стр. 3 из 5)

Правило: для того чтобы разыграть дискретную случайную величину, заданную законом распределения (2) нужно:

1) разбить интервал (0;

2) оси на Or на n частичных интервалов:

∆₁ = (0; p₁), ∆₂= (p₁; p₁ +p₂),..., ∆_n= (p₁ +p₂ +…+p_n-1;

3) выбрать случайное число r_{j (}например, из таблицы случайных чисел). Если r_j попало в частичный интервал ∆_i, то разыгрываемая случайная величина приняла возможное значение x_i.

2. Имитационная моделЬ железнодорожной сети

2.1 Формализация модели железнодорожной сети

Рассмотрим железнодорожную сеть:

Рисунок 2.1.1 - Граф железнодорожной сети

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

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

Эта задача решается следующим образом. Для получения усредненных характеристик максимального потока и его “выгоды" необходимо провести N прогонов.

На первой итерации применения процедуры Монте-Карло вероятностная задача поиска максимального потока в сети превращается в классическую. При этом определяются компоненты матрицы пропускных способностей путём вычисления c_ijl=c_ij-v_ijl, где v_ijl определяется по функции распределения H_ij (v) путём нахождения единичного жребия третьего типа.

При учёте влияния внутренних потоков на пропускные ситуации в сети возможны следующие ситуации:

внутренних потоков нет на участке дороги;

внутренние потоки влияют на пропускную способность участка таким образом, что она уменьшается, но остаётся больше либо равна значению потока на этом участке, т.е.

, где - пропускная способность сети изменённая с учётом внутренних потоков (при этом алгоритм Форда-Фалкерсона работает и находится максимальный поток и его распределение по ветвям сети);

внутренние потоки влияют на пропускную способность участка таким образом, что она уменьшается и становится меньше значения потока на этом участке, т.е.

, где - пропускная способность сети изменённая с учётом внутренних потоков (в этих условиях алгоритм Форда Фалкерсона не работает и данная ситуация говорит о возникновении “пробки" в сети на этом участке).

Для каждого i-го узла сети с учётом заданных функций распределения времён формирования-расформирования вычисляется среднее время нахождения в i-ом узле транспортной единицы. В качестве начального потока выбираются значения матрицы

.

На k-ой итерации (k - номер итерации в алгоритме Форда-Фалкерсона) с помощью алгоритма Форда-Фалкерсона, используя изменённую матрицу пропускных способностей определяется само распределение потока по сети и его значение потока. По формулам (1.2), (1.3), и (1.4) с учётом распределения потоков, определяется обобщённый показатель “выгоды" этого потока. Значения потока, матрица значений распределения потока по ветвям и показатель “выгоды" запоминаются в базе данных модели (БДМ). Модифицируется номер итерации процедуры Монте-Карло (l=l+1) и все расчёты повторяются сначала.

По завершении N итераций этих расчётов в БДМ модели сформированы следующие выборки: выборка матриц распределения потока по ветвям сети, то есть для каждого элемента матрицы распределений потока имеется своя выборка; выборка значений максимального потока; выборка интегральных показателей “выгоды" потока.

По этим выборкам объема N формируются средние значения, а именно:

; ;

Все эти значения должны быть вычислены и представлены пользователю по завершении работы программы.

Для поиска узких мест в G_h с начальным пунктом Z и конечным пунктом Y проведём покомпонентное вычитание из этой матрицы соответствующих значений матрицы пропускных способностей С_h::

В тех местах, где элементы этой матрицы будет иметь отрицательное значение, находятся “узкие места" в G_h. На величину этой разности пропускные способности с_ij должны быть увеличены для того, чтобы граф G_h обеспечивал максимальный поток транзитных маршрутов в направлении из точки Z в точку Y.

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

Алгоритм работы модели основан на сочетании процедуры Монте-Карло и теоремы Форда-Фалкерсона и применением единичного жребия третьего типа.

2.2 Алгоритм работы модели железнодорожной сети

Алгоритм работы модели железнодорожной сети представлен на рисунке 2.2 Для работы программного обеспечения необходимо задать следующие входные значения:

- матрица пропускной способности сети;

- матрица расстояния между узлами;

- матрица стоимости единицы пути;

- функция распределения времени на формирование и расформирование составов;

- вектор времени на формирование и расформирование составов;

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

Рассмотрим работу модели на первом прогоне (i=1). Программное обеспечение учитывает, что в сети кроме транзитных потоков существуют внутренние транспортные потоки. Эти внутренние потоки влияют на пропускную способность сети. Таким образом, на каждом прогоне изменяется матрица пропускных способностей c [i,j] путем разыгрывания единичного жребия третьего типа.

С помощью алгоритма Форда-Фалкерсона вычисляется максимальный поток maxpotok, распределение потока в сети f [i,j], и по формулам (1.2), (1.3) и (1.4) определяется обобщённый показатель “выгоды" этого потока Ф_zy. Все эти значения запоминаются в базе данных ЭВМ.

Если i<=pr, то программа продолжает первоначальные вычисления. В противном случае (если i>pr) вычисляется следующие средние значения: максимальный поток maxpotok, распределение потоков f [i,j] и обобщённый показатель “выгоды" Ф_zy на каждом прогоне. Далее определяются узкие места в сети. Для этого вычисляются значения: f_ср [i,j] -c [i,j] и в тех местах, где матрица принимает отрицательные значения на величину этой разницы увеличиваются пропускные способности матрицы c [i,j] для обеспечения рациональной организации потоков железнодорожной сети.

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

Рисунок 2.2 - Блок-схема реализованного программного обеспечения

2.3 Решение тестовых задач с помощью имитационной модели

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

поиск максимального потока и усредненного потока в сети железнодорожных дорог различным количеством узлов (N<100);

поиск узких мест и оптимальная организация потоков в сети дорог.

Интерфейс реализован на языке Borland Delphi 7.0. На рисунке 2.3 представлен интерфейс программного обеспечения.

Рисунок 2.3 - Интерфейс программного обеспечения

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