Xreferat.com » Рефераты по информатике и программированию » Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

для достижения этой цели можно:

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

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


Имитационное моделирование системы массового обслуживания, Имитационное моделирование системы массового обслуживания, т.е. Имитационное моделирование системы массового обслуживания, где


Имитационное моделирование системы массового обслуживанияматематическое ожидание (среднее значение), находится по формуле


Имитационное моделирование системы массового обслуживания,

Имитационное моделирование системы массового обслуживания исправленная дисперсия,


Имитационное моделирование системы массового обслуживания,


N – число прогонов программы, Имитационное моделирование системы массового обслуживания – надежность, Имитационное моделирование системы массового обслуживания.


Глава 2. Аналитическое моделирование СМО


2.1 Граф состояний системы и уравнения Колмогорова


Рассмотрим четырехканальную систему массового обслуживания (n = 3) с максимальной длиной очереди равной трем (m = 2). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4.0 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 1.0 и показательным законом распределения временем обслуживания.

Данная система имеет 9 состояний, обозначим их:

S0 – все каналы пусты, очередь пуста;

S1 – 1 канал занят, очередь пуста;

S2 – 2 канала заняты, очередь пуста;

S3 – 3 канала заняты, очередь пуста;

S4 – 3 канала заняты, в очереди 1 заявка;

S5 – 3 канала заняты, в очереди 2 заявки;

Вероятности прихода системы в состояния S0, S1, S2, …, S5 соответственно равны Р0, Р1, Р2, …, Р5.

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


Имитационное моделирование системы массового обслуживания

Рис. 3

Для построенного графа запишем уравнения Колмогорова:


Имитационное моделирование системы массового обслуживания


Чтобы решить данную систему зададим начальные условия:


Имитационное моделирование системы массового обслуживания


Систему уравнений Колмогорова (систему дифференциальных уравнений) решим численным методом Эйлера с помощью программного пакета Maple 8 (см. Приложение 1).

Метод Эйлера


Имитационное моделирование системы массового обслуживания

гдеИмитационное моделирование системы массового обслуживания- в нашем случае, это правые части уравнений Колмогорова, n=7.


Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания (1)


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


Имитационное моделирование системы массового обслуживания.


Последовательно N раз вычисляя Имитационное моделирование системы массового обслуживания по формуле (1) получим зависимости вероятностей состояний системы от времени, приведенной на рис.4. Очевидно, что уже при Имитационное моделирование системы массового обслуживания система выходит на стационарный режим. Значения вероятностей СМО при Имитационное моделирование системы массового обслуживания равны:

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания


Зависимости вероятностей состояний системы от времени


Имитационное моделирование системы массового обслуживанияИмитационное моделирование системы массового обслуживания


Рис. 4


2.2 Финальные вероятности системы


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

Т.к. в стационарном состоянии производные по времени равны 0, то уравнения для финальных вероятностей получаются из уравнений Колмогорова путем приравнивания правых частей 0. Запишем уравнения для финальных вероятностей для нашей СМО.


Имитационное моделирование системы массового обслуживания


Решим данную систему линейных уравнений с помощью программного пакета Maple 8 (см. Приложение 1).

Получим финальные вероятности системы:


Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


равны:


Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания


Это подтверждает правильность полученных результатов.


2.3 Расчет показатели эффективности системы по финальным вероятностям


Найдем показатели эффективности системы массового обслуживания. Наиболее важными являются следующие показатели:

1) Вероятность отказа в обслуживании заявки, т.е. вероятность того, что заявка покидает систему не обслуженной. В нашем случае заявке отказывается в обслуживании, если все 4 канала заняты, и очередь максимально заполнена (т.е. 3 человека в очереди), это соответствует состоянию системы S7. Т.к. вероятность прихода системы в состояние S7 равна Р7 , то

Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


5) Среднее время пребывания заявки в очереди определяется формулой Литтла


Имитационное моделирование системы массового обслуживания


6) Среднее число занятых каналов определяется следующим образом:


Имитационное моделирование системы массового обслуживания


Глава 3. Имитационное моделирование СМО


3.1 Алгоритм метода имитационного моделирования СМО (пошаговый подход)


Рассмотрим четырехканальную систему массового обслуживания (n = 3) с максимальной длиной очереди равной четырем (m = 2). В СМО поступает простейший поток заявок со средней интенсивностью λ = 4 и показательным законом распределения времени между поступлением заявок. Поток обслуживаемых в системе заявок является простейшим со средней интенсивностью μ = 1 и показательным законом распределения временем обслуживания.

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

Выберем шаг по времени (Имитационное моделирование системы массового обслуживания). Он должен быть много меньше среднего времени поступления заявки (Имитационное моделирование системы массового обслуживания) и среднего времени ее обслуживания (Имитационное моделирование системы массового обслуживания), т.е.


Имитационное моделирование системы массового обслуживания, где (3.1.1)

Имитационное моделирование системы массового обслуживания

Имитационное моделирование системы массового обслуживания


Исходя из условия (3.1.1) определим шаг по времени Имитационное моделирование системы массового обслуживания.

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

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


Имитационное моделирование системы массового обслуживания.


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

В программе это осуществляет функция Имитационное моделирование системы массового обслуживания. Интервал времени Имитационное моделирование системы массового обслуживания примем постоянным и равным 0,001, тогда отношение Имитационное моделирование системы массового обслуживания будет равно 1000 . Если заявка поступила, то она принимает значение «истина», в противном случае значение «ложь».

function sob: boolean;

var r:real;

begin

r := Random(1000)/1000;

if r <= (i_deltaT*r_Lamda) then

sob:= true

else

sob:= false;

end;

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

Имитационное моделирование системы массового обслуживания,


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

function tok: real;

var r:real;

t_ob: real;

begin

r:= Random(1000)/1000;

t_ob:= -1/r_Mu*ln(1-r);

tok:= t_ob;

end;

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

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

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


3.2 Блок-схема программы


Блок-схема программы, реализующей описанный алгоритм, приведена на рис.5. Распишем некоторые блоки более подробно.

Блок 1. Задание начальных значений параметров. Пользователем задаются значения: Time – время работы системы,

r_la – интенсивность потока поступления заявок (Имитационное моделирование системы массового обслуживания),

r_mu – интенсивность потока обслуживания заявок (Имитационное моделирование системы массового обслуживания).

Значения, задаваемые программой:

i_deltaT:=0.001 – шаг по времени;

i_post:=0;

i_otk:= 0;

i_obsl:=0;

i_och:=0;

i_tobs:=0;

t:=0 – параметр, следящий, сколько времени проработала система;

i_obsl:=0 – число обслуженных заявок;

i_tobs:=0 – общее время обслуживания заявок в системе;

i_post:=0 – число поступивших в СМО заявок;

i_otk:=0 – число заявок, которым было отказано в обслуживании;

i_obsl:=0 – число обслуженных заявок;

sost:='s1' – состояние системы (изначально устанавливаем СМО в состояние s1, т.е. все каналы свободны);

for i :=1 to 3 do

begin

t_och[i] := 0;- обнуляем время пребывания СМО в состояниях с длиной очереди 1, 2.

t_okonch[i] := 0; – время окончания обслуживания заявки во всех 3 каналах устанавливаем в 0, т.к. каналы пусты;

end;


Имитационное моделирование системы массового обслуживания

Рис.5.

Блок 3. Задание состояний системы. Выделим у данной 3-х канальной системы 9 различных состояний: s1, s2,.. s9. СМО находится в состоянии s1, когда система свободна; s2..s7 – хотя бы один канал свободен; в состоянии s8, когда все каналы заняты, и есть место в очереди; в состоянии s9 - все каналы заняты, и очередь достигла максимальной длины (och=2).

Задаем состояния системы:

_sost:=1;

for i:=0 to 3 do

begin

if t_okonch[i+1]>0 then i_temp:= 1

else i_temp:= 0;

_sost:=_sost + i_temp* round(Exp(i*ln(2)));

end;

if _sost<7 then begin Sost:= _sost; exit; end;


if (_sost= 7) and (i_och< 2) then Sost:= _sost

else

Sost := _sost+ 1;

Блок 4. Изменение времени пребывания СМО в состояниях с длиной очереди 1, 2. Это реализуется следующим программным кодом:

if i_och > 0 then t_och[i_och]:= t_och[i_och]+i_deltaT;

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

for i:=1 to 2 do

begin

if t_okonch[i]>0 then t_okonch[i]:= t_okonch[i] - i_deltaT

else

if i_och >0 then

begin

Dec(i_och);

t_okonch[i]:=tok;

i_tobs:=i_tobs + t_okonch[i];

end;

end;

Блок 17 реализуется следующим программным кодом:

for i:=1 to 2 do

if t_okonch[i]>0 then

t_okonch[i]:= t_okonch[i] - i_deltaT;

Алгоритм метода имитационного моделирования реализован на языке программирования C#.


3.3 Расчет показателей эффективности СМО на основе результатов ее имитационного моделирования


Наиболее важными являются такие показатели, как:

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


Имитационное моделирование системы массового обслуживания


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

Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


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


Имитационное моделирование системы массового обслуживания


5) Среднее время пребывания заявки в очереди определяется формулой Литтла


Имитационное моделирование системы массового обслуживания


6) Среднее число занятых каналов определяется следующим образом:


Имитационное моделирование системы массового обслуживания


7) Процент заявок, которым было отказано в обслуживании, находится по формуле

Имитационное моделирование системы массового обслуживания


8) Процент обслуженных заявок находится по формуле


Имитационное моделирование системы массового обслуживания


3.4 Статистическая обработка результатов и их сравнение с результатами аналитического моделирования


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

Величина Имитационное моделирование системы массового обслуживания

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: