ID: 86070

Название работы: Моделирование системы массового обслуживания

Категория: Курсовая

Предметная область: Информатика, кибернетика и программирование

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

Язык: Русский

Дата добавления: 2015-04-02

Размер файла: 780.5 KB

Работу скачали: 63 чел.

 24 -

ГОУ ВПО

«УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ»

РАЗРАБОТКА МОДЕЛИ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ И ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ ХАРАКТЕРИСТИК ЕЁ ЭФФЕКТИВНОСТИ

Пояснительная записка к курсовому проекту

по общепрофессиональной дисциплине

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

Направление  654600 (230100)  – Информатика и ВТ

Факультет  информатики и робототехники

Кафедра   автоматизированных систем управления

Курс   3

Семестр   6

2009.000000.МС.КП.ПЗ АСОИ-

Оценка ________________   Исполнитель

Консультант доцент каф. АСУ   студ. гр. АСОИ-

            (зач. кн.)

____________ Бакусов Л.М.   ___________

«___» ____________ 2009 г.   «___» ___________ 2009 г.

2009

СОДЕРЖАНИЕ

ВВЕДЕНИЕ……………………………………………………………………………………………….3

ПОСТАНОВКА ЗАДАЧИ…………………………………………………………………………….....5

1   ТЕОРЕТИЧЕСКАЯ ЧАСТЬ....……………………………………………………………………...6

1.1 Описание системы……………………………………………………………………….……6

1.2 Характеристики СМО…………………………………………………………………   ……7

1.3 Закон распределения Пуассона………………………………………………………………8

1.4 Экспоненциальное распределение…………………………………………………………..9

1.4.1   Моделирование экспоненциальной случайной величины…………………………10

1.5   Закон распределения Эрланга………………………………………………………………. 10

1.5.1   Моделирование эрланговской случайной величины……………………………… 12

 1.6  Описание потоков……………………………………………………………………………12

1.6.1 Поток заявок………………………………………………………………………… 13

 1.7   СМО с отказами……………………………………………………………………………... 14

1.7.1 Многоканальная СМО с отказами…………………………………………………..14

2   РЕШЕНИЕ ЗАДАЧИ………………………………………………………………………………..15

2.1   Алгоритм моделирования СМО……………………………………………………………. 15

2.2   Каноническая модель системы……………………………………………………………... 16

2.2.1   Характеристическая таблица……………………………………………………….. 18

2.2.2   Строим дерево алгоритма…………………………………………………………... 18

2.2.3   На основе полученного дерева алгоритма построим  основную блок-схему работы системы в операторном виде………………………………………………………………. 20

1.  Обобщенная блок-схема моделирующего алгоритма……………………………. 21

2.2.4.1   Моделирование случайной величины с распределением Эрланга…….. 22

3   РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ…………………………………………………………… 23

4   ТЕОРЕТИЧЕСКИЕ РАСЧЕТЫ………………………………………………………………….. 26

5   РЕЗУЛЬТАТЫ РАБОТЫ СМО………………………………………………………………….. 27

6   ГРАФИЧЕСКИЕ ЗАВИСИМОСТИ ОСНОВНЫХ ХАРАКТЕРИСТИК

ЭФФЕКТИВНОСТИ РАБОТЫ СМО…………………………………………………... 28

7   ВЫВОД…………..…………………………………………………………………..……………… 30

ЗАКЛЮЧЕНИЕ………………………………………………………………………………………... 31

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………………………………………...…… 32

ПРИЛОЖЕНИЕ ...………………………………………………………………………………….…. 33

ВВЕДЕНИЕ

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

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

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

Судить о результатах работы СМО можно по показателям эффективности. Наиболее часто рассматриваемые из них:

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

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

Целью данного курсового проекта является выработка умений и навыков моделирования системы массового обслуживания конкретного типа и определения характеристик эффективности ее работы в качестве статистических результатов моделирования. Для достижения этой цели выполняется разработка обобщенного и детального алгоритма моделирования работы СМО. Практическая реализация поставленной задачи осуществляется в среде Microsoft Visual Studio 6.0  на языке программирования С++. В процессе нескольких реализаций работы СМО фиксируются результаты функционирования системы. На основе полученных данных осуществляется построение графических зависимостей, позволяющих провести исследование СМО, проанализировать характеристики ее работы. В итоге делаются выводы, в общем характеризующие функционирование СМО, отражающие ее достоинства и недостатки, определяются направления улучшения ее качества.

 

Постановка задачи

Построить модель СМО и исследовать поведение характеристик её эффективности.

Описание системы:

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

 

Интенсивность входного потока	Интенсивность обслуживания	Первый канал обслуживания	Второй канал обслуживания
λ = 6	µ = 7	Поток Эрланга,      k = 1	Поток Эрланга,      k = 2

1   ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

Теория массового обслуживания опирается на теорию вероятностей и математическую статистику.

Первые задачи теории систем массового обслуживания (ТСМО) были рассмотрены сотрудниками Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878г. – 1929г.) в период между 1908 и 1922гг. Эти задачи были вызваны к жизни стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, работа морских и речных портов, магазинов, терминальных классов, радиолокационных комплексов, радиолокационных станций и т.д. и т.д. может быть описана в рамках ТСМО.

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

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

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

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

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

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

Заданная система является  n-канальной с отказами при n=2.

Рассмотрим 2-канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут: S0 - все каналы свободны, S1 - занят ровно один канал, остальные свободны, S2- заняты оба канала.

Граф состояний данной СМО представлен на рис.1. Разместим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. По стрелкам слева на право систему переводит один и тот же поток - поток заявок с интенсивностью λ (интенсивность входного потока).

Рис.1

Если система находиться в состоянии S1 (занят 1 канал) и пришла новая заявка, система переходит (перескакивает) в состояние S2(заняты оба канала).

Определим интенсивности потоков событий, переводящих систему по стрелкам справа налево.

Пусть система находиться в состоянии S1 (занят один канал). Тогда, как только закончиться обслуживание заявки, занимающей этот канал, система перейдет в S0; значит, поток событий, переводящий систему по стрелке S1 → S0, имеет интенсивность μ. Очевидно, если обслуживанием занято два канала, а не один, поток обслуживаний, переводящий систему по стрелке S2 → S1, будет вдвое интенсивнее (2μ). Проставим соответствующие интенсивности у стрелок, ведущих справа налево.

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

1.2   Характеристики СМО.

По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы:

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

В СМО с неограниченным временем ожидания очередное требование, застав все устройства занятыми, становится в очередь и ожидает обслуживания до тех пор, пока одно из устройств не освободится.

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

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

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

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

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

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

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

 

где Т - среднее значение интервала между поступлением очередных требований.

1.3  Закон распределения Пуассона

Для многих реальных процессов поток требований достаточно хорошо описывается законом распределения Пуассона. Такой поток называется простейшим.

Простейший поток обладает такими важными свойствами:

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

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

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

При простейшем потоке требований распределение требований, поступающих в систему подчиняются закону распределения Пуассона:

вероятность  того, что в обслуживающую систему за время t поступит именно k требований:

где - среднее число требований, поступивших на обслуживание в единицу времени.

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

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

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

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

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

Функция плотности вероятностей экспоненциального распределения с параметром l задается выражением:

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

Рассмотрим предельную теорему о суперпозиции потоков. Предположим, что наблюдается k независимых потоков событий. В свою очередь в каждом потоке наблюдается   элементарных событий. Интервалы времени между событиями – независимые случайные величины, распределенные по неизвестному закону с математическим ожиданием  1/ λj.

Теорема: При наложении (суперпозиции) достаточно большого числа n независимых, стационарных и ординарных потоков с интенсивностями λi (i=1,2..n) получается поток, близкий к простейшему с интенсивностью:  

1.4.1   Моделирование экспоненциальной случайной величины

Экспоненциальная случайная величина x имеет функцию распределения величины:

F(t) = 1 - e-λt,

Для экспоненциальной случайной величины x:

M(x) = 1 / λ, D(x) = 1 /λ2.

Для построения генератора такой случайной величины используем метод обращения.

Записываем формальное уравнение F(x) =1 – e-λt =   z.

Решаем его относительно x:

x = - (1/λ ) ln (1- z)     (1.4)

Формулу (1.4) можно упростить, заменив (1 - z) на z, так как обе эти величины совпадают по распределению. Тогда получаем:

x = - (1 / λ ) ln (z).

1.5   Закон распределения Эрланга

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

           Очевидно, что простейший поток может рассматриваться как поток Эрланга нулевого порядка.

           

Пусть имеется простейший поток с интервалами Т1, Т2, … между событиями. Величина Т – промежуток времени между двумя соседними событиями в потоке Эрланга k – го порядка.

           Очевидно, что . Так как первоначальный поток – простейший, то случайные величины Т1, Т2, … распределены по показательному закону:

          Обозначим fk(t) плотность распределения величины Т для потока Эрланга k – го порядка. Если умножить эту плотность на элементарный отрезок времени dt, мы получим вероятность того, что величина Т примет значение в некоторой сколь угодно малой окрестности точки t-  (t, t + dt). На этот участок должна попасть конечная точка промежутка, а предыдущие k точек простейшего потока – на промежуток  (0, t).

           Вероятность первого события равна , а второго - . Эти события должны осуществиться совместно, значит, их вероятности надо перемножить.

,  

Полученный закон распределения называется законом распределением Эрланга k- го порядка.

При k = 0 получаем показательный закон распределения.

           Математическое ожидание, дисперсия и среднее квадратическое отклонение для распределения Эрланга находятся по формулам:

           Плотность потока Эрланга равна  

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

           Закон распределения для такого потока будет иметь вид:

,      

           Математическое ожидание и дисперсия будут равны:

           Получается, что неограниченном увеличении k нормированный поток Эрланга приближается к регулярному потоку с постоянными интервалами, равными 1/ λ.

Для потоков Эрланга n – го порядка вероятность поступления k требований за промежуток времени t равна:

1.5.1   Моделирование эрланговской случайной величины

Эрланговская случайная величина имеет функцию распределения величины:

, где k - порядок распределения.

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

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

где zi - реализации БСВ, i = 1, ...,K.

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

Для реализации средствами языков программирования используют соотношение:

,

где τэрк - случайная величина с распределением Эрланга k-го порядка;

τ i- случайная величина, распределенная по показательному закону с параметром λ.

1.6  Описание потоков

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

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

        τj — интервал между событиями (случайная величина);

        tсi — момент совершения i-го события (отсчитывается от t = 0);

Tн — время наблюдения.

1.6.1 Поток заявок

Поток заявок задаётся случайной величиной с распределением Эрланга с параметрами µ = 7 (интенсивностью потока) и k = 1 (порядком распределения). Говорят, что случайная величина X имеет распределение Эрланга с параметрами k > 0 (параметр k принимает целое значение), µ > 0, если она непрерывна, принимает только положительные значения, и имеет плотность распределения:

.

Поток Эрланга k-го порядка — это поток случайных событий, получающийся, если в простейшем  случайном потоке сохранить каждое k-е событие, а остальные отбросить. Порядок потока — мера последействия потока. То есть обратной величиной к мере случайности потока является его порядок.

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

1.7   СМО с отказами

В качестве показателей эффективности СМО с отказами будем рассматривать:

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

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

Ротк - вероятность отказа, т.е. того, что заявка покинет СМО не обслуженной;

k  - среднее число занятых каналов (для многоканальной системы).

1.7.1   Многоканальная СМО с отказами

Рассмотрим классическую задачу Эрланга:

Имеется п каналов, на которые поступает поток заявок ,с интенсивностью l. Поток обслуживаний имеет интенсивность m. Найти предельные вероятности состояний системы и показатели ее эффективности.

Граф состояний СМО соответствует процессу гибели и размножения:

по формулам для процесса гибели и размножения:

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

                                    заявок;

Тогда, получим Формулы Эрланга:

      

Вероятность отказа СМО есть предельная вероятность того, что все п каналов системы будут заняты:  

Относительная пропускная способность:

Абсолютная пропускная способность:

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

2   РЕШЕНИЕ ЗАДАЧИ

2.1   Алгоритм моделирования СМО

Начальные условия:

1.  Рассматриваемая в задаче СМО представляет собой СМО с:

•  Одним входным потоком;
•  Двумя обслуживающими каналами.

1.  Определение времен поступления и обслуживания заявок:

•  Времена поступления и обслуживания  заявок генерируются случайно с заданным законом распределения Эрланга;
•  Интенсивности поступления и обслуживания заявок заданы.

1.  Функционирование рассматриваемой СМО:

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

1.  Дисциплина обслуживания:

•  Если к моменту поступления заявки оба канала обслуживания заняты, то поступившая заявка покидает систему необслуженной.

Задача моделирования:

зная параметры входных потоков заявок промоделировать поведение системы и вычислить её основные характеристики её эффективности.

Критерии эффективности функционирования СМО:

•  Вероятность простоя: ; 
•  Вероятность отказа (вероятность того, что заявка покинет СМО необслуженной):

 ;

•  Доля обслуженных заявок;
•  Относительная пропускная способность (средняя доля заявок, обслуживаемых системой):

;

•  Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени):

  

где  λ  – интенсивность потока заявок (величина, обратная среднему промежутку времени между поступающими заявками – t3);

μ – интенсивность потока обслуживаний (величина, обратная среднему времени обслуживания tобсл)

Принцип моделирования:

•  Вводим начальные условия: общее время работы системы, значение интенсивности потока заявок, количество прогонов программы;
•  Генерируем моменты времени, в которые прибывают заявки, время обслуживания каждой пришедшей заявки;
•  Считаем сколько заявок было обслужено, а, сколько получило отказ;
•  Рассчитываем критерий эффективности СМО.

2.2   Каноническая модель системы

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

Поток обслуживания характеризуется среднем временем обслуживания каждой заявки τ=1/μ.

Для данной модели должно выполняться следующее условие:

- существует только 1 вход и 1 выход.

Последовательное описание логических и арифметических операторов в канонической модели:

1.  Выбираем интервал моделирования [0;Tk] ;
2.  P1 – логический оператор, который определяет, попадает ли момент поступления первой  заявки r в интервал [0,Tk] -   в интервал работы системы, то есть

Р1: r<=Tk (r -  случайно сгенерированное время поступление первой заявки в систему, Тк – время работы системы, которое было задано).

Если время поступления в систему  самой первой заявки не попадает в  интервал [0,Tk], то дальнейшая обработка данных не целесообразна, поэтому происходит выход из системы.

Если  первая заявка попала в интервал [0,Tk], то осуществляется переход к следующим операторам, то есть определяется дальнейшая судьба заявки;

1.  Р2-  логический оператор, который определяет, будет ли обслужена заявка первым каналом,

Р2:= Tc>=T1  (Тс – время поступления очередной  заявки на обслуживание ;

Т1 – время освобождения 1 канала от обслуживания предыдущей заявки ).

Если время поступления в систему очередной заявки Tc больше, чем время освобождения 1-го канала от обслуживания предыдущей заявки, то есть

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

Если же Тс<T1, то есть первый канал еще занят, то  поступившая заявка не будет обслужена первым каналом, поэтому  осуществляется переход к следующим операторам, то есть определяется дальнейшая судьба заявки.

1.  Р3-  логический оператор, который определяет, будет ли обслужена заявка вторым  каналом или получит отказ,

Р3:= Tc>=T2  (Тс – время поступления  очередной заявки на обслуживание  ;

Т2 – время освобождения 2 канала от обслуживания предыдущей заявки ).

Если время поступления в систему очередной заявки Tc больше, чем время освобождения 2-го канала от обслуживания предыдущей заявки Т2, то есть к моменту поступления очередной заявки в систему второй канал уже освободился, то поступившая заявка идет на обслуживание вторым каналом.

Если же Тс<T2, то есть второй канал еще занят, то  поступившая заявка не будет обслужена вторым каналом, поэтому  она  получает отказ и покидает систему не обслуженной.

1.  Р4 – логический оператор, который определяет, выполняется ли условие  

Т <=Тк  (Т – текущий момент времени, Тк – общее время работы системы, которое было задано).

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

1.  A0 – арифметический оператор, который определяет  время прихода очередной заявки в систему, генератор случайных чисел. А0:=  r=random(λ);
2.  A1 - арифметический оператор, который определяет число поступивших заявок; А1:=N+1 (подсчет числа реализаций);
3.  А3- арифметический оператор, который определяет время обслуживания заявки первым каналом; А3:= r1=erlang(μ);
4.  А4 – это объединение арифметических операторов, которое определяет время освобождения от поступившей заявки Т1, ведет подсчет общего времени обслуживания 1 каналом заявок Tobs, а также считает количество обслуженных заявок 1 каналом Nobs. А4:=  Т1=Тс+r1; Tobs=Tobs+r1;  Nobs=Nobs +1;
5.  А5- арифметический оператор, который определяет время обслуживания заявки вторым  каналом. А3:= r2=erlang(μ);
6.  А6 – это объединение арифметических операторов, которое определяет время освобождения второго канала от поступившей заявки Т2, ведет подсчет общего времени обслуживания 2 каналом заявок Tobs, а также считает количество обслуженных заявок 2 каналом Nobs. А6:=  Т2=Тс+r2; Tobs=Tobs+r2;  Nobs=Nobs +1;
7.  А7- статистическая обработка результатов, которые были получены в ходе обслуживания заявок системой в течении времени Тк.
8.  А8 – арифметический оператор, который ведет подсчет отказанных заявок. А8:=Notk+1;

