Реферат на тему:
Дослідження операцій. Характеристики вхідного потоку вимог. Розподіли
вірогідностей для тривалостей обслуговування
План :
Характеристика потоку вимог.
Одноканальна модель з пуасонівським вхідним потоком і експоненційним
розподілом тривалостей обслуговування.
Багатоканальна модель з пуасонівським вхідним потоком і експоненційним
розподілом тривалостей обслуговування.
КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ
дисципліна черги
вимога
умова стаціонарності
пріоритет
діаграма інтенсивностей
переходів
процес загибелі та народження
апроксимація СМО
очікувана інтенсивність
трафік-інтенсивність
стаціонарний режим
рівняння балансу
операційні характеристики
середня довжина черги
інтенсивність потоку
багатоканальна СМО
період зайнятості
ординарність
скінчена черга
середній час перебування в
системі
середній час перебування в
черзі
середня тривалість
обслуговування
імітаційне моделювання
граничні вірогідності
одноканальна СМО
Характеристика потоку вимог.
У більшості систем масового обслуговування є декілька обслуговуючих
приладів, а дисципліна черги, як правило, виявляється дуже складною.
Так, наприклад, перед тим, як обрати касу у супермаркеті, покупець
спочатку подивиться, скільки осіб знаходиться в кожній черзі і яка
кількість різноманітних продуктів знаходиться у стоячих. Крім того, він
спробує вирішити, котра із кас знаходиться найближче до потрібного йому
виходу, і відзначить, який із касирів працює швидше за інших.
Аналогічними міркуваннями керується і водій, що обирає один із пунктів
збирання за проїзд платною автомагістраллю з таким розрахунком, щоб
витратити на всю процедуру мінімальний час. Але іноді, дійсно, діє
дисципліна „першим прийшов – першим обслуговуєшся”. Такого характеру
черги виникають, наприклад, на бензозаправних станціях, біля кас
кінотеатрів, у майстернях, де відбувається терміновий ремонт взуття і
т.п.
Як уже відзначалося, побудова операційної моделі для описання реальної
ситуації завжди пов’язана з необхідністю прийняття ряду апроксимуючих
припущень. У випадку розв’язання задачі масового обслуговування
апроксимації є неминучими незалежно від того, якого типу модель при
цьому використовується – математична, імітаційна або комбінована. Часто
вдається одержати приблизне уявлення про операційні характеристики
складної системи шляхом аналізу деяких „екстремальних” або граничних
випадків.
Один із таких наближених методів полягає в наступному: СМО, що нараховує
n обслуговуючих приладів, розглядається як „механічне” об’єднання n
одноканальних систем, що функціонують незалежно одна від іншої. Нехай,
наприклад, обслуговуюча система складається з п’ятьох приладів, а
інтенсивність вхідного потоку дорівнює 20 вимог/год. Тоді таку систему
приблизно можна розглядати як сукупність п’ятьох автономних систем з
одним обслуговуючим приладом, кожна з яких характеризується вхідним
потоком з інтенсивністю 4 вимоги/год. Цей метод є наближеним з двох
причин:
по-перше, передбачається, що вимога може потрапити на вхід будь-якої із
згаданих одноканальних підсистем з однаковою вірогідністю (незалежно від
довжини відповідної черги);
по-друге, потрапивши в одну з черг, вимога повинна залишатися саме в цій
обраній спочатку черзі.
Очікувана кількість вимог, що знаходяться у всіх автономних підсистемах
цієї гіпотетичної системи, і середній час перебування вимоги в ній
зазвичай перевищують значення відповідних операційних характеристик
реальних багатоканальних систем. Це пояснюється тим, що якщо б ми
застосували нашу гіпотетичну систему практично, то виявилося б, що
частіше, ніж це можна припустити, один з обслуговуючих приладів
знаходився б у вільному стані, у той час як вимоги простоювали у чергах
до інших приладів. Якщо ж припустити, що в системі з декількома
обслуговуючими приладами черга є єдиною і характеризується дисципліною
“першим прийшов – першим обслуговуєшся”, то відповідні апроксимуючі
оцінки очікуваної кількості вимог у системі і середнього часу,
витраченого кожною вимогою на очікування обслуговування, виявляться
заниженими в порівнянні з фактичними значеннями цих показників.
Можна відзначити, що системи з одним обслуговуючим приладом, як і
множина багатоканальних систем із єдиною чергою, що характеризується
дисципліною „першим прийшов – першим обслуговуєшся” зазвичай піддаються
математичному описанню і кількісному аналізу.
При розгляді загальних систем масового обслуговування передбачається, що
система функціонує протягом достатньо великого інтервалу часу, і після
закінчення перехідного періоду переходить в стаціонарний режим. Цей
режим функціонування обслуговуючої системи протиставляється перехідному
(або несталому) режиму, який превалює в початковий період функціонування
системи. Ми не розглядатимемо перехідні режими роботи систем масового
обслуговування, оскільки на практиці системи звичайно призначаються для
роботи протягом тривалого часу.
– вірогідність того, що в системі знаходиться n вимог.
. Ця залежність використовується потім при визначенні функціональних
характеристик обслуговуючої системи, таких як середня довжина черги,
середній час очікування і середній коефіцієнт використання обслуговуючих
пристроїв.
не визначене, оскільки не може відбуватися вибування клієнтів з
порожньої системи обслуговування.
…
Рис. 1. Діаграма інтенсивностей
При виконанні умов стаціонарності очікувані інтенсивності вхідного і
вихідного потоків в стані n (n > 0) повинні бути рівні. Оскільки стан n
може змінюватися лише до станів (n -1) і (n +1), отримаємо
співвідношення:
. (1)
Аналогічно,
.
(2)
Звідси, прирівнюючи ці дві інтенсивності, одержуємо наступне рівняння
балансу:
, n = 1, 2, … .
(3)
Як видно з рис.1, рівняння балансу, відповідне n = 0 , має вигляд:
.
(4)
. Таким чином, для n = 0 отримаємо:
.
(5)
Далі, для n = 1 одержуємо:
.
(6)
і спрощуючи отриманий вираз, маємо:
.
(7)
Використовуючи індукцію, приходимо до виразу:
, n=1, 2, …
(8)
. Такий процес є процесом загибелі та народження, оскільки об’єднує в
собі ці два процеси і описує функціонування СМО.
Одноканальна модель з пуасонівським вхідним потоком і експоненційним
розподілом тривалостей обслуговування.
Найпростішого одноканальною моделлю з вірогіднісним вхідним потоком і
процедурою обслуговування є модель, що характеризується показниковим
розподілом як тривалостей інтервалів між надходженнями вимог, так і
тривалостей обслуговування (тобто модель типу М/М/1). Таким чином,
передбачається, що щільність розподілу тривалостей інтервалів між
надходженнями вимог та щільність розподілу тривалостей обслуговування
мають вигляд відповідно:
.
(9)
, оскільки обслуговування здійснюється за допомогою одного
обслуговуючого пристрою.
Рис. 2. Діаграма інтенсивностей переходів для одноканальної системи з
необмеженою чергою
Нехай у деякий момент часу число вимог, що знаходяться в системі,
включаючи вже ті вимоги, що обслуговуються, дорівнює n . Припустимо, що
система починає функціонувати з моменту t = 0. Позначимо
. (10)
Взагалі, Рп (Т) залежить від кількості вимог і , що знаходилися в
системі в момент 0 ; в формулі (10) відповідний індекс для зменшення
захаращеності не наводиться.
(11)
.
2.
Перенесемо Рп(Т) із правої частини співвідношення (11) у ліву, розділимо
обидві частини цього співвідношення на h і спрямуємо h до нуля. За
допомогою цих перетворень одержимо наступний вираз:
при п >0 .
(12)
0 . Аналогічно неважко одержати рівняння:
для п =0 .
(13)
(14.13)
Система лінійних диференційних рівнянь (12) і (13) має єдиний розв’язок,
якщо задані відповідні початкові умови (тобто кількість вимог і , що
знаходилися в системі у момент 0 ). Цей розв’язок називається несталим,
оскільки він безпосередньо залежить від Т (нестаціонарний режим роботи).
виявляється скінченим, то система досягає стану статистичної рівноваги.
Назвемо граничні значення Рп сталими або стаціонарними вірогідностями.
*
b
„
°
?
3/4
ph
&
*
,
????,
b
d
?
T¬oT
O
R
T
x
z
?
?
?
°
Oe
O
?????????
@
??
???
відображає наступну властивість системи: якщо кількість вимог, що
знаходяться в ній, визначається в довільно обраний момент часу t за
допомогою розподілу Рп , то для будь-якого h > 0 Рn є також
вірогідністю виявлення в системі п вимог у момент Т + h . Значення Рп
можна також інтепретувати як частку часу довільно великого періоду,
протягом якого в системі знаходиться п вимог. Якщо виконується умова
,
(14)
є трафік-інтенсивністю.
Розв’язок, що відповідає рівноважному стану Рп (Т) = Рп при будь-якому
Т, легко знайти з умови
dPn / dT = 0 , яка відображає той факт, що Рп не залежить від Т . Таким
чином, для визначення Рр потрібно лише прирівняти до нуля похідні, що
стоять у лівих частинах рівнянь (12) і (13). У результаті отримаємо:
при п = 1,2,3,…,
(15)
при п = 0.
(16)
Система рівнянь у скінчених різницях (15) і (16) легко вирішується
методом математичної індукції. Почавши з розгляду (16), отримуємо:
.
(17)
Потім переходимо до (15), розглядаючи послідовно значення п =1, 2, 3, …;
в результаті отримаємо:
.
(18)
,
(19)
, так що
, п = 0,1,2,3,…
(20)
(геометричний розподіл), причому
(21)
.
також є тією часткою повного часу з початку функціонування системи,
протягом якої прилад не простоює, то цю величину називають іноді
коефіцієнтом використання або коефіцієнтом завантаженості приладу,
істотним є те, що така інтерпретація зберігає силу навіть у тому
випадку, коли не вводиться ніяких конкретизуючих припущень ні щодо
розподілу тривалостей інтервалів між надходженнями, ні щодо розподілу
тривалостей обслуговування (тобто коли модель належить до типу GI /G/1
).
Якщо через Рп (Т\і) позначити розв’язання рівнянь (20) і (21) за умови,
що в початковий момент часу t = () у черзі знаходилося і вимог, то можна
показати, що
.
і малих значеннях і .
Багатоканальна модель з пуасонівським вхідним потоком і експоненційним
розподілом тривалостей обслуговування.
Зрозуміло, що в переважній більшості випадків СМО є багатоканальними, і,
отже, моделі з S обслуговуючими приладами (де S > 1) є важливими.
Узагальнимо отримані результати на випадок декількох обслуговуючих
пристроїв. Постульована при цьому дисципліна черги виглядає дещо
спрощено для більшості ситуацій, із якими доводиться зустрічатися в
дійсності. Проте отримані результати можна розглядати як дуже корисні,
оскільки вони принаймні дозволяють у найпершому наближенні оцінити
функціональні характеристики складніших СМО.
Нехай S = число обслуговуючих приладів.
(1)
Будемо припускати, що
а) щільність розподілу тривалостей інтервалів між надходженнями вимог
має вигляд
,
(2)
, причому тривалості обслуговування взаємонезалежні як для окремо
узятого приладу, так і для системи загалом.
Діаграма інтенсивностей переходів для цієї системи наведена на рис. 3.
Рис. 3. Діаграма інтенсивностей переходів для багатоканальної системи з
необмеженою чергою
.
Рівняння в скінчених різницях, аналогічні рівнянням для випадку
одноканальної СМО, що визначають Рп в умовах сталого режиму, мають такий
вигляд:
, (3)
,
Розв’язки системи рівнянь мають наступний вигляд:
,
(4)
,
.
(5)
).
.
.
.
Операційні характеристики.
Коли Рп знайдені, більшість операційних характеристик цієї моделі
обчислюються за допомогою елементарних алгебраїчних операцій. До числа
дуже важливих характеристик СМО належить вірогідність того, що всі
прилади виявляться зайнятими:
. (6)
визначає частку часу, протягом котрої вимоги фактично перебувають у
системі.
Введемо в розгляд наступні величини:
. (7)
Тоді
. (8)
Отримаємо:
, (9)
, (10)
. (11)
Для розглянутої моделі
(12)
і, отже, розділивши обидві частини співвідношення (12) на l ,
отримаємо:
. (13)
У правій частині (13) перший доданок є тривалістю очікування в черзі, а
другий – тривалістю процедури обслуговування.
вимог, що обслуговуються, за одиницю часу.
на вході кожній із груп однакові.
Аналіз на чутливість.
Р [всі обслуговуючі прилади зайняті] зростає при спаданні S , те ж
саме відбувається при цьому і із середньою кількістю вимог, що очікують
у черзі, і із середньою тривалістю очікування початку обслуговування.
Проте середня кількість вимог, шо знаходяться в системі, а також і
середній час перебування вимоги в системі скорочуються при спаданні S .
і S і в результаті знайти необхідний оптимальний варіант. Якщо задача
має просту структуру, розв’язок може бути отриманий в аналітичному
вигляді, поданий за допомогою таблиць і графіків, то полегшують процес
оптимізації.
Дисципліна черги на грунті системи пріоритетів.
. Як і в попередньому випадку, визначимо:
.
(14)
, що гарантує можливість асимптотичного переходу системи в стан
рівноваги. Тоді
. (15)
.
, тим менше буде середня тривалість очікування для вимог обох
категорій.
Література
Карлин С. Математические методы в теории игр, программировании и
экономике. -М.: Мир, 1964.
Вентцель Е.С. Введение в исследование операций. Сов. радио, 1964.
Пономаренко О.І., Пономаренко В.О. Системні методи в економіці, бізнесі
й менеджменті. -К.: Либідь, 1995.
Пономаренко О.І., Перестюк М.О., Бурим В.М. Основи математичної
економіки. -К.: Інформтехніка, 1995.
Горелик В.А., Ушаков М.А. Исследование операций. -М.: Машиностроение,
1986.
PAGE
PAGE 1
0
1
2
n-1
n
Очікувана інтенсивність
вхідного потоку в стані n
n+1
Очікувана інтенсивність
вихідного потоку в n
Вірогідність того, що в момент Т в системі знаходиться n вимог
Нашли опечатку? Выделите и нажмите CTRL+Enter
