Математические модели систем массового обслуживания
Курсовая работа
по дисциплине «Имитационное моделирование»
группы 44 «ИС»
Красовский В.В.
Архангельск 2009 г.
Содержание.
Введение…………………………………………………………
Глава1.Построение математических моделей систем
массового обслуживания………………………………………………
- Простейший поток и его свойство…………………………………………….6
- Расчет характеристик для системы М/М/2/8…………………………….14
- Потоки Эрланга и их свойства……………………………………………17
- Расчет характеристик для системы М/Е3/1/3………………………………23
Глава 2.Иметационное моделирование систем массового обслуживания…..24
2.1 Методы моделирования случайных величин…………………………………24
2.2 Моделирование
М/Е3/1/3……………………………………………………….
Литература……………………………………………………
Введение.
Одним из видов компьютерного моделирования является имитационное моделирование. В частности, оно может использоваться для оптимизации моделей, путем нахождения лучшего решения проблемы или задачи из нескольких возможных вариантов.
Как подметил Ю. Адлер, сочетание слов имитация и моделирование недопустимо и является тавтологией. Но, рассматривая исторический процесс формирования этого термина, он пришел к выводу, что это словосочетание определяет в моделировании такую область, которая относится к получению экспериментальной информации о сложном объекте, которая не может быть получена иным путем, как экспериментируя с его моделью на ПЭВМ.
Второй определяющей чертой термина является требование повторяемости, ибо один отдельно взятый эксперимент ничего не значит. Имитационный объект имеет вероятностный характер функционирования. Для исследователя представляют интерес выводы, носящие характер статистических показателей, оформленных, например, в виде графиков или таблиц, в которых каждому варианту исследуемых параметров поставлены в соответствие определенные средние значения с набором характеристик их распределения, без получения зависимости в аналитическом виде.
Объектом имитационного моделирования служит какая-либо модель. В широком понимании модель - это образ или прообраз какого-либо объекта или системы объектов, используемый при определённых условиях в качестве их "заместителя" или "представителя". Модель - это образец, служащий эталоном (стандартом), устройство, воспроизводящее, имитирующее что-либо, такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале.
Полная классификация возможных видов моделирования крайне затруднительна, хотя бы в силу многозначности понятия "модель". Остановимся на структурно-функциональных и логико-математических моделях.
Структурно-функциональное моделирование, при котором моделями являются схемы (блок-схемы), графики, чертежи, диаграммы, таблицы, рисунки, дополненные специальными правилами их объединения и преобразования;
математическое (логико-математическое) моделирование, при котором моделирование, включая построение модели, осуществляется средствами математики и логики;
Для имитационного моделирования ст
Имитационное моделирование реализуется посредством набора математических инструментальных средств, специальных компьютерных программ и приемов, позволяющих с помощью компьютера провести целенаправленное моделирование в режиме «имитации» структуры и функции сложного процесса и оптимизации некоторых его параметров. Набор программных средств и приемов моделирования определяет специфику системы моделирования – специального программного обеспечения.
В отличие от других видов и способов математического моделирования с применением ЭВМ имитационное моделирование имеет свою специфику: запуск в компьютере взаимодействующих вычислительных процессов, которые являются по своим временным параметрам – с точностью до масштабов времени и пространства – аналогами исследуемых процессов.
Имитационное моделирование как особая информационная технология состоит из следующих основных этапов.
Структурный анализ процессов. Проводится формализация структуры сложного реального процесса путем разложения его на подпроцессы, выполняющие определенные функции и имеющие взаимные функциональные связи согласно легенде, разработанной рабочей экспертно группой. Выявленные подпроцессы, в свою очередь, могут разделятся на другие функциональные подпроцессы. Структура общего моделируемого процесса может быть представлена в виде графа, имеющего иерархическую многослойную структуру. В результате появляется формализованное изображение имитационной модели в графическом виде.
Структурны анализ особенно эффективен при моделировании экономических процессов, где (о отличие от технических) многие составляющие процессы не имеют физической основы и протекают виртуально, поскольку оперируют с информацией, деньгами и логикой (законами) их обработки.
Формализованное описание модели. Графическое изображение имитационной модели, функции, выполняемые каждым под процессов и особенности проведения моделируемого процесса (временная, пространственная и финансовая динамика) должны быть описаны на специальном языке для последующей трансляции. Для этого существуют различные способы:
- описание в ручную на языке типа GPSS, Pilgrim и даже на Visual Basic. Последний очень прост, на нем можно запрограммировать элементарные модели, но он не подходит для разработки реальных моделей сложных экономических процессов , так как описание модели средствами Pilgrim компактное аналогичной алгоритмической модели на Visual Basic в десятки-сотни раз;
- автоматизированное
описание с помощью
Построение модели (build).Обычно это трансляция редактирование связей (сборка модели), верификация (калибровка) параметров.
Трансляция осуществляется в различных режимах:
- в режиме интерпретации,
характером для систем типа GPS
- в режиме компиляции (характер для системы Pilgrim).
Каждый режим имеет свои особенности.
Режим интерпретации проще в реализации. Специальная универсальная программа - интерпретатор на основании формализованного описания модели запускает все имитирующие подпрограммы. Данный режим не приводит к получению отдельной модулирующей программы, которую можно было бы передать или продать заказчику (продавать пришлось бы и модель, и систему моделирования, что не всегда возможно). Режим компиляции сложнее реализуется при создании моделирующей системы. Однако это не усложняет процесс разработки модели. В результате можно получить отдельную модулирующую программу, которая работает независимо от системы моделирования в виде отдельного программного продукта.
Верификация (калибровка) параметров модели выполняется в соответствии с легендой, на основании которой построена модель, с помощью специально выбранных тестовых примеров.
Проведение экстремального эксперимента для оптимизации определенных параметров реального процесса. Концепция имитационного моделирования требует предварительного знакомства читателя с методом Монте – Карло, с методологией проведения проверок статистических гипотез, с устройством программных датчиков случайных (псевдослучайных) величин и с особенностями знаков распределения случайных величин при моделировании экономических процессов, которые не рассматриваются в типовых программах дисциплины «Теория вероятностей»
Кроме того, необходимо рассмотреть специальные стохастические сетевые модели, которые дают представление о временных диаграммах специальных имитационных процессов при выполнении программной модели.
Глава 1 Построение математических моделей систем массового обслуживания.
1.1 Простейший поток и его свойства.
Простейший поток событий называется случайный поток, обладающий 3-м средствами:
- Стационарность – означает, что вероятностные характеристики потока не зависят от времени или вероятности наступления к-событий, в потоке зависят только от данных интервала наблюдения и не зависят на поток участия временной оси этот интервал.
- Одинарность – означает, что в потоке одновременно события наступить не могут.
- Независимость – означает, что поток заявок в настоящем, не оказывает ни какого влияния на будущий поток заявок.
Вероятность наступления к-событий в простейшем потоке можно определить по формуле Пуассона:
λ – интенсивность потока.
Вероятность наступления 0 – событий в потоке равна
Длительность интервалов между наступлением событий в простейшем потоке подчиняется знаку с функцией
Распределения и плотность распределения
При рассмотрении процессов, протекающих в системе с дискретными состояниями и непрерывным временем, часто целесообразно представлять процесс так, как будто изменения состояний системы происходят под действием каких-то потоков событий (поток вызовов, поток неисправностей, поток заявок на обслуживание, поток посетителей и т. д.) Поэтому имеет смысл рассмотреть подробнее потоки событий и их свойства,
Поток событий можно изобразить последовательностью точек на оси времени 0—7, каждая из которых имеет определенную координату.
Иллюстрация к определению потока событий (а), простейший поток (б)
Поток событий называется регулярным, если события следуют одно за другим через строго определенные промежутки времени. Такой поток сравнительно редко встречается на практике, но представляет определенный интерес как предельный случай. Чаще приходится встречаться с потоками событий, для которых и моменты наступления событий, и промежутки времени между ними случайны.
Рассмотрим потоки событий, обладающие некоторыми простыми свойствами
1. Стационарность. Поток называется стационарным, если вероятность попадания того или иного числа событий на элементарный участок времени длиной т зависит только от длины участка и не зависит от того, где именно на оси t расположен этот участок.
Стационарность потока означает его однородность по времени; вероятностные характеристики такого потока не меняются в зависимости от времени. В частности, так называемая интенсивность (или «плотность») потока событий — среднее число событий в единицу времени — для стационарного потока должна оставаться постоянной. Это, разумеется, не значит, что фактическое число событий, появляющихся в единицу времени, постоянно, поток может иметь местные сгущения и разрежения. Важно, что для стационарного потока эти сгущения и разрежения не носят закономерного характера, а среднее число событий, попадающих на единичный участок времени, остается постоянным для всего рассматриваемого периода.
На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут рассматриваться как стационарные. Например, поток вызовов, поступающих на телефонную станцию, скажем, на интервале от 12 до 13 часов может считаться стационарным. Тот же поток в течение целых суток уже не будет стационарным (ночью интенсивность потока вызовов гораздо меньше, чем днем). Заметим, что так же обстоит дело и с большинством физических процессов, которые мы называем «стационарными» — в действительности они стационарны только на ограниченном участке времени, а распространение этого участка до бесконечности — лишь удобный прием, применяемый в целях упрощения.
2. Отсутствие последействия. Поток событий называется потоком без последействия, если для любых непересекающихся участков времени число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой (или другие, если рассматривается больше двух участков).
В таких потоках события, образующие поток, появляются в последовательные моменты времени независимо друг от друга. Например, поток пассажиров, входящих на станцию метро, можно считать потоком без последействия, потому что причины, обусловившие приход отдельного пассажира именно в данный момент, а не в другой, как правило, не связаны с аналогичными причинами для других пассажиров. Если такая зависимость появляется, условие отсутствия последействия оказывается нарушенным.
Рассмотрим, например, поток грузовых поездов, идущих по железнодорожной ветке. Если по условиям безопасности они не могут следовать один за другим чаще, чем через интервал времени , то между событиями в потоке имеется зависимость, и условие отсутствия последействия нарушается. Однако, если интервал мал по сравнению со средним интервалом между поездами, то такое нарушение несущественно.
3. Ординарность. Поток событий называется ординарным, если вероятность попадания на элементарный участок двух или более событий пренебрежимо мала по сравнению с вероятностью попадания одного события.
Ординарность означает, что события в потоке приходят поодиночке, а не парами, тройками и т. д. Например, поток клиентов, направляющихся в парикмахерскую, практически можно считать ординарным, чего нельзя сказать о потоке клиентов, направляющихся в ЗАГС для регистрации брака, и т. д.
Если в неординарном потоке события происходят только парами, только тройками и т. д., то можно его рассматривать как ординарный «поток пар», «поток троек» и т. д. Несколько сложнее обстоит дело, если число событий, образующих «пакет» (группу одновременно приходящих событий), случайно. Тогда приходится наряду с потоком пакетов рассматривать случайную величину X — число событий в пакете, и математическая модель потока становится более сложной.
Простейший поток
Рассмотрим поток событий, обладающий всеми тремя свойствами: стационарный, без последействия, ординарный. Такой поток называется простейшим (или стационарным пуассоновским) потоком. Название «простейший» связано с тем, что математическое описание событий, связанных с простейшими потоками, оказывается наиболее простым. Отметим, между прочим, что «самый простой», на первый взгляд, регулярный поток со строго постоянными интервалами между событиями отнюдь не является «простейшим» в вышеназванном смысле слова: он обладает ярко выраженным последействием, так как моменты появления событий связаны между собой жесткой функциональной зависимостью. Именно из-за этого последействия анализ процессов, связанных с регулярными потоками, оказывается, как правило, труднее, а не легче по сравнению с простейшими.
Простейший поток играет среди других потоков особую роль — можно доказать, что при суперпозиции (взаимном наложении) достаточно большого числа потоков, обладающих последействием (лишь бы они были стационарны и ординарны), образуется суммарный поток, который можно считать простейшим, и тем точнее, чем большее число потоков суммируется. Дополнительно требуется, чтобы складываемые потоки были сравнимы по интенсивности, т. е., чтобы среди них не было, скажем, одного, превосходящего по интенсивности сумму всех остальных.
Если поток событий не имеет последействия, ординарен, но не стационарен, он называется нестационарным пуассо-новским потоком. В таком потоке интенсивность (среднее число событий в единицу времени) зависит от времени:
тогда как для простейшего потока
Пуассоновский поток событий (как стационарный, так и нестационарный) тесно связан с известным распределением Пуассона — число событий потока, попадающих на любой участок, распределено по закону Пуассона.
Поясним, что это означает. Рассмотрим на оси t, где наблюдается поток событий, некоторый участок времени длины , начинающийся в момент и заканчивающийся в момент Нетрудно доказать (доказательство дается во всех
курсах теории вероятностей), что вероятность попадания на этот участок ровно т событий и выражается формулой:
где а — среднее число событий, приходящееся на участок ; е — основание натуральных логарифмов.
Для стационарного (простейшего) пуассоновского потока величина а равна интенсивности потока, умноженной на длину интервала:
т. е. не зависит от того, где на оси t находится период Для нестационарного пуассоновского потока величина а зависит от того, в какой точке начинается участок t.
Рассмотрим на оси t простейший поток событий с интенсивностью . Нас будет интересовать случайный интервал времени Т между соседними событиями в этом потоке; найдем его закон распределения. Сначала найдем функцию распределения:
т. е. вероятность того, что величина Т будет иметь значение, меньшее, чем t. Отложим от начала интервала Т (точки ) отрезок t и найдем вероятность того, что интервал Т будет меньше t. Для этого нужно, чтобы на участок длины t, примыкающий к точке попало хотя бы одно событие потока. Вычислим вероятность этого F(t) через вероятность противоположного события (на участок t не попадет ни одного события потока):
Вероятность найдем по формуле, полагая m = 0:
откуда функция распределения величины Т будет:
Чтобы найти плотность распределения случайной величины Т, необходимо продифференцировать выражение по t:
Закон распределения с плотностью называется показательным (или экспоненциальным). Величина называется параметром показательного закона.
Показательный закон распределения играет большую роль в теории марковских случайных процессов.
Найдем числовые характеристики случайной величины Т — математическое ожидание (среднее значение) и дисперсию .
Имеем (интегрируя по частям):
Дисперсия величины T составляет:
Извлекая корень квадратный из дисперсии, найдем среднее квадратическое отклонение случайной величины Т.
Итак, для показательного распределения математическое ожидание и среднее квадратическое отклонение равны друг другу и обратны параметру , где — интенсивность потока.
Приведем выражение для так называемого «элемента вероятности появления события» или вероятности наступления на элементарном участке (рис 5.3, а) события потока.
Найдем вероятность того, что на участке появится какое-то событие потока, т. е. участок не будет «пуст». Так как поток ординарен, вероятностью появления на участке более чем одного события можно пренебречь. Обозначим вероятность того, что на участке не будет события, а — вероятность того, что на нем появится одно событие.
В силу ординарности потока
а вероятность определяется по:
откуда
Разлагая в ряд и пренебрегая величинами высшего порядка малости, получаем:
Эта вероятность и называется «элементом вероятности появления события».
Очевидно, такая же формула
будет справедлива и для
Потоки Пальма и Эрланга
Рассмотрим вкратце некоторые смежные понятия . Поток событий называется потоком Пальма (или потоком с ограниченным последействием), если промежутки времени между последовательными событиями:
представляют собой независимые, одинаково распределенные случайные величины.
Простейший поток есть частный случай потока Пальма: в нем расстояния представляют собой случайные величины, распределенные по одному и тому же показательному закону; их независимость следует из того, что простейший поток есть поток без последействия, и расстояние по времени между любыми двумя событиями не зависит от того, каковы расстояния между другими.
Многие потоки событий, встречающиеся на практике, хотя и не являются в точности потоками Пальма, но могут быть ими приближенно заменены.
Важными для практики образцами потоков Пальма являются так называемые потоки Эрланга. Эти потоки образуются в результате «просеивания» простейших потоков.
Например, если из точек на оси t сохранить не все точки, а только каждую вторую, то в результате такой операции «просеивания» образуется снова поток событий; он называется потоком Эрланга второго порядка.
Вообще, потоком Эрланга к-то порядка называется поток, получающийся, если в простейшем потоке сохранить каждую k-го точку, а остальные выбросить. Очевидно, простейший поток представляет собой частный случай потока Эрланга, а именно поток Эрланга 1-го порядка
Интервал времени Т между соседними событиями в потоке Эрланга k-го порядка представляет собой сумму к независимых случайных величин - расстояний между событиями в исходном простейшем потоке:
Каждая из этих случайных величин распределена по показательному закону
Закон распределения интервала T между соседними событиями в потоке называется законом Эрланга k-го порядка.
Нетрудно получить следующие выражения для матожидания, дисперсии и среднего квадратичного отклонения для интервала событий в потоке Эрланга k-го порядка:
1.2 Расчет характеристик для системы М/М/2/8.
М/М/2/8 λ = 2; μ = 2;
Выделим состояние, в которых может находиться система, причем состояние выделяем по числу заявок.
S0 – в системе нет ни одной заявки
S1 – в системе одна заявка и она обслуживается
Sm+n – в системе m+n заявок из которых m – обслуживается и n – находится в очереди
Нарисуем граф поведение системы.
Таким образом, мы получили граф определяющий процесс «рождения» которого можно записать решение уравнений.
Pi=
Вероятность состояния S0 найдем, из условия сумма всех вероятностей равна 1.
Вычислим среднее число заявок находящихся в очереди. Известно, что с вероятностью Pm – в очереди находятся 0 – заявок с вероятностью Pm+1 – в очереди одна заявка, с вероятностью Pm+n – в очереди n – заявок.
Следовательно, число заявок находящихся в очереди – это дискретная случайная величина, среднее значение которой находится по формуле:
Среднее время пребывания заявки очереди определим по Теореме Литтла.
Среднее время нахождение заявки во всей системе складывается из среднего времени пребывания заявки в очереди и среднего времени обслуживания.
Нам известно, что время обслуживания представляет собой случайную величину, имеющую экспециальное распределение с плотностью.
Среднее значение этой случайной величины определим по формуле математического ожидания не прерывной случайной величины.
Средние числа заявок находящихся в системе определяем Теореме Литтла
1.3 Потоки Эрланга и их свойства.
Потоки Эрланга катового порядка получаются из простейшего потока прореживанием событии в нем, когда в простейшем потоке остается каждое какое-то событие.
Например:
Пусть событие в простейшем потоке наступают в моменты t1, t2, t3,…tn;
Если в простейшем потоке оставить каждое второе событие, то случайная величина Т будет иметь распределение Эрланга второго порядка.

- Математические модели систем управления и методы оптимизации
- Математические модели технических объектов
- Математические основы криптографии
- Математические основы решение задачи коммивояжера
- Математические основы цифровой обработки сигналов
- Математические подходы в разработке управленческих решений
- Математический анализ
- Математические модели и методы их расчета
- Математические модели и методы кредитных расчетов с позиции заёмщика
- Математические модели кривой намагничивания и петель магнитного гистерезиса
- Математические модели оптимизации технологических процессов раскроя материалов в машиностроении
- Математические модели поведения производителей
- Математические модели принятия решений в экономике
- Математические модели реальных объектов в курсе механики