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