ВІКІСТОРІНКА
Навигация:
Інформатика
Історія
Автоматизація
Адміністрування
Антропологія
Архітектура
Біологія
Будівництво
Бухгалтерія
Військова наука
Виробництво
Географія
Геологія
Господарство
Демографія
Екологія
Економіка
Електроніка
Енергетика
Журналістика
Кінематографія
Комп'ютеризація
Креслення
Кулінарія
Культура
Культура
Лінгвістика
Література
Лексикологія
Логіка
Маркетинг
Математика
Медицина
Менеджмент
Металургія
Метрологія
Мистецтво
Музика
Наукознавство
Освіта
Охорона Праці
Підприємництво
Педагогіка
Поліграфія
Право
Приладобудування
Програмування
Психологія
Радіозв'язок
Релігія
Риторика
Соціологія
Спорт
Стандартизація
Статистика
Технології
Торгівля
Транспорт
Фізіологія
Фізика
Філософія
Фінанси
Фармакологія


Системи масового обслуговання з очікуванням (чергою)

А Розглянемо одноканальну систему з необмеженою чергою (наприклад, телефон-автомат з однією будкою). Течія заявок, що поступають у СМО, має інтенсивність λ, а течія обслуговань – інтенсивність µ. Система може знаходитися в одному зі станів , , , …, , … за числом заявок, що знаходяться у СМО: − канал вільний; − канал зайнятий ( обслуговує заявку), черги немає; − канал зайнятий, одна заявка стоїть у черзі; … − канал зайнятий, ( k–1) заявок стоять у черзі і т.д.

Граф станів має такий вигляд

Перш ніж записати формули граничних ймовірностей відповідних станів, необхідно бути упевненим в їх існуванні, тому що у випадку коли час t→ ∞, черга може необмежено зростати. Доведено, що якщо , тобто середне число заявок, що надходять, менше середнього числа заявок, що обслужені (в одиницю часу), то граничні ймовірності існують. Якщо , то черга зростає до нескінченості.

Відповідні формули одержані аналогічно тому, як це було зроблено в 6.2.

Якщо , то

Граничні ймовірності утворюють спадаючу геометричну прогресію із знаменником , тобто ймовірність − найбільша. Це означає, що якщо СМО справляється з течією заявок ( при ), то найбільш ймовірним буде відсутність заявок в системі.

Далі визначимо показники ефективності системи:

 

1 Середне число заявок в системі.

 

Таким чином одержуємо

.

 

2 Середне число заявок у черзі.

Зауважимо, що черга утворюється зі стану .

тобто

.

 

3 Середній час перебування заявки в СМО

.

4 Середній час перебування заявки в черзі

 

.

 

5 Знайдемо ймовірність того, що в системі є хоча б одна заявка, тобто

.

6 Відносна пропускна спроможність Q=1, тому що заявка рано чи пізно буде обслужена.

 

7 Абсолютна пропускна спроможність А = λQ = λ.

Б Розглянемо n-канальну систему з необмеженою чергою. Течія заявок, що надходять в СМО, має інтенсивність λ, а течія обслуговань – інтенсивність µ.

Система може знаходитись в одному зі станів ..., занумерованих за числом заявок, що знаходяться у СМО, або у станах , в яких n каналів зайняті, r – число заявок у черзі.

 

 

Граф станів такої системи має такий вигляд

Можна довести, що при граничні ймовірності існують і мають вигляд

 

,

при 1≤ k ≤ n,

Для СМО, що розглядається використовуючи тіж прийоми, що і раніше, знайдемо показники ефективності системи,

1 Ймовірність того, що всі канали зайняті (тобто, що є черга)

.

2 Середнє число зайнятих каналів

3 Середнє число заявок в черзі

.

4 Середнє число заявок в системі

.

5 Середній час перебування заявки в черзі

.

6 Середній час перебування заявки в СМО

.

7 пропускна спроможність Q=1, абсолютна пропускна спроможність А= .

ВРозглянемо СМО с обмеженою чергою. Вони відрізняються від задач, що розглянуті вище, лише тим, що число заявок в черзі обмежено і не перевищує заданого числа m. Якщо нова заявка надходить в момент, коли всі місця у черзі заняті, то вона залишає СМО необслугованою. Для обчислення граничних ймовірностей і показників ефективності таких СМО використовується той самий підхід, що і раніше. Відповідні формули зведено в нижеподану таблицю.

 

Показники   Одноканальне СМО з обмеженою чергою довжини m n-канальна СМО з обмеженою чергою довжини
Граничні ймовірності
Ймовірність відмови
Відносна пропускна спроможність Q=1- Q=1-  
Абсолютна пропускна спроможність A=λQ=λ(1- A = λ (1- )
Середнє число заявок у черзі
Середнє число зайнятих каналів =  

 

Середній час перебування заявки в системі і в черзі обчислюється за формулами Ерланга , .

Приклади.

Задача 1 Заявки на телефонні перемовини в телеательє надходять з інтенсивністю λ=90 заявок за годину, а середня тривалість розмови Визначити показники ефективності роботи СМО (телефонного зв’язку) при наявності одного телефонного номера.

Розв’язання. Маємо λ=90 , . Тоді інтенсивність течії обслуговання

Відносна пропускна спроможність в цьому випадку , тобто в середньому тільки 25% заявок, що надходять, здійснять перемовини по телефону. Відповідно ймовірність відмови в обслугованні складає . Абсолютна пропускна спроможність СМО А=λQ=90*0,25=22,5 , тобто в середньому 22,5 заявки. Очевидно, що при наявності одного телефонного номера СМО погано справляється с течією заявок.

Задача 2 В умовах задачі 1 визначити оптимальне число телефонних номерів в телеательє, якщо умовою оптимальності вважати задоволення в середньому з кожних 100 заявок не менше ніж 30.

Розв’язання. За формулою маємо , тобто за час середної за тривалостю телефонної розмови надходить в середньому 3 заявки на перемовини.

Будемо поступово збільшувати число каналів (телефонних номерів) n=2,3,4,… і визначимо за відповідними формулами характеристики обслуговання. Наприклад, при n=2

.

Значення характеристик зведено до нижеподаної таблиці

 

Характеристика Число каналів
Q 0,25 0,47 0,65 0,79 0,90 0,95
A 22,5 42,4 58,8 71,5 80,1 85,3

 

За умовою оптимальності Q ≥ 0,9 ,тобто в телеательє потрібно встановити 5 телефонних номерів (в цьому випадку Q = 0,9). При цьому за годину буде обслуговано в середньому 80 заявок ( А=80,1), а середнє число зайнятих телефонних номерів (каналів) за формулою

.

Задача 3 В порту є один причал для розвантаження суден. Інтенсивність течії суден дорівнює 0,4 ( суден за добу ). Середній час розвантаження одного судна дорівнює 2 доби. Припускаємо, що черга може бути необмеженої довжини. Знайти показники ефективності роботи причалу, а також ймовірність того, що чекають розвантаження не більше, ніж 2 судна.

 

Розв’язання. Маємо , тобто черга на розвантаження не може нескінченно зростати і граничні ймовірності існують.

Ймовірність того, що причал є вільним , а ймовірність того, що він зайнят Ймовірність того, що у причала знаходяться 1,2,3 судна (тобто чекають розвантаження 0,1,2 судна), дорівнюють:

;

.

Ймовірність того, що чекають розвантаження не більше ніж 2 судна становить

=0,16+0,128+0,1024=0,3904.

Середнє число суден, що чекають розвантаження,

.

Середній час очікування розвантаження

.

Середнє число суден, що знаходяться біля причалу,

(діб).

Середній час перебування судна біля причалу

(діб).

Очевидно, що ефективність розвантаження суден невелика. Для того, щоб збільшити її, необхідно зменшення середнього часу розвантаження судна або збільшення числа причалів.

Задача 4В універсамі до вузла розрахунку поступає течія покупців з інтенсивністю 81 людина за годину (λ= 81 ). Середня тривалість обслуговування контролером – касиром одного покупця дорівнює 2 хвилини Визначити:

а) мінімальну кількість контролерів-касирів ( , при якій черга не буде зростати до нескінченості і відповідні характеристики обслуговування;

б) оптимальну кількість ( ) контролерів – касирів, при якій відносна величина затрат , пов’язана з витратами на утримання каналів обслуговування і з перебуванням покупців у черзі, що задається як ,буде мінімальною, і порівняти характеристики обслуговання при ;

в) ймовірність того, що в черзі буде не більше трьох покупців.

 

Розв’язання.

А За умовою λ= 81 = .

= .

Очевидно, що черга не буде зростати до нескінченості за умови , тобто n > =2,7

Таким чином, мінімальна кількість контролерів-касирів . Ймовірність того, що у вузлах розрахунку відсутні покупці, становить

, тобто в середньому 2,5% часу контролери-касири будуть простоювати. Ймовірність того, що у вузлі розрахунку буде черга, обчислимо за формулою

.

Середнє число покупців, що знаходяться у черзі,

.

Середній час очікування в черзі

.

Середнє число покупців у вузлі розрахунку

.

Середнє число перебування покупців у вузлі розрахунку

(хв.)

Середнє число контролерів – касирів, зайнятих обслугованням покупців, .

Абсолютна пропускна спроможність вузла розрахунка

А=λ=1,35 =81 .

Аналіз характеристик обслогування свідчить про значне навантаження вузла розрахунку при наявності трьох контролерів-касирів.

 

