Дослідження операцій. Характеристики вхідного потоку вимог. Розподіли вірогідностей для тривалостей обслуговування (реферат)

Реферат на тему:

Дослідження операцій. Характеристики вхідного потоку вимог. Розподіли
вірогідностей для тривалостей обслуговування

План :

Характеристика потоку вимог.

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

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

КЛЮЧОВІ ПОНЯТТЯ ТА ТЕРМІНИ

дисципліна черги

вимога

умова стаціонарності

пріоритет

діаграма інтенсивностей

переходів

процес загибелі та народження

апроксимація СМО

очікувана інтенсивність

трафік-інтенсивність

стаціонарний режим

рівняння балансу

операційні характеристики

середня довжина черги

інтенсивність потоку

багатоканальна СМО

період зайнятості

ординарність

скінчена черга

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

системі

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

черзі

середня тривалість

обслуговування

імітаційне моделювання

граничні вірогідності

одноканальна СМО

Характеристика потоку вимог.

У більшості систем масового обслуговування є декілька обслуговуючих
приладів, а дисципліна черги, як правило, виявляється дуже складною.
Так, наприклад, перед тим, як обрати касу у супермаркеті, покупець
спочатку подивиться, скільки осіб знаходиться в кожній черзі і яка
кількість різноманітних продуктів знаходиться у стоячих. Крім того, він
спробує вирішити, котра із кас знаходиться найближче до потрібного йому
виходу, і відзначить, який із касирів працює швидше за інших.
Аналогічними міркуваннями керується і водій, що обирає один із пунктів
збирання за проїзд платною автомагістраллю з таким розрахунком, щоб
витратити на всю процедуру мінімальний час. Але іноді, дійсно, діє
дисципліна „першим прийшов — першим обслуговуєшся”. Такого характеру
черги виникають, наприклад, на бензозаправних станціях, біля кас
кінотеатрів, у майстернях, де відбувається терміновий ремонт взуття і
т.п.

Як уже відзначалося, побудова операційної моделі для описання реальної
ситуації завжди пов’язана з необхідністю прийняття ряду апроксимуючих
припущень. У випадку розв’язання задачі масового обслуговування
апроксимації є неминучими незалежно від того, якого типу модель при
цьому використовується — математична, імітаційна або комбінована. Часто
вдається одержати приблизне уявлення про операційні характеристики
складної системи шляхом аналізу деяких „екстремальних” або граничних
випадків.

Один із таких наближених методів полягає в наступному: СМО, що нараховує
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 ¬ o T

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 вимог

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *