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

2016-07-30СтудИзба

Описание файла

Документ из архива "Разработка имитационной модели транспортной сети", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "48564"

Текст из документа "48564"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

Учреждение образования "Гомельский государственный университет имени Франциска Скорины"

Математический факультет

Кафедра МПУ

Разработка имитационной модели транспортной сети

Курсовая работа

Исполнитель

студентка группы ПМ-44

Бутакова О.В.

Научный руководитель

доцент кафедры МПУ Сукач Е.И.

Гомель 2007

Содержание

Введение

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

1.1 Актуальность использования имитационной модели для исследования потоков в железнодорожной сети

1.2 Описание модели железнодорожной сети

1.3 Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети

1.4 Метод Монте-Карло

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

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

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

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

Заключение

Список использованных источников

Приложение

Листинг программы


Введение

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

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

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

актуальность использования имитационной модели для исследования потоков транспортной сети;

составление списков входных и выходных параметров имитационной модели железнодорожной транспортной сети;

разработка и реализация алгоритма имитационной модели;

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

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

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


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

1.1 Актуальность использования имитационной модели для исследования потоков в железнодорожной сети

В наше время за счёт резкого увеличения числа транспортных средств в сетях дорог существенно возросли требования к рациональной организации транспортных потоков. Сама сеть дорог может быть представлена в виде графа, состоящего из узлов и дуг. Каждое ребро графа, соответствующее участку дороги, характеризуется длиной, пропускной способностью и стоимостью проезда по нему единицы транспортного средства. На пропускную способность ветви графа влияет скорость передвижения единицы транспорта, которая в свою очередь зависит от многих факторов, среди которых наиболее важными являются загруженность участков пути, состояние дорожного покрытия, условия внешней среды. Загруженность на различных участках дороги бывает различной и зависит от наличия внутренних транспортных потоков на данном участке, которые могут рассматриваться как помехи при передвижении транспортной единицы из начального пункта сети в конечный пункт. Состояние дороги определяется её изношенностью, условиями эксплуатации, влиянием погодных условий. Параметры внешней среды изменяются в зависимости от времени года, времени суток и подвержены влиянию погодных воздействий. Значения факторов, определяющих рациональную организацию транспортных потоков в сети, изменяются во времени. Наличие внутренних транспортных потоков на каждом участке сети носит вероятностный характер. Отдельные участки транспортной сети изменяют своё состояние (изнашиваются) с разной интенсивностью. Параметры внешней среды периодически изменяются. При управлении следует учитывать, что в реальной транспортной сети перечисленные факторы являются взаимосвязанными.

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

Наличие случайных факторов, влияющих на состояние транспортной сети, не позволяет решать перечисленные задачи с использованием известного аппарата, основанного на аналитических моделях, называемых графовыми моделями. Особенно большие трудности у исследователей вызывает определение узких мест в сети при наличии транспортных потоков относящихся к различным направлениям и вероятностных внутренних потоков на отдельных участках сети, которые могут приводить к увеличению числа аварий и возникновению “пробок".

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

1.2 Описание модели железнодорожной сети

Структуру транспортных потоков в железнодорожной сети можно представить в виде графа Gh, где h-вариант организации транспортных потоков в железнодорожной сети. Перевозки в сети реализуются в соответствии со следующими параметрами, определяемыми матрицами:

; ; ; , (1. 1)

где cij - пропускные способности ветвей графа Gh, соединяющих узел i с узлом j; lij - расстояния между узлами i и j; - начальный поток по ветви ij; qij - стоимость единицы пути движения транспортного средства по ветви ij. Определёно множество входов в сеть , и множество выходов из сети , в одном направлении. В сети кроме транзитных потоков существуют внутренние транспортные потоки на отдельных отрезках дороги в одну и другую сторону, которые снижают пропускные способности ветвей графа Gh. Величины внутренних транспортных потоков для ij-ых участков определяются функциями распределения . Пропускные способности ветвей ij графа Gh с учётом внутренних потоков изменяются и представляют собой случайные величины, определяемые с помощью функций распределения .

