Моделювання торгового центру 2

Лабораторна робота № 3

Моделювання торгового центру

Мета роботи

Освоєння основних елементів систем масового обслуговування
Вивчення основних принципів моделювання систем масового обслуговування на ПЕОМ
Отримання практичних навичок моделювання на прикладі дослідження торгового центру

II. Теоретичні відомості

2.1 Основні елементи систем масового обслуговування

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

Основними елементами систем масового обслуговування є:

Вхідний потік
Черга
Прилад або канал обслуговування
Вихідний потік

Загальна функціональна схема системи має вигляд (Рис 1)

Рис 1. Функціональна схема СМО

Де - Інтенсивність потоку заявок (середня кількість заявок, що надійшли в одиницю часу)

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

Вхідний потік заявок представляє собою послідовність однорідних подій йдуть одне за одним у випадкові моменти часу t ₀ <t _1, <t ₂ .... <T _n

t ₀ t ₁ t ₂ ... ... ... t _i _-1 t _{i ... ...} _{... ... ..} t _n

Рис.2 Вхідний потік заявок

Де τ _i = t _i - t _i _-1 - інтервал між двома сусідніми моментами надходження заявок

Якщо τ _i = Const, то токай потік називається регулярним. Якщо τ _i змінюється випадковим чином, то такий потік називається випадковим.

Випадковий потік називається найпростішим або стаціонарним Пуассонівський потоком, якщо він має властивості:

Стаціонарності
Безпоследействія
Ординарности

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

f (τ) = λe ^{- λτ,} (1)

де λ - інтенсивність потоку:

τ> 0-інтервал часу надходження заявок.

Для моделювання інтервалу надходження заявок використовується формула:

τ _i =- ln (x _i) (i = 1, n) (2)

де x _{i-випадкові} числа рівномірно-розподілені в інтервалі [0,1].

Тоді надходження заявок визначається за формулою

Для отримання випадкових чисел х необхідно звернутися до стандартної функції або до генератора випадкових чисел, рівномірно-розподілених в інтервалі RND (x).

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

Дисципліна заповнення черги включає 4 типи:

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

Дисципліна вибору заявок з черги передбачає 3 принципи:

«Першим прийшов - першим обслужений»
«Останнім прийшов - останнім обслужений»
за пріоритетом, тобто заявки з вищим пріоритетом обслуговуються першими.

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

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

Основною характеристикою приладу обслуговування є тривалість обслуговування, тобто середній час обслуговування однієї заявки τ _обс, яка дорівнює

τ _обс = (3)

де М - інтенсивність обслуговування.

Вихідний потік заявок характеризується потоком обслужених і не обслужених заявок. Але дані характеристики не дозволяють судити про якість функціонування СМО. Тому в якості вхідного потоку використовуються різні імовірнісні характеристики якості обслуговування:

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

q - відносна пропускна здатність, тобто середня частка обслужених заявок

Ротко - ймовірність відмови системи

Робс - ймовірність обслуговування

- Середня кількість заявок у черзі

_{очікуван-середній} час очікування в черзі

_{сист-середній} час перебування заявок в системі

-Середня кількість зайнятих каналів обслуговування

До _{пр-коефіцент} простою системи

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

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

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

Принцип Δ t
Принцип особливих станів
Принцип послідовної проводки заявок

Згідно з принципом Δ t процес переходу системи з одного стану в інший розглядається в часі на кожному кроці Δ t, починаючи з моменту часу t _0. Конкретне стан системи S _i (T) вибирається за жеребом. Так, якщо система має стану: S ₁ - надходження заявки, S _{2-звільнення} приладу і т.д. то на осі часу (Рис.3) через кожні інтервали Δ t за жеребом визначається настав цей стан чи ні. Якщо так, система переводиться в цей стан, а якщо ні, то робиться новий крок Δ t і так далі.

Δ t Δ t

t ₀ t ₁ t ₂ t ₃ t ₄ t _{5 ... ... ... ... ... ... ...} t _n

Рис. 3 Перехід системи з одного стану в інший за принципом Δ t

На малюнку показано, що в момент часу t ₂ прийшла заявка. Тому вона встає на обслуговування, а в момент t ₄ прилад звільняється.

До недоліків цього методу відносяться:

метод має безліч "холостих ходів", коли система не змінює свого стану
метод критичний до вибору інтервалу Δ t
метод найменш економічний з точки зору часу реалізації його на ЕОМ

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

... ....

.. .. .. ..

Рис.4 Блок-схема моделюючого алгоритму за принципом особливого стану

Б.О.О.С-блок визначення чергового події

Б.А.С. - Блок аналізу стану

БМС-блок модифікації стану

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

При використанні даного методу зручно виділити події і стани, які можна представити у вигляді матріциа _ij :

Чергове подія Стан приладу

Вільний Зайнятий Ремонт

Початок моделювання А11 А12 А13

Надходження заявок А21 А22 А23

Початок ремонту А31 А32 а33

Звільнення приладу після ремонту

А41

А42

А43

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

А51

а52

а53

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

Тоді в залежності від події і стани у СМО проводиться відповідна зміна стану.

Принцип послідовної проводки заявок є найбільш економічним з усіх принципів. Він полягає в тому, що доля кожної заявки простежується в порядку її надходження в систему до її виходу з неї. Заявка проходить всі етапи обробки: вона може надійти в чергу або на обслуговування; покинути прилад повністю або частково бути обслуженное; перейти знову в чергу або до іншого приладу обслуговування і т.д. У відповідності з даним принципом моделюючий алгоритм повинен відмовити роботу всіх елементів СМО. Доповнюючи його блоками управління та аналізу станів, отримаємо наступну блок-схему моделюючого алгоритму (Рис.5)

Малюнок 5. Узагальнена блок-схема

моделюючого алгоритму СМО

III. Завдання на виконання роботи

Є торговий центр, в якому працює n продавців. Центр обслуговує потік покупців, що приходять з інтенсивністю λ (чол / хв) середнє час обслуговування одного покупця кожним продавцем становить _обс (хв). Приміщення, в якому розташовується торговий центр, може помістити (під час утворення черг) не більше m покупців. Покупець, що прибуває, коли всі m місць у черзі зайняті, залишає торговий центр, тобто не обслуговується і отримує відмову.

Необхідно визначити оптимальну кількість продавців в торговому центрі, щоб середній час перебування покупців в торговому центрі не перевищувало заданого часу t _зад. (Хв), тобто щоб виконувалася умова t _сист t _зад, а також імовірнісні характеристики обслуговування покупців у даному центрі при знайденому оптимальній кількості продавців:

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

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

IV Порядок виконання роботи

Для виконання завдання необхідно:

1. Уявити торговий центр у вигляді системи масового обслуговування. Для чого слід зробити постановку завдання, проаналізувати умови задачі, визначити параметри (елементи) СМО і сформулювати мету вирішення завдання.

2. описати основні принципи моделювання СМО на ЕОМ

3. Розробити моделюючий алгоритм і скласти блок - схему імітації торгового центру на ПЕОМ.

4. Скласти програму моделювання торгового центру на одній з мов програмування.

5. Отримати результати моделювання на ПЕОМ і дати їх фізичну інтерпретацію

6. Привести лістинг програми з отриманими результатами моделювання.

7. Оформити звіт.