Амкнутая система с неоднородными каналами: моделирование грузовых автоперевозок

Нижегородский Государственный Архитектурно-Строительный Университет

Международный факультет экономики, права и менеджмента

Кафедра прикладной информатики и статистики

Курсовая работа по дисциплине:

«Математическое и имитационное моделирование»

На тему: «Замкнутая система с неоднородными каналами: моделирование грузовых автоперевозок»

Выполнил: студент 3-го курса

Группы: Пиэ11.11

Черезов Вадим Викторович 

Оглавление

Введение3

1. Имитационное моделирование5
1. Нормальное распределение7
2. Экспоненциальное распределение7
3. Распределение Эрланга8
2. Описание системы9
1. Модельное время10
2. Классы и объекты10
1. Класс HeavyCar12
2. Класс Fuller13
3. Класс Emptier13
3. События и методы14
4. Листинг программы15
5. Результат35
6. Анализ результатов35

Список используемой литературы35

Введение

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

Заявки поступают в СМО обычно не регулярно, а случайно, образуя так называемый случайный поток заявок (требований). Обслуживание заявок также продолжается какое-то случайное время. Случайный характер потока заявок и времени обслуживания приводит к тому, что СМО оказывается загруженной неравномерно: в какие-то периоды времени скапливается очень большое количество заявок (они либо становятся в очередь, либо покидают СМО не обслуженными), в другие же периоды СМО работает с недогрузкой или простаивает.

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

– Абсолютная пропускная способность системы, т.е. среднее число заявок, обслуживаемых в единицу времени;

– относительная пропускная способность, т.е. средняя доля поступивших заявок, обслуживаемых системой;

– вероятность отказа обслуживания заявки;

– среднее число занятых каналов;

– среднее число заявок в СМО;

– среднее время пребывания заявки в системе;

– среднее число заявок в очереди;

– среднее время пребывания заявки в очереди;

– среднее число заявок, обслуживаемых в единицу времени;

– среднее время ожидания обслуживания;

– вероятность того, что число заявок в очереди превысит определенное значение и т.п.

СМО делят на 2 основных типа: СМО с отказами и СМО с ожиданием (очередью). В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем процессе обслуживания не участвует (например, заявка на телефонный разговор в момент, когда все каналы заняты, получает отказ и покидает СМО не обслуженной). В СМО с ожиданием заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь на обслуживание.

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

Имитационное моделирование широко используется на различных этапах жизненного цикла сложной системы: при проектировании - для осуществления параметрического и структурного синтеза, проведения многовариантного анализа; при вводе в действие - для поиска «узких» мест; при эксплуатации - для прогнозирования эффекта от возможных модернизаций состава и структуры сложной системы (СС).

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

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

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

1. Имитационное моделирование

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

В русскоязычной литературе термин «моделирование» соответствует американскому «modeling» и имеет смысл создание модели и ее анализ, причем под термином «модель» понимается объект любой природы, упрощенно представляющий исследуемую систему. Слова «имитационное моделирование» и «вычислительный (компьютерный) эксперимент» соответствуют англоязычному термину «simulation». Эти термины подразумевают разработку модели именно как компьютерной программы и исполнение этой программы на компьютере.

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

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

Во многих случаях имитационное моделирование – это единственный способ получить представление о поведении сложной системы и провести ее анализ.

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

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

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

1. Структурный анализ процессов. Проводится формализация структуры сложного реального процесса путем разложения его на подпроцессы, выполняющие определенные функции и имеющие взаимные функциональные связи согласно легенде, разработанной рабочей экспертной группой. Выявленные подпроцессы, в свою очередь, могут разделяться на другие функциональные подпроцессы. Структура общего моделируемого процесса может быть представлена в виде графа, имеющего иерархическую многослойную структуру, в результате появляется формализованное изображение имитационной модели в графическом виде. Структурный анализ особенно эффективен при моделировании экономических процессов, где (в отличие от технических) многие составляющие подпроцессы не имеют физической основы и протекают виртуально, поскольку оперируют с информацией, деньгами и логикой (законами) их обработки.
2. Формализованное описание модели. Графическое изображение имитационной модели, функции, выполняемые каждым подпроцессов, условия взаимодействия всех подпроцессов и особенности поведения моделируемого процесса (временная, пространственная и финансовая динамика) должны быть описаны на специальном языке для последующей трансляций.
3. Построение модели (build). Обычно это трансляция и редактирование связей (сборка модели), верификация (калибровка) параметров.
4. Проведение экстремального эксперимента для оптимизации определенных параметров реального процесса.

1. Нормальное распределение

Нормальное распределение, также называемое распределением Гаусса - распределение вероятностей, которое в одномерном случае задается функцией плотности вероятности, совпадающей с функцией Гаусса:

где параметр μ — математическое ожидание, медиана и мода распределения, а параметр σ —стандартное отклонение (σ² — дисперсия) распределения.

Стандартным нормальным распределением называется нормальное распределение с математическим ожиданием μ = 0 и стандартным отклонением σ = 1.

2. Экспоненциальное распределение

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

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

Мы говорим, что случайная величина имеет экспоненциальное (показательное) распределение, если       

 (0)

Пусть   –  время ожидания события, тогда из формулы (0) следует, что вероятность того, что это событие наступит раньше x равна   . Этот удобный формализм позволяет описывать моменты возникновения случайных событий.

Параметр λ оценивается на основе реальных данных.

Плотность экспоненциального распределения имеет вид

,     (1)

где λ>0 —положительная постоянная, называемая параметром экспоненциального распределения.

Экспоненциальное распределение сосредоточено на положительной полуоси.

Экспоненциальная случайная величина принимает положительные значения.

Среднее значение   равно 

Дисперсия   равна 

Из формулы (0) следует:

Иными словами, вероятность того, что следующее событие наступит через время больше  , равна  .

3. Распределение Эрланга

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

Тогда сумма этих случайных величин имеет распределение Эрланга.

Плотность распределения Эрланга имеет вид:

Среднее и дисперсия равны соответственно   и 

Распределение Эрланга названо в честь А. Эрланга (A. Erlang), впервые применившего его в задачах теории массового обслуживания и телефонии.

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

2. Описание системы

Моделируемая система состоит из одного бульдозера, четырех самосвалов и двух механизированных погрузчиков. Бульдозер сгребает землю к погрузчикам. Для начала погрузки перед погрузчиками должны лежать две кучи земли. Один самосвал полностью загружается одной кучей. Каждая из куч относится только к одному, «своему» погрузчику, одна – для одного, другая – для другого, то есть перед каждым погрузчиком должно лежать по куче, с которой будет работать (загружать самосвал) только этот погрузчик. Время, затрачиваемое бульдозерами на подготовку фронта работ до начала погрузки, имеет распределение Эрланга и состоит из суммы двух экспоненциальных величин, каждая из которых имеет математическое ожидание равное 4 мин (это соответствует эрланговскому распределению с математическим ожиданием 8 мин и дисперсией 32). Кроме наличия земли для начала погрузки требуется погрузчик и порожний самосвал. Время погрузки распределено экспоненциально с математическим ожиданием 14 мин для первого погрузчика и 12 мин для второго.

Рис.1. Система грузовых автоперевозок (концептуальная модель системы)

После того как самосвал загружен, он уезжает к месту разгрузки, разгружается и вновь возвращается на погрузку. В пункте разгрузки находится только одно разгрузочное место, где самосвал может разгрузиться, то есть два и более самосвалов одновременно разгружаться не могут. Для краткости будем называть такое разгрузочное место разгрузчиком (название условное, так как самосвал разгружается сам). Время нахождения самосвала в пути распределено нормально, причем в загруженном состоянии он тратит на дорогу в среднем 22 мин, а в порожнем – 18 мин. Среднеквадратичное отклонение в обоих случаях равно 3 мин. Время разгрузки распределено равномерно на интервале от 2 до 8 мин. После погрузки каждого самосвала погрузчик должен «отдыхать» в течении 5 мин, а затем вновь может приступать к погрузке.

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

1. Модельное время

За единицу модельного времени принимаем секунду. Случайные величины, распределенные равномерно, генерируем сразу в секундах. Случайные величины, распределенные по закону Эрланга, экспоненциально и нормально, генерируем в минутах, чтобы избежать потери точности при численном решении уравнений и интегрировании, затем результат умножаем на 60 и округляем до ближайшего целого числа. Дальнейшее масштабирование времени в этой задаче использовать не будем.

2. Классы и объекты

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

Введем два класса – Пункт погрузки (Fuller) и Пункт разгрузки (Emptier). Хотя в условии задачи количество погрузчиков и разгрузчиков фиксировано (соответственно, 2 и 1), сделаем эти значения полями данных классов, чтобы повысить общность моделирующей программы и облегчить эксперименты с ней в дальнейшем. В связи с обобщением задачи на случай произвольного числа k погрузчиков необходимо добавить пояснение. Погрузка начинается только тогда, когда бульдозер нагреб k куч  - по одной перед каждым погрузчиком. Соответственно, время работы бульдозера при наличии k погрузчиков имеет распределение Эрланга порядка k.

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

Теперь разберемся, нужно ли выделять в отдельный класс самосвалы. В первую очередь отметим, что в условии задачи не сказано, какую именно статистику о работе системы нужно собрать. Это оставлено на усмотрение исследователя. Главным показателем, несомненно, является производительность, выражаемая в количестве земли, перевезенной в пункт разгрузки. Единицей ее измерения примем 1 самосвал. Каждый из самосвалов в пунктах погрузки и разгрузки выступает в качестве заявки на обслуживание. Так как система замкнутая, время пребывания заявки (самосвала) отслеживать не нужно, но, тем не менее, отдельный класс для самосвалов ввести следует. Дело в том, что не на всем протяжении производственного цикла самосвал находится «под патронажем» других объектов – во время курсирования между пунктами погрузки и разгрузки он выступает как самостоятельная обособленная единица, для которой  нужно отслеживать время, оставшееся до прибытия в один из пунктов. И то и другое время задано собственными законами распределения. Таким образом, вводим класс Самосвал (HeavyCar), представленный в системе четырьмя объектами.

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

• Состояние 1 – в очереди к погрузчику;
• Состояние 2 – непосредственно на погрузке;
• Состояние 3 – загруженный самосвал движется к пункту разгрузки;
• Состояние 4 – в очереди к разгрузчику;
• Состояние 5 – непосредственно на разгрузке;
• Состояние 6 – порожний самосвал движется к пункту погрузки.

Выходы самосвала из состояний 1, 2, 4, 5 будут моделироваться пунктами погрузки и разгрузки, из состояний 3 и 6 – самим самосвалом. Заметим, что номер состояния является логическим избыточным полем данных, так как его значение можно вычислить из информации, поставляемой полями данных, как самого самосвала, так и других объектов. Все же включим состояние самосвала в число полей данных для упрощения моделирования системы.

Самосвалу также нужна связь с пунктами погрузки и разгрузки для передачи им сообщений о своем прибытии на них. Это достигается уже опробованным способом – приведением «пустых» указателей.

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

Аналогии этих массивов требуются и в качестве полей данных класса Emptier, за исключением времени, оставшегося до окончания «отдыха» (так как отдыхать некому – самосвал разгружается сам), и признаков готовности кучи земли (для разгрузки это не требуется).

Приведем полные списки полей данных классов.

1. Класс HeavyCar

Неизменяемые поля:

