Математичне моделювання та оптимізація системи масового обслуговування

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

Системи масового обслуговування можуть бути одноканальними або багатоканальними.

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

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

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

Завдання оптимізації - завдання вибору з безлічі можливих варіантів найкращого, оптимального. Оптимізація - від латинського слова «Оптімус» - найкращий - пошук найкращого, пошук найкращого проектного виробу. [4]

Кожне завдання оптимізації обов'язково повинна мати три компоненти:

невідомі (що шукаємо, тобто, план);

обмеження на невідомі (область пошуку);

цільова функція (мета, для якої шукаємо екстремум).

Математична модель, та яка визначена за допомогою математичних формалізмів. Математична модель не є точною, а є ідеалізацією.

Визначення параметрів стану - завдання моделювання. Визначення змінних проектування - завдання проектування або завдання оптимізації. [3]

Виявлення основних особливостей, взаємозв'язків і кількісних закономірностей

Функціонування будь-якої системи масового обслуговування можна представити через всі можливі стани її та інтенсивність переходу з одного стану в інший. Основними параметрами функціонування СМО є ймовірності її стану, тобто можливості наявності n вимог в системі - Р _n.

Важливим параметром функціонування СМО є також середнє число вимог, що знаходяться в системі N _syst, тобто в черзі на обслуговування, а також середня довжина черги N _och. Вихідними параметрами, що характеризують систему масового обслуговування, є: число каналів обслуговування - n; число вимог - m; інтенсивність надходження однієї вимоги на обслуговування - λ, тобто число надходжень вимог в одиницю часу; інтенсивність обслуговування вимог - μ.

Багатоканальна СМО з відмовами

Розглянемо n-канальну СМО з відмовами. Будемо нумерувати стану системи за кількістю зайнятих каналів (або, що в даному випадку те ж, за кількістю заявок, пов'язаних з системою). Стану будуть:
S ₀ - всі канали вільні, S ₁ - зайнятий рівно один канал, інші вільні,

S _k - зайняті рівно k каналів, інші вільні, S _n - зайняті всі n каналів.

Граф станів СМО представлений на рис.1. Розмістимо граф, тобто проставимо у стрілок інтенсивності відповідних потоків подій. По стрілках зліва на право систему переводить один і той же потік - потік заявок з інтенсивністю l.

Рис.1

Якщо система перебувати в стані S _k (зайнято k каналів) і прийшла нова заявка, система переходить (перескакує) у стан S _{k +1}

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

Нехай система перебувати в стані S ₁ (зайнятий один канал). Тоді, як тільки закінчитися обслуговування заявки, що займає цей канал, система перейде в S _0; значить, потік подій, що переводить систему по стрілці S ₁ ® S _0, Має інтенсивність m. Очевидно, якщо обслуговуванням зайнято два канали, а не один, потік обслуговувань, що переводить систему по стрілці S ₂ ® S _1, буде вдвічі інтенсивніше (2m); якщо зайнято k каналів - в k разів інтенсивніше (km). Проставимо відповідні інтенсивності у стрілок, що ведуть справа наліво.

З рис.1 видно, що процес, що протікає в СМО, являє собою окремий випадок процесу загибелі і розмноження.

Користуючись загальними правилами, можна скласти рівняння Колмогорова для ймовірностей станів:

Рівняння (1) називаються рівняннями Ерланга. Природними початковими умовами для їх вирішення є:

p ₀ (0) = 1; p ₁ (0) = p ₂ (0 )=...= p _n (0) = 0 (у початковий момент система вільна).

Інтегрування системи рівнянь (1) в аналітичному вигляді досить складно; на практиці такі системи диференціальних рівнянь зазвичай вирішуються чисельно, на ЕОМ. Таке рішення дає нам всі ймовірності станів p ₀ (t), p ₁ (t ),..., p _n (t) як функції часу.

Природно, нас найбільше цікавитимуть граничні ймовірності станів p _0, p ₁ ,..., p _k ,..., p _n, що характеризують сталий режим роботи СМО (при t ® ¥). Для знаходження граничних ймовірностей скористаємося вже готовим рішенням завдання, отриманими для схеми загибелі і розмноження. Згідно з цим рішенням,

У цих формулах інтенсивність потоку заявок l і інтенсивність потоку обслуговувань (для одного каналу) m не фігурують окремо, а входять тільки своїм ставленням l / m. Позначимо це відношення l / m = r і будемо називати величину r "наведеної інтенсивністю" потоку заявок. Фізичний сенс її такий: величина r являє собою середнє число заявок, що приходять у СМО за середній час обслуговування однієї заявки.

З урахуванням цього позначення, формули (2) приймуть вид:

Формули (3) називаються формулами Ерланга. Вони висловлюють граничні ймовірності всіх станів системи залежно від параметрів l, m і n (l - інтенсивність потоку заявок, m - інтенсивність обслуговування, n - число каналів СМО).

Знаючи всі ймовірності станів p _0, p ₁ ,..., p _k ,..., p _n, можна знайти характеристики ефективності СМО: відносну пропускну здатність q, абсолютну пропускну здатність А і вірогідність відмови P _отк.

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

Ймовірність того, що заявка буде прийнята до обслуговування (вона ж відносна пропускна здатність q) доповнює P _отк до одиниці:

Абсолютна пропускна здатність:

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

Величину k ^- можна обчислити безпосередньо через ймовірності p _0, p ₁ ,..., p _n за формулою:

як математичне сподівання дискретної випадкової величини, що приймає значення 0,1 ,..., n з вірогідністю p _0, p ₁ ,..., p _n. проте значно простіше висловити середнє число зайнятих каналів через абсолютну пропускну здатність А, яку ми вже знаємо. Дійсно, А є не що інше, як середнє число заявок, що обслуговуються в одиницю часу, один зайнятий канал обслуговує в середньому за одиницю часу m заявок; середнє число зайнятих каналів вийде діленням А на m:

або, переходячи до позначення l / m = r,

Мета даної роботи полягає у розробці моделі, що імітує роботу поста ГИБДД. Таке завдання було поставлено для того, щоб виявити ефективність роботи системи обслуговування поста ГИБДД для подальшої її оптимізації.

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

Розглянемо детальніше математичну модель роботи поста ГИБДД як системи масового обслуговування. Для вирішення завдання було прийнято припущення, що черга клієнтів обмежена, і, отже, ця модель є СМО з обмеженою чергою, де n - кількість каналів обслуговування. Також приймаємо припущення, що всі потоки подій (випадкові події) в системі є Марковський. Нагадаємо, що випадковий процес, що протікає в системі, називається Марківським, якщо для будь-якого моменту часу t 0 імовірнісні характеристики процесу в майбутньому залежать тільки від його стану в даний момент t 0 і не залежать від того, коли і як система прийшла в цей стан.

Потік порушників в систему надходять з інтенсивністю . Тоді

Ймовірність відмови .

Відносна пропускна здатність .

Абсолютна пропускна здатність .

Середнє число заявок, пов'язаних з системою .

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

Кількість, що очікують у черзі .

Час в черзі .

Час в системі .

В результаті планується одержати найбільш наближену до реальності модель роботи поста ГИБДД. Практична значимість даної роботи очевидна: модель дозволяє шляхом експериментів виявити найбільш оптимальний розподіл ресурсів для підвищення ефективності його роботи. Також можна припустити застосування даної моделі на реальному об'єкті.

ПОСТАНОВКА ЗАВДАННЯ

На шосе перевіряє швидкість пост ГИБДД. На посту протягом дня працює 5 інспекторів. Робочий день інспектора дорівнює 10 годинам. Режим роботи - раз на три доби. Витрати на одного інспектора рівні 35000рублей в місяць (зарплата, податки, спецобмундірованіе та ін.) Інспектор оформляє протокол приблизно за 12 хвилин. Протягом години швидкісний режим порушують в середньому 35 водіїв. Інспектори зупиняють машину, якщо чекають оформлення не більше чотирьох машин. Середній розмір штрафу дорівнює 250 рублям.

Визначити параметри роботи системи. Знайти відсоток оштрафованих порушників. Яке середній час, який витрачає водій в очікуванні оформлення протоколу? Скільки, в середньому, машин очікує оформлення? Яка середня сума від штрафів за місяць? Які місячні витрати на пост ДПС? Визначити «прибуток» поста за місяць. (Ознайомча завдання).

Визначити оптимальне (з точки зору прибутку) число інспекторів на посту при збереженні інших умов завдання.

Є можливість орендувати обладнання, що дозволяє прискорити процес оформлення протоколу. Вартість оренди обладнання для одного інспектора лінійно залежить від його ефективності і зображення на графіку. Максимально можлива швидкість - 10 протоколів на годину. Визначити оптимальні витрати на обладнання при незмінних інших умовах завдання (число інспекторів одно п'яти) і при числі інспекторів, отриманих в п. 2. Визначити параметри роботи системи при цих витратах.

Рис. 2.

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

РІШЕННЯ ЗАДАЧІ

Формалізуємо завдання.

Дану задачу можна віднести до завдань СМО з обмеженою чергою. Максимальна довжина черги дорівнює m = 5. Інтенсивність потоку вимог (в якості якого виступає потік порушників) дорівнює водіїв на годину. Початково є п'ять каналів обслуговування (п'ять інспекторів знаходяться на посту одноразово): n = 5. Середній час обслуговування одним каналом (середній час, який витрачає інспектор на один автомобіль) дорівнює , Тоді авт. / хв авт. / год.

Знайдемо параметри роботи вихідної завдання.

30,4% порушників не буде оштрафовано.

Відсоток оштрафованих порушників дорівнює 69,6%.

В середньому 24,35 автомобілів буде оштрафовано на годину.

Майже всі інспектори (4,8 з 5) зайняті.

Знайдемо середню довжину черги:

У середньому очікує оформлення 3 машини.

Час в черзі і системі:

години = 7,2 хв.

Таким чином, середній час, який витрачає водій в очікуванні оформлення протоколу, так само 7,2 хв.

Знайдемо середню суму штрафів за місяць . Так як авт. / год., сума штрафу в середньому дорівнює 250 руб., в місяці 30 днів по 10 робочих годин, то:

тис.руб.

Оскільки витрати на одного інспектора рівні f = 35000 руб. / мес., А інспекторів по тричі по 5 чоловік, то місячні витрати на пост ДПС рівні:

руб. = 525 тис. руб.

«Прибуток» поста складається з суми штрафів («доходу») мінус витрати на інспекторів («витрати»). Таким чином, місячна «прибуток» поста дорівнює:

тис.руб.

Визначити оптимальне число інспекторів можна двома способами. По-перше, вручну обчислити всі цікавлять величини. По-друге, всі величини можна обчислити в пакеті MS Excel.

Складемо таблицю 1. У рядках 1-5 записані вихідні дані завдання. У стовпці А з 10-ї по 24-й рядок введені числа інспекторів.

Таблиця 1.

В останньому стовпці отримано значення прибутку поста за місяць. Побудуємо графік цієї величини залежно від числа інспекторів (рис.3). Тип діаграми - точкова.

Рис. 3.

З графіка і за значеннями у таблиці 1 видно, що максимальний прибуток досягається при значенні n = 8 і дорівнює 1635431 руб. в місяць.

Висновок: За інших постійних параметрах, вигідніше найняти 24 інспектора (по 8 інспекторів одночасно).

Визначимо оптимальні капіталовкладення на прискорення оформлення протоколів при п'яти інспекторів. Потрібен формалізувати задачу.

Як видно з графіка (рис.2), вартість оренди обладнання для одного інспектора (будемо її позначати R) лінійно залежить від швидкості оформлення протоколу (інтенсивності ), Тобто

.

Знайдемо значення параметрів R ₀ і R _1. При авт. / год R = 0. При авт. / год R = 2000 руб. / день. Тоді:

Звідки отримуємо:

Т.ч.

.

При цьому

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

і отже

. (1)

При цьому

Місячна «прибуток» поста в цьому випадку буде обчислюватися за формулою:

(2)

При n = 5 отримуємо:

(Руб. / мес.). (3)

Підставляючи (1) в (3) отримуємо:

(4) (тис. руб. / мес.) При

Визначивши, при якому досягається максимум функції прибутку , Ми визначимо по формулі (1) оптимальні витрати на оренду обладнання.

Розпишемо функцію :

Однак, аналізувати такі громіздкі формули незручно. Аналіз проведемо в MS Excel. У табл. 2 показані проведені розрахунки.

У рядках 1-4 наведені дані завдання.

У стовпці А з 7 по 42 рядки протабулювати параметр

Таблиця 2.

Побудуємо графік прибутку (рис. 4):

Рис. 4.

Уточнимо оптимальне значення параметра , Додатково розбивши проміжок на більш дрібні інтервали. Графік функції на цьому проміжку наведено на рис.5.

Рис. 5.

Фрагмент уточненої таблиці наведено в таблиці 3.

Таблиця 3.

З графіків і за таблицею 3 з високим ступенем точності можемо прийняти як оптимального значення , А оптимальна прибуток дорівнює приблизно 1764000 17 рублів на місяць.

Визначимо, при яких витратах на оренду ми отримаємо такий прибуток. З (1):

руб. / день.

Це дозволить оформляти протоколи з інтенсивністю

маш. / год.

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

Необхідно провести оптимізацію за двома параметрами n і .

Маємо функцію від двох змінних. Будемо використовувати формулу . (1)

Визначивши, за яких і n досягається максимум функції прибутку , Ми визначимо по формулі (1) оптимальні витрати на оренду обладнання.

Складемо таблиці 4 - 5. У таблиці 4 - n = 3, n = 4, n = 5, n = 6, в таблиці 5 - n = 7, n = 8, n = 9, n = 10. Розглянемо проміжок

Таблиця 4.

Таблиця 5.

Рис. 6.

З значень таблиці і графіка, оптимальне число інспекторів дорівнює 4. Побудуємо для n = 4 уточнений графік (рис.7).

Рис. 7.

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

руб. / день.

Інтенсивність роботи інспектора дорівнює:

маш. / год.

Висновок: маючи можливість міняти число інспекторів на посту і орендувати прискорюючу техніку, потрібно організувати роботу так, щоб на посаді одночасно знаходилося 4 інспектора, і для кожного з них орендувати техніки на 2000 рублів в день. Це дозволить отримати прибуток 1779337 карбованців на місяць.

ВИСНОВОК

В даному курсовому проекті представлена ​​тема "Математичне моделювання та оптимізація системи масового обслуговування". Системи масового обслуговування мають величезне практичне застосування в наш час, що показано в розглянутому прикладі.

Метою даного курсового проекту було визначення

- Параметрів роботи системи;

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

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

- Параметрів роботи системи при парі оптимальних параметрів.

Дане завдання є СМО з обмеженою чергою або СМО з очікуванням. У даній роботі в першій частині рішення задачі проводиться її аналіз, тобто визначаються основні параметри функціонування СМО при незмінних, наперед заданих вихідних характеристиках. Вихідні характеристики - це інтенсивність потоку вимог , Максимальна довжина черги m, кількість каналів обслуговування n, середній час обслуговування одним каналом , Інтенсивність обслуговування вимог . У ході вирішення першої частини завдання ми визначили такі основні параметри функціонування СМО: інтенсивність навантаження , Граничні ймовірності і ймовірність відмови , Відносну пропускну здатність Q, абсолютну пропускну здатність , Середнє число заявок, пов'язаних з системою , Середню довжину черги D, час у черзі W _0, час у системі W _c, середню суму штрафу за місяць З _штр, витрати на один канал f, витрати на посаду на місяць F, прибуток поста Z. При вирішенні завдання використовувалися формули Ерланга. У другій, третій і четвертій частинах рішення задачі проводився синтез - оптимізація СМО. Тут дії спрямовані на пошуки оптимальних параметрів СМО. У другій і третій частинах визначаються оптимальне число інспекторів на посту і витрати на обладнання відповідно, при незмінних інших умовах завдання. Розглядаються функції і , Будуються їхні графіки. У четвертій частині рішення задачі проводиться оптимізація за двома параметрами, тобто розглядається функція .

Модель СМО реалізована за допомогою програми MS Excel. Всі розрахунки виконувалися за допомогою даної програми, що спростило процес вирішення завдань оптимізації. У процесі декількох реалізацій роботи СМО були отримані результати функціонування системи. На основі отриманих даних були побудовані графіки, що дозволяють провести дослідження роботи СМО. За допомогою графіків проведено аналіз отриманих даних і зроблені висновки про роботу системи. З графіка (рис.3) і за значеннями у таблиці 1 видно, що максимальний прибуток досягається при значенні n = 8 і дорівнює 1635431 руб. в місяць. За інших постійних параметрах, вигідніше найняти 24 інспектора (по 8 інспекторів одночасно). З графіків (рис.4, 5) і за значеннями таблиць 2 і 3 видно, що якщо на посаді працює одночасно 5 інспекторів, то найбільш вигідно вкласти 1581 рубль в день в оренду техніки для кожного інспектора. Тоді прибуток за місяць буде оптимальною і рівної приблизно 1764 тис. 17 рублів. З графіків (рис.6, 7) і таблиць 4,5 видно, що маючи можливість міняти число інспекторів на посту і орендувати прискорюючу техніку, потрібно організувати роботу так, щоб на посаді одночасно знаходилося 4 інспектора, і для кожного з них орендувати техніки на 2000 рублів в день. Це дозволить отримати прибуток 1779337 карбованців на місяць.

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

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

Основна література:

1. Клейнрок Л. Теорія масового обслуговування. М.: Машинобудування, 1979.

2. Матвєєв В.Ф., Ушаков В.Г. Системи масового обслуговування. М.: Изд-во МГУ, 1984.

3. Рад Б.А., Яковлєв С.О. Моделювання систем, М: Вища школа, 1985.

Періодичні видання:

4. Іголкін В.М. Про оптимізацію однієї системи масового обслуговування / / Питання механіки і процесів управління. Вип.15. СПб.: Вид-во СПбГУ, 1992.

Інтернет-ресурси:

5. http://lib.vvsu.ru/books/Bakalavr01/page0220.asp

6. http://masteroid.ru/content/view/909/42/