В каждом узле железнодорожной сети происходят процессы формирования-расформирования составов. Длительность этих процессов, как правило, носит вероятностный характер и описывается функциями распределения. Функции распределения для каждого i-ого узла сети задаются матрицей , где каждый элемент матрицы есть функция распределения времени на формирование-расформирование в i-ом узле для состава, пришедшего с узла k и следующего в узел j. Матрица имеет вид:

где w- общее количество входящих-исходящих дуг для узла i. Время на формирование-расформирование составов местного назначения принимается равным нулю.

Максимальный поток между узлами распределяется по ветвям сети, где k-номер итерации алгоритма Форда-Фалкерсона при определении максимального значения потока. Показатель затрат движения транспортных средств вдоль ветви ij графа Gh может быть задан одной из функций:

, (1.2)

где весовые коэффициенты важности соответственно расстояния ( ), времени ( ), стоимости ( ) движения по ветвям сети. Величина есть среднее значение времени, затраченное транзитными составами на формирование-расформирование в i-ом узле. Оно определяется по формуле:

, (1.3)

где - значение времени на формирование-расформирование, полученное по функции распределения . Поскольку при движении транспортных средств по сети Gh необходимо стремиться к минимизации этих затрат, то в качестве показателя “выгоды" максимального потока берётся общая характеристика затрат, которая вычисляется по матрице распределений максимального потока по всем ветвям ij графа Gh:

(1.4)

Таким образом, формула (1.4) определяет величину затрат при перемещении транспортного средства в сети Gh в условиях максимального потока. С одной стороны поток необходимо максимизировать, а с другой стороны показатель “выгоды" должен быть минимальным.

Наличие внутренних транспортных потоков в Gh обусловливает вероятностный характер пропускных способностей на многих ветвях графа Gh. Недетерминированное время формирования и расформирования составов влияет случайным образом на время передвижения транзитных составов из пункта отправления в пункт назначения по пути, содержащим этот узел. Указанные особенности не позволяют использовать для поиска максимального потока в сети алгоритм Форда-Фалкерсона. Поэтому актуально использование имитационной модели, основанной на сочетании процедуры Монте-Карло и теоремы Форда-Фалкерсона. Таким образом, ставятся задачи определения с помощью имитационной модели максимального потока в заданном направлении между множеством узлов входов в сеть и множеством узлов выходов, а так же поиска узких мест в сети Gh при перемещении транспорта в заданном направлении, устранение которых позволит достичь оптимальной организации потоков в сети. При поиске интегрального максимального потока в сети необходимо выполнение следующих условий: для каждого сочетания входа и выхода имеется максимальный поток, интегральная функция затрат имеет минимальное значение.

1.3 Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети

Алгоритм решения задач нахождения максимального потока в железнодорожной сети основан на теореме Форда-Фалкерсона: в любой транспортной сети максимальный поток равен минимальной пропускной способности. Если поток максимален, то найдется такое сечение, пропускная способность которого равна мощности потока. Доказывается эта теорема применением алгоритма Форд-Фалкерсона. Согласно этому алгоритму, начиная с некоторого начального неполного потока, по итеративному алгоритму можно получить полный поток, если прибавлять к различным значениям потоков пути минимальное из чисел , которые вычислены по этому пути. После такой операции путь уже будет содержать хотя бы одну ненасыщенную дугу. Если таким же образом поступить с другими путями , то, в конце концов, получим полный поток. Поэтому алгоритм определения максимального потока состоит из следующих шагов:

Строим начальный поток ;

проверяем, попал ли узел в множество узлов , которые достижимы по ненасыщенным ребрам из . Если узел не попал, то считают, что построенный поток максимален, и алгоритм расчета останавливается;

если узел попал во множество , то выделяют путь , состоящий из ненасыщенных ребер и ведущий грузы из в ;

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4123
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее