Лекція Математичний опис потоків



Скачати 152.52 Kb.
Дата конвертації02.01.2017
Розмір152.52 Kb.
Лекція 3. Математичний опис потоків.

Вступ. Вхідний потік вимог (заявок)

Процес надходження в систему масового обслуговування потоку вимог є ймовірністним і представляє собою потік однорідних або неоднорідних подій, які надходять через випадкові проміжки часу. Потік вимог можна представити у вигляді графіка однієї із реалізацій випадкової функції, яка приймає лише цілі невід"ємні значення. При цьому кожна із реалізацій є невипадковою функцією з конкретними часовими інтервалами між появою подій (рис 1). Випадкові часові інтервали між настанням подій в потоці можуть підпорядковуватися різним законам розподілу. Але в більшості робіт по теорії масового обслуговування, особливо прикладного характеру, розглядається пуасонівський (найпростіший) потік, в якому ймовірність надходження в проміжок часу t рівно k вимог задається формулою Пуассона

(1)

де λ>0 – щільність потоку вимог (параметр потоку).

Це поясняється такими обставинами:

1) для інших видів потоків не отримані поки прості формульні залежності кількісної оцінки якості функціонування систем масового обслуговування;

2) до найпростішого потоку системам масового обслуговування іноді пристосуватися важче. Тому при розрахунку засобів обслуговування в цьому випадку ми ставимо їх роботу в більш тяжкі умови. Якщо засоби обслуговування розраховувати на цей тяжкий випадок, то обслуговування системою інших випадкових потоків вимог з однаковою щільністю надходження вимог буде надійнішою. Такий висновок отримав І. Н. Коваленко;

Рис 1.Графік випадкової функції, яка приймає дискретні цілі невід'ємні значення.


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

Найпростіший потік має три основні властивості: стаціонарність, відсутність післядії і ординарність. Випадковий потік називається стаціонарним, якщо ймовірність надходження визначеної кількості вимог за визначений проміжок часу залежить від його величини і не залежить від початку його відрахунку на осі часу. Це означає, що якщо на часовій осі відкласти рівні, интервали часу τ, які не перетинаються (рис. 2), то ймовірність появи в цих інтервалах визначеного числа вимог залежить для даного потоку від величини τ і не залежить від положення цього інтервалу на часовій осі (від моментів часу t1, t2, t3, ...). Таким чином, два найпростіших потока відрізняються один від одного тільки своїми параметрами. Тому для завдання найпростішого потоку достатньо задати тільки його параметр λ.

Рис. 2 Стаціонарний пошук однорідних подій



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

Ординарність потоку вимог означає практичну неможливість появи двох і більше вимог в один і той же момент часу. Якщо позначити ймовірність появи більш як однієї вимоги за відрізок часу Δt через , то умова ординарності запишеться так:

при
Таким чином, найпростіший потік – це стаціонарний, ординарний потік без післядії. Виведення рівнянь найпростішого потоку широко представлене в літературі по теорії масового обслуговування. Важливою характеристикою потоку є його інтенсивність, яка визначається як математичне очікування числа вимог, які надходять за одиницю часу.

Математичне очікування числа вимог, які надходять за проміжок часу (0, t), дорівнює

(3)

Звідси, математичне очікування числа вимог в одиницю часу або інтенсивність, яка отримується при t=1, дорівнює





В багатьох задачах фізичні умови появи вимог такі, що припущення про їх ординарність і відсутність післядії цілком прийнятні. В той же час припущення стаціонарності викликають великі сумніви, а іноді заздалегідь помилкові. Такі потоки будемо називати нестаціонарними найпростішими потоками. Для потоків цього типа ймовірність появи k вимог за час Δt залежить не тільки від величини Δt, але й від моменту t0, який є початком цього проміжку. В цьому випадку ймовірність появи k вимог за час Δt позначимо із вказаним початком проміжності t0.

Графічне представлення постійної в часі щільності потоку вимог


Рис 3 Графік щільності потоку вимог є постійний у часі

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

