Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Расчет систем массового обслуживания с отказами методом Монте-Карло




Читайте также:
  1. C2 Покажите на трех примерах наличие многопартийной политической системы в современной России.
  2. CASE-технология создания информационных систем
  3. CASE-технология создания информационных систем.
  4. ERP система
  5. GPSS World – общецелевая система имитационного моделирования
  6. I.2.3) Система римского права.
  7. II. Индукция методом исключения
  8. II. Организм как целостная система. Возрастная периодизация развития. Общие закономерности роста и развития организма. Физическое развитие……………………………………………………………………………….с. 2
  9. II. Системы, развитие которых можно представить с помощью Универсальной Схемы Эволюции
  10. II.5.1) Понятие и система магистратур.

Рассмотрим одну из самых простых систем массового обслуживания. Система эта состоит из n-линий (или каналов, или пунктов обслуживания), каждый из которых может обслуживать потребителей. В систему поступают заявки, причем моменты их поступления случайные. Каждая заявка поступает на линию № 1. Если в момент поступления k-й заявки (назовем его Тк) эта линия свободна, то она приступает к обслуживанию заявки, что продолжается t3 мин. (t3 – время занятости линии). Если в момент Тк линия № 1 занята, то заявка мгновенно передается на линию № 2. и т.д… Если все n-линии в момент Тк заняты, то система выдает отказ. Требуется определить, сколько (в среднем) заявок обслужит система за время Т и сколько отказов она даст. Ясно, что задачи такого типа встречаются при исследовании организации работы любых предприятий, а не только предприятий бытового обслуживания. Здесь метод Монте-Карло является единственным методом расчета.

Схема расчета. Каждой линии поставим в соответствие ячейку внутреннего накопителя ЭВМ, в которую будем записывать момент, когда эта линия освобождается. Обозначим момент освобождения i-й линии через ti. За начальный момент расчета выберем момент поступления первой заявки T1=0. Можно считать, что в этот момент все ti равны T1: все линии свободны. Время окончания расчета Ткон1+Т.

Первая заявка поступает на линию №1. Значит, в течение t3 линия эта будет занята. Поэтому заменяем t1 на новое значение (t1)нов = Т1+t3 , добавить единицу к счетчику выполненных заявок и перейти к рассмотрению второй заявки. Предположим, что к заявок уже рассмотрены. Тогда разыграем момент поступления (к+1)-й заявки. Для этого выбираем очередное значение γ и по формуле τ = 1/а lnγ вычисляем очередное значение τ = τк. А затем вычисляем момент поступления Тк+1 = Ткк. Свободна ли в этот момент первая линия? Для установления этого надо проверить условие t1 <=Tk+1. Если это условие выполнено, то значит, к моменту Тк+1 линия уже освободилась и может обслуживать эту заявку. Мы должны заменить t1 на Tk+1+t3, добавить единицу к счетчику выполненных заявок и перейти к следующей заявке. Если условие t1 <=Tk+1не выполнено, то значит, что первая линия в момент Tk+1 занята. Тогда проверяем, свободна ли вторая линия t2 <=Tk+1. Если условие t2 <=Tk+1 выполнено, то заменяем t2 на Tk+1+t3, добавляем единицу к счетчику выполненных заявок и переходим к следующей заявке. Если предыдущее условие не выполнено, то переходим к проверке условия t3 <=Tk+1. Может оказаться, что при всех i от 1 до n ti > Tk+1, т.е. все линии в момент Тк+1 заняты. Тогда надо добавить единицу в счетчик отказов и потом перейти к рассмотрению следующей заявки. Каждый раз, вычислив Тк+1, надо проверять еще условие окончания опыта Тk+1 > Ткон .Когда это условие окажется выполненным, опыт заканчивается. В счетчике выполненных заявок и в счетчике отказов будут стоять числа μвып и μотк. Такой опыт повторяется N раз (с использованием различных γ). И результаты всех опытов усредняются: ; , где μвып (j) и μотк (j) – значения μвып и μотк, полученные в j-ом опыте.



Представим блок-схему программы, реализующий расчет СМО методом Монте-Карло на рис. 7. [17]

Подсчет результатов, выдача, конец задачи
J: = J +1
i = 1
Конец опыта
Т1 = 0; t1 = t2 = … = tn = 0; k = 1
J= 1



 

Рисунок 7 - Блок-схема программы, осуществляющей расчет СМО методом Монте-Карло

Пример. В трехканальную систему массового обслуживания с отказами поступает пуассоновский поток заявок. Время между поступлениями двух последовательных заявок распределено по показательному закону f(τ) = 5e-5τ . Длительность обслуживания каждой заявки равна 0,5мин. Найти методом Монте-Карло математическое ожидание а числа обслуженных заявок за время Т=4мин.

Решение: Пусть Т1=0 – момент поступления первой заявки. Заявка поступит в первый канал и будет им обслужена. Момент окончания обслуживания первой заявки Т1+0,5=0+0,5=0,5. В счетчик обслуженных заявок записываем единицу.

Моменты поступления последующих заявок найдем по формуле:

Тi=Ti-1i.

где τi - длительность времени между двумя последовательными заявками с номерами i-1 и i.

Возможные значения τi разыгрываем по формуле

Учитывая, что, по условию, λ=5, получим τi=0,2 (ln ri).

Случайные числа ri берем из таблицы приложения 1, начиная с первой строки сверху. Для нахождения времени между поступлениями первой и второй заявок возьмем случайное число r1=0,10.

Тогда вычислим: τ2=0,2*(ln0,10)=0,2*2,30=0,460.

Первая заявка поступила в момент Т1 = 0. Следовательно, вторая заявка поступит в момент Т2 = Т1+0,460=0,460. В этот момент первый канал ещё занят обслуживанием первой заявки, поэтому вторая заявка поступит во второй канал и будет им обслужена. Момент окончания обслуживания второй заявки Т2+0,5=0,460+0,5=0,960. В счетчик обслуженных заявок добавляем единицу.



По очередному случайному числу r2=0,09 разыграем время τ3 между поступлениями второй и третьей заявок:

τ3 = 0,2*(-ln 0,09) = 0,2*2,41=0,482.

Вторая заявка поступила в момент Т2=0,460. Поэтому третья заявка поступит в момент Т32+0,482=0,460+0,482=0,942. В этот момент первый канал уже свободен, и третья заявка поступит в первый канал. Момент окончания обслуживания третьей заявки Т3+0,5=1,442. В счетчик обслуженных заявок добавляем единицу.

Дальнейшие расчеты производят и результаты записывают в таблице, причем если в момент поступления заявки все каналы заняты (момент поступления заявки меньше каждого из моментов окончания обслуживания), то в счетчик отказов добавляют единицу. Заметим, что обслуживание 20-й заявки закончится в момент 4,148>4, поэтому эта заявка получает отказ.

Таблица 1

№ заявки, i Случай-ное число, ri -ln ri Время между двумя послед. заявками τi=0.2(ln ri) Момент поступ-ления заявки Тi=Тi-1i Момент Тi+0,5 окончания обслуживания заявки каналом Счетчик
обс. заявок отка-зов
1.       0,500      
2. 0,10 2,30 0,460 0,460   0,960    
3. 0,09 2,41 0,482 0,942 1,442      
4. 0,73 0,32 0,064 1,006   1,506    
5. 0,25 1,39 0,278 1,284     1,784  
6. 0,33 1,11 0,222 1,506 2,006      
7. 0,76 0,27 0,054 1,560   2,060    
8. 0,52 0,65 0,130 1,690        
9. 0,01 4,60 0,920 2,610 3,110      
10. 0,35 1,05 0,210 2,820   3,320    
11. 0,86 0,15 0,030 2,850     3,350  
12. 0,34 1,08 0,216 3,066        
13. 0,67 0,40 0,080 3,146 3,646      
14. 0,35 1,05 0,210 3,356   3,856    
15. 0,48 0,73 0,146 3,502     4,002  
16. 0,76 0,27 0,054 3,556        
17. 0,80 0,22 0,044 3,600        
18. 0,95 0,05 0,010 3,610        
19. 0,90 0,010 0,020 3,630        
20. 0,91 0,09 0,018 3,648 4,148      
21. 0,17 1,77 0,354 4,002 (стоп)        
              Ито-го х1=12

Испытания прекращают (в таблице записывают «стоп»), если момент поступления заявки Т>4. Из таблицы находим, что за 4 мин. всего поступило 20 заявок; обслужено х1=12 заявок.

Выполнив аналогично ещё пять испытаний, получим: х2=15, х3=14, х4=12, х5=13, х6=15.

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

=(2*12+13+14+2*15)/6=13,5

Пример. В одноканальную систему массового обслуживания с отказами поступает пуассоновский поток заявок. Время между моментами поступления двух последовательных заявок распределено по закону f(τ)=0,8е-0,8τ; время обслуживания заявок случайное и распределено по закону f1(t)=1,5е-1,5t. Найти методом Монте-Карло за время Т=30мин: среднее число обслуженных заявок; среднее время обслуживания одной заявки; вероятность обслуживания; вероятность отказа. Произвести 6 испытаний.

Решение. Время между моментами поступления двух последовательных заявок распределено по закону f(τ)=0,8е-0,8τ, поэтому значения τi разыграем по формуле: τi = -(1/0,8)ln ri =1,25(-ln ri).

Случайные числа ri берем из таблицы равномерно распределенных случайных чисел, начиная с первой строки снизу. Время обслуживания заявок распределено по закону f1(t)=1,5е-1,5t, поэтому значения ti разыгрываем по формуле:

ti = -(1/1,5)ln Ri = 0,67 (-ln Ri).

Случайные числа Ri, берем из той же таблицы, начиная с первой строки сверху. Пусть Т1=0 – момент поступления первой заявки. По случайному числу R1=0,10 разыгрываем длительность времени обслуживания первой заявки (в мин): t1 = 0,67 (-ln 0,10) = 0,67*2,30 = 1,54.

Момент окончания обслуживания первой заявки Т1=1,54=0+1,54=1,54. В счетчик обслуженных заявок записываем единицу.

По случайному числу r2=0,69 разыграем время (в мин) между моментами поступления первой и второй заявок: τi = 1,25 (-ln 0,69) = 1,25*0,37=0,46.

Первая заявка поступила в момент Т1=0. Следовательно вторая заявка поступит в момент Т21+0,46=0+0,46=0,46.

В этот момент канал занят обслуживанием первой заявки (0,46<1,54), поэтому вторая заявка получит отказ. В счетчик отказов записываем единицу.

По очередному случайному числу r3=0,07 разыгрываем время между моментами поступления второй и третьей заявок:

τ3 = 1,25 (-ln 0,07) = 1,25*2,66 = 3,32.

Вторая заявка поступила в момент Т2=0,46. Следовательно, третья поступит в момент Т32+3,32=0,46+3,32=3,78. В этот момент канал уже свободен (3,78>1,54), поэтому он обслужит третью заявку. В счетчик обслуженных заявок добавляем единицу.

Дальнейший расчет ясен из таблиц 2 и 3. Испытание заканчивается, когда момент поступления заявки Тi>30. Например, в первом испытании, как видно из табл. 2, 23-я заявка поступила в момент Т23=31,35>30, поэтому эту заявку исключаем («Стоп») и первое испытание заканчиваем [2].

Таблица 2

Номер заявки i Случайное число ri -ln ri Время между двумя последовательными заявками τi = 1.25 (-ln ri) Момент поступления заявки Тi=Ti-1i
1.      
2. 0,69 0,37 0,46 0,46
1. 0,07 2,66 3,32 3,78
2. 0,49 0,71 0,89 4,67
3. 0,41 0,89 1,11 5,78
4. 0,38 0,97 1,21 6,99
5. 0,87 0,14 0,18 7,17
6. 0,63 0,46 0,58 7,75
7. 0,79 0,24 0,30 8,05
8. 0,19 1,66 2,08 10,13
9. 0,76 0,27 0,34 10,47
10. 0,35 1,05 1,31 11,78
11. 0,58 0,54 0,68 12,46
12. 0,40 0,92 1,15 13,61
13. 0,44 0,82 1,02 14,63
14. 0,01 4,60 5,75 20,38
15. 0,10 2,30 2,88 23,26
16. 0,51 0,67 0,84 24,10
17. 0,82 0,20 0,25 24,35
18. 0,16 1,83 2,29 26,64
19. 0,15 1,90 2,38 29,02
20. 0,48 0,73 0,91 29,93
21. 0,32 1,14 1,42 31,35 (стоп)

 

Таблица 3

Номер заявки i Случайное число Ri -ln Ri Длительность обслуживания заявки ti=0,67 (-ln Ri) Момент Счетчик
Поступления заявки Начала обслуживания Окончания обслуживания Обслуженных заявок отказов
1. 0,10 2,30 1,54 1,54  
2.       0,46      
3. 0,09 2,41 1,61 3,78 3,78 5,39  
4.       4,67      
5. 0,73 0,32 0,21 5,78 5,78 5,99  
6. 0,25 1,39 0,93 6,99 6,99 7,92  
7.       7,17      
8.       7,75      
9. 0,33 1,11 0,74 8,05 8,05 8,79  
0,76 0,27 0,18 10,13 10,13 10,31  
11. 0,52 0,65 0,44 10,47 10,47 10,91  
12. 0,01 4,60 3,08 11,78 11,78 14,86  
      12,46      
14.       13,61      
15.       14,63      
16. 0,35 1,05 0,70 20,38 20,38 21,08  
17. 0,86 0,15 0,10 23,26 23,26 23,26  
18. 0,34 1,08 0,72 24,10 24,10 24,82  
19.       24,35      
20. 0,67 0,40 0,27 26,64 26,64 26,91  
21. 0,35 1,05 0,70 29,02 29,02 29,72  
22. 0,48 0,73 0,49 29,93 30,42    
Σ     11,71      

Таблица 4

Номер испытания i Поступило заявок N i пост Обслужено заявок N i обсл. Длительность обслуживания t i обсл Среднее время обслуживания tср i обсл= t i обсл /Ni обсл. Вероятность обслуживания Р i обсл= N i обсл / Ni пост Вероятность отказа Рiотк.= 1-Рi обсл.
1. 11,71 0,90 0,591 0,409
2. 8,80 0,52 0,680 0,320
3. 13,46 0,84 0,667 0,333
4. 12,19 0,81 0,682 0,318
5. 11,99 0,92 0,650 0,350
6. 9,57 0,50 0,704 0,296
Σ   4,49 3,974  

 

Используя таблицу 4, найдем искомые величины:

а) среднее число обслуженных за 30мин заявок Nобсл. =93/6=15,5;

б) среднее время обслуживания одной заявки tобсл. =4,49/6=0,748;

в) вероятность обслуживания Робсл.=3,974/6=0,662;

г) вероятность отказа Ротк. =1-Робсл.=1-0,662=0,338.

Таким образом, примерно 66% заявок будут обслужены, а 34% получат отказ.


Дата добавления: 2015-01-05; просмотров: 155; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.012 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты