Главная | Обратная связь

Теорія масового обслуговування

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

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

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

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

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

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

моментами надходження замовлень доволі різної величини. Система має один абсолютно надійний канал обслуговування. Тривалість виконання (обслуговування) замовлення є також випадковою величиною. Закони розподілу випадкових величин вважаються заданими і можуть бути різними. Закон розподілу вхідного потоку і закон розподілу тривалості обслуговування замовлень позначають, відповідно, кодами lλ_вх. і lkλ_обсл, де l –умовний номер закону; k – порядок закону Ерланга, λ – інтенсивність потоку замовлень. Вважають, що момент вивільнення каналу після обслуговування нульового замовлення необхідно позначати через t₀, інтервал моделювання – T, момент надходження – t_j j-го замовлення визначають так:

t_j=t_j-1+η

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

Результатом експерименту над моделлю системи масового обслуговування є оцінки математичних сподівань і середньоквадратичних відхилень таких величин як:

1. тривалість перебування обслуженого j-го замовлення у системі τ_ij:

2. тривалість перебування j-го замовлення у черзі τ_2j :

3. довжина черги для j-го замовлення mj :

4. тривалість простою каналу перед обслуговуванням j-го замовлення τ4j :

Використані у цих формулах величини:

– с – загальна кількість виконаних замовлень;

– j^* – загальна кількість замовлень, що надійшли у систему за весь період моделювання;

– τ_1j = τ_2j + τ_3j;

– τ_2j= t_1j – tj , де момент вивільнення каналу t1j після обслуговування j-го замовлення визначають так:

t_1j = tj + τ_2j + τ_3j,

де τ_3j – тривалість обслуговування j-го замовлення;

– τ_4j = tj – t_lj-1;

– P₁ – імовірність обслуговування замовлення: P₁=

– P₂ – імовірність відмови в обслуговуванні: P₂=1-

– P3 - імовірність обслуговування замовлення без очікування: P₃=

де а – загальна кількість заявок обслужених без очікування;

– P ₄ – імовірність перебування обслуженого замовлення у системі протягом часу, що не перевищує заданого: P₄= , де d-число замовлень, для яких виконується умова τ_1j ≤ τ5 (τ5 –

допустима тривалість перебування замовлення у системі).

Згідно з встановленою дисципліною очікування обслуговування, замовлення, щодо якого наведена умова не виконується, повинна вийти з системи. Розподіл вхідного потоку замовлень може бути досить різноманітним, наприклад: показниковим, Ерланга k-го порядку, Релея, нормальним, рівномірним тощо. Вхідні потоки, описані переліченими законами розподілу, є нерегулярними і ординарними, тобто за нескінченно малий проміжок часу до системи може надійти не більше одного замовлення. Ймовірне також надходження значної кількості замовлень, проміжок часу між якими і реєстрація замовлень будуть випадковими величинами, описаними за певним законом розподілу, який не обов'язково належить до зазначеного переліку.

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

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

що таких обмежень не враховують.

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

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

Першим дослідником теорії масового обслуговування є датський вчений А. Ерланг, який у 1909-1922 рр. здійснив дослідження з метою вирішення проблем створення телефонних мереж. О.Я. Хінчин у 1932-33 рр. сприяв розвиткові теорії масового обслуговування, розв'язуючи задачі в галузі багатоверстатного виробництва.

 

Теорія ігор.

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

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

розуміти конкурентну обстановку.

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

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

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

Людино-машинні ігри полягають у створенні структури, в якій органічно взаємодіють імітаційна модель певного процесу на ЕОМ та учасники гри.

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

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

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

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

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

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

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

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

Наступним базовим поняттям теорії ігор є поняття функції виграшу H_k, яка фактично є правилом, визначення очікуваного виграшу першого гравця у випадку вибору ним будь-якої стратегії зі своєї множини допустимої стратегії, а інший гравець вибере будь-яку стратегію зі своєї множини допустимих стратегій. Для коаліції k множину всіх стратегій позначають через S_k.

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

формування коаліції інтересів, множину яких позначають через Ri. Перевагу ситуації S’ над ситуацією S’’ для коаліції k записують як S’’>S”.

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

У випадку скінченності множини S1 і S2 (гра двох гравців) нормальну форму гри можна записати у вигляді матриці A=(a_ij), у якій елементи стрічок представляють стратегії першого гравця, а елементи стовпчиків представляють стратегії другого гравця.

Елементи a_ij матриці A є платою другого гравця першому у випадку вибору першим гравцем i-ої стрічки, а другим гравцем – j-го стовпчика. Очевидно, перший гравець вибирає стрічку з

метою максимізувати плату (свій виграш), а другий гравець вибирає стовпчик з метою мінімізувати плату (свій програш). Таку гру називають матричною. Оптимальним розв’язком цієї гри є сідлова точка, тобто елемент akl матриці A, який задовольняє

умову a_il≤a_kl≤a_kjдля будь-яких і та j.

У більшості матричних ігор відсутні сідлові точки, тобто не виконується умова:

max_i min_j a_ij ≤ min_j max_i a_ij .

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

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

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

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

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

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

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

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

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

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

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

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