Наприклад, представимо потік пасажирів в метро. Тут пікові значення інтенсивності потоку віддзеркалюють збільшення числа пасажирів в часи «пік». Можливі й інші закономірності зміни щільності вимог, які поступають, і зв'язані з явищами сезонного характеру та іншими причинами. Щільність надходження вимог змінна у часі

Рис. 4 Графічне представлення змінної в часі щільності надходження вимог.

Розглянемо характеристики вхідного потоку зі змінною щільністю. Математичне очікування числа вимог, які надійшли за період (t0, t) рівне

(4)

а середня інтенсивність потоку рівна



(5)

Якщо миттєвий параметр потоку в проміжку (t0, t) постійний, тобто , то



Визначимо миттєву інтенсивність як границю





Ймовірність появи за час Δt = t – t0 хоча б однієї вимоги визначається із виразу

(6)

а ймовірність хоча б двох вимог



(7)

Тоді вимога ординарності в кількісних тер­мінах може бути виражена у вигляді



при (8)

а миттєве значення параметра буде рівне



при

Найпростіший нестаціонарний потік є частковим випадком так називаних «фінітних» потоків, для яких повинна виконуватися умова


Під СМО розуміють динамічну систему, призначену для ефективного обслуговування деяких заявок (вимог), які потребують цього обслуговування. На практиці зустрічаються випадки, коли окремі споріднені СМО утворюють об’єднання, діяльність яких спрямована на досягнення тієї ж мети, що і кожної окремої СМО, але у більш широких масштабах, або у поглибленому виді. Сукупність таких взаємозалежних СМО називається мережею масового обслуговування. Прикладами таких мереж є мережа автозаправних станцій однієї фірми-постачальника паливних продуктів, мережа закладів швидкого харчування, система медичних закладів, тощо.

Теорія масового обслуговування (ТМО) – це розділ прикладної кібернетики і дослідження операцій, предметом якого є вивчення й організація процесів масового обслуговування у відповідних системах. Результати досліджень, проведених з використанням ТМО спрямовуються на покращення організації СМО та їх мереж, визначення раціональних режимів використання обладнання СМО, створення нових ефективних технологій обслуговування, підвищення якості обслуговування, тощо.

Ознайомимося більш докладно з предметом ТМО, а також її основними задачами, що вирішуються.

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

Саме при створенні проекту майбутньої СМО, а також у процесі її вдосконалення неоціненну поміч можуть надати методи ТМО. Для розробки проекту СМО необхідно зробити ряд попередніх розрахунків, вміти знайти співвідношення між очікуваним імовірним числом потенційних “клієнтів” та запланованими виробничими потужностями системи, оцінити вплив випадкових факторів, які можуть викликати збої у процесі обслуговування і т.д., тобто одержати відповіді на цілий ряд запитань, вирішення яких саме і є справою ТМО. Навіть самий поверхневий екскурс у будь-яку сферу людської діяльності покаже, що подібних завдань, пов’язаних з організацією СМО або підвищенням ефективності їх функціонування, виникає досить багато. Розподіл електроенергії між споживачами, організація постачання промислових підприємств, співставлення устаткування різних типів при проектуванні автоматичних потокових ліній і багато чого іншого - все це сфери, у яких допомагає або може допомогти ТМО.

Наведені вище міркування дозволяють нам тепер більш чітко уявити, що являє собою ТМО як метод дослідження і сформулювати її науково-практичну спрямованість наступним чином.



Метою ТМО є розробка математичних методів для оцінювання основних характеристик процесів масового обслуговування та результатів функціонування обслуговуючої системи.

Предметом ТМО є кількісна сторона процесів, пов'язаних із масовим обслуговуванням, а об’єктом – системи масового обслуговування та процеси, які у них відбуваються.

Зважаючи на викладене, суть дослідження СМО полягає у вирішенні наступної проблеми: необхідно знайти такий варіант організації СМО та режиму її роботи, щоб забезпечити, з одного боку, якісне обслуговування „клієнтів”, а з другого боку – найкращі результати роботи цієї системи з точки зору її власників. Але для того, щоб розв’язати поставлену проблему необхідно вирішити дві задачі:

- оцінити якість функціонування СМО;

- знайти методи поліпшення результатів її роботи.

Дві вказані вище задачі визначають два основні напрями дослідження систем з використанням методів ТМО:

- задача аналізу, зміст якої полягає у встановленні значень основних результуючих характеристик функціонування СМО із заданою структурою та параметрами її елементів. У ТМО така задача класифікується як пряма і ставить на меті надати об’єктивну оцінку процесу, який досліджується;

- задача синтезу оптимальної СМО. Метою вирішення цієї задачі є обґрунтування такої структури СМО та параметрів її елементів, які забезпечать найкращі результуючі показники її функціонування.

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



Комплекс масового обслуговування. Під комплексом масового обслуговування (КМО) надалі будемо розуміти всю сукупність об'єктів, які беруть участь у процесі масового обслуговування. Ці об'єкти можуть мати різну фізичну природу, однак кожен з них відіграє у процесі масового обслуговування свою роль, і для функціонування цього процесу необхідна його присутність у КМО. Узагальнена структура КМО подана на рис. 1. За ходом викладення матеріалу даного розділу будемо звертатися до цієї схеми з метою надання визначень елементам КМО та їх місцю у процесі масового обслуговування.

Як було зазначено у попередньому матеріалі процеси масового обслуговування у різних сферах діяльності людини полягають у задоволенні потреб у обслуговуванні великої кількості однорідних вимог. Вимогою або заявкою у ТМО називається запит на задоволення якої-небудь потреби „клієнта”. При цьому термін „клієнт” використовується в широкому розумінні, тобто як об'єкт, що вимагає своєрідної „послуги”, яку може надати йому система, до якої він звернувся. „Клієнтом” може бути і покупець у магазині, і пасажир на зупинці транспорту, і корабель у порту. Зазначимо, що термін „вимога” („заявка”), як правило, ототожнюється не тільки із самим запитом на обслуговування, а і з його носієм – „клієнтом”. Надалі у матеріалах будемо використовувати тільки термін “вимога” для позначення елемента КМО, який надійшов до нього на обслуговування. Під обслуговуванням будемо розуміти процес задоволення потреби „клієнта”.



Джерела вимог. Якщо аналізувати побудову КМО то не можна не поставити собі питання про те, звідки у ньому виникають вимоги на обслуговування, а саме – про джерело надходження вимог. Джерелом вимог у КМО називається їхня першопричина, яка може мати саму різну природу. Так, для приведених вище прикладів вимог джерелами є: множина всіх потенційних покупців, пасажирів, кораблів взагалі і підмножина кораблів, які заходять у даний порт. Можна сперечатися з приводу того, чи варто відносити джерело вимог до складу КМО, чи вважати його елементом довкілля, яке оточує КМО. У такій суперечці можна порекомендувати наступний компроміс. Якщо у планах нашого майбутнього дослідження КМО є місце ідеї впливу на характеристики джерела вимог для оптимізації функціонування КМО, то введення джерела до складу КМО є обов’язковим. Якщо такі дослідження не передбачаються, то віднесемо джерело вимог до довкілля і будемо розглядати його характеристики як незмінні у процесі усіх досліджень. Для повноти подання складу елементів КМО на рис. 1 наведено джерело вимог. Характеристиками джерел вимог є їх:

- обсяг, тобто число вимог, які можуть у них міститися;

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

Щодо першої характеристики джерела, то можна згадати приклад з множиною усіх літаків, які знаходяться у даний момент у польоті, та множиною тих літаків, які знаходяться зоні аеропорту і мають у ньому приземлитися. І в тому, і в іншому випадку ці множини літаків можна вважати джерелами вимог. Але для задачі організації обслуговування літаків у даному аеропорту першу множину літаків формально можна вважати нескінченною, а другу – обмеженою. З цього випливає, що джерела вимог за своєю характеристикою обсягу можуть бути класифіковані при розв’язку задач ТМО на обмежені (кінцевого обсягу) і необмежені (нескінченного обсягу).



Вимоги, які потребують обслуговування однакового виду і яке проводиться за однаковою технологією, називаються однорідними. З огляду на це, за характеристикою складу вимог, які у них містяться, джерела вимог поділяються на однорідні і неоднорідні.

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