Б Відносна величина витрат при n=3

.

Розрахуємо відносну величину витрат при інших значеннях n.

 

Характеристика   Число контролерів-касирів
Ймовірність простою 0,025 0,057 0,065 0,067 0,067
Середній час (хв.) перебування в черзі 5,47 0,60 0,15 0,03 0,01
Відносна величина витрат 18,63 4,76 4,15 4,53 5,21

 

Як бачимо з таблиці, мінімальні витрати одержуємо, якщо

Визначимо характеристику ефективності при n=5.

.

; ; ; ; .

Як ми бачимо при n=5 в порівнянні з n=3 суттєво зменшилась ймовірність виникнення черги і середній час перебування в черзі і, відповідно, середне число покупців і середній час перебування їх у вузлі розрахунку . А середнє число зайнятих обслуговуванням касирів и абсолютно пропускна спроможність вузла розрахунку А не змінились (вони не залежать від n).

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

- у випадку n=3,

;

- у випадку n=5,

+ =0,986;

Задача 5 При умовах задачі 3 знайти показники ефективності роботи причалу, якщо відомо, що судно залишає порт (без розвантаження), за умови, що в черзі на розвантаження стоїть більше 3 суден.

Розв’язання. За умовою m=3 – це СМО з обмеженою чергою.

Ймовірність того, що причал вільний

.

Ймовірність того, що судно залише причал без розвантаження,

.

Відносна пропускна спроможність причалу

- .

Абсолютна пропускна спроможність причалу

Q = 0,4 * 0,878+0,351, тобто в середньому за добу розвантажується 0,35 суден.

Середнє число суден, що чекають розвантаження,

.

Середній час очікування розвантаження

.

Середнє число суден біля причалу

.

Середній час перебування судна буля причалу

.

Питання для самоперевірки

1 Що є предметом теорії масового обслуговування?

2 Наведіть приклади систем масового обслуговування.

3 Якому закону розподілу підкоряється течія заявок в СМО?

4 Якому закону розподілу підпорядковується час обслуговування заявки в СМО?

5 Охарактеризуйте одноканальну систему масового обслуговування з втратами, її стани, їх кількість.

6 Охарактеризуйте n-канальну систему масового обслуговування з втратами, її стани, їх кількість.

7 Охарактеризуйте одноканальну систему масового обслуговування з нескінченою чергою, її стани, їх кількість.

8 Охарактеризуйте n-канальну систему масового обслуговування з нескінченою чергою, її стани, їх кількість.

9 Охарактеризуйте одноканальну систему масового обслуговування із скінченою чергою довжини m, її стани, їх кількість.

10 характеризуйте n-канальну систему масового обслуговування із скінченою чергою довжини m, її стани, їх кількість.

11 За якими формулами обчислюються наступні характеристики системи масового обслуговування:

а) абсолютна пропускна спроможність системи;

б) відносна пропускна спроможність системи;

в) ймовірність відмови в обслуговуванні;

г) середнє число заявок в СМО;

д) середнє число заявок в черзі;

е) середній час перебування заявки в СМО;

ж) середній час перебування заявки в черзі;

з) середнє число зайнятих каналів.

Розглянути формули для всіх видів наведених вище систем.

 

Задачі для самостійної роботи

1 Розглядається одноканальна система з втратами з інтенсивністю числа заявок з/с. Система обслуговує дві заявки за секунду. Знайти характеристики системи.

2 Розглядається триканальна система МО з втратами, на вхід якої надходить пуасонівська течія замовлень з параметрами з/с,

з/с. Знайти ймовірність відмови та середнє число зайнятих каналів.

3 Одноканальна СМО з відмовами є однією телефонною лінією, на вхід якої надходить найпростіша течія викликів з інтенсивністю в/с. Середня тривалість розмови 3 хвилин. Час розмови має показників розподіл з . Знайти ймовірність простою, зайнятості, відмови системи, а також абсолютну пропускну спроможність і середнє число зайнятих каналів.

4 У стоматологічному кабінеті 3 лікарі, у коридорі є 3 стільці для чекання прийому. Течія клієнтів найпростіша з клієнтів за годину. Час обслуговування показників з параметром хвилин на клієнта. Якщо всі 3 стільці в коридорі зайняті, тоді клієнт не займає чергу (m=3). Знайти:

а) середнє число клієнтів, яких обслуговано за годину;

б) середню частку клієнтів, які обслуговані, з числа клієнтів, які прийшли;

в) середнє число зайнятих в коридорі стільців;

г) середній час, який клієнт перебуває в коридорі та на обслуговуванні.

5 Маємо двоканальну систему з відмовами, на вхід якої поступає течія заявок з інтенсивністю з/год. Математичне сподівання часу обслуговування однієї заявки дорівнює 0,8 год. Кожна заявка приносить прибуток 4 грн. Утримання кожного каналу потребує 2 грн за годину. З’ясувати, вигідно чи ні, збільшити число каналів до трьох?

