Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ,

МОЛОДІ ТА СПОРТУ УКРАЇНИ

Ніжинський державний університет

імені Миколи Гоголя

Кафедра прикладної математики, інформатики

та освітніх вимірювань

Дипломна робота

Моделювання систем масового обслуговування

Ніжин - 2013



• Вступ
• Розділ 1
• 1.1 Основні елементи математичної моделі СМО
• 1.2 Класифікація та характеристики основних елементів моделі СМО
• Розділ 2
• 2.1 Характеристика систем масового обслуговування по видах
• 2.1.1 Одноканальні СМО
• 2.1.2 Багатоканальні СМО
• 2.3 Задачі моделювання
• 2.3.1 Поняття та класифікація моделі
• 2.3.2 Способи побудови моделей
• 2.3.3 Задачі моделювання
• 2.4 Методи моделювання
• 2.4.1 Процес та методи моделювання
• 2.4.2 Системний підхід до побудови моделей
• Розділ 3
• 3.1 Імітаційне моделювання
• 3.2 Введення в SIMULINK
• Розділ 4
• 4.1 Імітаційне моделювання роботи каси
• 4.2 Імітаційне моделювання потоку Пуассона
• Висновок
• Література

• Вступ
• В будь-якій практичній діяльності людина стикається із станом очікування. Це може бути черга в касу (аеропорт, супермаркет), стоянки технічного обслуговування автомобілів, черга на телефонній станції, на складі під час завантаження або розвантаження товару, або чого-небудь іншого. Всі ці і багато інших випадків вказують на масовість і обслуговування. Вивченням таких ситуацій займається теорія масового обслуговування. У теорії систем масового обслуговування об'єктом є запит, який необхідно задовольнити будь то розмова по телефону, покупка квитка або ремонт автомобіля. Робота будь-якої системи масового обслуговування полягає в обслуговуванні потоку вимог, що надходить до неї (виклики абонентів прихід покупців в магазин, вимоги на виконання роботи в майстерні і т. д.).

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

Створення моделі - кропіткий і творчий процес, що вимагає від дослідника не тільки глибоких теоретичних знань з різних математичних та технічних дисциплін, але й творчого підходу до розв'язання задач, уміння генерувати певні евристики, що відповідають глибинній суті досліджуваного об'єкта. Відомий науковець з імітаційного моделювання систем Роберт Шеннон навіть назвав свою книгу "Имитационное моделирование - искусство и наука". Моделювання, як спосіб пізнання використовувалось людиною з давніх часів. Але з появою комп'ютера, моделювання систем збагатилось появою принципово нових методів моделювання як: імітаційне моделювання, еволюційне моделювання, методи групового урахування аргументів. Моделі і методи моделювання використовуються при створенні систем автоматизованого проектування, систем прийняття рішень, систем автоматизованого керування, систем штучного інтелекту. Потрібність у розв'язанні задач моделювання систем виникає не тільки у науковця, але й у проектувальника, виробника, ділової людини під час повсякденної праці.

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

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

Для досягнення поставленої мети в дипломній роботі вирішуються наступні завдання:

· формування цілі та задачі дослідження, а також аналіз об'єкта дослідження;

· вибір програмного засобу для представлення моделі;

· реалізація моделі - найбільш відповідальний етап моделювання системи;

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

Розділ 1

1.1 Основні елементи математичної моделі СМО

Мал. 1. Структура СМО

Математична модель системи масового обслуговування включає такі елементи:

· вхідній потік вимог, що надходять на обслуговування;

· черга, яка складається з вимог, що очікують на обслуговування;

· система обслуговування;

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

· характеристики якості системи;

· механізм (дисципліна) обслуговування

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

1.2 Класифікація та характеристики основних елементів моделі СМО

Системи масового обслуговування класифікуються за різноманітними ознаками. На мал.2 зображена узагальнена схема класифікації СМО за різними ознаками.



Мал. 2. Класифікація СМО

Класифікація СМО за складом:

- одноканальні ( з одним обслуговуючим пристроєм);

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

За складом обслуговуючих пристроїв багатоканальні СМО поділяють на:

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

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

Класифікація за часом перебування вимоги в системі до початку обслуговування:

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

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

Очікування може бути обмеженим і необмеженим. Обмежуватись очікування може часом очікування або довжиною черги.

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

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

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

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

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

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

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

Потік замовлень називається ординарним, якщо події надходять по одному, а не групами. Наприклад, потік поїздів у метро є ординарним, а потік вагонів - не ординарним.

Потік замовлень називається найпростішім (або стаціонарним пуасоновським), якщо він одночасно стаціонарний, ординарний і не має наслідків.

Черга - ряд замовлень, що очікують на обслуговування. Розрізняють дві її характеристики - довжину (місткість) і дисципліну черги.

Довжина черги може бути скінчена і нескінчена. Так, наприклад, у комп'ютерному класі, що має N комп'ютерів, сумарна кількість потенційних замовлень на їх ремонт не перевищує N, отже, черга не може бути більша за N-1.

Дисципліна черги визначає принцип, відповідно до якого обслуговуються замовлення в системі. Частіше усього використовуються дисципліни черги, обумовлені наступними правилами:

· першим прийшов - перший обслуговуєшся;

· прийшов останнім - обслуговуєшся першим;

· випадковий добір замовлень;

· добір замовлень за критерієм пріоритетності;

· обмеження часу очікування моменту настання обслуговування (має місце черга з обмеженим часом очікування обслуговування, що асоціюється з поняттям "припустима довжина черги").

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

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

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

(1)

При дослідженні СМО можуть розв'язуватися:

1) задачі аналізу СМО - визначення характеристик якості обслуговування залежно від параметрів і властивостей вхідного потоку вимог, параметрів і структури системи обслуговування і дисципліни обслуговування;

2) задачі параметричного синтезу - визначення параметрів системи обслуговування при заданій структурі залежно від параметрів і властивостей

потоку вимог, дисципліни і якостей обслуговування;

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



Розділ 2

2.1 Характеристика систем масового обслуговування по видах

Введемо позначення:

i - кількість клієнтів в системі обслуговування (в черзі і на обслуговуванні);

лi - інтенсивність надходження в систему клієнтів за умови, що в системі вже знаходиться i клієнтів;

µi - інтенсивність вихідного потоку обслужених клієнтів за умови, що в системі знаходиться i клієнтів;

Pi - ймовірність того, що в системі знаходиться i клієнтів; с - зведена інтенсивність завантаження каналу (або інтенсивність завантаження каналу). Вона виражає середню кількість замовлень, що надходять за час обслуговування одного замовлення. Обчислюється за формулою

(2)

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

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

Нехай маємо один канал, на який надходить потік замовлень з інтенсивністю л. Вихідний потік має інтенсивність м. Граф станів цієї системи масового обслуговування наведений на мал.3.



Мал. 3. Граф стану одноканальної СМО з відмовами

Дана система може приймати два стани:

S0 - канали вільний;

S1 - канал зайнятий (йде обслуговування замовлення).

Граничні ймовірності системи:

P0 - ймовірність стану S0

(3)

P1 - ймовірність стану S1

(4)

Одноканальні СМО з необмеженим очікуванням черги.

На мал. 5 зображений граф станів даної системи

Мал. 5. Граф станів одноканальної СМО з необмеженим очікуванням черги

Стани СМО мають таку інтерпретацію:

S0 - "канал вільний";

S1 - "канал зайнятий" (черги немає);

S2 - "канал зайнятий" (одне замовлення знаходиться в черзі);

........................

Si - "канал зайнятий" ( i-1 замовлення знаходиться в черзі);

........................

SN - "канал зайнятий" ( N-1 замовлення знаходиться в черзі)

........................

Граничні ймовірності системи:

(7)

(8)

Одноканальні СМО з обмеженою чергою

Граф стану даної системи наведений на мал.4.

Мал. 4. Граф стану одноканальної СМО с обмеженим очікуванням

Стани СМО мають таку інтерпретацію:

S0 - "канал вільний";

S1 - "канал зайнятий" (черги немає);

S2 - "канал зайнятий" (одне замовлення знаходиться в черзі);

........................

Si - "канал зайнятий" ( i-1 замовлення знаходиться в черзі);

.....................

SN - "канал зайнятий" ( N-1 замовлення знаходиться в черзі).

Граничні ймовірності системи:



(5)

і=0,1…. N (6)

Багатоканальна СМО з необмеженим очікуванням черги

Нехай маємо C каналів для обслуговування з потоком замовлень інтенсивністю л та інтенсивністю обслуговування м.

Граф станів даної системи зображений на мал. 8

Мал. 8. Граф станів багатоканальної СМО з необмеженим очікуванням черги

Система може приймати один із станів:

S0 - "всі канали вільні";

S1 - "один канал зайнятий, інші N-1 канал вільні";

S2 - "два канали зайняті, інші N-2 канали вільні";

........................

Si - "i каналів зайняті, інші N-i канали вільні;

........................

SC - "всі канали зайняті, черги немає";

SC+1 - "всі канали зайняті, одне замовлення знаходиться в черзі";

SC+2 - "всі канали зайняті, два замовлення знаходиться в черзі";

........................

Слід звернути увагу на те, що в даній системі інтенсивність потоку обслуговування із збільшенням кількості замовлень від 0 до C збільшується від µ до Cµ відповідно, тому що відповідно збільшується кількість каналів обслуговування. При кількості вимог, більшій за C, інтенсивність обслуговування залишається рівною Cµ.

Сталий режим функціонування даної СМО можливий за умови

(15)

Формули для розрахунку ймовірностей виникнення станів даної

системи мають вигляд:

(16)

(17)

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

Нехай маємо N каналів для обслуговування, потік замовлень на обслуговування має інтенсивність л, а інтенсивність обслуговування дорівнює м.

Мал. 6. Граф станів багатоканальної СМО з відмовами

Дана СМО має такі стани:

S0 - "всі канали вільні";

S1 - "один канал зайнятий, інші N-1 канал вільні";

S2 - "два канали зайняті, інші N-2 канали вільні";

........................

Si - "i каналів зайняті, інші N-i канали вільні;

........................

SN - "всі канали зайняті, замовлення отримує відмову в обслуговуванні".

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

(9)

(10)

Багатоканальна СМО з обмеженою чергою

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

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

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

Граф стану даної СМО представлений на мал. 7.



Рис. 7. Граф станів багатоканальної СМО з обмеженням на довжину черги

Дана СМО має стани:

S0 - "всі канали вільні";

S1 - "один канал зайнятий, інші C -1 канал вільні";

S2 - "два канали зайняті, інші C-2 канали вільні";

........................

SС - "C каналів зайняті (тобто, всі, що є у розпорядженні), черги немає;

SC+1 - "C каналів зайняті, одне замовлення знаходиться в черзі";

........................

SN - "всі C каналів зайняті, N-C замовлень знаходиться в черзі";

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

(11)

Інтенсивність обслуговування відповідно

(12)

Граничні ймовірності розраховуються за формулами:



(13)

(14)

2.3 Задачі моделювання

2.3.1 Поняття моделі

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

В загальному випадку модель має структуру, зображену на мал. 9. Тут X - множина вхідних змінних системи, Y - множина вихідних змінних системи, P - множина параметрів, F - функція, функціонал, алгоритм або формальне представлення залежності змінних Y від змінних X.

Мал. 9. Загальна структура моделі

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

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

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

2.3.3 Способи побудови моделей

Існують два способи побудови моделей. При першому способі в результаті ретельного вивчення системи встановлюються закони функціонування системи, які потім відтворюються за допомогою моделі. Поведінку системи, таким чином, досліджують на моделі. Параметри моделі P в цьому випадку пов'язані з реальними процесами, що протікають в системі, і мають фізичну інтерпретацію. Тому моделі такого типу називають фізичними моделями.

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

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

2.3.4 Задачі моделювання

Однакові об'єкти моделювання в залежності від цілі та задачі дослідження можуть мати різні моделі.

Серед задач моделювання виділимо такі задачі: задача моделювання, задача управління, задача ідентифікації, задача оптимізації, задача прогнозування.

Задача моделювання (або пряма задача) полягає у відшуканні значень вихідних змінних Y при відомих значеннях вхідних змінних X, відомій моделі F та визначених параметрах P (див. мал.9).

Задача управління (або зворотна задача) полягає у відшуканні таких значень вхідних змінних Х, що забезпечують задані значення вихідних змінних Y при відомій моделі F та фіксованих значеннях параметрів P.

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

У постановці задачі оптимізації відомими являються модель F, множина можливих вхідних значень X та критерій оптимізації К, а від дослідника вимагається знайти значення вхідних змінних X, значення параметрів P, та значення вихідних змінних Y, що задовольняють заданому критерію оптимізації К.

Задача прогнозування формулюється так, що при відомих для дослідника значеннях вхідних та вихідних значень моделі Xt, Yt до моменту часу t та заданому часі прогнозування Т потрібно визначити модель F та її параметри P, які забезпечують найліпший прогноз Yt+Т .

Стисло визначення методів моделювання представлені на мал.10.

Задачі моделювання

Моделювання: відомі X, P, F ? знайти Y
Управління: відомі Y, P, F ? знайти X
Ідентифікації: відомі X, Y, множина F? знайти f?F, P
Оптимізації: відомі F, критерій K ? знайти P, X, Y
Прогнозування: відомі Xt, Yt, Т ? знайти F, P, Yt+Т

Мал. 10. Задачі моделювання

масовий обслуговування моделювання імітаційний

2.4 Методи моделювання

2.4.1 Процес та методи моделювання

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

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

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

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

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

На мал. 12 представлений процес моделювання з урахуванням можливих повернень до попередніх етапів моделювання.

Мал. 12. Процес моделювання



Серед великої кількості методів моделювання, що існують, виділимо такі методи: аналітичне моделювання, математичне моделювання, імітаційне моделювання.

Моделювання аналітичне, якщо представлення залежності F вихідних змінних Y від вхідних її змінних X має аналітичний вигляд, тобто представлений у вигляді відомих аналітичних функцій. Нагадаємо, що функція називається аналітичною, якщо вона розкладається у ряд Тейлора. Аналітичні функції диференційовані безліч разів і тому до них можуть застосовуватись методи математичного аналізу. Перевагою цього методу моделювання є можливість отримання залежності Y=f(X) в явному вигляді і застосування до неї методів класичного математичного аналізу. Якщо є можливість побудувати аналітичну модель системи, то завжди віддають перевагу цьому методу моделювання.

Зауважимо, що відшукання залежності Y=f(X) може виявитись настільки складним, що досліднику доведеться застосовувати спеціальне програмне забезпечення, а для деяких систем доводиться відмовлятись від пошуку абстрактної залежності Y=f(X) і задовольнятись наближеним розв'язком, що знаходиться чисельними методами.

Деякі системи настільки складні, що не дивлячись на те, що опис їх функціонування піддається опису аналітичними функціями, знаходження залежності Y=f(X) у явному вигляді виявляється неможливим. Наприклад, усі задачі математичного програмування мають досить простий аналітичний опис, але розв'язок задачі може бути знайдений тільки в результаті виконання певної кількості кроків. Іншими словами відомий алгоритм відшукання точного розв'язку задачі, але сам розв'язок не може бути записаний в аналітичній формі. Такий метод моделювання називають математичним моделюванням. Зауважимо, що алгоритм F відшукання точного розв'язку задачі може бути реалізований дослідником самостійно, за допомогою спеціального програмного забезпечення або за допомогою чисельних методів.

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

Стисло визначення методів моделювання представлені на мал. 11

Мал. 11. Методи моделювання

2.4.2 Системний підхід до побудови моделей

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

1) набору вхідних змінних системи з указуванням їх основних характеристик;

2) набору вихідних змінних системи, визначення яких забезпечує досягнення цілі дослідження;

3) границь системи з указуванням того, що являється для системи її зовнішнім середовищем;

4) елементів системи з указування їх основних властивостей;

5) зв'язків між елементами системи.

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

· змінюваність - жодна реальна система не являється статичною продовж тривалого проміжку часу, тому модель, що будується, має обмежений термін користування;

· наявність оточуючого середовища - в моделі має бути передбачений вплив зовнішнього середовища, який часто має випадковий характер;

· противоінтуітивна поведінка - виникає як результат того, що інколи наслідок проявляється пізніше причини;

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

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

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

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

Моделі, побудовані із застосуванням системного підходу, отримали назву системних моделей.

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

Умовно можна виділити такі етапи створення концептуальної моделі системи:

- Визначення цілі дослідження системи (орієнтація).

- Вибір рівня деталізації системи (стратифікація).

- Визначення елементів системи (деталізація)

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

- Визначення зв'язків між елементами системи та із зовнішнім середовищем (структуризація).

Розділ 3

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

Історія розвитку засобів імітаційного моделювання охоплює час з 50-их років ХХ століття до теперішнього часу. Відомі фахівці в галузі імітаційного моделювання Р. Ненсі та Ф. Ківіат у своїх працях визначили кілька етапів розвитку засобів імітаційного моделювання. Перший етап охоплює 1955-1960 роки. В цей час імітаційні моделі розроблялися на основі універсальних мов програмування FORTRAN і ALGOL. Вражаюче, але деякі бібліотеки алгоритмів моделювання, написані мовою FORTRAN, є актуальними і сьогодні в науковому світі. Мова ALGOL відома тим, що в ній вперше було введене поняття процедури. Поява цієї мови програмування внесла корінні зміни в концепцію програмування і відкрила шлях до об'єктного програмування.

Другий етап охоплює роки 1961-1965, коли з'явились перші мови моделювання GPSS, SIMSCRIPT, SIMULA CSL, SQL. Саме в ці роки розроблена концепція дискретних мов моделювання, за якою мови ділились на орієнтовані на події, на певні види діяльності та на процеси. Стали уніфіковані об'єкти, необхідні для моделювання, такі як черги та генератори випадкових величин.

На третьому етапі розвитку засобів імітаційного моделювання, що тривав з 1966 по 1970 роки, з'явилось друге покоління мов моделювання - GPSS V, SIMSCRIPT II.5, SIMULA 67. Ці мови були орієнтовані на комп'ютери третього покоління. У мові SIMULA 67, яка є універсальною мовою, вперше введено поняття об'єкта та дії, що виконується об'єктом, а також поняття класів, як множини споріднених об'єктів. Таким чином, мова SIMULA 67 випередила свій час більш ніж на 20 років.

Четвертий етап, що продовжувався з 1971 по 1978 роки, став етапом вдосконалення мов моделювання. В ці роки з'явились непевно-дискретні мови моделювання, наприклад, ASCL.

П'ятий етап розвитку засобів імітаційного моделювання тривав з 1979 по 1984 роки і став етапом розвитку технологій моделювання. В цей час створюються інтегровані засоби імітаційного моделювання. Змінилась концепція моделювання, відтепер це єдиний процес побудови та дослідження моделей, що має програмну підтримку. Особлива увага приділяється аналізу властивостей моделі - чутливості, надійності, достовірності результатів моделювання.

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

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

Інший погляд на етапи розвитку засобів моделювання представив Б. Шмідт (B. Schmidt). Він визначає п'ять поколінь програмних засобів моделювання:

І етап (50-ті роки ХХ століття)- програмування моделей мовами високого рівня без спеціальної підтримки завдань моделювання (мови FORTRAN і ALGOL);

ІІ етап (60-ті роки ХХ століття) - спеціалізована підтримка моделювання у вигляді виразів мови, генераторів випадкових чисел, засобів подання результатів (мови GPSS, SIMSCRIPT, SIMULA);

ІІІ етап (70-ті роки ХХ століття) - розвиток можливостей проведення неперервно-дискретного моделювання (мова ASCL);

ІV етап (80-ті роки ХХ століття) - орієнтація на конкретні галузі, розвиток можливостей анімації (мови SIMFACTORY, XCELL);

V етап (90-роки ХХ століття) - розробка графічного інтерфейсу, інтегрованих середовищ, призначених для створення і редагування моделей, планування і проведення експериментів, керування моделюванням та аналізу результатів моделювання (мови SIMPLEX II, SIMPLE++).

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

Мова моделювання СЛЭНГ, автором якої є Л.А.Калениченко, створювалась в Інституті Кібернетики Академії наук України протягом 1966-1968 років. Мова СЛЭНГ використовувалась під час розробки компонентів обчислювальних машин і систем, призначених для виконання завдань планування виробництва, для оцінювання показників надійності складних систем.

Система АЛСИМ-БЭСМ, що була створена у 1973 році в Інституті кібернетики під керівництвом д.т.н. В.В.Литвинова. Система призначалась для моделювання обчислювальних систем і мереж і використовувалась під час виконання завдань радіолокації, протиповітряної оброни, аналізу і розподілу ресурсів.

Система НЕДИС, автором якої є В.В.Гусев, створювалась в Інституті кібернетики у 1973-1975 роки. Використовувалась система для проектування обчислювальних машин і систем, передачі даних, моделювання надзвичайних ситуацій у вугільних шахтах і процесів на залізничному транспорті, проектуванні засобів і систем космічної техніки, оптимізації технологічних процесів у суднобудуванні.

Комплекс АЛСИМ-2, що створювався під керівництвом В.В.Литвинова у 1979-1980 роках. Комплекс АЛСИМ-2 широко використовувався для дослідження процесів функціонування військово-морських баз Тихоокеанського узбережжя та під час розробки проекту їх автоматизації.

Система імітаційного моделювання ІСІМ, яка розроблена у 1994 році в Національному технічному університеті „КПІ". Основне призначення системи ІСІМ, що має генератор імітаційних GPSS програм, - моделювання дискретних систем, які можна представити засобами мереж масового обслуговування.

Системи НЕДИС-90, що створювалась протягом 1991-1993 років. Система призначалась для проектування в реальному часі проблемно-орієнтованих мов. На основі НЕДИС розроблені проблемно-орієнтовані пакети моделювання СИМПО, САУККС, ПАРК, МЕРЕЖА, КОМПЛЕКС.

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

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

Більшість колективів, що займаються моделюванням систем, розробляють пакети програм, пристосовані для потреб конкретного колективу і для задач, що розв'язуються цим колективом. На кафедрі комп'ютерних технологій Черкаського державного технологічного університету розроблені система імітаційного моделювання PTRSIM, що є універсальною системою моделювання систем засобами мереж Петрі, і система моделювання транспортного руху через перехрестя міста CroossRoads, що є проблемно-орієнтованою системою.

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

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

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

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

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

· потрібне знання не лише тієї предметної області, до якої належить досліджувана система, а й мови програмування, причому на досить високому рівні;

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

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

Реалізація таких можливостей на універсальній мові програмування - справа дуже непроста. В даний час існує досить багато програмних продуктів, що дозволяють моделювати процеси. До таких пакетів відносяться: Pilgrim, GPSS, Simplex і ряд інших.

Разом з тим в даний час на російському ринку комп'ютерних технологій є продукт, що дозволяє досить ефективно вирішувати зазначені проблеми, - пакет МАТLАВ, що містить в своєму складі інструмент візуального моделювання SIMULINK.

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



Розділ 4

4.1 Імітаційне моделювання роботи каси

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

В роботі розглядається методика створення і проведення досліджень однієї з моделей систем масового обслуговування (СМО) - моделі M/G/1в середовищі SimEvents, що є одним з компонентів системи MATLab + SimuLink.

Для позначення основних припущень, що застосовуються при моделюванні СМО, була розроблена так звана нотація Кендалла (Kendall's notation). Ця нотація має вид X / Y / N, де X означає розподіл інтервалів часу між надходженнями запитів, Y - розподіл часу обслуговування, N - кількість кас. У позначенні моделі M/G/1, M позначає випадковий час надходження запитів на обслуговування з показниковим законом розподілу, G - довільний час обслуговування запитів, N - кількість обслуговуючих приладів.

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

Розробка моделі. Розглянемо касу, на вході якої заявки прибувають випадково з середньою швидкістю 2 с. Середній час обслуговування заявок касою становить 2 с. Припустимо, що каса обробляє заявку відразу, як тільки вона надходить на його вхід. Коли каса завершує обробку поточної заявки, надходить нова заявка і каса знову береться за роботу.

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

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

Для побудови моделі були обрані наступні блоки:

· блок формування розподілених у часі сигналів, що імітують послідовність надходять на вхід системи запитів на обслуговування (Time - Based Entity Generator);

· блок, що реалізує дисципліну обслуговування заявок (FIFO Queue);

· обслуговуючий прилад (Single Server);

· приймач обслужених заявок (Entity Sink);

· блок формування тимчасових інтервалів, що використовуються як час обслуговування заявок в обслуговуючому приладі (Event - Based Random Number), а також він використовується для формування заявок;

· чотири блоки візуалізації процесу моделювання (Service time, Wait time, InterTime, Utilization);

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

Виконаємо необхідні з'єднання блоків і отримаємо схему моделі M/G/1, представлену на малюнку 20.



Мал.20. Модель з однією касою

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

У блоці Event - Based Random Number 1 встановити розподіл Пуассона з середнім значенням 2 с. (мал. 21)

Мал. 21. Діалогове вікно випадкових значень



У блоці Time - Based Entity Generator вибираємо значення Intergeneration time from port t значення в цей блок будуть надходити з порту t. Блок параметрів цього блоку представлений на малюнку 22.

Мал. 22. Встановлення параметрів для входу заявок

У блоці параметрів блоку FIFO Queue в розділі Statistics у вікні параметра Average wait слід вибрати On. Для блоку Single Server необхідно встановити такі параметри: у вікні Service time from: Signal port t і On - у вікні Utilization. Для формування часу обслуговування кожної заявки в касі в блоці Event - Based Random Number у вікнах Minimum і Maximum занесемо 1.5 та 2.5 відповідно (мал. 23).



Мал. 23. Діалогове вікно випадкових значень з інтервалу

Початок моделювання. В меню робочого вікна моделі потрібно встановити час моделювання - 50 і натиснути кнопку Start. Коли моделювання завершиться, блоки Signal Scope відкриють вікна, що містять графіки. Блок Signal Scope, названий InterTime, показує процедуру формування заявок (мал. 24). Горизонтальна вісь часу показує моменти, в які заявки надходять на вхід блоку FIFO Queue.

Мал. 24. Формування заявок на вході FIFO Queue блоку

Блок Service time представляє послідовність псевдовипадкових чисел, кожне з яких застосовується як час обслуговування заявки в касі (мал. 25).



Мал. 25. Формування часу обслуговування заявок в касі

Блок Wait time (мал. 26) показує час очікування кожної заявки в черзі перед обслуговуючим приладом. Горизонтальна вісь відображає номера заявок, а вісь Y - час очікування кожної заявки.

Мал. 26. Час очікування заявок на обслуговування

Блок Utilization (мал. 27) відображає завантаження каси при обслуговуванні кожної заявки. Горизонтальна вісь відображає номера заявок, а вертикальна - завантаження.

Мал. 27. - Завантаження каси.



В результаті виконання програми дослідження моделі D/D/1, яка управляє роботою сукупності блоків, що входять до емпіричної моделі D/D/1, в автоматичному режимі були побудовані графіки завантаження каси (малюнок 28) і часу очікування заявок (малюнок 29).

Мал.28 Залежність завантаження каси від інтенсивності вхідного потоку заявок

Мал. 29 Залежність часу очікування від інтенсивності входу в касу заявок



Аналогічно можна побудувати модель з двома касами. В якій випадково будуть подаватися заявки за Пуассонівським розподілом з середнім значенням дві секунди. Кожна каса також випадковим чином обробляє заявку в середньому 2 секунди. Заявка на другій касі поступає тільки тоді коли перша каса зайнята

Поставивши час моделювання 50 с і провівши симуляцію ми бачимо що загальна кількість заявок 26, всі заявки були оброблені, першою касою оброблено 15 заявок, другою - 11 заявок. На дисплеях видно, що жодна заявка в даний час не оброблюється і в черзі не стоїть. Модель мал. 30

Мал. 30. Модель 2-х кас з випадковим обслуговуванням черги

Для порівняння побудуємо ще одну модель з двома касами. В якій випадково будуть подаватися заявки за Пуассонівським розподілом з середнім значенням дві секунди. Але кожна каса обробляє заявку зі сталою швидкістю 2 секунди. Заявка на другу касу поступає тільки тоді коли перша каса зайнята.

Знову зробимо час моделювання 50 с і як в попередньому випадку провівши симуляцію загальна кількість заявок на обслуговування становить 26. Бачимо, що всі заявки були оброблені, першою касою оброблено 16 заявок, другою - 10 заявок. На дисплеях видно, що жодна заявка в даний час не оброблюється і в черзі не стоїть. Модель мал. 31

Мал. 31. Модель 2-х кас із сталим обслуговуванням черги

Размещено на Allbest.ru