Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Исследование системы методом имитационного моделирования

Министерство образования и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Факультет информационных технологий

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

Курсовая работа

по дисциплине "Компьютерное моделирование"

«Исследование системы методом имитационного моделирования»

Руководитель работы

__________________ Паничев В.В.

"____" _____________________2013г.

Исполнитель

студент гр. З-11ПИнж(б)РПиС(у)

___________________ Нургалиев А.И

"____" _____________________2013г.

Оренбург 2013

Содержание

Введение 3

Постановка задачи 4

1. Разработка математической модели 5

1.1 Построение концептуальной модели 5

1.2 Формализация концептуальной модели системы 7

2. Разработка структурной схемы имитационной модели 8

2.1 Разработка моделирующего алгоритма 8

2.2 Описание программной реализации имитационной модели 14

3. Эксперимент с имитационной моделью 16

Заключение 20

Список использованной литературы 21

Введение

Имитационная модель СМО представляет собой алгоритм, отражающий поведение СМО, то есть отражающий изменения состояния СМО во времени при заданных потоках заявок, поступающих на входы системы.

Имитационное моделирование позволяет исследовать СМО при различных типах входных потоков и интенсивностях поступления заявок на входы, при вариациях параметров обслуживающих аппаратов, при различных дисциплинах обслуживания заявок. Дисциплина обслуживания – правило, по которому заявки поступают из очередей на обслуживание. Величина, характеризующее право на первоочередное обслуживание, называется приоритетом. В моделях СМО заявки, приходящие на вход занятого обслуживающего аппарата, образуют очереди, отдельные для заявок каждого приоритета. При освобождении обслуживающего аппарата на обслуживание принимается заявка из непустой очереди с наиболее высоким приоритетом.

Постановка задачи

Система обработки данных состоит из накопителя перед фазой подготовки данных к специальной обработке, фазы собственно специальной обработки, состоящей из 5 однотипных каналов обслуживания, и фазы сбора полученных результатов. Поступление на один из семи каналов обслуживания осуществляется по равновероятному закону. Принять экспоненциальными законы распределения со следующими средними: 1 мин – поступление, подготовка данных и сбор полученных результатов, 6 мин – обработка данных. Первая и третья фазы функционируют независимо друг от друга.

Задание по моделированию:

- Смоделировать прохождение через систему требований в течение 5ч.

- Определить вероятность немедленного обслуживания

- Определить среднюю длину очереди

- Определить среднее число занятых каналов обслуживания (из 5)

1 Разработка математической модели системы

1.1 Построение концептуальной модели

На первом этапе компьютерного моделирования осуществляется построение концептуальной модели системы и её формализация. Формулируется модель и строится её формальная схема. На этапе построения концептуальной модели системы:

- описывается концептуальная модель в абстрактных терминах и понятиях;

- дается описание модели с использованием типовых математических схем;

- принимаются окончательно гипотезы и предположения;

- обосновывается выбор процедуры аппроксимации реальных процессов при построении модели.

Таким образом, на этом этапе проводится подробный анализ задачи, рассматриваются возможные методы её решения, и дается детальное описание концептуальной модели, которая затем используется на втором этапе моделирования.

Требования из источника поступают в накопитель с интервалом, распределенным по экспоненциальному закону с параметром λ=1 1/мин. Во время первой фазы проходят подготовку к специальной обработке. Во время второй фазы требование пытается пойти на обработку на канал К21, в случае его занятости – на канал К22, в случае занятости канала К22– на канал К23, в случае его занятости – на канал К24, в случае занятости канала К24 – на канал К25, в случае его занятости – на канал К26, в случае занятости канала К26 – на канал К27.

В случае занятости всех семи каналов требование встает в очередь на обработку.

По завершении обработки требование освобождает канал и во время третьей фазы осуществляется сбор полеченных результатов и требование считается обработанным.

Обозначения на Q-схеме:

И - источник требований;

Н₁-накопитель;

