Разработка имитационной модели транспортной сети (стр. 2 из 5)
где w- общее количество входящих-исходящих дуг для узла i. Время на формирование-расформирование составов местного назначения принимается равным нулю.
Максимальный поток между узлами распределяется по ветвям сети, где k-номер итерации алгоритма Форда-Фалкерсона при определении максимального значения потока. Показатель затрат движения транспортных средств вдоль ветви ij графа Gh может быть задан одной из функций:
, (1.2)где
весовые коэффициенты важности соответственно расстояния ( 
), времени ( 
), стоимости ( 
) движения по ветвям сети. Величина 
есть среднее значение времени, затраченное транзитными составами на формирование-расформирование в i-ом узле. Оно определяется по формуле: 
, (1.3)где
- значение времени на формирование-расформирование, полученное по функции распределения 
. Поскольку при движении транспортных средств по сети Gh необходимо стремиться к минимизации этих затрат, то в качестве показателя “выгоды" максимального потока берётся общая характеристика затрат, которая вычисляется по матрице распределений максимального потока по всем ветвям ij графа Gh: 
(1.4)Таким образом, формула (1.4) определяет величину затрат при перемещении транспортного средства в сети Gh в условиях максимального потока. С одной стороны поток необходимо максимизировать, а с другой стороны показатель “выгоды" должен быть минимальным.
Наличие внутренних транспортных потоков в Gh обусловливает вероятностный характер пропускных способностей на многих ветвях графа Gh. Недетерминированное время формирования и расформирования составов влияет случайным образом на время передвижения транзитных составов из пункта отправления в пункт назначения по пути, содержащим этот узел. Указанные особенности не позволяют использовать для поиска максимального потока в сети алгоритм Форда-Фалкерсона. Поэтому актуально использование имитационной модели, основанной на сочетании процедуры Монте-Карло и теоремы Форда-Фалкерсона. Таким образом, ставятся задачи определения с помощью имитационной модели максимального потока в заданном направлении между множеством узлов входов в сеть и множеством узлов выходов, а так же поиска узких мест в сети Gh при перемещении транспорта в заданном направлении, устранение которых позволит достичь оптимальной организации потоков в сети. При поиске интегрального максимального потока в сети необходимо выполнение следующих условий: для каждого сочетания входа и выхода имеется максимальный поток, интегральная функция затрат имеет минимальное значение.
1.3 Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети
Алгоритм решения задач нахождения максимального потока в железнодорожной сети основан на теореме Форда-Фалкерсона: в любой транспортной сети максимальный поток равен минимальной пропускной способности. Если поток максимален, то найдется такое сечение, пропускная способность которого равна мощности потока. Доказывается эта теорема применением алгоритма Форд-Фалкерсона. Согласно этому алгоритму, начиная с некоторого начального неполного потока, по итеративному алгоритму можно получить полный поток, если прибавлять к различным значениям потоков
пути 
минимальное из чисел 
, которые вычислены по этому пути. После такой операции путь уже будет содержать хотя бы одну ненасыщенную дугу. Если таким же образом поступить с другими путями , то, в конце концов, получим полный поток. Поэтому алгоритм определения максимального потока состоит из следующих шагов:Строим начальный поток
;проверяем, попал ли узел
в множество узлов 
, которые достижимы по ненасыщенным ребрам из 
. Если узел не попал, то считают, что построенный поток максимален, и алгоритм расчета останавливается;если узел
попал во множество , то выделяют путь 
, состоящий из ненасыщенных ребер и ведущий грузы из в ;увеличивают поток через каждое ребро этого пути на величину
;строят новый поток
и переходят к шагу 2.Обычно сеть задается матрицей пропускной способностей
всех ребер сети 
. Задавая 
, затем вычисляют на k-м шаге матрицу значений потоков на дугах 
. Строят матрицу разностей 
. В этой матрице насыщенным ребрам при потоке 
будут соответствовать нулевые элементы, ненасыщенным - ненулевые элементы. Поэтому вычисление матрицы 
достаточно как для построения множества узлов по которым вещество из 
достигает по ненасыщенным ребрам до , так и для построения последовательности ненасыщенных ребер.Технология составления этих списков следующая:
сначала составляют список узлов, в каждый из которых ведет ненасыщенное ребро из вершины i;
далее для каждого i-го узла составляют свой список узлов, в каждый из которых из i-го узла ведет ненасыщенное ребро (за исключением тех узлов, которые уже вошли в ранее составленные списки) и так далее.
Этот процесс выписывания списков заканчивается в двух случаев. Либо появиться узел
, что означает продолжение работы алгоритма, либо в список выписанных узлов не попал узел , что означает конец расчетов. 1.4 Метод Монте-Карло
Пусть требуется разыграть дискретную случайную величину X, т. е получить последовательность её возможных значений xi, зная закон распределения X:
| X | x1 | x2 | … | xn |
| p | p1 | p2 | … | pn |
Рисунок 1.1 - Распределение случайной величины X
Обозначим через R непрерывную случайную величину, распределённую равномерно в интервале (0,1), а через rj,
- её возможные значения, т.е. случайные числа.Разобьём интервал 0£ R <1 на оси Оr точками с координатами p1, p1+ p2, p1+ p2+ p3,..., p1 + p2 +…+ pn-1 на n частичных интервалов ∆1, ∆2,..., ∆n, длины которых p1, p2,…, pn соответственно. Таким образом, |∆i|= pi (1), где i=1, 2, …,n.
Теорема: если каждому случайному числу rj (0£ rj <1), которое попало в интервал ∆i, ставить в соответствие возможное значение xi, то разыгрываемая величина будет иметь заданный закон распределения:
Так как при попадании случайного числа rj в частичный интервал ∆i разыгрываемая величина принимает возможное значение xi, а таких интервалов всего n, то разыгрываемая величина имеет те же возможные значения, что и X, а именно x1, x2,..., xn. Вероятность попадания случайной величины R в интервал ∆i равна его длине, а в силу |∆i|= pi, получим, что вероятность попадания R в интервал ∆i равна pi. Следовательно, вероятность того, что разыгрываемая величина примет возможное значение xi, также равна pi. Таким образом разыгрываемая величина имеет заданный закон распределения как показано на рисунке 1.1