6 Бензозаправна станція має 3 бензоколонки, в кожній з яких на заправку авто потрібно 1/12 год. Знайти середню довжину черги, середній час очікування в черзі, якщо течію авто на заправці можна заправці пуасонівською з:

а) авт./год.

б) авт./год.

7 Розглядається одноканальна система з необмеженою чергою.

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

Знайти:

а) ймовірність того, що канал є зайнятим у момент надходження заявки;

б) середній час очікування початку обслуговування;

в) середню довжину черги.

8 При якому співвідношенні між і середня довжина черги в одноканальній СМО буде не більше 1.

9 З’ясувати, чи достатньо одного каналу обслуговування з параметром =5 з/год для того, щоб при вхідній течії з параметром =4 з/год середній розмір черги не перевищував 3. Чи зміниться відповідь, якщо у два рази більшу течію заявок будуть обслуговувати два таких же канали ( ).

 

 

СПИСОК ЛІТЕРАТУРИ

 

1 Хемди А.Таха. Введение в исследование операций. – М.: Вильямс, 2007.-912 с.

2 Исследование операций в экономике / Под редакцией Н.Ш.Кремера. – М.: Банки и биржи, 2003.-395 с.

3 Глебов Н.И., Кочетов Ю.А., Плясунов А.В. Методы оптимизации. – Новосибирск.: НГУ, 2000.-105 с.


ЗМІСТ

Вступ..............................................................................................................3

Глава 1 Задача теорії розкладу...........................................................................4

Питання для самоперевірки........................................................................5

Задачі для самостійної роботи.....................................................................5

Глава 2 Екстремальні задачі на графах...............................................................5

2.1 Основні поняття......................................................................................5

2.2 Способи задання графа...........................................................................6

2.3 Дерева та ліс. Остовне дерево графа.....................................................8

2.4 Алгоритм побудови остовного дерева зв’язного графа.....................10

2.5 Знаходження найкоротшого шляху в орієнтованому графі...............11

2.6 Мережевий граф та його розрахунок....................................................16

2.7 Задача про максимальну течію в мережі..............................................21

Питання для самоперевірки.........................................................................27

Задачі для самостійної роботи.....................................................................29

Глава 3 Метод гілок та меж.................................................................................31

3.1 Основні поняття...................................................................................31

3.2 Задача про рюкзак................................................................................32

3.3 Задача комівояжера..............................................................................35

Питання для самоперевірки.........................................................................41

Задачі для самостійної роботи.....................................................................41

Глава 4 Задача про призначення (вибір).............................................................44

Питання для самоперевірки.........................................................................46

Задачі для самостійної роботи.....................................................................46

Глава 5 Теорія ігор................................................................................................47

5.1 Платіжна матриця. Нижня та верхня ціна гри..................................48

5.2 Розв’язання гри у мішаних стратегіях...............................................50

5.3 Ігри 2x2..................................................................................................52

5.4 Геометрична інтерпретація гри .................................................53

5.5 Розв’язання ігор та .........................................................55

5.6 Розв’язання ігор...................................................................................57

Питання для самоперевірки.........................................................................60

Задачі для самостійної роботи.....................................................................60

Глава 6 Елементи теорії масового обслуговування...........................................62

6.1 Основні поняття....................................................................................62

6.2 Системи масового обслуговування з відмовамию............................64

6.3 Системи масового обслуговання з очікуванням (чергою)...............67

Питання для самоперевірки........................................................................75

Задачі для самостійної роботи....................................................................76

Список літератури................................................................................................77

 

 

Навчальне видання

 

 

ІОХВИДОВИЧ Нона Юзефівна

ПОКЛОНСЬКИЙ Евген Васильович

ПОДКОПАЙ Ірина Василівна

ПОСИЛАЄВА Раїса Вікторівна

 

 

ДОСЛІДЖЕННЯ ОПЕРАЦІЙ

 

 

Навчально – методичний посібник

 

 

Відповідальний за випуск О.М. Стасенко

 

Редактор Л.І. Христенко

 

План 2010р., поз. 13. Формат 60х84 1/16. Папір друк. №2.

Підп. до друку Обл.-вид. арк. 4,0.

Надруковано на ризографі. Умов. друк. арк. 3,8

Тираж 50 прим. Зам. № 1741. Безкоштовно.

__________________________________________________________________

ХДТУБА, Україна, 61002, Харків, вул. Сумська, 40

__________________________________________________________________

 

Підготовлено та надруковано РВВ Харківського державного технічного університету будівництва та архітектури

 

© 2013 wikipage.com.ua - Дякуємо за посилання на wikipage.com.ua | Контакти