K₁₁-канал подготовки данных;

K₂₁, K₂₂, K₂₃, K₂₄, K₂₅, K₂₆, K₂₇ – каналы обслуживания требований, время обслуживания каждого прибора подчиняется экспоненциальному закону с параметром =0,1 1/мин;

K₃₁-канал сбора полученных результатов;

N - поток поступающих на обработку требований с источника;

N₁ - поток необработанных требований;

N₃ - поток обслуженных требований.

Система состоит из источника требований, накопителя (с неограниченной емкостью), канала подготовки данных, семи каналов обслуживания и канала cбора полученных результатов. На Q-схеме (рисунок 1) система представлена так: выход источника требований И соединен с вводом накопителя Н1, выход накопителя Н1 соединен с каналом подготовки данных К11, который соединен с каналами обслуживания К21..К27; выводы каналов К21..К27 соединены с входом канала сбора полученных данных, выход которого завершает схему.

1.2 Формализация концептуальной модели системы

Формализация подразумевает под собой построение формализованной схемы процесса функционирования системы и математической модели этого процесса.

Опишем возможные состояния системы для второй фазы.

Все возможные состояния системы будут представлять собой:

S₀ – все каналы свободны;

S₁ – занят 1 канал;

S₂ – заняты 2 канала;

S₃ – заняты 3 канала;

S₄ – заняты 4 канала;

S₅ – заняты 5 каналов;

S₆ – заняты 6 каналов;

S₇ – заняты все каналы;

P_i– вероятность нахождения системы в состоянии S_i;

λ – интенсивность потока требований;

μ – интенсивность потока обслуживания;

Граф состояний представлен на рисунке 2.

Финальные вероятности состояний находим по формулам Эрланга:

;

где =1/10=0,1

Характеристики эффективности:

_{Пропускная способность
системы:}

А=(1-р_n)=0,99999999998

Вероятность обслуживания требований:

Вероятность не обслуживания требований:

Оценка среднего числа занятых приборов: _*=0,1*0,9=0,09

Оценка времени нахождения требования в системе:

Коэффициент использования каналов:

2 Разработка структурной схемы имитационной модели

2.1 Разработка моделирующего алгоритма

Для моделирования процессов функционирования системы используем детерминированный моделирующий алгоритм. Укрупненная схема моделирующего алгоритма с постоянным шагом соответствующего системе (Рисунок 1 – Q-схема) приведена на рисунке 3. Особенностью ее является наличие блока системного времени, вычисляющего значения текущих моментов времени , и блока, определяющего момент окончания моделирования по условию , где T- время моделирования.

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

Рассмотрим детальные схемы алгоритмов этих блоков с учетом принятых обозначений в них: Процедура обслуживания заявки каналом оформлена в виде подпрограммы WORK[K(K,J)], позволяющей обратиться к генератору случайных чисел с соответствующим данному каналу законом распределения, генерирующей длительности интервалов обслуживания очередных заявок . Процедура генерации заявок источником также оформлена в виде подпрограммы, но D(TM), которая определяет момент поступления очередной заявки в систему.

Окончание обслуживания заявки каналом в момент может вызвать процесс распространения изменений состояний элементов системы в направлении, обратном движению заявки, поэтому все накопители и каналы должны просматриваться при моделировании, начиная с обслуживающего канала последней фазы по направлению к накопителю первой фазы (рисунок 3).

После проверки условия окончания моделирования переходят к имитации обслуживания заявки каналом 3-й фазы. Если закончено обслуживание в канале 3-й фазы, то фиксируется выход из системы очередной заявки (подсчет их) и производится освобождение этого канала (рисунок 4).

Далее имитируется переход заявки из 2-й в 3-ю фазу (рисунок 5). При этом осуществляется просмотр каналов 2-й фазы и определение заявок, ожидающих обслуживания в канале К₃₁ и, если он свободен, то согласно дисциплине обслуживания выбирается одна из заявок и имитируется ее обслуживание в канале К₃₁, занятость его и освобождение канала 2-й фазы. Если канал К₃₁ занят, то осуществляется блокировка заявки в канале 2-й фазы.

Далее имитируется обслуживание заявок каналом 1-й фазы (рисунок 6). Для этого проверяется наличие заявок в накопителе Н₁ и отсутствие их в канале 1-й фазы, а также организуется обслуживание заявок каналом 1-й фазы и изменение состояний канала и накопителя.

Алгоритм имитации поступления заявок из источника в накопитель 1-й

фазы (рисунок 7) с учетом занятости канала заключается в последовательном выполнении следующих операций:

- проверка поступления заявки из источника в текущий момент времени;

- проверка отсутствия заявки в канале 1-й фазы;

- организация обслуживания поступившей заявки в канал первой фазы

(вызов процедуры WORK и изменения состояния канала);

- генерация момента поступления очередной заявки.

Если канал первой фазы занят, то поступившая заявка помещается в накопитель первой фазы. После чего опять осуществляется генерация момента поступления очередной заявки и управления передается блоку 9, который определяет момент очередного шага моделирования (рисунок 3).

Затем управление снова передается блоку 3, который при наборе необходимой статистики проводит обработку и выдачу результатов моделирования, а потом и остановку моделирования.

2.2 Описание программной реализации имитационной модели

Рассмотрим принципиальные особенности реализации имитационной вероятностной модели СМО в среде GPSS World.

Для организации реализации обработки заявок в течение 5 часов через СМО в программной реализации использован блок генерации количества моделирования, в котором остановка моделирования происходит по факту выхода из цикла переданного через оператор TERMINATE

Текст программы:

GENERATE 300

TERMINATE 1

GENERATE (EXPONENTIAL(1,0,1))

QUEUE MEN

SEIZE 11

DEPART MEN

ADVANCE (EXPONENTIAL(1,0,1))

RELEASE 11

TRANSFER ALL,CHAN1,CHAN7,4

CHAN1 SEIZE 21

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 21

TRANSFER ,OUT

CHAN2 SEIZE 22

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 22

TRANSFER ,OUT

CHAN3 SEIZE 23

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 23

TRANSFER ,OUT

CHAN4 SEIZE 24

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 24

TRANSFER ,OUT

CHAN5 SEIZE 25

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 25

TRANSFER ,OUT

CHAN6 SEIZE 26

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 26

TRANSFER ,OUT

CHAN7 SEIZE 27

ADVANCE (EXPONENTIAL(2,0,10))

RELEASE 27

OUT SEIZE 31

ADVANCE (EXPONENTIAL(3,0,1))

RELEASE 31

TERMINATE 0

Оператор GENERATE.

Оператор GENERATE осуществляет первоначальный ввод транзактов в модель:

В – может быть отличен от const и рассматривается как модификатор;

С – задержка начала генерации;

D – число генерируемых транзактов (емкость источника);

Е – приоритет транзактов. Целое без знака: 0, 1,2, ...;

Операнды могут быть опущены.

Оператор ADVANCE.

Задержка транзактов осуществляется блоком ADVANCE. Войти в ADVANCE и находиться в нем одновременно, может любое число заявок. Обычно блок ADVANCE моделирует обслуживание заявок в устройстве или в многоканальном устройстве и поэтому он обрамляется блоками входа/выхода в них

Оператор TERMINATE.

Начав свой путь на выходе блока GENERATE и пройдя то число операционных блоков GPSS-модели, которое при создавшейся случайной ситуации предусмотрено логикой модели, транзакт выводится из модели на языке GPSS.

Операторы SEIZE и RELEASE.

Занятие устройства происходит в момент прохода транзактом блока SEIZE

Если в течение некоторого интервала модельного времени несколько транзактов пытаются войти в блок SEIZE, то организуется очередь транзактов, ждущих разрешения на вход в блок SEIZE.

Освобождение накопителя происходит в момент прохода транзактом блока с именем RELEASE.

Операторы QUEUE и DEPART.

Оператор QUEUE фиксирует вход транзакта в очередь, а оператор DEPART – выход из очереди.

Оператор ENTER.

ENTER A,B предназначен для фиксации входа транзакта в память:

А – указывается номер памяти;

В – число единиц памяти, занимаемые транзактом;

Оператор LEAVE.

LEAVE A, B – выход из транзакта:

А – указывается номер памяти;

В – число единиц памяти освобожденные транзактом;

3 Эксперимент с имитационной моделью

Планирование и проведение эксперимента

Имитационное моделирование является по своей сути машинным экспериментом с моделью исследуемой или проектируемой системы. План имитационного эксперимента на ЭВМ представляет собой метод получения с помощью эксперимента необходимой пользователю информации. Эффективность использования экспериментальных ресурсов существенным образом зависит от выбора плана эксперимента.

Машинный эксперимент с моделью системы при её исследовании и проектировании проводится с целью получения информации, о характеристиках процесса функционирования рассматриваемого объекта. Эффективность машинных экспериментов с моделями существенно зависит от выбора плана эксперимента, так как именно план определяет объемы и порядок проведения вычислений на ЭВМ, приемы накопления и статистической обработки результатов моделирования системы. Поэтому основная задача планирования машинных экспериментов с моделью формулируется следующим образом: необходимо получить информацию об объекте моделирования, заданном в виде моделирующего алгоритма, при минимальных или ограниченных затратах машинных ресурсов на реализацию процесса моделирования.

Анализ результатов моделирования

Отчет GPSS

GPSS World Simulation Report - Untitled Model 2.16.1

Monday, February 04, 2013 20:59:11

START TIME END TIME BLOCKS FACILITIES STORAGES

0.000 300.000 40 9 0

NAME VALUE

CHAN1 10.000

CHAN2 14.000

CHAN3 18.000

CHAN4 22.000

CHAN5 26.000

CHAN6 30.000

CHAN7 34.000

MEN 10000.000

OUT 37.000

LABEL LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY

1 GENERATE 1 0 0

2 TERMINATE 1 0 0

3 GENERATE 278 0 0

4 QUEUE 278 0 0

5 SEIZE 278 0 0

6 DEPART 278 0 0

7 ADVANCE 278 0 0

8 RELEASE 278 0 0

9 TRANSFER 278 92 0

CHAN1 10 SEIZE 36 0 0

11 ADVANCE 36 1 0

12 RELEASE 35 0 0

13 TRANSFER 35 0 0

CHAN2 14 SEIZE 16 0 0

15 ADVANCE 16 1 0

16 RELEASE 15 0 0

17 TRANSFER 15 0 0

CHAN3 18 SEIZE 25 0 0

19 ADVANCE 25 1 0

20 RELEASE 24 0 0

21 TRANSFER 24 0 0

CHAN4 22 SEIZE 30 0 0

23 ADVANCE 30 1 0

24 RELEASE 29 0 0

25 TRANSFER 29 0 0

CHAN5 26 SEIZE 42 0 0

27 ADVANCE 42 1 0

28 RELEASE 41 0 0

29 TRANSFER 41 0 0

CHAN6 30 SEIZE 18 0 0

31 ADVANCE 18 1 0

32 RELEASE 17 0 0

33 TRANSFER 17 0 0

CHAN7 34 SEIZE 19 0 0

35 ADVANCE 19 1 0

36 RELEASE 18 0 0

OUT 37 SEIZE 179 0 0

38 ADVANCE 179 0 0

39 RELEASE 179 0 0

40 TERMINATE 179 0 0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

11 278 0.884 0.954 1 0 0 0 0 0

21 36 0.983 8.194 1 178 0 0 92 0

22 16 0.979 18.362 1 131 0 0 92 0

23 25 0.963 11.559 1 180 0 0 92 0

24 30 0.975 9.749 1 185 0 0 92 0

25 42 0.972 6.940 1 186 0 0 92 0

26 18 0.941 15.680 1 187 0 0 92 0

27 19 0.933 14.731 1 153 0 0 92 0

31 179 0.610 1.023 1 0 0 0 0 0

QUEUE MAX CONT. ENTRY ENTRY(0) AVE.CONT. AVE.TIME AVE.(-0) RETRY

MEN 17 0 278 31 3.275 3.534 3.978 0

FEC XN PRI BDT ASSEM CURRENT NEXT PARAMETER VALUE

280 0 300.106 280 0 3

153 0 300.570 153 35 36

186 0 300.704 186 27 28

178 0 305.703 178 11 12

180 0 307.039 180 19 20

131 0 307.164 131 15 16

187 0 308.625 187 31 32

185 0 309.730 185 23 24

281 0 600.000 281 0 1

Проведем несколько моделирующих экспериментов, результаты которых занесем в таблицу 1.

Таблица 1 – Результаты прогонов:

№ прогона	N	N₀	Q	P_отк	K_u
1	287	276	0,962	0,038	0,918
2	305	267	0,875	0,125	0,942
3	304	292	0,961	0,039	0,963
4	276	276	1,000	0,000	0,869
5	287	271	0,944	0,056	0,940
6	267	267	1,000	0,000	0,890
7	316	286	0,905	0,095	0,968
8	325	300	0,923	0,077	0,973
9	309	278	0,900	0,100	0,942
10	271	268	0,989	0,011	0,868
M(x)	294,7	278,1	0,944	0,056	0,927

Проведем проверку модели на адекватность. Так как выборка малая, то используем t-критерий. В качестве параметра расчета возьмем среднее число занятых каналов K. Теоретически рассчитаем К_т.

;

=0,000000000002

где =1/10=0,1

Применим метод сравнения выборочной средней с гипотетической генеральной средней нормальной совокупностью.

Для того, чтобы при заданном уровне значимости α=0,05 проверить нулевую гипотезу Н₀: а = а₀ о равенстве генеральной средней нормальной совокупности а с известной дисперсией σ² гипотетическому (предполагаемому) значению а₀ при конкурирующей гипотезе Н₁ : а≠а₀ , надо вычислить наблюдаемое значение критерия:

и по таблице функции Лапласа найти критическую точку U_кр двусторонней критической области из равенства:

Т.к. |U_набл| < U_кр (< 1.96), то нет оснований отвергать нулевую гипотезу, следовательно, модель адекватна.

Заключение

Программные средства GPSS World позволяют проанализировать характеристики и результаты деятельности любой системы, без ее физического построения. Это позволяет спрогнозировать результаты создаваемой системы, используя минимальное количество материальных ресурсов и времени.

Список использованной литературы

1 Советов Б.Я., Яковлев С.А. Моделирование систем: Учебник для вузов. – М.: Высш. шк., 2001. – 343с.

2 Гультяев А. Визуальное моделирование в среде «Matlab»: Учебный курс. – СП: Питер, 2000.

3 Вентцель Е.С., Овчаров Л.А. Задачи и упражнения по теории вероятностей: Учебное пособие для студ. втузов. – М.: Издательский центр «Академия», 2003. – 448.

4 Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике: Учебн. пособие для вузов. – М.: Высш. шк., 2003. – 405 с.

5 Лебедев А.Н. Моделирование в научно-технических исследованиях. – М.: Радио и связь, 1989. – 224 с.

6 Х. Шенк. Теория инженерного эксперимента. Перевод с английского Е.Г. Коваленко. – М.: Мир, 1972. – 382 с.

7 Романцев В.В., Яковлев С.А. Моделирование систем массового обслуживания. – СПб.: Поликом, 1995.

Исследование системы методом имитационного моделирования 📙 Курсовая → 🆔 96743