Вхідний потік вимог у комплексі масового обслуговування. Потоком вимог (заявок) у ТМО називається їхнє просторове переміщення у структурі КМО, яке відбувається у часі. Оскільки в рамках ТМО фізична природа вимог не має значення, а перехід кожної такої вимоги від елемента до елемента КМО розцінюється як подія, то потоки вимог розглядаються як потоки подій, які функціонують у часі.

Потік вимог, які потребують свого обслуговування і для цього надходять в обслуговуючу систему, називається вхідним потоком вимог (рис. 1 – потік ). Такий потік у КМО формується джерелом вимог з їх множини, яка міститься у ньому.

Прикладів вхідних потоків можна привести багато. Це може бути інформація, яка надходить на опрацювання до ЕОМ; клієнти, які потребують побутового обслуговування у відповідному закладі; судна, які заходять у порт, тощо.

Ознайомившись з продуктом джерела вимог – їх вхідним потоком – перейдемо до характеристики основного елемента КМО – системи масового обслуговування.



Система масового обслуговування. Система масового обслуговування є основним структурним елементом КМО, який реалізує технологію обслуговування заявок, тобто задовольняє їх потребу в такому обслуговуванні. Технологія обслуговування заявок в СМО здійснюється за рахунок виконання деякої послідовності операцій із застосуванням необхідного для цього технічного устаткування та виконавців, які є елементами обслуговуючої системи. В СМО ці елементи носять назву обслуговуючих пристроїв або обслуговуючих апаратів (на рис. 1 – елементи ). Слід зазначити, що такий термін у ТМО слід вживати у широкому розумінні, оскільки у деяких випадках операція обслуговування може виконуватися одним виконавцем, у деяких – їх групою, а в деяких – технічним пристроєм. Таким чином під терміном „обслуговуючий пристрій” (ОП) надалі ми будемо розуміти такий елемент СМО, який у даний момент функціонування системи може обслуговувати тільки одну вимогу. На практиці, як правило, у СМО у процесі обслуговування заявки бере участь не один ОП, а деяка їх кількість, причому ця їх кількість є обмеженою.

Обслуговуючі пристрої, які здатні задовольняти тільки однакові запити заявок, називаються однорідними. Наприклад, перукарню можна розглядати як СМО, яка складається з обмеженої кількості однорідних ОП – перукарів. Природно, що кожному майстрові властиві свої індивідуальні якості обслуговування – швидкість та якість виконання операцій, комунікабельність та творчий підхід до вимог клієнтів, тощо. Але вважаємо, що кожен з виконавців здатний виконувати всі операції, які від нього вимагає даний процес обслуговування клієнтів. Тому властивість однорідності ОП не зумовлює того, що всі вони мають однакові технологічні характеристики.

Якщо декілька ОП (не обов'язково однорідних) обслуговують вимогу послідовно (що зумовлено прийнятою для даної СМО технологією обслуговування), то таку їхню сукупність називають каналом або лінією обслуговування. При цьому етап процесу обслуговування, здійснюваний одним апаратом, називається фазою або стадією обслуговування. Наприклад, при звертанні до магазину вимога (“клієнт”) проходить дві фази обслуговування, кожна з яких виконується окремим ОП (продавцем і касиром).

Для відсутності плутанини у термінології надалі під вихідним потоком вимог будемо розуміти лише ту послідовність вимог, які повністю пройшли обслуговування у КМО. Потоки вимог, які не були обслуговані взагалі або були обслуговані частково будемо називати потоком вимог з відмовами на обслуговування. Як видно потоки можуть формуватися з вимог, які:

- ще не надійшли до накопичувача („не бажають” очікувати у черзі – потік );

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

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

Рис. 1. Узагальнена структура комплексу масового обслуговування






Класифікація систем масового обслуговування. Із наведених вище прикладів можна зробити висновок, що організація процесу обслуговування у СМО залежить не тільки від його характеристик (наявність чи відсутність накопичувачів, ступінь надійності ОП, їх продуктивність, тощо), але й від поведінки „клієнтів”, яка визначається наявністю у них резерву часу на очікування у черзі. Якщо припустити, що – це час, який відведений комплексом кожній вимозі на очікування у черзі, то за цією характеристикою КМО можна класифікувати на:

- СМО „з відмовами” (іноді їх називають СМО „з втратами”). Для таких комплексів ;



- СМО „з очікуванням” (так звані СМО „з чергою”). Для них ;

- СМО змішаного типу, де ( – відповідно мінімальний та максимальний терміни, які відведено комплексом вимогам на очікування у черзі свого обслуговування).

Наступною важливою характеристикою СМО є число каналів обслуговування, які у них присутні. За цією характеристикою СМО поділяються на одноканальні () та багатоканальні ().

В теоретичних дослідженнях перепускна здатність СМО іноді вважається необмеженою, тобто число її каналів обслуговування приймається нескінченно великим (). Система масового обслуговування з необмеженою перепускною здатністю будемо називати ідеальною.

Наступна характеристика СМО пов’язана з організацією надходження вимог на обслуговування. Мова йде про так звану її „доступність”, під якою розуміють принцип формування системою дозволу на зайняття вимогою, яка потребує обслуговування, якого-небудь з вільних каналів. За цією характеристикою розрізняють повнодоступні та неповнодоступні СМО. В СМО першого типу ніяких обмежень на зайняття вільних каналів вимогами, які очікують свого обслуговування, немає. У неповнодоступних СМО можуть вводитися різні обмеження структурного та часового характеру, які регламентують певний порядок надходження вимог на обслуговування. Як варіанти структурних обмежень у організації роботи СМО можна навести такі приклади: у довільний момент часу доступним для вимоги буде вважатися вільний канал, який має найменшу (або найбільшу) продуктивність обслуговування або деякі з вільних каналів можуть бути призначені лише для вимог певного рангу, а для вимог інших рангів будуть недоступними, тощо. Якщо організація роботи СМО має часові обмеження, то це може означати, що у деякі проміжки часу її функціонування навіть вільні канали можуть бути недоступними для надходження до них вимог („зачинено на обід”). Можливі і інші обмеження на доступність каналів СМО



Дослідження властивостей імітаційної моделі. На цьому етапі оцінюються точність імітації явищ, усталеність результатів моделювання, чутливість обраних критеріїв якості ОМ до зміни значень параметрів моделі. Одержати ці оцінки в ряді випадків буває дуже складно. Однак без успішних результатів цієї роботи, довіри до адекватності моделі не буде ні в розробника ІМ, ні в її замовника. У різних дослідників у залежності від виду ІМ склалися різні інтерпретації понять основних характеристик моделі: точності, усталеності, стаціонарності, чутливості. Поки не існує загальноприйнятої теорії імітації явищ на ЕОМ. Кожному досліднику приходиться покладатися на свій досвід організації процесу імітації і на своє розуміння особливостей ОМ. Дамо один з варіантів визначень основних характеристик результатів роботи ІМ.

Точність імітації явищ являє собою оцінку впливу стохастичних елементів на функціонування моделі СС.

Усталеність результатів моделювання характеризується збіжністю значень обраних параметрів моделювання з деякими визначеними величинами при збільшенні часу моделювання варіанта складної системи

Стаціонарність режиму моделювання характеризує собою деяку сталу рівновагу процесів у моделі системи, коли подальша імітація безглузда, оскільки нової інформації з моделі дослідник не одержить і продовження імітації практично приводить тільки до збільшення витрат машинного часу. Таку можливість необхідно передбачити і розробити спосіб визначення моменту досягнення стаціонарного режиму моделювання.



Чутливість ІМ оцінюється як величина мінімального приросту обраного критерію якості, який обчислюється за статистиками моделювання, при послідовному варіюванні параметрів та змінних моделювання на всьому діапазоні їхнього існування.

КМО можна класифікувати на:

- СМО „з відмовами” (іноді їх називають СМО „з втратами”). Для таких комплексів ;

- СМО „з очікуванням” (так звані СМО „з чергою”). Для них ;

- СМО змішаного типу, де ( – відповідно мінімальний та максимальний терміни, які відведено комплексом вимогам на очікування у черзі свого обслуговування


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка