Курсовая работа
«Имитационноемоделирование системы массового обслуживания»
покурсу «Исследование операций»
Введение
Приисследовании операций часто приходится сталкиваться с системами,предназначенными для многоразового использования при решении однотипных задач.Возникающие при этом процессы получили название процессов обслуживания, асистемы – систем массового обслуживания (СМО). Каждая СМО состоит изопределенного числа обслуживающих единиц (приборов, устройств, пунктов,станций), которые называются каналами обслуживания. Каналами могут быть линиисвязи, рабочие точки, вычислительные машины, продавцы и др. По числу каналовСМО подразделяют на одноканальные и многоканальные.
Заявкипоступают в СМО обычно не регулярно, а случайно, образуя так называемыйслучайный поток заявок (требований). Обслуживание заявок также продолжаетсякакое-то случайное время. Случайный характер потока заявок и времениобслуживания приводит к тому, что СМО оказывается загруженной неравномерно: вкакие-то периоды времени скапливается очень большое количество заявок (они либостановятся в очередь, либо покидают СМО не обслуженными), в другие же периодыСМО работает с недогрузкой или простаивает.
Предметомтеории массового обслуживания является построение математических моделей,связывающих заданные условия работы СМО (число каналов, их производительность,характер потока заявок и т.п.) с показателями эффективности СМО, описывающимиее способность справляться с потоком заявок. В качестве показателейэффективности СМО используются:
– Абсолютнаяпропускная способность системы (А), т.е. среднее число заявок,обслуживаемых в единицу времени;
– относительнаяпропускная способность (Q), т.е. средняя доля поступивших заявок,обслуживаемых системой;
– вероятностьотказа обслуживания заявки (/>);
– среднеечисло занятых каналов (k);
– среднеечисло заявок в СМО (/>);
– среднеевремя пребывания заявки в системе (/>);
– среднеечисло заявок в очереди (/>);
– среднеевремя пребывания заявки в очереди (/>);
– среднеечисло заявок, обслуживаемых в единицу времени;
– среднеевремя ожидания обслуживания;
– вероятностьтого, что число заявок в очереди превысит определенное значение и т.п.
СМО делят на2 основных типа: СМО с отказами и СМО с ожиданием (очередью). В СМО с отказамизаявка, поступившая в момент, когда все каналы заняты, получает отказ, покидаетСМО и в дальнейшем процессе обслуживания не участвует (например, заявка нателефонный разговор в момент, когда все каналы заняты, получает отказ ипокидает СМО не обслуженной). В СМО с ожиданием заявка, пришедшая в момент,когда все каналы заняты, не уходит, а становится в очередь на обслуживание.
Одним изметодов расчета показателей эффективности СМО является метод имитационногомоделирования. Практическое использование компьютерного имитационногомоделирования предполагает построение соответствующей математической модели,учитывающей факторы неопределенности, динамические характеристики и веськомплекс взаимосвязей между элементами изучаемой системы. Имитационноемоделирование работы системы начинается с некоторого конкретного начальногосостояния. Вследствие реализации различных событий случайного характера, модельсистемы переходит в последующие моменты времени в другие свои возможныесостояния. Этот эволюционный процесс продолжается до конечного моментапланового периода, т.е. до конечного момента моделирования.
1. Основные характеристики CМО и показатели их эффективности
1.1 Понятие марковского случайного процесса
Пусть имеетсянекоторая система, которая с течением времени изменяет свое состояние случайнымобразом. В этом случае говорят, что в системе протекает случайный процесс.
Процессназывается процессом с дискретными состояниями, если его состояния /> можно заранее перечислитьи переход системы из одного состояния в другое происходит скачком. Процессназывается процессом с непрерывным временем, если переходы системы из состоянияв состояние происходят мгновенно.
Процессработы СМО – это случайный процесс с дискретными состояниями и непрерывнымвременем.
Случайныйпроцесс называют марковским или случайным процессом без последействия, если длялюбого момента времени /> вероятностныехарактеристики процесса в будущем зависят только от его состояния в данныймомент и не зависят от того, когда и как система пришла в это состояние.
При анализепроцессов работы СМО удобно пользоваться геометрической схемой – графомсостояний. Обычно состояния системы изображаются прямоугольниками, авозможные переходы из состояния в состояние – стрелками. Пример графа состоянийприведен на рис. 1.
/>
Рис. 1.
Поток событий– последовательность однородных событий, следующих одно за другим в случайныемоменты времени.
Потокхарактеризуется интенсивностью λ – частотой появления событий или среднимчислом событий, поступающих в СМО в единицу времени.
Поток событийназывается регулярным, если события следуют одно за другим через определенныеравные промежутки времени.
Поток событийназывается стационарным, если его вероятностные характеристики не зависят отвремени. В частности, интенсивность стационарного потока есть величинапостоянная: />.
Поток событийназывается ординарным, если вероятность попадания на малый участок времени /> двух и более событий малапо сравнению с вероятностью попадания одного события, т.е., если событияпоявляются в нем поодиночке, а не группами.
Поток событийназывается потоком без последействия, если для любых двух непересекающихсяучастков времени /> и /> число событий, попадающихна одно из них, не зависит от числа событий, попадающих на другие.
Поток событийназывается простейшим (или стационарным пуассоновским), если он одновременностационарен, ординарен и не имеет последействия. 1.2 Уравнения Колмогорова
Все переходыв системе из состояния в состояние происходят под некоторым потоком событий.Пусть система /> находится внекотором состоянии />, из котороговозможен переход в состояние />, тогдаможно считать, что на систему воздействует простейший поток с интенсивностью />, переводящий ее из состояния/> в />. Как только появляетсяпервое событие потока, происходит ее переход />.Для наглядности на графе состояний у каждой стрелки, соответствующей переходу,указывается интенсивность />. Такойразмеченный граф состояний позволяет построить математическую модель процесса, т.е.найти вероятности всех состояний /> какфункции времени. Для них составляются дифференциальные уравнения, называемыеуравнениями Колмогорова.
Правилосоставлений уравнений Колмогорова: В левой части каждого из уравнений стоитпроизводная по времени от вероятности данного состояния. В правой части стоитсумма произведений всех состояний, из которых возможен переход в данноесостояние, на интенсивности соответствующих потоков событий минус суммарнаяинтенсивность всех потоков, выводящих систему из данного состояния, умноженнаяна вероятность данного состояния.
Например, дляграфа состояний, приведенного на рис. 1, уравнения Колмогорова имеют вид:
/>
Т.к. в правойчасти системы каждое слагаемое входит 1 раз со знаком /> и 1 раз со знаком />, то, складывая все /> уравнений, получим, что
/>,
/>,
/>. (1.2.1)
Следовательно,одно из уравнений системы можно отбросить и заменить уравнением (1.2.1).
Чтобыполучить конкретное решение надо знать начальные условия, т.е. значениявероятностей в начальный момент времени.
/>
/>/>
/> 1.3 Финальные вероятности и граф состояний СМО
Придостаточно большом времени протекания процессов в системе (при />) могут устанавливатьсявероятности состояний, не зависящие от времени, которые называются финальнымивероятностями, т.е. в системе устанавливается стационарный режим. Если числосостояний системы конечно, и из каждого из них за конечное число шагов м.перейти в любое другое состояние, то финальные вероятности существуют, т.е.
/>
Смыслфинальных вероятностей состоит в том, что они равны среднему относительномувремени нахождения системы в данном состоянии.
Т.к. встационарном состоянии производные по времени равны нулю, то уравнения дляфинальных вероятностей получаются из уравнений Колмогорова путем приравниваниянулю их правых частей.
Графысостояний, используемые в моделях систем массового обслуживания, называютсясхемой гибели и размножения. Такое название обусловлено тем, что эта схемаиспользуется в биологических задачах, связанных с изучением численностипопуляции. Его особенность состоит в том, что все состояния системы можнопредставить в виде цепочки, в которой каждое из состояний связано с предыдущими последующим (рис 2).
/>
Рис. 2. Графсостояний в моделях СМО
Предположим,что все потоки, переводящие систему из одного состояния в другое, простейшие.По графу, представленному на рис. 2, составим уравнения для финальныхвероятностей системы. Они имеют вид:
/>
Получаетсясистема из (n+1) уравнения, которая решается методом исключения.Этот метод заключается в том, что последовательно все вероятности системы выражаютсячерез вероятность />.
/>,
/>,
/>
/>.
Подставляяэти выражения в последнее уравнение системы, находим />, затем находим остальныевероятности состояний СМО.
1.4 Показатели эффективности СМО
Цельмоделирования СМО состоит в том, чтобы рассчитать показатели эффективностисистемы через ее характеристики. В качестве показателей эффективности СМОиспользуются:
– абсолютнаяпропускная способность системы (А), т.е. среднее число заявок,обслуживаемых в единицу времени;
– относительнаяпропускная способность (Q), т.е. средняя доля поступивших заявок,обслуживаемых системой;
– вероятностьотказа (/>), т.е. вероятность того,что заявка покинет СМО не обслуженной;
– среднеечисло занятых каналов (k);
– среднеечисло заявок в СМО (/>);
– среднеевремя пребывания заявки в системе (/>);
– среднеечисло заявок в очереди (/>) –длина очереди;
– среднеечисло заявок в системе (/>);
– среднеевремя пребывания заявки в очереди (/>);
– среднеевремя пребывания заявки в системе (/>)
– степеньзагрузки канала (/>), т.е.вероятность того, что канал занят;
– среднеечисло заявок, обслуживаемых в единицу времени;
– среднеевремя ожидания обслуживания;
– вероятностьтого, что число заявок в очереди превысит определенное значение и т.п.
Доказано, чтопри любом характере потока заявок, при любом распределении времениобслуживания, при любой дисциплине обслуживания, среднее время пребываниязаявки в системе (очереди) равна среднему числу заявок в системе (очереди),деленному на интенсивность потока заявок, т.е.
/> (1.4.1)
/> (1.4.2)
Формулы (1.4.1)и (1.4.2) называются формулами Литтла. Они вытекают из того, что в предельномстационарном режиме среднее число заявок, прибывающих в систему, равно среднемучислу заявок, покидающих ее, т.е. оба потока заявок имеют одну и ту жеинтенсивность />.
Формулы длявычисления показателей эффективности приведены в таб. 1.
Таблица 1.Показатели
Одноканальная СМО с
ограниченной очередью
Многоканальная СМО с
ограниченной очередью
Финальные
вероятности
/>
/>, />
/>
/>
/>
/>/>
Вероятность
отказа
/>
/>
Абсолютная пропускная
способность
/>
/>
Относительная пропускная
способность
/>
/>
Среднее число заявок в
очереди
/>
/>
Среднее число заявок под
обслуживанием
/>
/> Среднее число заявок в системе
/>
/> 1.5 Основные понятия имитационного моделирования
Основная цельимитационного моделирования заключается в воспроизведении поведения изучаемойсистемы на основе анализа наиболее существенных взаимосвязей ее элементов.
Компьютерноеимитационное моделирование следует рассматривать как статический эксперимент.
Из теориифункций случайных величин известно, что для моделирования случайной величины /> с любой непрерывной имонотонно возрастающей функцией распределения /> достаточноуметь моделировать случайную величину />,равномерно распределенную на отрезке />.Получив реализацию /> случайной величины/>, можно найтисоответствующую ей реализацию /> случайнойвеличины />, так как они связаныравенством
/> (1.5.1)
Предположим,что в некоторой системе массового обслуживания время обслуживания одной заявкираспределено по экспоненциальному закону с параметром />, где /> – интенсивность потокаобслуживания. Тогда функция распределения /> времениобслуживания имеет вид
/>
Пусть /> — реализация случайнойвеличины />, равномерно распределеннойна отрезке />, а /> – соответствующая ейреализация случайного времени обслуживания одной заявки. Тогда, согласно (1.5.1) />
1.6 Построение имитационных моделей
Первый этапсоздания любой имитационной модели – этап описания реально существующей системыв терминах характеристик основных событий. Эти события, как правило, связаны спереходами изучаемой системы из одного возможного состояния в другое иобозначаются как точки на временной оси. Для достижения основной целимоделирования достаточно наблюдать систему в моменты реализации основныхсобытий.
Рассмотримпример одноканальной системы массового обслуживания. Целью имитационногомоделирования подобной системы является определение оценок ее основныххарактеристик, таких, как среднее время пребывания заявки в очереди, средняядлина очереди и доля времени простоя системы.
Характеристикисамого процесса массового обслуживания могут изменять свои значения либо вмомент поступления новой заявки на обслуживание, либо при завершенииобслуживания очередной заявки. К обслуживанию очередной заявки СМО можетприступить немедленно (канал обслуживания свободен), но не исключенанеобходимость ожидания, когда заявке придется занять место в очереди (СМО сочередью, канал обслуживания занят). После завершения обслуживания очереднойзаявки СМО может сразу приступить к обслуживанию следующей заявки, если онаесть, но может и простаивать, если таковая отсутствует. Необходимую информациюможно получить, наблюдая различные ситуации, возникающие при реализацияхосновных событий. Так, при поступлении заявки в СМО с очередью при занятомканале обслуживания длина очереди увеличивается на 1. Аналогично длина очередиуменьшается на 1, если завершено обслуживание очередной заявки и множество заявокв очереди не пусто.
Дляэксплуатации любой имитационной модели необходимо выбрать единицу времени. Взависимости от природы моделируемой системы такой единицей может бытьмикросекунда, час, год и т.д.
Так как посвоей сути компьютерное имитационное моделирование представляет собойвычислительный эксперимент, то его наблюдаемые результаты в совокупности должныобладать свойствами реализации случайной выборки. Лишь в этом случае будетобеспечена корректная статистическая интерпретация моделируемой системы.
Прикомпьютерном имитационном моделировании основной интерес представляютнаблюдения, полученные после достижения изучаемой системой стационарного режимафункционирования, так как в этом случае резко уменьшается выборочная дисперсия.
Время,необходимое для достижения системой стационарного режима функционирования,определяется значениями ее параметров и начальным состоянием.
Посколькуосновной целью является получение данных наблюдений с возможно меньшей ошибкой,то для достижения этой цели можно:
1) увеличитьдлительность времени имитационного моделирования процесса функционированияизучаемой системы. В этом случае не только увеличивается вероятность достижениясистемой стационарного режима функционирования, но и возрастает число /> используемыхпсевдослучайных чисел, что также положительно влияет на качество получаемыхрезультатов.
2) прификсированной длительности времени Т имитационного моделированияпровести N вычислительных экспериментов, называемых еще прогонами модели, сразличными наборами псевдослучайных чисел, каждый из которых дает однонаблюдение. Все прогоны начинаются при одном и том же начальном состояниимоделируемой системы, но с использованием различных наборов псевдослучайныхчисел. Преимуществом этого метода является независимость получаемых наблюдений />, показателей эффективностисистемы. Если число N модели достаточно велико, то границысимметричного доверительного интервала для параметра /> определяются следующим образом:
/>, />, т.е. />, где
/>математическое ожидание(среднее значение), находится по формуле
/>,
/> исправленная дисперсия, />,
N– число прогоновпрограммы, /> – надежность, />.
2. Аналитическое моделирование СМО2.1 Граф состояний системы и уравнения Колмогорова
Рассмотримдвухканальную систему массового обслуживания (n = 2) с ограниченнойочередью равной шести (m = 4). В СМО поступает простейший поток заявок со среднейинтенсивностью λ = 4,8 и показательным законом распределения времени междупоступлением заявок. Поток обслуживаемых в системе заявок является простейшимсо средней интенсивностью μ = 2 и показательным законом распределениявременем обслуживания.
Даннаясистема имеет 7 состояний, обозначим их:
S0– система свободная, нетзаявок;
S1 – 1 заявка наобслуживании, очередь пуста;
S2 – 2 заявки наобслуживании, очередь пуста;
S3 – 2 заявки наобслуживании, 1 заявка в очереди;
S4 – 2 заявки наобслуживании, 2 заявки в очереди;
S5 – 2 заявки наобслуживании, 3 заявки в очереди;
S6 – 2 заявки наобслуживании, 4 заявки в очереди;
Вероятностиприхода системы в состояния S0, S1, S2, …, S6 соответственно равны Р0, Р1,Р2, …, Р6.
Графсостояний системы массового обслуживания представляет собой схему гибели иразмножения. Все состояния системы можно представить в виде цепочки, в которойкаждое из состояний связано с предыдущим и последующим.
/>
Рис. 3. Графсостояний двухканальной СМО
Дляпостроенного графа запишем уравнения Колмогорова:
/>
Чтобы решитьданную систему зададим начальные условия:
/>
Системууравнений Колмогорова (систему дифференциальных уравнений) решим численнымметодом Эйлера с помощью программного пакета Maple 11 (см. Приложение 1).
МетодЭйлера
/>
где/> — в нашем случае, этоправые части уравнений Колмогорова, n=6.
/>
/>
/>
/> (1)
Выберем шагпо времени />. Предположим />, где Т – это время,за которое система выходит на стационарный режим. Отсюда получаем число шагов />. Последовательно Nраз вычисляя /> по формуле (1) получимзависимости вероятностей состояний системы от времени, приведенной на рис. 4.
Значениявероятностей СМО при /> равны:
/>
/>
/>
/>
/>
/>
/>
/>
Рис. 4.Зависимости вероятностей состояний системы от времени
P0
P5
P4
P3
P2
P1 2.2Финальные вероятности системы
Придостаточно большом времени протекания процессов в системе (/>) могут устанавливатьсявероятности состояний, не зависящие от времени, которые называются финальнымивероятностями, т.е. в системе устанавливается стационарный режим. Если числосостояний системы конечно, и из каждого из них за конечное число шагов можноперейти в любое другое состояние, то финальные вероятности существуют, т.е. />
Т.к. встационарном состоянии производные по времени равны 0, то уравнения дляфинальных вероятностей получаются из уравнений Колмогорова путем приравниванияправых частей 0. Запишем уравнения для финальных вероятностей для нашей СМО.
/>
Решим даннуюсистему линейных уравнений с помощью программного пакета Maple 11 (см. Приложение 1).
Получимфинальные вероятности системы:
/>
/>
/>
/>
/>
/>
/>
Сравнениевероятностей, полученных из системы уравнений Колмогорова при />, с финальнымивероятностями показывает, что ошибки /> равны:
/>
/>
/>
/>
/>
/>
/>
Т.е.достаточно малы. Это подтверждает правильность полученных результатов.2.3 Расчет показатели эффективности системыпо финальным вероятностям
Найдемпоказатели эффективности системы массового обслуживания.
Сначала вычислим приведеннуюинтенсивность потока заявок:
/>
1) Вероятность отказа в обслуживании заявки, т.е. вероятность того, что заявкапокидает систему не обслуженной. В нашем случае заявке отказывается вобслуживании, если все 2 канала заняты, и очередь максимально заполнена (т.е. 4человек в очереди), это соответствует состоянию системы S6. Т.к. вероятность прихода системы в состояние S6 равна Р6, то
/>
2) Относительная пропускнаяспособность – это средняя доля поступивших заявок, обслуживаемых системой.
/>
3) Абсолютная пропускная способность – это среднее число заявок, обслуживаемыхв единицу времени.
/>
4) Средняя длина очереди, т.е.среднее число заявок в очереди, равна сумме произведений числа заявок в очередина вероятность соответствующего состояния. />
5) Среднее время пребывания заявки вочереди определяется формулой Литтла:
/>
6) Среднее число занятых каналов определяется следующим образом:
/>/>
3. Имитационноемоделирование СМО3.1 Алгоритм метода имитационного моделирования СМО(пошаговый подход)
Рассмотримдвухканальную систему массового обслуживания (n = 2) с максимальнойдлиной очереди равной шести (m = 4). В СМО поступает простейший поток заявок со среднейинтенсивностью λ = 4,8 и показательным законом распределения времени междупоступлением заявок. Поток обслуживаемых в системе заявок является простейшимсо средней интенсивностью μ = 2 и показательным законом распределениявременем обслуживания.
Для имитацииСМО воспользуемся одним из методов статистического моделирования – имитационныммоделированием. Будем использовать пошаговый подход. Суть этого подхода в том,что состояния системы рассматриваются в последующие моменты времени, шаг междукоторыми является достаточно малым, чтобы за его время произошло не болееодного события.
Выберем шагпо времени (/>). Он должен быть многоменьше среднего времени поступления заявки (/>)и среднего времени ее обслуживания (/>), т.е.
/>, где (3.1.1)
/>
/>
Исходя изусловия (3.1.1) определим шаг по времени />.
Времяпоступления заявки в СМО и время ее обслуживания являются случайнымивеличинами. Поэтому, при имитационном моделировании СМО их вычислениепроизводится с помощью случайных чисел.
Рассмотрим поступлениезаявки в СМО. Вероятность того, что на интервале /> вСМО поступит заявка, равна: />.Сгенерируем случайное число />, и,если />, то будем считать, чтозаявка на данном шаге в систему поступила, если />,то не поступила.
В программеэто осуществляет isRequested(). Интервал времени /> примемпостоянным и равным 0,0001, тогда отношение /> будетравно 10000. Если заявка поступила, то она принимает значение «истина», впротивном случае значение «ложь».
bool isRequested()
{
double r = R. NextDouble();
if (r
{return true;}
return false;
}
Рассмотримтеперь обслуживание заявки в СМО. Время обслуживания заявки в системеопределяется выражением />, где />– случайное число. Впрограмме время обслуживания определяется с помощью функции GetServiceTime().
double GetServiceTime()
{
double r = R. NextDouble();
return (-1/mu*Math. Log (1-r, Math.E));
}
Алгоритмметода имитационного моделирования можно сформулировать следующим образом.Время работы СМО (Т) разбивается на шаги по времени dt, на каждом из них выполняетсяряд действий. Вначале определяются состояния системы (занятость каналов, длинаочереди), затем, с помощью функции isRequested(), определяется, поступилали на данном шаге заявка или нет.
Если поступила,и, при этом имеются свободные каналы, то с помощью функции GetServiceTime() генерируем времяобработки заявки и ставим ее на обслуживание. Если все каналы заняты, а длинаочереди меньше 4, то помещаем заявку в очередь, если же длина очереди равна 4,то заявке будет отказано в обслуживании.
В случае,когда на данном шаге заявка не поступала, а канал обслуживания освободился,проверяем, есть ли очередь. Если есть, то из очереди заявку ставим наобслуживание в свободный канал. После проделанных операций время обслуживаниядля занятых каналов уменьшаем на величину шага dt.
По истечениивремени Т, т.е., после моделирования работы СМО, вычисляются показателиэффективности работы системы и результаты выводятся на экран.
3.2 Блок-схема программыБлок-схемапрограммы, реализующей описанный алгоритм, приведена на рис. 5./>
/>
Рис. 5. Блок-схемапрограммы
Распишемнекоторые блоки более подробно.
Блок 1.Задание начальных значений параметров.
Random R; // Генератор случайных чисел
public uint maxQueueLength; // Максимальная длина очереди
public uint channelCount; // Число каналов в системе
public double lambda; // Интенсивность потока поступлениязаявок
public double mu; // Интенсивность потока обслуживания заявок
public double timeStep; // Шаг по времени
public double[] timeOfFinishProcessingReq; // Время окончанияобслуживания заявки во всех каналах
public double[] timeInQueue; // Время пребывания СМО всостояниях с очередью
public double processingTime; // Время работы системы
public double totalProcessingTime; // Суммарное время обслуживания заявок
public uint requestEntryCount; // Число поступивших заявок
public uint declinedRequestCount; // Число отказанных заявок
public uint acceptedRequestCount; // Число обслуженных заявок
uintqueueLength; // Длина очереди //
Тип,описывающий состояния СМО
enum SysCondition {S0, S1, S2, S3, S4, S5, S6};
SysCondition currentSystemCondition; // Текущее состояниесистемы
Задание состоянийсистемы.Выделим у данной 2-х канальной системы 7 различных состояний: S0, S1. S6. СМО находится всостоянии S0, когда система свободна; S1 – хотя бы один каналсвободен; в состоянии S2, когда все каналы заняты, и есть место вочереди; в состоянии S6 – все каналы заняты, и очередь достигламаксимальной длины (queueLength = 4).
Определяемтекущее состояние системы с помощью функции GetCondition()
SysCondition GetCondition()
{
SysCondition p_currentCondit = SysCondition.S0;
int k = 0;
int busyChannelCount = 0;
for (int i = 0; i
{
if (timeOfFinishProcessingReq[i] > 0)
{
k = 1;
busyChannelCount++;
}
else
{k = 0;}
p_currentCondit += k * (i + 1);
}
if (busyChannelCount > 1)
{p_currentCondit ++;}
return p_currentCondit + (int) QueueLength;
}
Изменениевремени пребывания СМО в состояниях с длиной очереди 1, 2,3,4. Это реализуетсяследующим программным кодом:
if (queueLength > 0)
{
timeInQueue [queueLength – 1] += timeStep;
if (queueLength > 1)
{timeInQueue [queueLength – 2] += timeStep;}
}
Присутствуеттакая операция, как помещение заявки на обслуживание в свободный канал.Просматриваются, начиная с первого, все каналы, когда выполняется условие timeOfFinishProcessingReq[i] (канал свободен), в него подается заявка, т.е. генерируетсявремя окончания обслуживания заявки.
for (int i = 0; i
{
if (timeOfFinishProcessingReq [i]
{
timeOfFinishProcessingReq [i] = GetServiceTime();
totalProcessingTime+= timeOfFinishProcessingReq [i];
break;
}
}
Обслуживание заявок в каналах моделируется кодом:
for (int i = 0; i
{
if (timeOfFinishProcessingReq [i] > 0)
{
timeOfFinishProcessingReq [i] -= timeStep;
}
}
Алгоритм методаимитационного моделирования реализован на языке программирования C#.
3.3 Расчет показателейэффективности СМО на основе/>результатов ееимитационного моделирования
Наиболее важными являются такие показатели, как:
1) Вероятность отказа в обслуживании заявки, т.е. вероятность того, что заявкапокидает систему не обслуженной. В нашем случае заявке отказывается вобслуживании, если все 2 канала заняты, и очередь максимально заполнена (т.е. 4человек в очереди). Для нахождения вероятности отказа разделим время пребыванияСМО в состоянии с очередью 4 на общее время работы системы.
/>
2) Относительная пропускнаяспособность – это средняя доля поступивших заявок, обслуживаемых системой.
/>
3) Абсолютная пропускная способность – это среднее число заявок, обслуживаемыхв единицу времени.
/>
4) Длина очереди, т.е. среднее числозаявок в очереди. Длина очереди равна сумме произведений числа человек вочереди на вероятность соответствующего состояния. Вероятности состояний найдемкак отношение времени нахождения СМО в этом состоянии к общему времени работысистемы.
/>
5) Среднее время пребывания заявки вочереди определяетсяформулой Литтла
/>
6) Среднее число занятых каналов определяется следующим образом:
/>
7) Процентзаявок, которым было отказано в обслуживании, находится по формуле
/>
8) Процентобслуженных заявок находится по формуле
/>
3.4 Статистическая обработка результатов/>иих сравнение с результатами аналитического моделирования
Т.к.показатели эффективности получаются в результате моделирования СМО в течениеконечного времени, они содержат случайную компоненту. Поэтому, для полученияболее надежных результатов нужно провести их статистическую обработку. С этойцелью оценим доверительный интервал для них по результатам 20 прогоновпрограммы.
Величина /> попадает в доверительныйинтервал, если выполняется неравенство
/>, где
/>математическое ожидание(среднее значение), находится по формуле
/>,
/> исправленная дисперсия,
/>,
N=20 – число прогонов,
/> – надежность. При /> и N=20 />.
Результатработы программы представлен на рис. 6.
/>
Рис. 6. Видпрограммы
Для удобствасравнения результатов, полученных различными методами моделирования, представимих в виде таблицы.
Таблица 2.
Показатели
эффективности СМО
Результаты
аналитического
моделирования
Результаты
имитационного моделирования (послед. шаг)
Результаты имитационного моделирования
Нижняя граница
доверительного
интервала
Верхняя граница
доверительного
интервала Вероятность отказа
/> 0,174698253017626 0,158495148639101 0,246483801571923 Относительная пропускная способность
/> 0,825301746982374 0,753516198428077 0,841504851360899 Абсолютная пропускная способность
/> 3,96144838551539 3,61687775245477 4,03922328653232 Средняя длина очереди
/> 1,68655313447018 1,62655862750852 2,10148609204869 Среднее время пребывания заявки в очереди 0,4242558575 0,351365236347954 0,338866380730942 0,437809602510145 Среднее число занятых каналов
/> 1,9807241927577 1,80843887622738 2,01961164326616
Из табл. 2видно, что результаты, полученные при аналитическом моделировании СМО, попадаютв доверительный интервал, полученный по результатам имитационногомоделирования. Т.е., результаты, полученные разными методами, согласуются.
Заключение
В даннойработе рассмотрены основные методы моделирования СМО и расчета показателей ихэффективности.
Проведеномоделирование двухканальной СМО с максимальной длиной очереди равной 4 спомощью уравнений Колмогорова, а также, найдены финальные вероятности состоянийсистемы. Рассчитаны показатели ее эффективности.
Проведеноимитационное моделирование работы такой СМО. На языке программирования C# составлена программа,имитирующая ее работу. Проведена серия расчетов, по результатам которых найденызначения показателей эффективности системы и выполнена их статистическаяобработка.
Полученныепри имитационном моделировании результаты согласуются с результатамианалитического моделирования.
Литература
1. Вентцель Е.С. Исследованиеопераций. – М.: Дрофа, 2004. – 208 с.
2. Волков И.К., Загоруйко Е.А. Исследованиеопераций. – М.: Изд.-во МГТУ им. Н.Э. Баумана, 2002. – 435 с.
3. Волков И.К., Зуев С.М.,Цветкова Г.М. Случайные процессы. – М.: Изд.-во МГТУ им. Н.Э. Баумана,2000. – 447 с.
4. Гмурман В.Е. Руководствок решению задач по теории вероятностей и математической статистике. – М.:Высшая школа, 1979. – 400 с.
5. Ивницкий В.Л. Теориясетей массового обслуживания. – М.: Физматлит, 2004. – 772 с.
6. Исследование операций вэкономике/ под ред. Н.Ш. Кремера. – М.: Юнити, 2004. – 407 с.
7. Таха Х.А. Введениев исследование операций. – М.: ИД «Вильямс», 2005. – 902 с.
8. Харин Ю.С., Малюгин В.И.,Кирлица В.П. и др. Основы имитационного и статистического моделирования. –Минск: Дизайн ПРО, 1997. – 288 с.