• Среднее время пути груженого самосвала (22);
• Среднеквадратичное отклонение в пути груженого самосвала (3);
• Среднее время в пути порожнего самосвала (18);
• Среднеквадратичное отклонение времени в пути порожнего самосвала (3);
• Порядковый номер (уникальный идентификатор);
• Указатель на Пункт погрузки;
• Указатель на Пункт разгрузки;

Изменяемые поля:

• Состояние самосвала (от 1 до 6);
• Время, оставшееся до прибытия на разгрузку;
• Время, оставшееся до прибытия на погрузку.

2. Класс Fuller

Неизменяемые поля:

• Количество погрузчиков (2);
• Производительность бульдозера (по условию – 0,25 кучи в минуту);
• Продолжительность отдыха после погрузки (300);
• Массив производительностей погрузчиков (0,0714; 0,0833).

Изменяемые поля:

• Время до окончания подготовки бульдозером фронта работ – двух куч;
• Массив значений времени, оставшегося до окончания погрузки каждым погрузчиком;
• Массив указателей на объекты класса HeavyCar, обслуживаемые в данный момент погрузчиками;
• Массив указателей на объекты класса HeavyCar, находящиеся в очереди на погрузку;
• Массив значений времени, оставшегося до окончания «отдыха» погрузчиков;
• Массив признаков того, готова ли для погрузчика куча земли.

3. Класс Emptier

Неизменяемые поля:

• Количество разгрузчиков (1);
• Минимальное время разгрузки (120);
• Максимальное время разгрузки (480).

Изменяемые поля:

• Массив значений времени, оставшегося до окончания разгрузки каждым разгрузчиком;
• Массив указателей на объекты класса HeavyCar, обслуживаемые в данный момент разгрузчиками;
• Массив указателей на объекты класса HeavyCar, находящиеся в очереди на разгрузку.

Количество самосвалов зададим как глобальную переменную, описанную в заголовочном файле.

3. События и методы

Класс HeavyCar не имеет моделирующих методов, за исключением метода run(), так как все события, происходящие с самосвалом, моделируются методами других классов. С пунктом погрузки могут происходить следующие события:

• Окончание работы бульдозера;
• Прибытие в пункт очередного самосвала;
• Окончание загрузки самосвала одним из погрузчиков;
• Окончание «отдыха» одного из погрузчиков.

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

Возможные события для пункта разгрузки – прибытие очередного самосвала и окончание разгрузки самосвала одним из разгрузчиков.

Условие завершения всех начатых работ, чтобы не усложнять программу, учтем только при вычислении основной характеристики – количества разгруженных самосвалов. Это сделано следующим образом. В момент завершения рабочего дня, то есть истечения восьмичасового интервала времени, проверяется состояние каждого самосвала. Если самосвал находится в очереди на погрузку или движется порожняком, он оставляется без внимания. При любом другом состоянии он должен «дойти» до разгрузки, поэтому к числу разгруженных самосвалов прибавляется единица.

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

Реализация классов:

#include<cstdio>

#include<ctime>

#include "erlang.h"       //генераторы распределений Эрланга

//и экспоненциального

#include "normal.h"       //генератор нормального распределения

#include "random.h"

FILE *qu1;                //файл для сбора статистики  о длине очереди

//на погрузку

FILE *qu2;                //файл для сбора статистики  о длине очереди

//на разгрузку

enum states {Que_Fuller=1,Full,Full_Move,Que_Emptier,Empty,Empty_Move};

int S=4;                  //количество самосвалов

int completed=0;          //счетчик разгруженных самосвалов

float que1_ave=0;         //счетчик средней длины очереди  на погрузку

float que2_ave=0;         //счетчик средней длины очереди  на разгрузку

long int total;           //счетчик общего времени моделирования

float ro_fuller=0;        //счетчик средней загрузки пункта  погрузки

long int ro_buld=0L;      //счетчик средней загрузки бульдозера