2.2.1   Характеристическая таблица

А0- обязательно для начала работы системы.

Сначала идут арифметические операторы, потом – логические.

N0	Р1	N1	P2	N2	P3	N3	P4	N4
A0	0	Z	0	Z	0	Z	0	A7,END
A0	0	Z	0	Z	0	Z	1	A0
A0	0	Z	0	Z	1	Z	0	A7,END
A0	0	Z	0	Z	1	Z	1	A0
A0	0	Z	1	Z	0	Z	0	A7,END
A0	0	Z	1	Z	0	Z	1	A0
A0	0	Z	1	Z	1	Z	0	A7,END
A0	0	Z	1	Z	1	Z	1	A0
A0	1	A1	0	Z	0	A8	0	A7,END
A0	1	A1	0	Z	0	A8	1	A0
A0	1	A1	0	Z	1	A5,A6	0	A7,END
A0	1	A1	0	Z	1	A5,A6	1	A0
A0	1	A1	1	A3,A4	0	Z	0	A7,END
A0	1	A1	1	A3,A4	0	Z	1	A0
A0	1	A1	1	A3,A4	1	Z	0	A7,END
A0	1	A1	1	A3,A4	1	Z	1	A0

2.2.2   Строим дерево алгоритма

В соответствии с характеристической таблицей определяем ранги вершин и их нумерацию,  получим следующее дерево алгоритма :

После объединения операторов получим следующее дерево алгоритма:

2.2.3   На основе полученного дерева алгоритма построим  основную блок-схему работы системы в операторном виде

1.  Обобщенняа блок-схема моделирующего алгоритма

2.2.4.1   Моделирование случайной величины  с распределениемЭрланга

Функция erlahg();

3   РЕЗУЛЬТАТЫ МОДЕЛИРОВАНИЯ

4   ТЕОРЕТИЧЕСКИЕ РАСЧЕТЫ

λ=6

μ=7

n=2;

ρ= λ/ μ =>  ρ=6/7;

, следовательно,

для двухканальной системы p0=(1+6/7+(6/7)2/2)-1= 0,7315

Вероятность отказа СМО есть предельная вероятность того, что все п каналов системы будут заняты:  

                Pотк=0,732*(6/7)2/2=0,1546

Относительная пропускная способность:

               Q= 0,8454

Абсолютная пропускная способность:

                        A=6*0,8454=4,7455

5   РЕЗУЛЬТАТЫ РАБОТЫ СМО

	Tobs	Npost	Nobs	Notk	Lambda	Mu	Q	A	K	Tprost	Pprost	Potk
1	105,962	881	742	139	5,873	7,003	0,842	4,947	0,707	44,038	0,295	0,158
2	104,916	814	670	144	5,427	6,386	0,823	4,467	0,638	45,084	0,301	0,177
3	100,684	798	667	131	5,32	6,625	0,836	4,445	0,635	49,316	0,331	0,16
4	103,154	813	690	123	5,42	6,689	0,849	4,6	0,657	46,846	0,315	0,151
5	102,039	855	727	128	5,7	7,1247	0,850	4,847	0,692	47,961	0,321	0,15
6	110,591	900	730	170	6	6,601	0,811	4,867	0,695	39,41	0,263	0,189
7	103,933	830	688	142	5,533	6,619	0,828	4,587	0,655	46,067	0,307	0,171
8	106,46	869	728	141	5,793	6,838	0,838	4,853	0,693	43,539	0,291	0,162
9	105,554	817	666	151	5,447	6,31	0,815	4,44	0,634	44,446	0,297	0,185
10	107,545	837	719	118	5,58	6,685	0,859	4,793	0,685	42,455	0,283	0,141

1.  ГРАФИЧЕСКИЕ ЗАВИСИМОСТИ ОСНОВНЫХ ХАРАКТЕРИСТИК

ЭФФЕКТИВНОСТИ РАБОТЫ СМО

1) Рассмотрим интенсивность поступления заявки (λ)

2) Рассмотрим интенсивность обслуживания заявки (μ)

3) Рассмотрим относительную пропускную способность (Q)

4) Рассмотрим абсолютную пропускную способность (А)

5) Рассмотрим вероятность простоя системы (Pprost)

6) Рассмотрим вероятность отказа системы (Potk)

7   ВЫВОД

В результате моделирования работы СМО, а также анализа полученных данных были сделаны следующие выводы:

1. При увеличении времени функционирования системы соответственно увеличивается и количество заявок, поступивших в систему;

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

3. Теоретические расчеты дают следующие данные:

— интенсивность поступления заявки λ=6; интенсивность обслуживания заявок μ=7; каналов n=2;

— коэффициент загрузки ρ=6/7;

— вероятность того, что система находится в режиме ожидания  p0= 0,7315;

— вероятность отказа СМО : Pотк=0,1546;

— относительная пропускная способность: Q= 0,8454;

— абсолютная пропускная способность: A= 4,7455

       Полученные данные взяты усредненными и имеют следующие показатели:

Интенсивность поступления заявки λ=5,609;

Интенсивность обслуживания заявок μ=6,688;

Вероятность отказа СМО : Pотк=0,164;

Вероятность того, что система находится в режиме ожидания  p0= 0,75;

Относительная пропускная способность: Q=0,835;

Абсолютная пропускная способность: A=4,685.

    Сравнивая теоретические расчеты с полученными данными,  ви0,8615т следующие показатели:
ы усредненные.ми данными  идно, что значения теоретические и эмпирические практически сходятся с некоторой погрешностью. Следовательно разработанная программа, реализованная в среде Microsoft Visual Studio 6.0 на языке программирования C++ работает правильно.

ЗАКЛЮЧЕНИЕ

Целью данного курсового проекта было построение модели двухканальной СМО с отказами, с входным и обслуживающим Эрланговским потоком, при заданных значениях k, а также была поставлена задача определения основных характеристик системы. Модель СМО была реализована с помощью программы в среде Microsoft Visual Studio С++ 6.0  на языке программирования С++. В процессе нескольких реализаций работы СМО были получены результаты функционирования системы. На основе полученных данных были построены графики, позволяющие провести исследование работы СМО. С помощью графиков проведен анализ полученных данных и сделаны выводы о работе системы.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.  Бакусов Л.М.- Конспект лекций по предмету «Моделирование систем»
2.  Вентцель Е.С., Овчаров Л.А. Теория вероятностей и её инженерные приложения, М: Наука, 1988
3.  Вентцель Е.С. Исследование операций, М:Наука, 1980.
4.  Гмурман В.Е. Теория вероятностей и математическая статистика, М: Высшая школа, 2001
5.  Википедия – свободная энциклопедия. http://ru.wikipedia.org
6.  Советов Б.А., Яковлев С.А. Моделирование систем, М: Высшая школа, 1985

ПРИЛОЖЕНИЕ

#include<iostream.h>

#include<stdio.h>

#include<math.h>

#include<conio.h>

#include <stdlib.h>

#include <fstream.h>

#include <time.h>

#include<windows.h>

char* rus(const char* stroka);

char Rus[256];

//получение равномерно распределенных величин:[0;1]

double get_ravn() {

return (rand() % 100) * 0.01;

}

//функция вычисления Эрганговской случайной величины

double erlang(double c)

{  int k=3;

double x;

   x=0;

   for (int j=0; j<k; j++)

{

     x=-1*pow(c,-1)*log(get_ravn()+0.0001);

   

}

return x;

}

void main()

{

cout<<rus("                            КУРСОВАЯ РАБОТА\n")<<endl;

 cout<<rus("                по дисциплине МОДЕЛИРОВАНИЕ СИСТЕМ")<<endl<<endl;

cout<<rus("ЗАДАНИЕ 1:")<<endl;

cout<<rus("  Построить модель СМО и исследовать поведение характеристик ее эффективности.")<<endl<<endl;

cout<<rus("ОПИСАНИЕ СИСТЕМЫ:")<<endl;

cout<<rus("  Имеется двухканальная СМО с отказами, на которую поступает произвольный поток заявок. Поступившие заявки попадают на обслуживание. Поток обслуживания также произвольный.")<<endl<<endl;

   cout<<rus("ВАРИАНТ 6:")<<endl;

cout<<rus("  Лямбда=6   Мю=7 ")<<endl;

 cout<<rus("  Входной поток-ЭРЛАНГА k=1;    Поток обслуживания- ЭРЛАНГА k=2")<<endl<<endl;

 double lambda, mu, Tk, Tc=0, T1=0, T=0, Tobs=0, T2=0, p, A, Pobs, Potk, r=0,r1=0,r2=0;

 int i, N=0, Nobs=0, Notk=0;

cout<<rus("Количество реализаций = "); cin>>p;

cout<<endl;

 cout<<rus("Лямбда = ");

 cin>>lambda; cout<<endl;

 cout<<rus("Мю = ");

 cin>>mu;

 cout<<endl;

 

 cout<<rus("Введите время выполнения = ");

 cin>>Tk; cout<<endl<<endl;

 for (i=0; i<p; i++)

 { Tc=0; T1=0; T=0; T2=0;

 N=0; Nobs=0; Notk=0; Tobs=0;

   cout<<endl<<endl;

 cout<<rus("РЕАЛИЗАЦИЯ № ")<<(i+1)<<endl<<endl;

  do

 {

     r=erlang(lambda);

  Tc=Tc+r;

  N=N+1;

  

   if(Tc>=T1)

   {

    

    r1=erlang(mu);

          

    T1=Tc+r1;

    Tobs=Tobs+r1;

    Nobs=Nobs+1;

   

    T=T1;

   }

   else { if (Tc>=T2)

   {

   

    r2=erlang(mu);

    

    T2=Tc+r2;

    Tobs=Tobs+r2;

    Nobs=Nobs+1;

    T=T2;

   }

   else{ Notk++; }

   }

 

 

 }

 while(T<=Tk);

 

  A=Nobs/Tk;

  Pobs=Nobs*pow(N,-1);

  Potk=Notk*pow(N,-1);

 cout<<rus("Время обслуживания системы_Tобс = ")<<Tobs<<endl;

 cout<<rus("Количество поступивших заявок_Npost = ")<<N<<endl;

 cout<<rus("Количество обслуженных заявок_Nobs   = ")<<Nobs<<endl;

 cout<<rus("Количество отказанных заявок_Notk   = ")<<Notk<<endl;

 cout<<rus("Интенсивность поступления заявки_Lambda     = ")<<N*pow(Tk,-1)<<endl;

 cout<<rus("Интенсивность обслуживания заявки_Mu ")<<Nobs*pow(Tobs,-1)<<endl;

 cout<<rus("Относительная пропускная способность_Q = ")<<Nobs*pow(N,-1)<<endl;

 cout<<rus("Абсолютная пропускная способность_A = ")<<A<<endl;

 cout<<rus("Количество занятых каналов_K = ")<<A*pow(mu,-1)<<endl;

 cout<<rus("Время простоя системы_Tprost = ")<<Tk-Tobs<<endl;

 cout<<rus("Вероятность простоя системы_Pprost = ")<<(T-Tobs)/T<<endl;

 cout<<rus("Вероятность отказа_Potk          = ")<<Potk<<endl<<endl;

 }

  getch();

}

char* rus (const char* stroka)

 {

CharToOem(stroka,Rus);

return Rus;

}

А0

А5

А4

А6

А3

А1

А8

Р1

Р2

Р3

Р3

А7, END

P4

P4

P4

P3

P3

P3

P3

P2

P2

P1

1

1

P4

P4

P4

P4

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

P1

P2

P2

P3

P3

P3

P3

P4

P4

P4

P4

P4

P4

P4

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

А0

A1 

Z 

Z 

0

0

Z 

A3,A4

Z 

Z 

A5,A6

A8 

A7,END

A7,END

A7,END

A7,END

A7,END

A7,END

A7,END

A7,END

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A0 

A7,END

=>

A7,END

A7,END

A7,END

A7,END

A7,END

A7,END

=>

=>

A7,END

=>