47495

дискретно-событийного моделирования систем и технология имитационного моделирования

Книга

Информатика, кибернетика и программирование

МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ. Основы дискретнособытийного моделирования СМО. ВЕРОЯТНОСТНОЕ МОДЕЛИРОВАНИЕ. Моделирование дискретных случайных величин.

Русский

2013-12-12

3.66 MB

137 чел.

Оглавление

[1] Оглавление

[2]
ПРЕДИСЛОВИЕ

[2.1] ВВЕДЕНИЕ

[2.2] ГЛАВА 1. МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ

[3] 1.1. Системы  массового обслуживания и их характеристики

[4] 1.2. Системы с одним устройством обслуживания

[5] 1.3. Основы дискретно-событийного моделирования СМО

[6] 1.4. Многоканальные системы массового обслуживания

[7] ГЛАВА 2. ВЕРОЯТНОСТНЫЕ СЕТИ СИСТЕМ МАССОВОГО

[8] ОБСЛУЖИВАНИЯ

[9] 2.1. Общие сведения о сетях

[10] 2.2. Операционный анализ вероятностных сетей

[11] 2.3. Операционные зависимости

[12] 2.4. Анализ узких мест в сети

[13] ГЛАВА 3. ВЕРОЯТНОСТНОЕ МОДЕЛИРОВАНИЕ

[14] 3.1. Метод статистических испытаний

[15] 3.2. Моделирование дискретных случайных величин

[16] 3.3. Моделирование непрерывных случайных величин

[16.0.1] Таблица 3.3

[17] 3.4. Сбор статистических данных для получения оценок характеристик случайных величин

[17.0.0.1] Для оценки дисперсии случайной величины ξ используют формулу

[18] 3.5. Определение количества реализаций при моделировании

[19] случайных величин

[19.0.0.1] По формулам (3.18-3.20) находим

[20] Задачи для самостоятельной работы

[20.0.1] Таблица 3.4

[20.0.2] Таблица 3.5

[20.0.3] Таблица 3.6

[21] ГЛАВА 4. СИСТЕМА МОДЕЛИРОВАНИЯ GPSS

[22] 4.1. Объекты

[22.0.1] Таблица 4.1

[23] 4.2. ЧАСЫ модельного времени

[24] 4.3. Типы операторов

[25] 4.4. Внесение транзактов в модель. Блок GENERATE

[25.0.1] Таблица 4.2

[26] Задание для самостоятельной работы:

[27] 4.5. Удаление транзактов из модели. Блок TERMINATE

[28] 4.6. Элементы, отображающие одноканальные обслуживающие

[29] устройства

[29.0.1] Таблица 4.5

[30] 4.7. Реализация задержки во времени. Блок ADVANCE

[30.0.1] Таблица 4.6

[31] Задания для самостоятельной работы:

[32] 4.8. Сбор статистики об ожидании. Блоки QUEUE, DEPART

[33] 4.9. Переход транзакта в блок, отличный от последующего.

[34] Блок TRANSFER

[34.0.1] Таблица 4.8

[34.0.2] Таблица 4.9

[35] Задания для самостоятельной работы:

[36] 4.10. Моделирование многоканальных устройств

[36.0.1] Таблица 4.11

[37] 4.11. Примеры построения GPSS-моделей

[38] 4.12. Переменные

[38.0.1] Таблица 4.20

[39] 4.13. Определение функции в GPSS

[39.0.1] Таблица 4.21

[39.0.2] Таблица 4.22

[39.0.3] Таблица 4.23

[39.0.4] Таблица 4.24

[39.0.5] Таблица 4.25

[40] 4.14. Стандартные числовые атрибуты, параметры транзактов. Блоки ASSIGN, MARK, LOOP

[41] 4.15. Изменение приоритета транзактов. Блок PRIORITY

[42] 4.16. Организация обслуживания с прерыванием. Блоки PREEMPT и RETURN

[43] Задание для самостоятельной работы:

[44] 4.17. Сохраняемые величины

[44.0.1] Таблица 4.39

[44.0.2] Таблица 4.40      

[44.0.3] Таблица 4.41

[44.0.4] Таблица 4.42

[45] 4.18. Проверка числовых выражений. Блок TEST

[46] Задание для самостоятельной работы:

[47] 4.19. Определение и использование таблиц

[47.0.1] Таблица 4.44

[47.0.2] Таблица 4.45

[47.0.3] Таблица 4.46

[48] Задания для самостоятельной работы:

[49] 4.20. Косвенная адресация

[50] 4.21. Обработка транзактов, принадлежащих одному семейству

[50.0.1] Таблица 4.47

[51] 4.22. Управление процессом моделирования в системе GPSS

[52] 4.23. Списки пользователей

[53] 4.24. Блоки управления потоками транзактов LOGIC, GATE LR, GATE LS и GATE

[54] 4.25. Организация вывода временных рядов из GPSS-модели

[55] 4.26. Краткая характеристика языка PLUS

[55.0.1] Таблица 4.48

[56] 4.27. Команды GPSS World

[56.0.1] Таблица 4.49

[57] 4.28. Диалоговые возможности GPSS World

[58] 4.29. Отличия между GPSS World и GPSS/PC

[59] ГЛАВА 5. МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ И ОПЕРАЦИОННЫХ СИСТЕМ

[60] 5.1. Операционные системы компьютеров

[61] 5.2. Сети и системы передачи данных

[62] 5.3. Проблемы моделирования компьютеров и сетей

[63] ГЛАВА 6. ОСНОВЫ МОДЕЛИРОВАНИЯ ПРОЦЕССОВ

[64] 6.1. Производственные процессы

[65] 6.2. Распределительные процессы

[66] 6.3. Процессы обслуживания клиентов

[67] 6.4. Процессы управления разработками проектов

[68] ГЛАВА 7. ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

[69] Задание 1. Моделирование разливной линии

[69.0.1] Таблица 7.5

[69.0.2] Таблица 7.6

[69.0.3] Таблица 7.7

[69.0.4] Таблица 7.8

[69.0.5] Таблица 7.9

[69.0.6] Таблица 7.10

[69.0.7] Таблица 7.11

[69.0.8] Таблица 7.12

[69.0.9] Таблица 7.13

[69.0.10] Таблица 7.14

[69.0.11] Таблица 7.15

[69.0.12] Таблица 7.16

[69.0.13] Таблица 7.17

[69.0.14] Таблица 7.18

[69.0.15] Таблица 7.20

[70] ГЛАВА 8. ПРОЕКТИРОВАНИЕ ИМИТАЦИОННЫХ МОДЕЛЕЙ

[71] С ПОМОЩЬЮ ИНТЕРАКТИВНОЙ СИСТЕМЫ

[72] ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

[73] 8.1. Структура интерактивной системы имитационного моделирования

[74] 8.2. Построение концептуальной схемы модели

[75] 8.3. Параметрическая настройка модели

[76] 8.4. Генератор формул

[77] 8.5. Управление экспериментом

[78] 8.6. Запуск эксперимента и обработка результатов моделирования

[79] 8.7. Управление проектами и общей настройкой системы

[80] 8.8. Пример построения модели средствами ISS 2000

[80.0.1] Таблица 8.1

[80.0.1.1] 70        ADVANCE 160,FN$XPDIS

[81] ГЛАВА 9. ТЕХНОЛОГИЯ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

[82] 9.1. Имитационные проекты

[83] 9.2. Организация экспериментов

[84] 9.3. Проблемы организации имитационных экспериментов

[85] 9.4. Оценка точности результатов моделирования

[86] 9.5. Факторный план

[87] 9.6. Дисперсионный анализ ANOVA в планировании экспериментов

[88] 9.7. Библиотечная процедура ANOVA

[89] 9.8. Технология проведение дисперсионного анализа в системе GPSS World

[90] 9.9. Особенности планирования экспериментов

[91] 9.10. Нахождение экстремальных значений на поверхности

[92] отклика

[93] 9.11. Организация экспериментов в GPSS World

[94] 9.12. Выбор наилучшего варианта структуры системы

[95] ГЛАВА 10. ПРИМЕРЫ ПРИНЯТИЯ РЕШЕНИЙ С ПОМОЩЬЮ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

[96] 10.1. Моделирование производственного участка

[97] 10.2. Моделирование технологического процесса ремонта и замены оборудования

[98] ГЛАВА 11. ЗАДАНИЯ ДЛЯ ИМИТАЦИОННЫХ ПРОЕКТОВ

[99] ПРИЛОЖЕНИЕ

[100] Системные СЧА

[101] СЧА транзактов

[102] СЧА блоков:

[103] СЧА МКУ

[104] СЧА одноканальных устройств:

[105] СЧА очередей

[106] СЧА таблиц

[107] СЧА ячеек и матриц ячеек сохраняемых величин:

[108] СЧА вычислительных объектов

[109] СЧА списков и групп

[110] СПИСОК ЛИТЕРАТУРЫ


ПРЕДИСЛОВИЕ

В книге рассматриваются основы дискретно-событийного моделирования систем и технология имитационного моделирования. Авторами обобщен опыт преподавания дисциплин, связанных с имитационным моделированием, и предыдущих двух книг [1,2]. Приведенный материал имеет практическую направленность и позволяет самостоятельно освоить средства имитационного моделирования для решения практических задач. Большое количество приведенных примеров, пояснений и задач способствует этому. Основное назначение этой книги - научить принимать решение по результатам экспериментов с имитационными моделями.

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

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

Четвертая глава знакомит с языком GPSS и конкретно с его реализацией GPSS World для построения имитационных моделей. Принцип изложения материала - от простого к сложному. Возможности языка иллюстрируются конкретными примерами с пояснениями. Приведены также основные средства языка для моделирования разных задач.

В пятой главе изложены основы моделирования вычислительных и операционных систем (ОС), а в шестом - основы моделирования разных процессов, которые надо знать, чтобы выполнить самостоятельные задания, приведенные в седьмой главе.

В восьмой главе рассматривается технология работы с программной системой ISS 2000, позволяющей автоматизировать процесс создания имитационных моделей на языке GPSS и проведения экспериментов с моделями без написания кода программы. Встроенные аналитические средства позволяют определить узкие места в моделируемой системе до начала моделирования.

Девятая глава охватывает проблемы построения имитационных проектов и технологии выполнения работ по моделированию и включает вопросы организации, планирования и проведения экспериментов. Особое внимание уделено вопросам точности получаемых оценок по результатам моделирования в переходном и установившемся режиме. Рассмотрен дисперсионный анализ; отсеивающий, оптимизационный и пользовательский эксперименты, приведены примеры их реализации в GPSS World. Рассмотрены вопросы структурной оптимизации моделируемой системы и выбора наилучшего из альтернативных вариантов.

Примеры принятия решений по результатам имитационного моделирования приведены в десятой главе.

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

ВВЕДЕНИЕ

Компьютерное моделирование нашло практическое применение во всех сферах деятельности человека, начиная от моделей технических, технологических и организационных систем и заканчивая проблемами развития человечества и вселенной. Еще с детства человек через игрушки и игры узнает мир и таким образом моделирует действительность. Вместо того, чтобы учиться на своих ошибках или на ошибках других людей, целесообразно закреплять и проверять познание реальной действительности полученными результатами на компьютерной модели. В этом случае есть возможность «проигрывать» на модели любые ситуации, включая те, при которых реальная система вышла бы из строя. Это позволяет моделировать катастрофы, редкие события и т. п. Одно из преимуществ компьютерного моделирования - это также моделирование того, что не существует на самом деле, то есть моделирование виртуальной реальности. Вспомним компьютерные игры: сидя в самолете или космическом корабле, мы осуществляем полет так, как будто мы действительно находимся там.

Когда же необходимо использовать компьютерное моделирование? Всегда, когда можно поставить вопрос, «что будет, если ...?». Следовательно, компьютерное моделирование используют, прежде всего, для принятия решений. Модель позволяет проигрывать любые ситуации и получать наиболее эффективные решения проблемы.

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

- содержательная постановка задачи;

- разработка концептуальной модели;

- разработка и программная реализация имитационной модели; проверка правильности,

- достоверности модели и оценка точности результатов моделирование;

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

- принятие решений.

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

Широкому внедрению этого метода на практике препятствует необходимость создания программных реализаций имитационных моделей, которые воссоздают в модельном времени динамику функционирования моделируемой системы. В отличие от традиционных методов программирования разработка имитационной модели требует перестройки принципов мышления. Недаром принципы, положенные в основу имитационного моделирования, дали толчок к развитию объектного программирования. Поэтому усилия разработчиков программных средств имитации направлены на упрощение программных реализаций имитационных моделей: для этих целей создаются специализированные языки и системы. Программные средства имитации в своем развитии изменялись на протяжении нескольких поколений, начиная с языков моделирования и средств автоматизации конструирования моделей [4] до генераторов программ [5], интерактивных и интеллектуальных систем [6], распределенных систем моделирования. Основное назначение всех этих средств - уменьшение трудоемкости создания программных реализаций имитационных моделей и экспериментирования с моделями.

Одним из первых языков моделирования, облегчающих процесс написания имитационных программ, был язык GPSS, созданный в виде конечного продукта Джеффри Гордоном в фирме IBM в 1962 г. Этот язык в свое время входил в первую десятку лучших языков программирования, опережая транслятор с языка АЛГОЛ, и был реализован практически на всех типах ЭВМ. В настоящее время есть трансляторы для операционных систем DOS - GPSS/PC, для OS/2 и DOS - GPSS/H и для Windows - GPSS World. Изучение этого языка и создания моделей позволяет понять принципы разработки имитационных программ и научиться работать с имитационными моделями.

GPSS (General Purpose Simulation System - система моделирования общего назначения) - язык моделирования, который используется для построения событийных дискретных имитационных моделей и проведения экспериментов на ЭВМ.

Модели систем на GPSS могут быть записаны в виде блок-схем или представлены в виде последовательности строк программы, эквивалентных блок-схеме. Блок-схема - это набор фигур с характерными контурами блоков языка GPSS, соединенных между собою линиями. Блоки - это подпрограммы, реализованные средствами макроассемблера. В разных версиях языка количество блоков для создания имитационных программ разное и составляет около 40. В язык моделирования GPSS входят специальные средства для описания динамического поведения систем через изменение состояний в дискретные моменты времени, то есть время моделирования изменяется случайно от события к событию.

Система GPSS представляет собой язык и транслятор. Как каждый язык он содержит словарь и грамматику, с помощью которых могут быть разработаны модели систем определенного типа. Транслятор языка работает в две фазы. На первой фазе компиляции проверяется синтаксис и семантика написания строк GPSS-программы или всей программы в целом, а на второй (интерпретирующей) осуществляется продвижение транзактов по модели от блока к блоку.

ГЛАВА 1. МОДЕЛИ МАССОВОГО ОБСЛУЖИВАНИЯ

1.1. Системы  массового обслуживания и их характеристики

С системами массового обслуживания (СМО) мы встречаемся повседневно. Любому из нас приходилось когда-то ждать обслуживания в очереди (например, в магазине, на автозаправке, в библиотеке, кафе и т. д.). Аналогичные ситуации возникают при потребности воспользоваться телефонной связью или выполнить свою программу на компьютере. Более того, любое производство можно представить как последовательность систем обслуживания. К типичным системам обслуживания относят также ремонтные и медицинские службы, транспортные системы, аэропорты, вокзалы и другие.

Особое значение приобрели такие системы при изучении процессов в информатике. Это, прежде всего, компьютерные системы, сети передачи информации, ОС, базы и банки данных. Системы обслуживания играют значительную роль в повседневной жизни. Опыт моделирования разных типов дискретных событийных систем свидетельствует о том, что приблизительно 80% этих моделей основаны на СМО.

Что же характеризует эти системы как СМО? Такие системы можно описать, если задать:

1) входящий поток требований или заявок, которые поступают на обслуживание;

2) дисциплину постановки в очередь и выбор из нее;

3) правило, по которому осуществляется обслуживание;

4) выходящий поток требований;

5) режимы работы.

Входящий поток. Для задания входящего потока требований необходимо описать моменты времени их поступления в систему (закон поступления) и количество требований, которое поступило одновременно. Закон поступления может быть детерминированный (например, одно требование поступает каждые 5 мин) или вероятностный (требования могут появляться с равной вероятностью в интервале 5±2 мин). В общем случае входящий поток требований описывается распределением вероятностей интервалов времени между соседними требованиями. Часто предполагают, что эти интервалы времени независимые и имеют одинаковое распределение случайных величин, которые образуют стационарный входящий поток требований. Классическая теория массового обслуживания рассматривает так называемый пуассоновский (простейший) поток требований. Для этого потока число требований k для любого интервала времени распределено по закону Пуассона:

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

На практике обоснованием того, что входящий поток требований имеет распределение Пуассона, является то, что требования поступают от большого числа независимых источников за определенный интервал времени. Примерами могут быть вызовы абонентов в телефонной сети, запросы к распределенной базе данных от абонентов сети за некоторое время и другие. Для того, чтобы при моделировании задать пуассоновский поток требований в систему, достаточно задать экспоненциальное распределение интервалов времени поступление для соседних требований, графики функций плотности и распределения которых для λ = 1 показаны на рис. 1.1.

Дисциплины постановки в очередь и выбора из нее определяют порядок постановки требований в очередь, если заняты устройства обслуживания, и порядок выбора из очереди, если освобождается обслуживающее устройство. Простейшая дисциплина допускает постановку в очередь в порядке поступления требований. Такую дисциплину называют «раньше поступил - раньше обслужился» (РПРО, в англоязычной литературе FIFO - First In-First Out), например, очередь к телефону-автомату.

 

Организация очереди по правилу «последний поступил - первый обслужился» (ПППО, в англоязычной литературе LIFO - Last In-First Out) допускает, что на обслуживание выбираются последние требования из очереди. Это правило также называется «стеком» или «магазином».

Правило выбора из очереди может быть случайным (RANDOM).

Возможна также организация выбора из очереди по параметрам (например, мужчины в очереди пропускают женщин вперед).

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

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

Правила обслуживания характеризуются длительностью обслуживания (распределением времени обслуживание), количеством требований, которые обслуживаются одновременно и дисциплиной обслуживания. Время обслуживания бывает детерминированным или заданным вероятностным законом распределения.

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

Дисциплины обслуживания определяют:

- при каких условиях прекращается обслуживание требований;

- как выбирается для обслуживания следующее требование;

- что делать с частично обслуженным требованием.

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

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

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

При использовании абсолютного приоритета появление требования с более высоким приоритетом перерывает обслуживание менее приоритетного требования (обслуживание с прерыванием). В таких системах могут происходить вложенные прерывания, если требование, которое вытеснило из обслуживания менее приоритетное требование, само будет прервано более приоритетным требованием и т.д. Поэтому иногда в этих системах ограничивают глубину прерывания. Прерванные требования могут или оставлять систему обслуживания, или снова становиться в очередь для дообслуживания.

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

Выходящий поток - это поток требований, которые покидают систему, причем требования в нем могут быть как обслуженные, так и не обслуженные. Структура выходящего потока может иметь большее значение для многофазных систем, где этот поток становится входящим для следующей фазы обслуживания. Распределение требований в выходящем потоке во времени зависит от плотности входящего потока и характеристик работы устройств обслуживания. Из теории массового обслуживания известно, что выходящий поток из СМО с т устройствами с ожиданием при простейшем входящем потоке с параметром λ и экспоненциальном распределении времени обслуживания с параметром μ есть простейший поток с параметром λ = min{λ,mμ}. Такое замечание дает возможность построить теорию сложных СМО, где выходящий поток из одних систем обслуживания есть входящий в другие системы. Это так называемые многофазные системы и сети СМО. Во всех других случаях распределение выходящих потоков из СМО имеет более сложную вероятностную природу и может изучаться только наблюдениями за функционированием этих СМО с помощью моделирования.

По практическим соображениям часто приходится изучать режимы работы СМО. Например, устройства обслуживания время от времени могут выходить из строя (режим отказа), в особенности, если с помощью этих систем описывается некоторый производственный или информационный процесс. Есть еще один режим - блокирование обслуживания, - который связан с временным прерыванием процесса обслуживания или с замедлением его. Изменение режима работы СМО может быть вызвано внешним влиянием (например, временным отсутствием деталей в технологическом процессе, ремонтом оборудования и т.п.) или продолжительностью работы (например, выход из строя элемента в компьютере).

Для СМО любого вида справедлив закон Литтла: для любого распределения времени между двумя событиями поступления требований, любого распределения времени их обслуживания, любого количества устройств обслуживания и любой дисциплины обслуживания среднее количество требований N в СМО определяется через интенсивность поступления λ и среднее время пребывания требований в системе Т, то есть:

N = λ T. (1.2)

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

1.2. Системы с одним устройством обслуживания

Рассмотрим одноканальную (с одним устройством обслуживания) СМО, показанную на рис. 1.2.

Если обозначить среднее время пребывания требований в очереди w и рассматривать СМО как очередь q, то, используя формулу Литтла, можно найти среднее количество требований в очереди:

Если обозначить среднее время обслуживания в устройстве х и рассматривать СМО как устройство S, то, используя формулу Литтла можно найти среднее количество требований в устройстве:

Всегда имеет место уравнение T = w+x, где Т - среднее время пребывания требований в СМО с одним устройством обслуживания.

Коэффициент загрузки p определяет, какую часть времени устройство было занято на протяжении всего времени наблюдения за СМО.

Для обозначения СМО используются три параметра для первых трех параметров: X/Y/Z, где X - распределение времени поступления; Y- распределение времени обслуживания; Z- число обслуживающих устройств.

В теории СМО некоторые аналитические решения были получены для систем вида D/D/1, М/М/1 и M/G/1. Для других значений параметров систем обслуживания аналитические решения не были получены, то есть эта проблема мотивирует использование моделирования.

Самая известная модель - это так называемая СМО типа М/М/1, где М - марковские процессы распределения времени поступления и обслуживания с одним устройством. Например, в системе М/М/1 время между двумя поступлениями в систему требований и время обслуживания имеют экспоненциальные распределения. Такая СМО иногда используется как модель для одного процессора компьютерной системы или как стандартное устройство ввода-вывода (например, магнитный диск). Система D/D/1 - детерминированная система, тогда как D/M/1 - смешанная. Если о системе мало известно, это обозначается как G/G/m, то есть система с произвольными распределениями и т устройствами.

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

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

Часто рабочая нагрузка на систему определяется одним или несколькими распределениями вероятностей в отличие от заданных сценариев. Например, можно бросать монету каждые 15 мин на протяжении операции исследования системы, и если монета падает лицевой стороной, то новая задача поступает в систему в этот момент времени. Если монета падает обратной стороной, то никакая задача не поступает в систему. Это пример метода розыгрыша случайной величины (метод Монте-Карло), который используется для моделирования вероятностных систем.

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

Введем коэффициент вариации С как отношение стандартного отклонения к среднему:

где σx - среднеквадратичное отклонение для x.

Для экспоненциального закона распределения С= 1, поскольку х и σx для этого закона равняется λ. Для регулярного детерминированного закона распределения С = О (σx =0).

Для системы G/G/1 среднее количество требований определяется как

Используя результат Хинчина-Полячека, можно получить среднее время пребывания в одноканальной СМО по формуле

Основной результат (1.7) состоит в том, что среднее время пребывания требования в системе зависит только от математического ожидания и стандартного отклонения времени обслуживания. Таким образом, время ожидания определяется как

Обычно интересуются нормированным временем ожидания:

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

1.3. Основы дискретно-событийного моделирования СМО

Определим основные понятия и термины, используемые в моделировании.

Система - множество объектов (например, людей и машин), которые взаимодействуют одновременно для достижения одной или большего количества целей.

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

Состояние системы - множество переменных, которые содержат всю информацию, необходимую для описания свойств системы в любое время.

Объект - любой элемент или компонент в системе, который должен быть представлен в модели в явном виде (например, обслуживающее устройство, клиент, машина).

Свойство или атрибут - свойства данного объекта (например, приоритет ожидающего клиента, маршрут процесса выполнения работ в цеху).

Список - множество (постоянное или временное) связанных объектов, упорядоченное некоторым логическим способом (например, все клиенты, находящиеся в настоящее время в очереди ожидания, упорядочены по принципу «раньше прибыл, раньше обслужился» или по приоритету).

Событие - мгновенно возникающее изменение состояние системы (например, прибытие нового требования).

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

Список событий - список намеченных будущих событий, упорядоченных по времени возникновения, известный также как список будущих событий (СБС).

Действие - продолжительность времени указанного промежутка (например, время обслуживания или время между поступлениями заявок), для которого известно, когда оно начинается и заканчивается (хотя оно может быть определено в терминах статистического распределения).

Задержка - продолжительность времени неопределенного промежутка, для которого неизвестно заранее, когда он заканчивается (например, задержка клиента в очереди по правилу «последний пришел - первый обслужился», так как начало обслуживания зависит от будущих поступлений).

Модельное время - неотрицательная возрастающая величина, отражающая течение времени в имитационной модели.

Часы - переменная, отражающая протекание времени моделирования, называется в примерах ЧАСЫ (CLOCK).

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

Для СМО с одним устройством обслуживания событиями будут поступление требования и конец его обслуживания устройством. Начало обслуживания - это условное событие, которое зависит от состояния прибора (занят или свободен) и числа требований, находящихся в очереди. Задержку иногда называют условным ожиданием, в то время как действие называют безусловным ожиданием. Действиями будут время между поступлениями требований и время обслуживания прибором. Завершение действия - событие, часто называемое первичным событием, для управления которым в СБС помещается уведомление о событии. Напротив, управление задержками связано с помещением объекта в другой список, возможно представляющий очередь ожидания до такого времени, когда системные условия разрешат обработку требования. Окончание задержки иногда называют условным или вторичным событием, но такие события не представлены в соответствующих уведомлениях о событиях и не появляются в СБС.

Пример. Представим себе, что есть магазин, в котором один продавец и он же кассир. Если пришедший покупатель застает продавца свободным, то продавец немедленно приступает к его обслуживанию. Продавец переходит в состояние «занятый». Если продавец занят обслуживанием покупателя и в это время приходит другой (другие) покупатели, то они становятся в конец очереди к продавцу. Когда продавец закончил обслуживание, то он переходит в состояние свободный.

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

В табл. 1.1 представлены интервалы времени между приходами покупателей в магазин и требуемыми временами их обслуживания продавцом, а на рис. 1.3 проведено графическим методом «ручное» моделирование СМО с одним устройством.

С точки зрения объектного подхода имеются динамические объекты - требования (ПОКУПАТЕЛИ) и некоторый ресурс - устройство обслуживания (статический объект ПРОДАВЕЦ), которое они используют. Если требование претендует на ресурс, а он занят, то оно ' становится в ОЧЕРЕДЬ к ресурсу. ОЧЕРЕДЬ может быть отдельным объектом или просто списком, связанным с ресурсом. Примем за правило обслуживания - FIFO.

Таблица 1.1

Для каждой пары «требование - ресурс» мы хотим определить, как долго требование j будет использовать ресурс R, т.е. необходимо определить интервал времени, когда требованию j назначен ресурс R и когда оно освободит этот ресурс. Однако, прежде чем ресурс будет назначен требованию j, он должен быть запрошен. В общем случае требование может ожидать в очереди до назначения ресурса.

Опишем алгоритм работы системы с точки зрения «жизненного цикла» ПОКУПАТЕЛЯ, т.е. от момента его прихода в магазин до момента выхода из магазина. Так как покупатели непрерывно приходят в магазин на протяжении некоторого периода времени наблюдения за системой (время, в течении которого моделируется система), то необходимо обеспечить поток ПОКУПАТЕЛЕЙ путем их создания в модели (генерации в некоторые моменты времени - моменты их прихода в магазин). Для генерации ПОКУПАТЕЛЕЙ используем специальную подпрограмму ГЕНЕРАТОР (в языке GPSS этой подпрограмме соответствует блок GENERATE). Алгоритм ее работы следующий:

1. Создать динамический объект ПОКУПАТЕЛЬ в виде структуры данных, включающей в себя поля: номер покупателя -j, момент его прихода –

t jвх, а также при необходимости свойства покупателя или его атрибуты (например, его приоритет). Запланировать событие - приход покупателя j на момент времени t jвх - т.е. создать уведомление о событии в СБС.

2. Запланировать следующее событие для покупателя j -ЗАПРОС-НАЗНАЧЕНИЕ ресурса R (ПРОДАВЦА) на момент времени t jвх. Запланировать приход следующего динамического объекта ПОКУПАТЕЛЬ j + 1, т.е. определить событие прихода следующего покупателя t j+1вх:= t jвх + t j об.

Описание процесса использования ресурса требованием целесообразно разбить на три подпрограммы.

Первая - это ЗАПРОС-НАЗНАЧЕНИЕ ресурса R требованию j (в языке GPSS этой подпрограмме соответствует блок SEIZE). Алгоритм ее работы следующий:

1. Если ресурс R (ПРОДАВЕЦ) может быть сразу назначен требованию j, то изменить состояние ресурса R на «занятый». Запомнить момент начала обслуживания требования tj.+1н. Передать управление подпрограмме ОБСЛУЖИВАНИЕ требования j.

2. Если ресурс R занятый, то поставить требование j в ОЧЕРЕДЬ к ресурсу R.

Вторая подпрограмма - ОБСЛУЖИВАНИЕ требования j (в языке GPSS этой подпрограмме соответствует блок ADVANCE). Ее алгоритм работы очень простой - определить событие «конец обслуживания требования j» как tjK = tjH + tjоб (где tjоб - время обслуживания в устройстве). Т.е. создается уведомление о событии в СБС для передачи управления подпрограмме освобождения ресурса R требованием j.

Третья подпрограмма - ОСВОБОЖДЕНИЕ ресурса R требованием j (в языке GPSS этой подпрограмме соответствует блок RELEASE). Алгоритм ее работы следующий.

1. Изменить состояние ресурса R (ПРОДАВЕЦ) на «свободный». Передать управление подпрограмме УНИЧТОЖЕНИЕ требования.

2. Проверить, есть ли требования в ОЧЕРЕДИ к ресурсу R? Если есть, то выбрать требование из ОЧЕРЕДИ и запланировать для него событие ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Подпрограмма УНИЧТОЖЕНИЕ требования (в языке GPSS этой подпрограмме соответствует блок TERMINATE) необходима для уничтожения структуры данных каждого требования. Если требования не уничтожать, то со временем они переполнят память компьютера.

Кроме перечисленных подпрограмм необходима программа управления процессом моделирования (ПУМ), которая запускает процесс моделирования и отслеживает движение каждого требования па модели путем вызова названных подпрограмм обработки событий. Другое назначение этой программы - вести список упорядоченных во времени событий СБС и продвигать ЧАСЫ модельного времени от события к событию. В языке GPSS функции ПУМ выполняет программа-интерпретатор (транслятор).

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

Планирование будущего события означает, что в момент начала действия его продолжительность вычисляется или определяется (например, из заданного статистического распределения), чтобы установить время конца действия и занести это событие вместе с его временем в СБС. В реальном мире большинство будущих событий не намечено, они просто происходят (как, например, случайные поломки оборудования или случайные поступления покупателей). В модели такие случайные события представлены концом некоторого действия, которое запланировано на будущее модельное время.

В любое данное время моделирования tм СБС содержит все предварительно намеченные будущие события и связанные с этими событиями времена t1м , t2м, ... . В СБС события упорядочены в хронологическом порядке по времени, то есть времена событий удовлетворяют условиям

Время tм значения ЧАСОВ - текущее значение времени моделирования. Событие, связанное со временем t1м, называется предстоящим событием, то есть это следующее событие, которое произойдет. После того, как отображающие состояния системы ЧАСЫ =tм во время моделирования были модифицированы, ЧАСЫ продвигаются ко времени моделирования ЧАСЫ= t1м, предстоящее намеченное событие удаляется из СБС и выполняется подпрограмма события. Выполнение подпрограммы предстоящего события означает, что отображено новое состояние системы в течение времени t1м, которое создано на основании старого состояния модели во время tм и характера предстоящего события. Во время t1м новые будущие события могут произойти или не произойти, но если любые из них намечены, то создаются намеченные события и помещаются в соответствующие позиции в СБС. После того, как новое отображение состояния системы в течение времени t1м было модифицировано, ЧАСЫ продвигаются ко времени нового предстоящего события, и выполняется подпрограмма этого события. Такой процесс повторяется до окончания имитации. На рис. 1.4 показана структурная схема имитационной модели.

В момент начала моделирования (время моделирования t0м = 0) ПУМ передает управление подпрограмме ГЕНЕРАТОР, которая определяет момент прихода первого покупателя и намечает событие ЗАПРОС-НАЗНАЧЕНИЕ ресурса R в СБС на время t}м =t1BX. Так как больше событий в системе нет, то ЧАСЫ переводятся на значение времени t1м вызывается подпрограмма ГЕНЕРАТОР и подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Подпрограмма ГЕНЕРАТОР определяет будущее событие (момент прихода второго покупателя t2ВХ) и намечает это событие в СБС на время t2ВХ .

Подпрограмма ЗАПРОС-НАЗНАЧЕНИЕ проверяет состояние ресурса (ПРОДАВЦА). Так как ресурс R свободный, то он назначается первому покупателю и состояние ресурса R изменяется на «занятый». Запоминается момент начала обслуживания требования t1н. Передается управление подпрограмме ОБСЛУЖИВАНИЕ покупателя 1.

Подпрограмма ОБСЛУЖИВАНИЕ определяет событие конца обслуживания покупателя 1, как t1K = t1H + t1об, т.е. создается уведомление о будущем событии в СБС для передачи управления подпрограмме ОСВОБОЖДЕНИЯ ресурса R требованием 1 на время t1к.

Таким образом, в СБС имеется два элемента - один с намеченным событием появления покупателя 2 на время t2ВХ, а второй с намеченным событием окончания обслуживания покупателя 1 на время t1 K. Если время t2ВХ < t1 K, то ЧАСЫ будут переведены на время t2М = t2ВХ, т. е. снова будет вызвана подпрограмма ГЕНЕРАТОР и сгенерировано появление покупателя 2. В этот же момент времени t2м произойдет вызов подпрограммы ГЕНЕРАТОР, которая наметит в СБС появление покупателя 3 на время t3ВХ и вызов подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурса R, но так как ресурс занят обслуживанием покупателя 1, то покупатель 2 будет поставлен в очередь к ресурсу R.

В СБС снова окажутся два элемента - один для намеченного события появления покупателя 3 на время t3BX, а второй с намеченным событием окончания обслуживания покупателя 1 на время t1k. Если время t3вх >t1k, то ЧАСЫ будут переведены на время t3м=t1K, т, е. будет вызвана подпрограмма ОСВОБОЖДЕНИЕ ресурса R покупателем 1. Она изменить состояние ресурса R (ПРОДАВЕЦ) на «свободный и передаст управление подпрограмме УНИЧТОЖЕНИЕ требования. Затем проверит, есть ли требования в ОЧЕРЕДИ к ресурсу R, и выберет покупателя 2 из ОЧЕРЕДИ, наметив для него событие для подпрограммы ЗАПРОС-НАЗНАЧЕНИЕ ресурса R.

Вызванная в это же модельное время t3м подпрограмма УНИЧТОЖЕНИЕ разрушит структуру данных (удалит ссылку на адрес) для покупателя 1. Эта же подпрограмма при необходимости могла бы вычислить время пребывания покупателя 1 в системе, как t3пр = tЗмt1bx , для дальнейшей статистической оценки времени пребывания покупателей в системе.

В дальнейшем жизненный цикл других покупателей в системе будет происходить по описанному выше алгоритму.

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

1. Через модель пройдут все покупатели, сгенерированные ГЕНЕРАТОРОМ, например, 100 покупателей. В этом случае в СБС после обслуживания последнего, сотого, покупателя не будет ни одного намеченного события.

2. Если поток покупателей от генератора не ограничен (например, генерируется неограниченный пуассоновский поток), то моделирование можно закончить после прохождения через модель определенного количества покупателей, например, 1000. Для этого в подпрограмме УНИЧТОЖЕНИЕ надо поставить счетчик покупателей и прекратить моделирование после 1000 покупателей. В языке GPSS такой счетчик организуется в команде START, которая начинает процесс моделирования.

3. Необходимо промоделировать работу системы в течение заданного периода времени, например, 480 мин. В этом случае можно при каждом продвижении ЧАСОВ модельного времени tм проводить сравнение текущего времени со значением 480. Как только значение модельного времени будет больше или равно 480, необходимо прекратить моделирование. Однако такой способ неудачный, так как может сильно замедлить работу модели из-за проверки условия. Поэтому обычно поступают следующим образом. Генерируют специальное требование-таймер с помощью еще одной подпрограммы ГЕНЕРАТОР с намеченным временем входа в модель tBX = 480. Требование-таймер после генерации сразу же направляется в еще одну подпрограмму УНИЧТОЖЕНИЯ, в которой ставят счетчик требований на единицу. По этому счетчику прекращают моделирование. В этом случае в СБС будет все время находиться элемент для требования-таймера со временем наступления события 480. Как только это событие станет предстоящим намеченным, ЧАСЫ будут переведены на время 480 и моделирование прекратится.

В процессе моделирования обычно собирается статистическая информация о работе модели при каждом продвижении ЧАСОВ модельного времени. Такой информацией может быть величина очереди, время пребывания в очереди и устройстве обслуживания, загрузка устройства, состояние прибора и другие параметры. Для сбора этой информации обычно создается подпрограмма ВЫБОРОЧНЫЙ ИЗМЕРИТЕЛЬ, которая накапливает ее и по окончании моделирования выдает стандартный статистический отчет. В языке GPSS такая статистическая информация накапливается в системных числовых атрибутах (СЧА) и доступна в процессе моделирования только на считывание. Доступ к СЧА дает возможность управлять процессом движения требований, например, ограничивать размер или время нахождения в очереди.

В этой главе даны основы организации моделирования на примере простой СМО. В языке GPSS обычно используются более сложные алгоритмы, описанные в параграфе 4.22.

1.4. Многоканальные системы массового обслуживания

Многоканальная СМО (с несколькими одинаковыми устройствами обслуживания) изображена на рис. 1.5. В отличие от одноканальных СМО многоканальные системы рассчитать сложнее. Теория массового обслуживания позволяет получать аналитические зависимости для расчетов характеристик работы многоканальных СМО в стационарном режиме работы, однако, эти зависимости можно получить только для системы М/М/m.

Если система имеет т одинаковых устройств, то

Для многоканальных СМО р можно трактовать, как математическое ожидание части занятых устройств.

Рассмотрим диаграмму работы многоканальной СМО (рис. 1.6) с двумя устройствами (ПР 1 и ПР 2) и двумя позициями для ожидания в очереди (Поз. 1 и Поз. 2). Время поступления и время, когда требование покинуло систему, показаны рядом с номером требования в нижней и верхней частях рис. 1.6, соответственно. Время наблюдения за СМО H) составляет 55 мин.

Рассчитаем по диаграмме некоторые оценки характеристик работы СМО.

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

где Noб, N- количество обслуженных требований и общее количество требований, соответственно.

2. Пропускная способность СМО в требованиях в минуту

где ТH - время наблюдения за системой.

3. Вероятность отказа в обслуживании

где Nотк - количество требований, которым отказано в обслуживании.

4. Вероятность того, что требование застанет оба устройства свободными,

где Tсв - время, на протяжении которого оба устройства были свободными.

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

где Т13, Т23 - время, когда было занято только первое и только второе устройство, соответственно.

6. Вероятность того, что обслуживанием заняты оба устройства,

где T1+23 - время, когда были занятые оба устройства.

7. Среднее количество занятых устройств 

8. Вероятность того, что в очереди нет требований,

где T°оч - время, на протяжении которого в очереди не было требований.

9. Вероятность того, что в очереди есть только одно требование,

где T1оч - время, когда в очереди было только одно требование.

10. Вероятность того, что в очереди два требования,

где Т2оч - время, на протяжении которого в очереди было два требования.

11. Среднее количество требований в очереди

12. Среднее время пребывания в очереди

где tiоч - время пребывания i -го требования в очереди (j = 1,2,...).

13. Среднее время пребывания в очереди без учета требований, которые не ждали,

где Nоб(-О) - количество требований, которые не ждали в очереди.

14. Среднее время обслуживания требования в устройствах

где tiоб - время обслуживания i -го требования в СМО (i = 1,2,...).

15. Общее среднее время пребывания требования в СМО

16.  Среднее количество требований в системе обслуживания

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

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

Приведем основные формулы для расчетов СМО вида М/М/m [7]. ‘

1. Вероятность того, что все устройства обслуживания свободны,

2. Вероятность того, что занято обслуживанием k-e устройство или в системе находится k требований,

3. Вероятность того, что все устройства заняты (km ). Обозначим эту вероятность через π:

4. Вероятность того, что все устройства заняты обслуживанием и s требований находятся в очереди,

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

6. Средняя длина очереди

7. Среднее количество свободных от обслуживания устройств

8. Среднее количество занятых обслуживанием устройств

9. Среднее время ожидания требованием начала обслуживания в системе

Приведенные формулы позволяют выполнять расчеты для СМО вида М/М/m и сравнивать их с полученными результатами имитационного моделирования. 

ГЛАВА 2. ВЕРОЯТНОСТНЫЕ СЕТИ СИСТЕМ МАССОВОГО

ОБСЛУЖИВАНИЯ

2.1. Общие сведения о сетях

В общем случае сеть СМО можно представить в виде графа, вершинами которого являются одноканальные и многоканальные СМО (дуги определяют потоки передачи требований).

Простейшая разомкнутая или открытая сеть получается при последовательном соединении СМО (рис. 2.1). Она еще называется многофазной СМО.

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

Простейшая замкнутая сеть показана на рис. 2.2. Эта система с отказами и восстановлениями хорошо известна из теории массового обслуживания. В системе постоянно находятся М требований, которые появляются при отказе устройств М. Если устройство отказало, то поступает требование на его ремонт к бригаде с N ремонтниками, которые ремонтируют устройство, а потом отремонтированное устройство восстанавливает свою работу. На рис. 2.2 это показано обратной связью от N устройств. Сеть также используется при моделировании компьютерной системы, которая работает в режиме «запрос - ответ», то есть пользователь не посылает новый запрос к системе до тех пор, пока не получит ответ на предшествующий запрос. Запросы обрабатываются любым из N компьютеров. Примерами таких систем могут быть автоматизированные системы продажи билетов на поезда или самолеты, системы передачи транзакций от кассиров в банке и т. п.

Сеть (рис. 2.3) содержит К узлов и N требований, которые находятся в сети. Каждый узел может иметь одно или несколько одинаковых устройств обслуживания. С вероятностью (или частотой) q0j требования поступают к любому узлу сети, а с вероятностью qkj (j = 1,..., К) требование, которое оставляет узел k, направляется к узлу j. Таким образом, любое требование до завершения своего обслуживания в сети обычно проходит несколько узлов.

Внешняя среда обозначается как узел 0 сети. Если сеть замкнутая, то требования с выхода направляются на вход (рис. 2.3, пунктирная линия) и количество требований N в сети не изменяется.

Для потоков требований в сети справедливы законы о суммарных потоках, которые показаны на рис. 2.4, 2.5, при условии, что сеть работает в установившемся режиме.

Для расчетов сетей массового обслуживания используется теория вероятностных сетей, которая основывается на марковских и полумарковских процессах [8], но большинство результатов получено
только для экспоненциальных законов распределения. При количестве узлов сети больше трех для расчетов используются численные
приближенные методы. Операционный анализ [9] в отличие от теории массового обслуживания опирается на логику работы рассматриваемой или моделируемой системы. Это позволяет установить простые зависимости между параметрами и показателями работы системы, не абстрагируясь от процессов ее функционирования.

2.2. Операционный анализ вероятностных сетей

Операционный анализ вероятностных сетей базируется на следующих принципах:

- все предположения относительно операционных переменных можно проверить измерениями на реальной системе или на ее  модели;

- в системе должен существовать баланс потоков: количество требований, которые покинули систему за некоторый период наблюдения, должно равняться количеству требований, которые поступили в систему за этот же период;

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

Таким образом, рассматриваемая система должна работать в установившемся, а не в переходном режиме.

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

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

Введем операционные переменные, которые можно получить
или измерениями, или в процессе имитационного моделирования системы:

q0j (j=1,k)- вероятность (частота) поступления требований в сеть извне к любому узлу (К- общее количество узлов);

qkj (j = 1,к)- вероятность перехода требований из узла k к узлу j (k = 1,K, J=1,K);

qk0 - вероятность того, что после окончания обслуживания в узле k требования покинут сеть;
        
Ak (k =1,К} - количество требований, которые поступили в узел k;

Ckj (k = 1,К, j =1,K) - количество требований, которые покинули узел k и поступили в узел j;

Bk (k=1,K) - общее время обслуживания требований узлом k.

Т - общее время наблюдения за системой или время моделирования.

Внешнюю среду обозначим как вершину с номером 0. Тогда A0j,Ck0 будут приобретать значения количества требований, которые поступили в узел j, и требований, которые покинули узел k, соответственно.

Узел считается занятым, если в нем есть хотя бы одно требование. Введем дополнительные обозначения:   

Для замкнутой сети А 0= С0.

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

где Uk- коэффициент использования узла;

         где Sk- среднее время обслуживания в узле k;

        где Xk - интенсивность выходящего потока требований из узла k;

где qkj - относительная частота перехода требований между узлами k и j.

Используя выражения (2.2 - 2.4), имеем:

2.3. Операционные зависимости

Основные результаты операционного анализа формулируются в I виде соотношений между операционными переменными. Основой этих соотношений является гипотеза о балансе потоков в сети: количество требований, которые поступили в некоторый узел на протяжении продолжительного периода Т, равняется количеству требований, которые покинули этот узел. Эта гипотеза определяет работу сети СМО в установившемся режиме, то есть требования всегда покидают узлы сети.

Гипотеза о балансе позволяет установить зависимости между операционными переменными для каждого узла сети. Эта гипотеза позволяет записать уравнения баланса потоков:

Справедливость выражения (2.7) вытекает из предположения о балансе

Поделив последнее соотношение (левую и праву его части) на общее время наблюдения Т, получим выражение (2.7). Уравнения (2.7) будут иметь единственное решение для замкнутой сети при заданном X0. Для разомкнутой сети уравнения (2.7) будут линейно зависимыми, однако, и в этом случае они имеют полезную информацию о динамике потоков сети.

Найдем из выражения (2.6) производительность узла

Определим коэффициент посещаемости узла k

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

Поделим левую и правую части выражения (2.7) на Х0:

Выражения (2.10)   справедливы,   если   справедливы   уравнения (2.7), поскольку (2.10) получены из (2.7).

Связь коэффициентов посещаемости и производительности узла определяем по формуле 

Для определения среднего времени пребывания требования в вероятностной сети обозначим это время через R, а для отдельных узлов - через Rk. Введем еще одну операционную переменную - Wk , которая равняется суммарному времени ожидания и времени обслуживания требования узлом k на протяжении времени Т:

Среднее время пребывания в системе можно найти через Rk и коэффициенты посещаемости отдельных узлов, то есть 

Это общий закон времени пребывания, который справедлив и в том случае, если гипотеза о балансе потоков не выполняется.

Среднее количество требований в сети N, которое определяется через среднее количество требований в каждом узле nk, равно

где nk - выводимая операционная переменная, которую можно получить из основных операционных переменных:

Для среднего времени пребывания требований в сети справедлив закон Литтла: среднее время пребывания в устройстве k определяется через среднее количество требований в устройстве и интенсивность потока

Обосновать формулу Литтла можно с помощью операционного анализа. Из выражения (2.15) находим:

Подставляем полученную операционную переменную в уравнение (2.12):

Закон Литтла справедлив также для всей сети в целом. Подставим выражение для Vk из уравнения (2.9) в (2.13) и выражение для Rk из (2.16), тогда

Покажем, как можно использовать операционный анализ для определения времени пребывания в замкнутой сети (рис. 2.6).

Пусть есть М устройств, время обслуживания требования любым из них - Z. Среднее время пребывания требования в сети определяем по формуле

Выражение (2.20)  получено  из таких  соображений.  Среднее время одного цикла взаимодействия, включая время обслуживания требования во внешней сети и пребывание в одном из М устройств, определяется суммой Z + R. Если предположить, что выполняется гипотеза о балансе потоков, то для рассматриваемого цикла справедлива формула Литтла. Поэтому величина (Z + R)X0 должна определять среднее количество занятых устройств или среднее количество работающих устройств для системы с отказами. Таким образом, общее количество устройств

Продемонстрируем использование приведенных соотношений операционного анализа на примерах.

Пример 2.1. Пусть имеем М= 20 устройств. Среднее время обслуживания каждым Z = 25 с (рис. 2.7).

Для узлов l, g, n сети частоты перехода к узлу t равняются соответственно: qlt = 0,5; qmt = 0,7; qnt=0,85, а коэффициенты посещаемости этих узлов равняются Vl = 12; Vg =17; Vn =19. Узел t используется на 50%, среднее время обслуживания узлом t поступающих требований составляет 25 мс. Необходимо найти среднее время пребывания и среднее количество требований в сети.

Определим коэффициент посещаемости узла t, используя уравнения баланса потоков (2.10), записанные через коэффициенты посещаемости узлов:

Находим интенсивность поступления требований в сеть

В выражение (2.22) входят известные из условий операционные переменные: U, = 50% и S, = 0,025 с. Следовательно получим

Из выражения (2.19) находим время пребывания требования в сети

Для определения среднего количества требований в сети воспользуемся формулой Литтла:

Пример 2.2. Рассмотрим сеть, в которую поступают требования как из обслуживающих устройств (замкнутая часть сети), так и извне (рис. 2.8).

Есть М= 40 обслуживающих устройств. Среднее время обслу-пнания каждым Z= 15 с. В результате проведенных исследований получены такие данные о сети:

- среднее время пребывания требований, которые поступают от 40 устройств обслуживания в сеть, равняется 5 с;

- среднее время обслуживания любого требования узлом t составляет 40 мс;

- каждое   требование,    которое   поступает   от   М   устройств обслуживания, порождает 10 требований к узлу t;

- каждое требование, которое поступает в систему извне, порождает 5 требований к узлу t;

  •  узел t используется на 90%.

Нужно определить нижнюю границу времени пребывания в сети требований, которые поступают от М устройств обслуживания с интенсивностью входящего потока x0  и от внешнего источника требований в сеть с интенсивностью Xt, что выходят из узла t.

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

Из выражения (2.20) для потока требований от М устройств находим

где Z- среднее время обслуживания М устройствами; R* - среднее время пребывания требований, которые поступили от 40 устройств обслуживания в сеть. Тогда

Интенсивность потока требований в узел t определяем как сумму

интенсивности потоков требований от устройств обслуживания и интенсивности потока внешних требований, то есть Xt* +Хt ,. Тогда в соответствии с выражением (2.3.1) можно записать:

Используя формулу для коэффициента посещаемости (2.8), находим Xt*:

Теперь можно найти интенсивность Х0 входящего потока внешних требований в сеть

Допустим, что исходные условия изменились и интенсивность входящего потока внешних требований увеличилась втрое, то есть Х0= 1,5 требований/с. Тогда Xt = VtХ0 =7,5 требований/с. Считая, что среднее время обработки требований узлом t не изменилось, получаем, что максимально возможная интенсивность обслуживания требований  узлом t, составляет 1/St = 25 требований/с при 100% использовании узла t. Таким образом, интенсивность обслуживания требований чем t от устройств обслуживания не может превышать

Итак, нижняя граница времени пребывания в сети требований, которые поступают от 40 устройств обслуживания в соответствии с выражением (2.19)

Таким образом, увеличение в три раза интенсивности потока внешних требований приведет к увеличению среднего времени пребывания требований в сети от 40 устройств обслуживания на 2,9 с.

2.4. Анализ узких мест в сети

Поиск узких мест в сети является важным аспектом анализа ее работы. Узкое место создается тем узлом сети, у которого коэффициент загрузки U приближается к единице. В этом узле образуется большая очередь, которая при U1 становится бесконечной, и сеть переходит в неустойчивый режим работы. Такой узел становится «насыщенным» требованиями. Узкие места в сети обусловливают ее пропускную способность, то есть полностью определяют время пребывания в сети. Поэтому при анализе работы сети необходимо особое внимание уделять поиску узких мест.

Покажем на простом примере, почему узкое место определяет пропускную способность сети. Рассмотрим трубопровод, в котором есть трубы разного диаметра, доставляющие воду потребителю. Если после трубы маленького диаметра поставить трубу с любым большим диаметром, то потребитель не получит большего количества воды за единицу времени, чем ее может пропустить узкая труба. Это - так называемый эффект «узкого горлышка». Поэтому при рассмотрении таких систем важно иметь сбалансированные потоки в сети, то есть такой баланс потоков в узлах, при котором среднее время пребывания в сети было бы минимально или ее пропускная способность максимальна.

Приведем соотношения, которые связывают коэффициенты использования узлов с коэффициентами посещаемости этих узлов:

Устройство k будет «насыщено» требованиями, если его коэффициент использования близок к единице. В этом случае при выполнении гипотезы о балансе потоков интенсивности входящего потока и обслуживания будут практически совпадать, то есть

При увеличении числа требований, одновременно обслуживающихся в сети, первым достигнет насыщения тот узел d, который будет иметь максимальную величину Vi Si  i = 1,...,K, то есть

При увеличении количества требований коэффициент использования  Ud приближается к  1   и  Xd = 1/Sd.  Поскольку  X0/Xd=1/Vd , то

Таким образом, исходный поток из сети при большом числе N полностью определяется узлом d, который является узким местом.

Определим минимальное среднее время пребывания требования R0, если в сети есть лишь одно требование, через коэффициенты посещаемости отдельных устройств и время обслуживания устройства

На рис. 2.9 изображен график зависимости интенсивности потока в сети от количества требований в сети. При увеличении N интенсивность x0 монотонно возрастает до предельной асимптоты Vd Sd, то есть пока на эту интенсивность не начнет влиять потенциально узкое место - узел d. На рис. 2.9 через N* обозначено число требований, при котором узкое место еще не влияет на пропускную способность сети.

Для простейшей замкнутой сети, если количество устройств M = 1, то R' = R'0. При увеличении М поток из сети будет возрастать, но не больше, чем Х0 =1/ Vd Sd. Таким образом,

Итак, при увеличении М среднее время пребывания имеет асимптоту MVdSd -Z. На рис. 2.10 показана зависимость среднего времени пребывания в замкнутой сети от числа устройств М. Асимптота, которая создает узкое место в сети, пересекает ось абсцисс в точке Md=Z/ Vd Sd.

Изложенный подход к поиску узких мест в сети просто использовать на практике. Покажем это на примерах.

Пример 2.3. Проведем расчет характеристик сети, которая изображена на рис. 2.11, там же приведены значения операционных переменных Sk qkj и Z.

Запишем уравнения баланса потоков для коэффициентов посещаемости этой сети:

Решая приведенную систему уравнений, получаем

Определяем значения Vk Sk для каждого из узлов сети:

Таким образом, минимальное среднее время пребывания одного требования составляет: R0 = 1 + 0,088 + 0,32 = 2,2 с.

Поскольку  V1S1>V2S2>V3S3, то потенциальным узким местом в сети является первый узел.

Основываясь на рассматриваемом методе операционного анализа, дадим ответ на некоторые вопросы.

1. Пусть измерениями определено, что X0 = 0,715 требований/с, а вреднее время пребывания требования в сети составляет 5,2 с. Какое среднее количество устройств обслуживания взаимодействует с сетью за все время наблюдения?

В соответствии с формулой (2.13) имеем:

2. Можно ли обеспечить среднее время пребывания требований в сети равным 8 с при 30 устройствах обслуживания? Какое максимальное  среднее  время  обслуживания требования должен иметь узел 1, чтобы это стало возможным?         

В соответствии с формулой (2.13) имеем:

Таким образом, при взаимодействии с сетью 30 устройств, среднее время пребывания требования в ней превысит 10с.

Обозначим через S* допустимое среднее время обслуживания требования. Тогда можно записать

то есть максимально возможное среднее время обслуживания требования узлом 1 составляет 0,047 с. На рис. 2.12 изображены графики для асимптоты среднего времени обслуживания требования.

Пример 2.4. Допустим, что в сеть, кроме требований от устройств обслуживания, поступают еще и требования от узла 3, как по казано на рис. 2.13.

На рис. 2.13 параметры со штрихом характеризуют требования узла 3. Измерения в данной сети показали, что узел 3 загружен практически полностью, а время ответа системы равняется 7 с. Как в этих условиях загружен узел 1 и какое значение приобретает Х0 ?

Из рис. 2.13 видно, что V1 = V3 = 1. Тогда V1S1 = 0,05 с, VlSl = 0,1 с.

Таким образом, потенциально узким местом для требований узла 3 есть сам узел 3.

х1 =18,48 требований/с.

Загрузка узла 3, создаваемая требованиями от устройств обслуживания, составляет

Вторая загрузка узла 3 создается требованиями, которые поступают от этого узла (Uз = 0,704).

Поскольку требования от узла 3 циркулируют в замкнутом контуре, то при условии замкнутости сети имеем

Таким образом, узел 1 также используется практически полностью.

Операционный анализ вероятностных сетей СМО и приведенные примеры расчетов таких сетей показывают, как, не прибегая к моделированию, можно получить некоторые расчетные характеристики на уровне средних значений. В технологии имитационного моделирования операционный анализ может быть использован для сравнения результатов моделирования с расчетными значениями при проверке правильности (валидации) имитационной модели и при поиске наилучших решений по результатам моделирования (см. главу 11).

ГЛАВА 3. ВЕРОЯТНОСТНОЕ МОДЕЛИРОВАНИЕ

3.1. Метод статистических испытаний

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

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

Пример 3.1. Пусть четыре стрелка одновременно стреляют по движущейся цели. Вероятность попадания в цель каждым стрелком равняется 0,5 (попал или не попал). Цель считается пораженной, если в нее попало два или более стрелка. Найти вероятность поражения цели.

Эту задачу можно легко решить методами теории вероятности. Вероятность поражения цели Рпор = 1 - Рнепор.

Вероятность не поражения Рнепор определяют как число сочетаний, когда в цель не попал ни один стрелок, плюс попал один из стрелков:

Решим эту задачу методом статистических испытаний. Процедуру розыгрыша реализуем подбрасываниям одновременно четырех монет. Если монета падает лицевой стороной, то считаем, что стрелок попал в цель. Обозначим через т число успешных испытаний. Сделаем N испытании, тогда в соответствии с теоремой Бернулли: Рпорm/N.

Пример 3.2. Пусть есть некоторая цель, на которую бомбардировщики сбрасывают п бомб. Каждая бомба поражает область в виде круга радиусом r (рис. 3.1). Цель считается пораженной, если одновременно бомбами накрыто К процентов площади S. Найти вероятность поражения цели.

Аналитически решить эту задачу очень трудно. Покажем, как ее можно решить методом статистических испытаний.

Наложим координатную сетку на всю возможную область попадания бомб. Разыграем п точек - координат попадания бомб. Опишем возле каждой точки круг радиусом r (рис. 3.2) и определим заштрихованную площадь поражения. Если заштрихованная площадь будет составлять К процентов и больше всей площади цели S, то цель считается пораженной, а испытание успешным. В противном случае цель не будет поражена и испытание не успешное.

Выполним N испытаний. Тогда вероятность поражения цели Рпорm/N, где т - количество испытаний, при которых цель была поражена.

Методом статистических испытаний можно оценить математическое ожидание и другие вероятностные характеристики. Например, оценку математического ожидания площади поражения цели можно определить как M(s)=1/NSi. При N ->°° эта оценка будет приближаться к математическому ожиданию в соответствии с законом больших чисел. В этом выражении Si - площадь поражения в i-м испытании.

Алгоритм метода статистических испытаний такой:

1. Определить, что собой будет представлять испытание или розыгрыш.

2. Определить, какое испытание является успешным, а какое -нет.

3. Провести большое количество испытаний.

4. Обработать полученные результаты статистическими методами и рассчитать статистические оценки искомых величин.

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

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

Для эффективного розыгрыша случайных величин используют генераторы случайных чисел. Такие генераторы строятся аппаратными и программными методами. Наиболее применимыми являются программные методы, которые дают возможность получить последовательности псевдослучайных чисел по рекуррентным формулам. Обычно используется мультипликативный конгруэнтный метод, рекуррентное соотношение для которого имеет вид:

где а и т - некоторые константы. Необходимо взять последнее псевдослучайное число Xi , умножить его на постоянный коэффициент a и взять модуль полученного числа по т, то есть разделить на т и получить остаток. Этот остаток и будет следующим псевдослучайным числом Хi+1 . Для двоичного компьютера m= 2g-1, где g- длина разрядной сетки. Например, для 32-разрядного компьютера от = 231 -1 = 2147483647, поскольку один разряд задает знак числа.

В языке GPSS World используется мультипликативный конгруэнтный алгоритм Лехмера с максимальным периодом, который генерирует 2147483647 уникальных случайных чисел без повторения. Эти числа генерируют специальные генераторы, которые обозначаются RN<№>, где № - номер генератора случайных чисел (может принимать значения от 1 до 7). При обращении к этим генераторам выдаются целые случайные числа в диапазоне от 0 до 999 включительно. При использовании генераторов в случайных функциях распределений случайные числа генерируются в диапазоне от 0 до 0,999999 включительно.

3.2. Моделирование дискретных случайных величин

Моделирование события. Пусть необходимо смоделировать появление некоторого события А, вероятность наступления которого равняется Р(А)= Р. Обозначим обращения к генератору, который разыгрывает псевдослучайные, равномерно распределенные на интервале (О, 1) числа ri через R. Событие а при розыгрыше будет наступать тогда, когда r ≤ Р (рис. 3.3), в противном случае происходит событие А с вероятностью r > Р.

Данный метод используется в языке GPSS для блока TRANSFER в статистическом режиме работы, когда транзакты следуют по двум разным направлениям в зависимости от вероятности (см. параграф 4.9).

Моделирование группы несовместных событий. Пусть есть группа несовместимых событий A1,A2,---,Ak. Известны вероятности наступления событий Р(А1) Р(А2),..., P(Ak). Тогда из-за несовместности событий Пусть pi =P(Ai), p0=0. На отрезке (0, l) отложим эти вероятности (рис. 3.4).

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

Моделирование случайной дискретной величины. Моделирование случайной дискретной величины выполняется аналогично моделированию группы несовместимых событий. Дискретная случайная величина X задается в соответствии с табл. 3.1.

Случайную величину X можно представить как полную группу событий:

Данный метод используется в языке GPSS для моделирования дискретных случайных функций распределения (см. параграф 4.13).

Моделирование условного события. Моделирование условного события А, которое происходит при условии, что наступило событие В с вероятностью Р(А/В), показано на рис. 3.2.3. Сначала моделируем событие В. Если событие В происходит, то моделируем наступление события А, если имеем В, то не моделируем наступление события А.

3.3. Моделирование непрерывных случайных величин

В данном случае используется метод обратной функции. Пусть есть некоторая функция распределения случайной величины (рис. 3.6). Разыграем на оси ординат точку r, используя функцию F(x). Тогда можем получить значение величины x такое, что F(x)=r.

Найдем функцию распределения F(x) случайной величины X. По определению она равна вероятности Р(Х<х). Из рис. 3.7 очевидно, что

Таким образом, последовательность r1, r2, r3,..., принадлежащая R(0, 1), преобразуется в последовательность х1, x2, х3,..., которая имеет заданную функцию плотности распределения f(x).

Моделирование равномерного распределения в интервале (а, b) случайной величины. Для моделирования воспользуемся методом обратной функции. На рис. 3.8 показана функция плотности равномерного распределения.

Находим функцию распределения и приравниваем ее к случайному числу

Моделирование экспоненциального распределения случайной величины. Функция плотности экспоненциального распределения случайной величины            f(x) =λеx  и функция распределения показаны на рис. 1.1.

Воспользуемся методом обратной функции:

Можно показать, что случайная величина (1-R) распределена так же, как и величина R. Тогда, сделав замену (1-R) на R, получаем

Покажем, как, используя метод обратной функции, можно моделировать случайную величину, распределенную по экспоненциальному закону. Подобный подход принят в языке GPSS [10].

Пусть λ = 1. Выполним аппроксимацию функции экспоненциального распределения линейными участками, чтобы можно было использовать ее для моделирования методом обратной функции. Для аппроксимации достаточно 24 точек. В табл. 3.2 занесены соответствующие значения аргумента х и функции F(x), значения которой генерируют с помощью генератора случайных чисел.

На рис. 3.9 и 3.10 показаны графики двух функций. На рис. 3.9 изображена аппроксимация экспоненциальной функции с параметром λ, = 1, а на рис. 3.10 - функция, обратная к аппроксимированной. Первая функция воспроизводит заданные в табл. 3.2 значения. Вторая функция используется для розыгрыша экспоненциального распределения, поскольку удобнее задавать значение x, а получать значение функции.

Если необходимо моделировать случайные величины X, распределенные по экспоненциальному закону с параметром ёх ≠1, которые используется как задержка во времени с параметром T = 1/ ёх, например, для моделирования пуассоновского потока поступления требований, то поступают таким образом:

- генерируют значения случайной величины, распределенной по экспоненциальному закону с λ = 1 (рис. 3.10);

- находят произведение полученного значения и математического ожидания случайной величины Т =1/λx.                                   Рис3.10

В результате получают искомую последовательность значений реализации случайной величины X.

Моделирование нормального закона распределения случайной величины. Для моделирования нормального закона распределения случайной величины нельзя непосредственно воспользоваться методом обратной функции, поэтому используем центральную предельную теорему. Пусть случайная величина X имеет математическое ожидание тх и среднеквадратичное отклонение σх, а случайная величина Z имеет математическое ожидание mz = 0 и среднеквадратичное отклонение σz = 1. Легко показать, что

Сформулируем центральную предельную теорему.

Если Х1,...,Хп - независимые случайные величины со средним значением E[Xi]=a, i=1,n и дисперсией D[Xi]=σ2, i=1,n, то при неограниченном увеличении п функция распределения случайной  функции распределения стандартного нормального закона Ф(z) при всех значениях аргумента, то есть

Для получения нормального закона распределения случайной величины достаточно суммировать шесть случайных величин, полученных с помощью генератора случайных чисел R, и, пронормировав полученные значения так, чтобы определить Z, по формуле (3.8) найти значение X.

Обычно суммируют 12 случайных величин , тогда дисперсия D(Z) будет равняться единице.

Рассмотрим, как моделируются нормально распределенные случайные величины в системе моделирования GPSS.

Выполним аппроксимацию функции нормального распределения случайной величины Z c параметрами mz=0 и σz=l. Для этого достаточно 25 точек. В табл. 3.3 занесенные соответствующие значения аргумента х и функции F (х).

Для того, чтобы получить функцию нормального распределения с математическим ожиданием тх0 и среднеквадратичным отклонением σz≠1, необходимо сделать вычисления по формуле (3.8).

На рис. 3.11 изображен график функции, полученной в результате аппроксимации функции нормального распределения Ф(z), а на рис. 3.12 - более удобный для моделирования график функции (как аргумент используют генератор случайных чисел и получают значение функции).

Таблица 3.3

Если необходимо обеспечить положительные разыгрываемые значения, то нужно выполнить условие тх > 5σх.

В рассмотренных приближенных методах «хвосты» нормального распределения оказываются неточными. Существуют и более точные методы моделирования нормального распределения случайной величины [11].

3.4. Сбор статистических данных для получения оценок характеристик случайных величин

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

Искомыми величинами при использовании метода статистических испытаний являются оценки:

  •  вероятности наступления некоторого события;
  •  математического ожидания случайной величины;

-    дисперсии случайной величины;

-    коэффициентов ковариации или корреляции случайной величины.

Для оценки вероятности р наступления некоторого события А используется частота наступления этого события

где т - частота наступления события, a N- число опытов.

Для оценки математического ожидания случайной величины используется среднее значение

где хi - i-я реализация случайной величины.

Для оценки дисперсии случайной величины ξ используют формулу

где S2  - оценка дисперсии случайной величины ξ.

Непосредственно использовать эти формулы для вычисления дисперсии сложно, поскольку среднее значение изменяется по мере накопления хi то есть нужно запоминать все N значений хi. Поэтому для вычисления используют формулу:

В этом случае достаточно накапливать две суммы значений – хi и xi2.

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

Все статистические оценки должны иметь определенные качественные показатели, к которым относятся несмещенность, эффективность и состоятельность оценки.

Для случайных величин ξ и η с возможными значениями хk , уk оценка корреляционного момента определяется так

3.5. Определение количества реализаций при моделировании

случайных величин

Число испытаний N определяет точность получаемых результатов моделирования. Если необходимо оценить величину параметра а по результатам моделирования хi, то за оценку следует брать величину х, которая выступает в функции от xi.

Из-за случайности х будет отличаться от а, то есть

где ε - точность оценки. Вероятность того, что данное неравенство выполняется, обозначим через α:

Для определения точности результатов статистических испытаний необходимо воспользоваться выражением (3.17).

Определение количества реализаций для оценки вероятности наступления события. Пусть целью моделирования будет определение вероятности наступления некоторого события А, определяющего состояние моделированной системы. В любой из N реализаций процесс наступления события А является случайной величиной, которая может приобретать значение x1=1 с вероятностью р и x2=0 с вероятностью 1-р. Тогда можно найти математическое ожидание

В качестве оценки р используют частоту наступления события А. Эта оценка несмещенная, состоятельная и эффективная.

При условии, что N заведомо задано, достаточно накапливать т:

где ξi - наступление события А в реализации, ξi = {1,0}.

По формулам (3.18-3.20) находим

В соответствии с центральной предельной теоремой (в данном случае можно взять теорему Лапласа) случайная величина m/N – будет иметь распределение, близкое к нормальному (рис. 3.13). Поэтому для каждой достоверности α из таблиц нормального распределения можно найти такую величину ta, что точность ε будет равняться величине

При α = 0,95    ta=l,96.

При α = 0,997  ta=3.

Подставим в уравнение (3.21) выражение дисперсии

Поскольку вероятность р заранее неизвестна, прибегают к пробным испытаниям (N = 50... 100), получают частоту m/N - и подставляют ее значения в выражение (3.23) вместо р, после чего определяют конечное количество испытаний.

Определение количества реализаций для оценки среднего значения случайной величины. Пусть случайная величина имеет математическое ожидание α и дисперсию σ2. В реализации с номером i она принимает значение xi. Для оценки математического ожидания a используем среднее

В соответствии с центральной предельной теоремой при больших значениях N среднее арифметическое х будет нормально распределено с математическим ожиданием α и дисперсией σ2/N-1. Тогда

Поскольку дисперсия оцениваемой случайной величины неизвестна, необходимо провести 50-100 испытаний и оценить σ2, а потом полученное значение оценки подставить в формулу (3.26), чтобы определить необходимое количество реализаций N.

Задачи для самостоятельной работы

Задача 1

Оцените значения константы π.

Учитывая то, что площадь круга S = πr2, используя метод Монте-Карло, найдите площадь круга, а через нее - значение π.

Задача2

Молодой пилот-стажер, который осуществляет свой первый полет, оказался небрежным курсантом и практически ничего не помнил из того, чему его учили. От его пилотирования инструктор сразу же потерял сознание, и при посадке молодому пилоту пришлось полагаться лишь на себя. Вероятность того, что за одну попытку стажер благополучно завершит посадку самолета, составляет 0,1. Определите число заходов на посадку, которое сделает стажер для того, чтобы полет благополучно закончился для него и его инструктора (количество бензина в баках считать неограниченным).

Задача 3

Найдите оценку интеграла , величина которого равняется площади под кривой х3/2 на отрезке 0 ≤ х ≤1.

Задача 4

Вероятность получения зачета студентом, который не посещал лекционные и практические занятия, составляет 0,13. Найдите оценку вероятности того, что студент получит зачет, если общее число сдач зачета не может превышать 7.

Задача 5

Найдите оценку площади равностороннего треугольника со стороной 1 см. Определите уравнения прямых, которые образуют стороны треугольника и используйте эти выражения в процедуре оценки попадания «случайной» точки в треугольник.

Задача 6

Для получения допуска к экзамену студенту необходимо получить зачет по лабораторным работам (лабораторный курс состоит из К лабораторных работ). Вероятность зачета одной лабораторной работы для студента, который не защищал их в срок, составляет 0,3 за один «заход». Найдите оценку количества дней, нужных студенту на получение допуска к экзамену, если за один день он сможет получить зачет не более чем по одной лабораторной работе (на протяжении семестра он не защитил ни одной работы).

Задача 7

Стрелку необходимо выбить четыре мишени. Вероятность поражения одной мишени составляет 0,14. Найдите оценку количества патронов, которое необходимо стрелку для того, чтобы попасть во все четыре мишени.

Задача 8

Молодой пилот-стажер, который полетел в свой первый полет, оказался небрежным курсантом. От его пилотирования инструктор сразу же потерял сознание, и при посадке молодому пилоту пришлось полагаться лишь на себя. Вероятность того, что за одну попытку стажер благополучно совершит посадку самолета, составляет 0,12. Найдите оценку вероятности того, что полет благополучно закончится для него и его инструктора, если бензина в баках хватает только на 20 кругов, а пилот-стажер для одной попытки посадки делает один круг.

Задача 9 [12]

Багдадский вор заключен в подземелье с тремя дверями. Одни двери ведут на волю, вторые - в длинный туннель, а третьи - в короткий. Попав в один из туннелей, вор снова оказывается в темнице. Он пробует выйти на волю, но при этом не помнит, в какие двери входил прошлый раз, то есть предполагается Марковский процесс. Вероятность того, что вор выберет нужные двери, равняется 0,3; вероятность попадания в короткий туннель - 0,2; вероятность попадания в длинный туннель - 0,5. Время пребывания вора в коротком туннеле - 3 мин, в длинном - 6 мин. Определите среднее время поиска пути на волю. Постройте процедуру статистических испытаний для решения задачи.

Задача 10 [14]

Промоделируйте поведение истребителя-бомбардировщика, посланного атаковать некоторый объект ракетами класса «воздух-земля». Каждая ракета наводится индивидуально. Размеры объекта -60x150 м2. Заход на атаку происходит в направлении, которое совпадает с направлением длинной оси цели, точка прицеливания- геометрический центр цели. Фактическую точку попадания для каждой ракеты можно определить горизонтальным и вертикальным отклонениями (рис. 3.14).

Для расстояния, с которого запускают ракеты, оба отклонения независимые, нормально распределенные величины относительно точки прицеливания и имеют нулевое среднее значение. Среднеквадратичное отклонение составляет 60 м в направлении X и 30 м в направлении Y.

Бомбардировщик при каждом заходе выпускает шесть ракет. Взяв объем выборки в 10 заходов, найдите оценку среднего числа попаданий при каждой атаке. Для моделирования нормального распределения случайной величины воспользуйтесь рис. 3.12.

Задача 11

Промоделируйте случайную двумерную дискретную величину (X,Y). Случайная величина (СВ) X может принимать значения 1, 2, 3, 4, а случайная величина Y- 10, 20, 30, 40, причем каждой паре значений XiYi соответствует вероятность p(ij) (см. табл. 3.4).

Таблица 3.4

Задача 12

Промоделируйте случайную двумерную дискретную величину
(X,Y). Случайная величина X может принимать значения 3, 5, 7, 9, а
случайная величина
Y- 150, 250, 350, причем каждой паре значений
хi уi соответствует вероятность  p(ij) (см. табл. 3.5).

Таблица 3.5

;|

Задача 13 [14]

Допустим, что потребление воды в городе имеет нормальное распределение. Найдите оценку среднего потребления воды в день так, чтобы ошибка не превышала ±6000 л с вероятностью 0,95. Известно, что разумная область разброса потребления воды составляет 120 тыс. л/день. Каким должен быть необходимый для этого исследования объем выборки (сколько дней нужно моделировать)?

Задача 14 [12]

Используя результаты 20 имитационных прогонов для оценки времени пребывания посетителей в системе, которые приведены в скобках (1,1; 2,8; 3,7; 1,9; 4,9; 1,6; 0,4; 3,8; 1,5; 3,4; 1,9; 2,1; 3,8; 1,6; 3,2; 2,9; 3,7; 2,0; 4,2; 3,3), вычислите оценки для выборочного среднего, дисперсии и коэффициента вариации. Постройте гистограмму, которая содержит пять интервалов (длина каждого интервала равняется единице), причем нижняя граница первого интервала равняется нулю.

Задача 15

Даны случайные некоррелированные переменные А, В, С. Переменная А имеет нормальное распределение с т = 100 и σa - 20. Переменная В также распределена нормально с т = 20 и σв = 5. Распределение переменной С задано в табл. 3.6.

Таблица 3.6

Используя метод Монте-Карло, оцените среднее значение новой переменной D, которая определяется так: D = (A + B)/C. Используйте выборку из 10 значений, которую необходимо получить с помощью распределения, приведенного на рис. 3.12.

Задача 16

Пусть имеется модель наземной противовоздушной ракетной установки. Сколько нужно смоделировать отражений воздушной атаки, чтобы частота поражения цели отличалась от истинной вероятности не больше чем на 0,02 с вероятностью не меньше чем 0,85?

ГЛАВА 4. СИСТЕМА МОДЕЛИРОВАНИЯ GPSS

4.1. Объекты

Язык GPSS - это язык декларативного типа, построенный по принципу объектно-ориентированного языка. Основными элементами этого языка являются транзакты и блоки, которые отображают соответственно динамические и статические объекты моделируемой системы.

Предназначение объектов системы различно. Выбор объектов в конкретной модели зависит от характеристик моделируемой системы. Каждый объект имеет некоторое число свойств, названых в GPSS стандартными числовыми атрибутами (СЧА)*. Часть СЧА доступна пользователю только для чтения, а на значение других он может влиять, используя соответствующие блоки.

Блоки и транзакты. Каждая GPSS-модель обязательно должна содержать такие объекты, как блоки и транзакты.

В GPSS концепция передачи управления от блока к блоку имеет специфические особенности. Последовательность блоков GPSS-модели показывает направления, в которых перемещаются элементы. Каждый такой элемент называется транзактом. Транзакты - это динамические элементы GPSS-модели.

Блоки языка GPSS представляют собой подпрограммы, написанные на макроассемблере или на языке Си, и содержат набор параметров (операндов) для обращения к ним. Как и во всех языках моделирования в GPSS существует внутренний механизм передачи управления, который реализуется в модельном времени, что дает возможность отобразить динамические процессы в реальных системах. Передача управления от блока к блоку в GPSS-программах реализуется с помощью движения транзактов в модельном времени. Обращение к подпрограммам блоков происходит через движение транзактов.

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

* В GPSS World используется термин «системные числовые атрибуты». При изложении материала авторы придерживаются термина «стандартные числовые атрибуты» в соответствии с известной работой Т. Дж. Шрайбера [10], полагая, что понятие «системная» применимо к глобальной информации, которая не связана с какими-то отдельными элементами. Практически всегда к системным атрибутам относится системное время. См. Е. Киндлер «Языки моделирования», 1985, стр. 18.

Такая аналогия никогда не указывается транслятору GPSS, она остается в воображении разработчика моделей. В табл. 4.1 приведены примеры аналогий между транзактами и элементами реальных систем.

Таблица 4.1

С точки зрения программы - транзакт это структура данных, которая содержит такие поля: имя или номер транзакта; время появления транзакта; текущее модельное время; номер блока, в котором находится транзакт; номер блока, куда он продвигается; момент времени начала продвижения; приоритет транзакта; параметры транзакта: PI, P2, ...

В языке GPSS все транзакты нумеруются по мере их появления в модели. Параметры транзактов отображают свойства моделируемого динамического объекта. Например, если моделируется движение автомобилей на участке дороги, то параметрами транзакта (автомобиля) в зависимости от целей моделирования могут быть скорость, тормозной путь, габариты и др.

Каждый транзакт занимает некоторые объем памяти ЭВМ. После того, как он закончит свое движение по блокам модели, его необходимо уничтожать для освобождения памяти, чтобы избежать ее переполнения. Поскольку транслятору не известно, сколько транзактов одновременно будет находиться в модели, то память под транзакты выделяется динамически.

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

Если транзакт начал свое движение, он передвигается от блока к
блоку по пути, указанному блок-схемой (логикой работы модели). В
тот момент, когда транзакт входит в блок, вызывается соответствующая этому блоку подпрограмма. Далее транзакт (в общем случае) пытается войти в следующий блок. Его перемещение продолжается до  тех пор, пока не выполнится одно из таких возможных условий:

1. Транзакт входит в блок, функцией которого является задержка транзакта на определенное время. Н|  Зактом; среднее время нахождения транзакта в устройстве и др.

2. Транзакт входит в блок, функцией которого является удаление транзакта из модели. В,   нить ДВИжение транзактов. Например, кассир кинотеатра, идя на

3. В соответствии с логикой модели транзакт пытается войти следующий блок, но блок не принимает этот транзакт. В этом случае транзакт остается в том блоке, в котором в данное время находится, но позже будет повторять попытки войти в следующий блок. Когда условия в модели изменятся, одна из таких попыток может быть успешной. После этого транзакт продолжит свое перемещение по модели. Подробнее это рассматривается в параграфе 4.22. момента изменения состояния ключа. Состояние ключа

Если выполняется одно из указанных условий, транзакт остается на месте и в модели делается попытка перемещения другого транзакта. 

Объекты типа «ресурсы». Аналогами обслуживающих устройств реальных систем в GPSS являются объекты типа «ресурсы». К объектам этого типа относятся устройства, многоканальные устройства и логические ключи.

Как и в каждом объектно-ориентированном языке в GPSS каждый объект имеет свойства и методы, которые изменяют эти свойства. В GPSS свойства объектов называют стандартными числовыми атрибутами (СЧА).

Устройство  (одноканальное устройство,  прибор) представляет собой ресурс, который в любой момент времени может быть занят только одним транзактом. Интерпретатор автоматически вычисляет такие его СЧА, как общее время занятости устройства, число транзактов, который занимали устройство, коэффициент использования устройства, среднее время занятости устройства одним транзактом и т. п. В    выполняют транзакты. Записанную в этих объектах информацию

Многоканальные устройства (МКУ) (несколько параллельных одинаковых устройств) представляют собой объекты типа «ресурсы» для параллельной обработки. Они могут быть использованы несколькими транзактами одновременно. Пользователь определяет емкость каждого МКУ, который используется в модели, а интерпретатор ведет учет числа устройств, занятых в каждый момент времени. Интерпретатор также автоматически подсчитывает такие СЧА: число транзактов, которые вошли в МКУ; среднее число каналов, занятых одним транзактом; среднее время нахождения транзакта в устройстве и др.

Некоторые события в системе могут заблокировать или изменить движение транзактов. Например, кассир кинотеатра, идя на обед, ставит табличку «В другое окно», и все следующие клиенты на протяжении обеда обращаются в другую кассу. Для моделирования этих ситуаций введены логические ключи. Транзакт может устанавливать эти ключи в положение «Включено» или «Выключено». Через некоторое время состояние ключа может быть использовано другими транзактами для выбора одного из двух возможных путей движения или ожидания момента изменения состояния ключа. Состояние ключа может быть изменено любым транзактом.

Переменные. Арифметические переменные позволяют вычислять арифметические выражения, которые состоят из операций над СЧА объектов. В выражениях могут быть использованы функции (библиотечные или пользовательские). Булевы переменные позволяют пользователю одновременно проверять несколько условий, исходя из состояния объектов или значений СЧА.

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

Ячейки и матрицы сохраняемых величин. Ячейки сохраняемых величин и матрицы используются для хранения некоторой пользовательской числовой информации, запись в эти объекты выполняют транзакты. Записанную в этих объектах информацию может считывать любой транзакт. Таким образом, эти объекты являются глобальными и доступны из любой части модели.

Очереди. В любой системе движение потока транзактов может быть задержано из-за недоступности ресурсов (например, необходимые устройства или МКУ уже заняты). В этом случае задержанные транзакты становятся в очередь - еще один тип объектов GPSS. Учет этих очередей составляет одну из основных функций интерпретатора.

Пользователь может специально определить точки модели, в которых необходимо собирать статистику об очередях, то есть установить регистраторы очереди. Тогда интерпретатор будет автоматически собирать статистику об очередях (длину очереди, среднее время нахождения в очереди и т.п.). Вся эта информация является СЧА и доступна пользователю в процессе моделирования.

Интерпретатором автоматически поддерживается дисциплина обслуживания очереди FIFO («первым пришел - первым обслужился»), и пользователь может получить стандартную статистическую информацию только об этих очередях. Если у пользователя возникает необходимость организовать очередь из транзактов с другой дисциплиной обслуживания (например, LIFO ), то для этого используются списки пользователей. Эти списки также помогают осуществлять синхронизацию движения разных транзактов по модели.

Таблицы. Объект «таблица» предназначен для сбора статистики о случайных величинах, заданных пользователем. Таблица состоит из частотных классов, в которые заносится число попаданий конкретной величины (некоторого СЧА). Для каждой таблицы вычисляется математическое ожидание и среднеквадратическое отклонение.

4.2. ЧАСЫ модельного времени

Разные события реальных систем происходят в течение некоторого периода времени. Например, покупатели приходят в магазин, когда подходит их очередь, они попадают на обслуживание. Когда покупки сделаны, покупатели покидают магазин. Если все эти события представить в модели, то их возникновение должно происходить на фоне модельного времени. Интерпретатор автоматически обслуживает ЧАСЫ модельного времени.

В момент начала моделирования интерпретатор планирует появление первого транзакта. После этого ЧАСЫ модельного времени устанавливаются на значение времени, которое соответствует моменту появления первого транзакта в модели. Этот транзакт (и другие, если они приходят в этот же момент времени) входит в модель. Далее он передвигается через все возможные блоки модели, которые ему встречаются. События, которые возникают вследствие перемещения транзакта через блоки, планируются на дальнейшие моменты времени. Естественно, что в этот первый отмеченный момент времени ничего больше в системе не происходит. Интерпретатор GPSS продвигает дальше значения ЧАСОВ к тому значению времени, на которое запланировано следующее ближайшее событие. Если во второй, отмеченный ЧАСАМИ момент времени, нет транзактов, которые нужно перемещать, ЧАСЫ снова продвигаются вперед и т.д. Именно так, от события к событию, и происходит смена модельного времени.

Особенности ЧАСОВ GPSS:

1. ЧАСЫ в ОР88 регистрируют целые значения (за исключением языка GPSS World, где время может иметь действительные значения), то есть события могут появляться только в целые моменты времени. Это сделано с целью ускорения процесса моделирования, поскольку целочисленная арифметика выполняется процессором ЭВМ быстрее и требует меньше памяти.

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

3. Система GPSS является интерпретатором «следующего события». Иначе говоря, после того, как модель полностью скорректирована в данный момент дискретно изменяющегося времени, ЧАСЫ перемещаются к следующему моменту времени, на который запланировано следующее событие. Таким образом, ЧАСЫ модельного времени продвигаются от одного события к другому.

4.3. Типы операторов

Операторы ОР88 делятся на три типа:

1) блоки;

2) операторы описания данных;

3) команды GPSS.

Общие сведения о формате операторов GPSS. В GPSS для ссылки на числа, блоки и объекты используются имена (идентификаторы). Имя представляет собой алфавитно-цифровую последовательность длиной до 20 символов в GPSS/PC и до 250 символов в GPSS World, которая начинается с буквы. Допускается использование символов только латинского алфавита, цифр и знака подчеркивания.

Формат GPSS-блоков такой:

[Номер строки] [< Метка >] < Операция > < Операнды > <; Комментарии >

Номер строки. Обязательное поле для GPSS/PCGPSS World - игнорируется). Начинается с первой позиции строки. Представляет собой десятичное число.

Метка (имя блока). Содержимым поля является имя - последовательность символов, начинающаяся с буквы. В некоторых операторах это поле является обязательным.

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

Операнды. Блоки могут иметь операнды. Операнды блоков задают информацию, специфичную для действия данного блока. Число операндов блока зависит от типа блока. В блоках не может использоваться больше семи операндов. Операнды в общем случае обозначаются символами: А, В, С, D, E, F, G. Значения операндов определяются типом блока. Одни операнды некоторых блоков должны быть определены всегда, а другие могут задаваться или не задаваться (т.е. являются необязательными). Операнды следуют один за другим и отделяются запятыми или одним пробелом. Если операнд опущен, то вместо него ставится запятая. Между операндами не должно быть более одного пробела, так как это будет означать, что операнды закончились и интерпретатор прекращает чтение строки.

Комментарии. Необязательное поле. Комментарии отделяются от поля операндов символом «;». Допускается запись комментария с начала строки. В этом случае в первой позиции строки ставится символ «;» или «*». В GPSS/PC допускаются комментарии с использованием заглавных или строчных букв только латинского алфавита, в GPSS World также допускается использование символов кириллицы.

*Термин используется согласно [10]. В GPSS World для этого поля используется термин Verb - глагол.

Строка описания блока может содержать до 79 символов в С PSS/PC и до 250 символов в GPSS World. При описании форматов квадратные скобки [ ] указывают на необязательность поля.

Именами и метками не могут быть названия или начальные символы названии блоков, операторов, команд и СЧА. Во избежание конфликтов с ключевыми словами рекомендуется в именах использовать символ подчеркивания.

4.4. Внесение транзактов в модель. Блок GENERATE

Блок GENERATE (ГЕНЕРИРОВАТЬ) - это блок, через который транзакты входят в модель. Не существует ограничений на количество разных блоков GENERATE в одной модели.

Интервал времени между последовательными появлениями транзактов из блока GENERATE называют интервалом поступления. Когда транзакт входит в модель через блок GENERATE, интерпретатор планирует время поступления следующего транзакта путем розыгрыша случайного числа с соответствующим распределением интервалов поступления на время, равное текущему значению ЧАСОВ плюс разыгранное значение. При достижении этого значения модельного времени следующий транзакт вводится в модель через блок GENERATE и т.д.

Разработчик должен задать функцию распределения интервалов поступления транзактов в блоке GENERATE.

Все возможные виды случайных распределений интервалов поступления транзактов в GPSS делятся на равномерное распределение и другие виды распределений. В нашем случае специально рассматривают самое простое из всех случайных нетривиальных распределений - равномерное распределение. Использование других видов распределений требует задания функций, которые описаны ниже (см. параграф 4.13).

Формат блока:

GENERATE      [A],[B],[C],[D],[E]

Таблица 4.2

Значение операндов:

А - среднее значение интервала поступления;

В - величина разброса возможных значений относительно среднего значения. (Если операнд В не задается, то интервал времени поступления - детерминированная величина);

С - момент времени, в который в блоке GENERATE должен
появиться первый транзакт. (После этого первого прихода все остальные приходы транзактов возникают в соответствии с распределением, заданным операндами А и В);

D - ограничитель общего числа транзактов, которое может войти в модель через данный блок GENERATE на протяжении времени моделирования. (Если это число достигнуто, данный блок GENERATE перестает быть активным);

Е - уровень или класс приоритета каждого из транзактов, которые вводятся в модель через данный блок GENERATE. (Всего существует 128 разных уровней, которые задаются с помощью чисел от 0 до 127. Чем больше число, тем выше приоритет).

  1.  Транзакты не могут входить в блок GENERATE, так как он сам их генерирует.
  2.  Если в модели GPSS/PC встречаются подряд два
    или больше блоков
    GENERATE, то последний блок переопределяет операнды предыдущих блоков. В GPSS World транслятор
    выдает ошибку.
  3.  Операнды не могут быть отрицательными числами.

Операнды А, В, С целочисленные (в GPSS World могут быть действительными числами).

Пример 4.1

1. Задание равномерного закона распределения:

 GENERATE      6,4

Операнды: А = 6, В = 4. Интервал времени поступления является «случайным числом со средним значением 6 и полем допуска 8, то есть он может приобретать только одно из девяти разных значений: 2, 3,4,5,6,7,8,9,10.

2. Задание детерминированного значения интервалов поступления:

GENERATE      10

Операнды: А = 10, В = 0 (по умолчанию). Транзакты входят в модель каждые 10 единиц модельного времени.

3. Генерирование одного транзакта.

GENERATE      ,„1

Операнды: А = В = С = 0 (по умолчанию), D = 1. В нулевой момент в модель входит один транзакт.

Блоки GENERATE являются основными средствами создания транзактов и ввода их в модель. Кроме блока GENERATE, для ввода транзактов в модель используется также блок SPLIT, который создает заданное число копий транзактов, вошедших в блок.

Задание для самостоятельной работы:

1. Напишите сегмент модели, который моделирует поступление 14 транзактов с равномерным законом распределения (23±9).

2. Смоделируйте приход в нулевой момент времени пяти транзактов с уровнем приоритета 25.

3. Смоделируйте ситуацию, когда Транзакты поступают в модель каждые 45±15 мин (первый транзакт появляется на 20-й минуте).

Единица модельного времени - 0,1 мин.

4.5. Удаление транзактов из модели. Блок TERMINATE

Транзакты удаляются из модели, попадая в блок TERMINATE (ЗАВЕРШИТЬ). В этот момент освобождается память, выделенная под транзакт. Эти блоки всегда позволяют выйти всем транзактам,
которые пытаются это сделать. В модели может быть любое количество блоков
TERMINATE.
           Формат блока:

TERMINATE    [A]

Операнд А является величиной уменьшения специального счетчика, который называется счетчиком завершения. Этот операнд задает величину, которая вычитается из счетчика каждый раз, когда транзакт входит в блок TERMINATE. По умолчанию А = 0. Вход транзакта в блок TERMINATE с нулевым значением операнда А не вызывает уменьшения счетчика завершения.

Счетчик завершения - это ячейка в памяти ЭВМ, которая хранит целое положительное число. Начальное значение этого счетчика устанавливается в начале моделирования. Оно равняется значению операнда А команды START (НАЧАТЬ). В процессе моделирования транзакты попадают в блок TERMINATE и, таким образом, уменьшают значение счетчика на величину операнда А. Моделирование заканчивается, когда значение счетчика становится равным нулю или отрицательному числу.

1. В модели может быть много блоков TERMINATE,
но счетчик завершения - один, с начальным значением, указанным в команде START.

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

Интерпретатор начинает моделирование по команде START. Ее

формат:

START A,[B],[C],[D]

В операнде А задается начальное значение счетчика завершения. О назначении остальных операндов будет рассказано в параграфе 4.27.

Управление продолжительностью процесса моделирования.

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

1) завершать моделирование после того, как модель покинет заданное число транзактов определенного типа;

2) завершать моделирование по истечению заданного интервала времени.

Первый способ:

1. В команде START операнду А присваивается значение заданного числа транзактов.

2. Во всех блоках TERMINATE, через которые транзакты заданного типа покидают модель, операнду А присваивается значение «1» или другое, отличное от нуля (соответственно содержательному значению транзактов).

3. Во все других блоках TERMINATE используется значение операнда А по умолчанию (А = 0). Значение счетчика завершения не будет зависеть от этих блоков.

Первый способ позволяет закончить моделирование, когда через модель пройдет заданное количество транзактов, например 1000:

GENERATE     40,5

TERMINATE    
          START 1000

Второй способ:

Пусть разработчик выбрал за единицу модельного времени 1 мин и хочет Смоделировать поведение системы на протяжении 8 часов. Это можно сделать таким образом:

1. Ввести в модель таймер-сегмент, состоящий из двух блоков:

GENERATE      480

TERMINATE    I

2. Во всех других блоках TERMINATE в модели использовать значение операнда А по умолчанию (А = 0). Это означает, что прекращение моделирования, определяемое счетчиком завершения, не будет зависеть от других блоков TERMINATE.

3. В команде START операнд А должен равняться единице.

Таким образом, в процессе моделирования завершение движения транзактов в других блоках TERMINATE не влияет на счетчик завершения. В момент времени 480 транзакт выйдет из блока GENERATE и сразу же перейдет в блок TERMINATE. Счетчик завершения уменьшится на единицу, и интерпретатор завершит моделирование.

Задание для самостоятельной работы:

1. Напишите сегмент программы, в котором моделирование заканчивается после того, как через модель пройдут 300 транзактов. Транзакты должны поступать в модель каждые 25±4 ед. модельного времени.

2. Задайте время моделирования работы системы "8 часов. Единица модельного времени - 1 сек.

4.6. Элементы, отображающие одноканальные обслуживающие

устройства

Рассмотрим элементы, которые используются для представления обслуживания. Аналогами обслуживающих элементов могут быть люди, механизмы, линии связи и другие объекты реальных систем. В GPSS такие объекты моделируются с помощью устройств, МКУ, логических ключей.

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

1) либо подождать своей очереди,

2) либо направиться в другое место,

3) либо, если вновь пришедший транзакт имеет больший приоритет, устройство прерывает текущее обслуживание и начинает обслуживать новый транзакт.

2. Когда транзакт поступает в устройство, он должен пробыть там необходимое для обслуживания время.

Всем устройствам необходимо задавать имена. Они могут быть или числовыми (числа должны быть положительными целыми), или символьными. Во время трансляции символьным именам сам транслятор присваивает числовые значения.

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

Первый шаг. Ждать своей очереди, если это необходимо. Ожидание длится в течение некоторого интервала времени.

Второй шаг. Когда подходит очередь, занять устройство. Событие «занятие устройства» происходит в некоторый момент модельного времени.

Третий шаг. Устройство находится в состоянии занятости до тех пор, пока не закончится обслуживание. Для обслуживания необходим некоторый интервал времени.

Четвертый шаг. Когда обслуживание закончится, освободить устройство. Событие «освобождение устройства» происходит в некоторый момент модельного времени.

Эта последовательность шагов выполняется GPSS при моделировании использования устройства. Второй и четвертый шаги реализуются блоками SEIZE (ЗАНЯТЬ) и RELEASE (ОСВОБОДИТЬ).

Формат блока:

SEIZE A

Этот блок имеет следующие свойства:

1. Если в текущий момент времени устройство используется, то транзакт не может войти в блок и должен ожидать своей очереди.

2. Если устройство свободно, транзакт может войти в блок. Вход транзакта в блок вызывает выполнение подпрограммы обработки этого блока. Состояние устройства изменяется со СВОБОДНОЕ на ЗАНЯТОЕ.

Предварительного объявления устройства в модели не требуется, так как тот факт, что блок SEIZE используется, свидетельствует о существовании данного устройства.

Предназначением блока RELEASE является изменение состояния ранее занятого устройства с ЗАНЯТОГО на СВОБОДНОЕ. Блок RELEASE никогда не запрещает вход транзакта.

Формат блока:

RELEASE A

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

Статистическая информация о работе устройства при моделировании собирается автоматически.

Если в модели используются объекты типа «устройство», то в файле стандартной статистики будет представлена информация об использованных устройствах.

Таблица 4.5

Статистику работы устройств в процессе моделирования можно наблюдать в окне устройств для GPSS/PC (перейдя в это окно с помощью клавиш [ALT+F]) или в окне Facilities Window для GPSS World.

1. После блока SEIZE может сразу же следовать другой блок SEIZE, если транзакт должен одновременно занять
два или более устройств (например, рабочего и инструмент).

2.Транзакт не может освободить устройство, которое
он не занимал.

4.7. Реализация задержки во времени. Блок ADVANCE

Перевод с английского языка блока ADVANCE (ЗАДЕРЖАТЬ) - продвигать, а не задерживать. Этот блок действительно продвигает ЧАСЫ модельного времени на некоторое значение, но фактически он осуществляет задержку продвижения транзакта в течение некоторого интервала времени. Обычно этот интервал задается случайной величиной.

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

1) детерминированное (постоянное);

2) равномерное распределение;

3) другие распределения.

Как и при использовании блока GENERATE особо рассматривается равномерное распределение случайных величин. Применение более сложных видов распределений требует использования дополнительных функций (см. параграф 4.13).

Формат блока:

ADVANCE        A[,B]

Таблица 4.6

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

Если время пребывания в блоке равно нулю, то вместо задержки в блоке ADVANCE интерпретатор сразу же пытается переместить этот транзакт в следующий блок. Более подробно о взаимодействии блока ADVANCE с интерпретатором описано в параграфе 4.21.

1. В GPSS/PC не допускаются дробные значения времени задержки.

2.Отрицательное значение задержки всегда вызывает
ошибку.

Пример 4.2

Использование блока ADVANCE:

ADVANCE        30,5

Время задержки транзакта в этом блоке - случайная величина, равномерно распределенная на интервале [25, 35], которая принимает одно из 11 целых значений.

Пример 4.3

Классический случай использования последовательности SEIZE - ADVANCE - RELEASE:

SEIZE PRIB

ADVANCE 16,4

RELEASE PRIB

Транзакт, двигаясь по этой цепочке блоков, займет устройство с именем PRIB, задержится там на 16+4 единицы времени и затем покинет его. После того как транзакт войдет в блок RELEASE и соответствующая этому блоку подпрограмма закончится, интерпретатор попытается переместить транзакт в следующий блок модели и следующий транзакт может уже использовать устройство PRIB.

Блоки ADVANCE можно располагать в любых местах программы, а не только между блоками SEIZE и RELEASE.

Задания для самостоятельной работы:

1. Приведите фрагмент программы, который моделирует обработку детали на станке. Название устройства - MACHINE, время об
работки 10 ед. модельного времени.

2. Приведите фрагмент программы, который описывает процесс шлифования изделия. Шлифование занимает 4 + 1 мин., в каждый момент времени может обрабатываться только одно изделие. Единица модельного времени - 1 с.

3. Приведите фрагмент программы, который иллюстрирует по
краску двигателя в одноканальном устройстве покраски
PAINT. По
краска занимает 10±3 мин. Единица модельного времени - 1 с. Как
определить коэффициент загрузки устройства покраски?

4.8. Сбор статистики об ожидании. Блоки QUEUE, DEPART

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

Система моделирования GPSS обеспечивает возможность сбора статистики с помощью такого средства, как регистратор очереди. При использовании регистратора очереди в тех точках модели, где число ресурсов ограничено, интерпретатор автоматически начинает собирать различную информацию об ожидании с помощью СЧА, а именно:

1) число входов транзактов в очередь;

2) количество транзактов, которые фактически присоединились к очереди и сразу ее покинули, т.е. имели время ожидания равное нулю;

3) максимальная длина очереди;

4) среднее число ожидавших транзактов;

5) среднее время ожидания тех транзактов, которым пришлось ждать.

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

QUEUE A|,B|
         DEPART            A|,B|

 Таблица 4.7

При входе транзакта в блок QUEUE (СТАТЬ В ОЧЕРЕДЬ) выполняются четыре действия:

1) счетчик входов для данной очереди увеличивается на В;

2) длина очереди (счетчик текущего содержимого) для данной очереди увеличивается на В;

3) значение текущей длины очереди хранится в стандартном числовом атрибуте q$<hmh очереди>;

4) транзакт присоединяется к очереди с запоминаем ее имени и значения текущего модельного времени.

Транзакт перестает быть элементом очереди только после того, как он переходит в блок DEPART (ПОКИНУТЬ ОЧЕРЕДЬ)соответствующей очереди. Когда это происходит, интерпретатор выполняет такие операции:

1) длина очереди соответствующей очереди уменьшается на В;

2) используя привязку к значению времени, определяет: является ли время, проведенное транзактом в очереди, нулевым; если да, то такой транзакт по определению является транзактом с нулевым пребыванием в очереди и одновременно изменяется счетчик нулевых вхождений;

3) ликвидируется «привязка» транзакта к очереди.

Если в модели используются объекты типа «очередь», то в файле стандартной статистики будет представлена информация об этих объектах. В конце моделирования интерпретатор автоматически выдает статистические данные: значение счетчика входов, максимальное значение длины очереди, среднее значение длины очереди, текущее значение длины очереди в конце периода моделирования, среднее значение времени нахождения в очереди и т.д.

Статистическая информация об ожидании выдается в следующем виде:

Пример 4.4

Пусть необходимо собрать статистику об ожидании в очереди при обслуживании устройством PRIB, тогда в сегмент модели будут введены блоки QUEUE и DEPART:

QUEUE QPRIB

SEIZE PRIB

DEPART QPRIB

ADVANCE 16,4                                                                                                             

RELEASE PRIB

В этом примере все транзакты, попадающие в устройство, должны пройти через пару QUEUE - DEPART даже тогда, когда устройство свободно и его можно сразу же занять.

Пример 4.5

 Увеличение на единицу длины QSQPR1 очереди QPR1:

QUEUE QPR1

Увеличение на две единицы длины QSQPR2 очереди QPR2:

QUEUE QPR2,2

Уменьшение   на   единицу   длины   Q$QWORKER   очереди QWORKER:

DEPART   QWORKER

1. Когда транзакт входит в блок QUEUE, то ищется очередь с именем, определенным операндом А. При необходимости очередь создается.

2. Блок QUEUE не поддерживает список членов очереди, он только добавляет единицы к длине очереди.

3. Использование регистратора очереди необязательно. С его помощью интерпретатор собирает лишь статистику об ожидании. Еcли же регистратор не используется, то статистика не собирается, но везде, где должна возникать очередь, она возникает. Ожидание является следствием состояния устройства, а не следствием использования регистратора. Если в планы не входит обработка статистических данных об очередях, то лучше не собирать статистику - это сэкономит время, расходуемое на моделирование.

4. Один и тот же транзакт может одновременно увеличить длину нескольких очередей.

5. При выходе транзакта из очереди через блок DEPART транзакту не обязательно уменьшать длину очереди на ту же величину, на которую он увеличил ее при входе в блок QUEUE. Но в итоге число входов в очередь должно равняться числу выходов из нее.

Задания для самостоятельной работы:

1. Увеличить на три единицы длину очереди с номером 3.

2. Увеличить длину очереди QPR в два раза.

3. Приведите фрагмент программы, который иллюстрирует обработку детали на станке. Устройство - MACHINE, время обработки 10 ±4 ед. модельного времени. Как определить среднее время пребывания деталей в очереди на обслуживание станком?

4. Уменьшить длину очереди с номером 1 на три единицы.

5. Обнулить длину очереди QPR.

4.9. Переход транзакта в блок, отличный от последующего. 

Блок TRANSFER

В GPSS блок TRANSFER (ПЕРЕДАТЬ) может быть использован в девяти разных режимах. Рассмотрим три основных.

Блок TRANSFER в режиме безусловной передачи. Его формат:

TRANSFER       ,B

Таблица 4.8

Позиция блока - это номер или метка блока. Так как операнд А
не используется, то перед операндом
В должна стоять запятая. В ре
жиме безусловной передачи блок
TRANSFER не может отказывать
транзакту во входе. Кстати, если транзакт входит в блок, то он сразу
же пытается войти в блок
В.

Транслятор GPSS/PC не улавливает пропущенную запятую вместо операнда А (например, TRANSFER LAMD). На этапе трансляции метке LAMD присваивается числовое значение, и транзакт в этом случае направляется в блок с соответствующем номером.

Статистический режим. В этом режиме осуществляется передача транзакта в один из двух блоков случайным образом. Формат блока:

TRANSFER      A,[B],C

Таблица 4.9

При задании вероятности (операнд А) используется не более трех цифр, первый символ записи частоты «.» (десятичная  точка),   если   используется  действительное число, которое должно быть в пределах от 0 до 1,0 (например, 0,235). Если операнд - положительное целое число, то вероятность интерпретируется в долях тысячи.

Пример 4.6

TRANSFER .333,LPRIB1,LPRIB2

LPR1B1              SEIZE   PR1

LPRIB2              QUEUE QPR2

С частотой 0,667 транзакт переходит в блок с меткой LPRIB1 и с частотой 0,333 - в блок с меткой LPRIB2.

Пример 4.7

TRANSFER 4,,LPRIB2
         SEIZE                                      PR1

LPRIB2 QUEUE              QPR2

С частотой 0,6 транзакт переходит в блок SEIZE PR1 и с частотой 0,4 - в блок с меткой LPRIB2.

Режим BOTH. Если в операнде А стоит зарезервированное слово BOTH, то блок TRANSFER работает в режиме BOTH.

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

Пример 4.8

TRANSFER BOTH,LL1,LL2

LL1 SEIZE      PRI1

LL2 SEIZE      PRI2

Транзакт сначала пытается перейти в блок с меткой LL1. Если устройство PRI1 занято, транзакт пытается войти в блок с меткой LL2. Если транзакт не может войти и в этот блок (устройство PRI2 также занято), он остается в списке текущих событий и повторяет эти попытки при каждом просмотре списка до тех пор, пока не выйдет из блока TRANSFER.

1. Не путайте метку блока SEIZE с именем соответствующего этому блоку устройства.

2. Если бы меткой LL1 был помечен блок QUEUE, а не блок SEIZE, то все транзакты были бы направлены по метке LL1, так как в отличие от блока SEIZE блок QUEUE всегда готов принять транзакты.

Задания для самостоятельной работы:

1. На некотором станке четыре работника по очереди обрабатывают детали. Время обработки детали - 15±2мин, Промоделируйте работу станка на протяжении 8 часов (транзакты - работники).

2. На станцию технического обслуживания, которая состоит из бокса для ремонта и бокса для техосмотра, каждые 25±10 минут поступают автомобили. Из них 73% требуют ремонта, который продолжается 45±15 минут, а 27% проходят техосмотр (17±8 минут). Промоделируйте 40 часов работы станции технического обслуживания.

3. В магазине работают два кассира, один из которых более проворный, поэтому покупатели и отдают ему предпочтение. Покупатели заходят в магазин каждые 7±2 минут. Первый кассир обслуживает покупателя за 2±1 мин, а второй - за 3±2 мин. Промоделируйте работу магазина на протяжении 40 часов.

4. Выполните задание 1 из главы 7.

4.10. Моделирование многоканальных устройств

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

Однако очень часто параллельно работающие устройства являются одинаковыми, и GPSS предоставляет для их моделирования объект, называемый многоканальным устройством (МКУ).

Количество устройств, которое моделируется каждым из МКУ, определяется пользователем. В этом смысле употребляют термин «емкость МКУ». Эта емкость заранее должна быть определена пользователем, чтобы интерпретатор знал, сколько устройств использует данное МКУ.

Блоки ENTER (ВОЙТИ) и LEAVE (ВЫЙТИ). Использование МКУ аналогично использованию одиночного устройства. Элементом, который занимает и использует МКУ, является транзакт. При моделировании МКУ события происходят в следующем порядке:

1) транзакт ожидает своей очереди, если это необходимо;

2) транзакт занимает устройство;

3) устройство осуществляет обслуживание на протяжении некоторого интервала времени;

4) транзакт освобождает устройство.

Блоки ENTER и LEAVE моделируют события 2 и 4.

Формат блоков:

ENTER A[,B]
            
LEAVE              А[,В]

Когда транзакт входит в блок ENTER, интерпретатор выполняет следующие действия:

1) увеличивает счетчик входов МКУ на значение операнда В;

2) увеличивает текущее содержимое МКУ на значение операнда В;

3) уменьшает доступную емкость МКУ на значение операнда В. Когда транзакт входит в блок LEAVE, интерпретатор выполняет обратные действия:

1) уменьшает текущее содержимое МКУ на значение операнда В;

2) увеличивает доступную емкость МКУ на значение операнда В.

Операнду В можно присвоить значение, отличное от единицы. Например, пусть транзакт моделирует корабль, а МКУ - причалы в порту. В зависимости от размера корабль может занимать нескольких причалов, т.е. В>1.

Если в модели используются объекты типа МКУ, то в файле стандартной статистики об этих объектах будет представлена такая информация:

Поле STORAGE определяет имя или номер МКУ.

Поле САР. определяет емкость МКУ, заданную оператором STORAGE.

Поле REMAIN определяет количество единиц свободной емкости МКУ в конце периода моделирования.

Поле MIN определяет минимальное количество используемой емкости МКУ за период моделирования.

Поле МАХ определяет максимальное количество используемой емкости МКУ за период моделирования.

Поле ENTRIES определяет количество входов в МКУ за период моделирования.

Поле AVL. определяет состояние готовности МКУ в конце периода моделирования: 1 - МКУ готов, 0 - не готов.

Поле AVE.C определяет среднее значение занятой емкости за период моделирования.

Поле UTIL. определяет средний коэффициент использования всех устройств МКУ.

Поле RETRY определяет количество транзактов, ожидающих специальных условий, зависящих от состояния МКУ.

Поле DELAY определяет количество транзактов, ожидающих возможности входа в блок ENTER.

Для GPSS/PC статистику о работе МКУ можно наблюдать в окне МКУ, перейдя в это окно с помощью клавиш [ALT+S], а для GPSS World - в окне Storages Window.

Определение емкости МКУ. Все используемые в модели МКУ должны быть заранее описаны, т.е. должно быть определено количество однотипных устройств, входящих в МКУ. Для этого используется оператор STORAGE (ХРАНИЛИЩЕ или ПАМЯТЬ), определяющий емкость МКУ. Название STORAGE становится понятным, если представить себе, что МКУ это автоматизированный склад или многоэтажный гараж с определенным числом мест, которое и задает этот оператор. В таких случаях МКУ определяет не количество одинаковых устройств для обслуживания, а количество одинаковых мест для хранения.

Формат оператора задания емкости МКУ:

Таблица 4.11

Пример 4.9

Пусть система состоит из восьми механиков и десяти подъемных кранов, тогда в GPSS-модель могут быть введены такие МКУ:

MECHANICIAN            STORAGE 8
LIFTING_CRANE         STORAGE                                                                        10

Существует возможность периодически переопределять емкость МКУ при необходимости выполнения нескольких прогонов за один этап моделирования. Это делается введением в программу между операторами START предыдущего прогона и оператором START последующего прогона нового определения емкостей.

Пример 4.10

Необходимо найти наилучшую комбинацию среди значений пар «количество механиков - количество кранов» за один этап моделирования. Для этого нужно использовать следующую последовательность операторов STORAGE и команд START:

MECHANICIAN                      STORAGE         <значение 1.1>
LIFTING_CRANE         STORAGE         <
значение 1.2>
                <
текст GPSS- прoграммы >

                                         START 1

                                         RESULT            REZ.TXT,1,1112

                                        CLEAR

MECHANICIAN                      STORAGE                            <значение 2.1>

LIFTING_CRANE                 STORAGE                             <значение 2.2>

START 1

            RESULT REZ.TXT,1,2122

                                           CLEAR

MECHANICIAN                          STORAGE        <значение 3.1>
LIFTING_CRANE                      STORAGE                                  <
значение 3.2>

START 1

             RESULT REZ.TXT,1,3132

                                            CLEAR

Действия, выполняемые оператором CLEAR описаны в параграфе 4.27. Команда RESULT используется только в GPSS/PC. Отметим, что второй параметр команды RESULT указывает на ячейку сохраняемых величин, в которой хранится значение критерия, по которому сравнивают комбинации пар значений.

Задания для самостоятельной работы:

1. В магазине одновременно может находиться лишь 15 покупателей. Они остаются в магазине на протяжении 15±5 мин. Напишите сегмент GPSS-программы.

2. Морские суда прибывают в порт каждые 20±5 часа. В порту имеется 10 причалов. Каждый корабль по длине занимает три причала и находится в порту 10±3 часа. Промоделируйте работу порта на протяжении 500 часов. Напишите сегмент GPSS-программы.

3. Выполните задания 2, 3, 4 из главы 7.

4.11. Примеры построения GPSS-моделей

Пример 4.11 [10]

Интервалы прихода клиентов в парикмахерскую с одним креслом распределены равномерно на- интервале 18 ±6 мин. Время стрижки также распределено равномерно на интервале 16 ±4 мин. Клиенты приходят в парикмахерскую, стригутся в порядке очереди: «первым пришел - первым обслужился». Необходимо построить GPSS-модель парикмахерской, которая должна обеспечить сбор статистических данных об очереди. Промоделируйте работу парикмахерской в течение 8 часов.

Построение модели

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

1) клиент приходит;

2) если необходимо, ждет своей очереди;

3) садится в кресло парикмахера;

4) парикмахер обслуживает клиента;

5) клиент уходит из парикмахерской.

Единица модельного времени - 1 минута. Программа:

; MODEL SEGMENT 1

GENERATE      18,6 ; Приход клиентов
       
QUEUE              BARBERQ        ; Присоединение к очереди

SEIZE BARBER           ; Переход в кресло парикмахера
       
DEPART           BARBERQ        ; Выход из очереди
       
ADVANCE        16,4                     ; Обслуживание у парикмахера

RELEASE         BARBER ; Освобождение парикмахера

TERMINATE   0 ; Уход из парикмахерской
;
MODEL SEGMENT 2

GENERATE     480 ; Транзакт-таймер

TERMINATE   1 ; Завершение прогона

START 1

Пример 4.12 [10]

В парикмахерскую с одним креслом приходят клиенты двух типов. Клиенты первого типа желают только стричься. Распределение интервалов их прихода - 35±10 мин. Клиенты второго типа желают постричься и побриться. Распределение интервалов их прихода -60±20 мин. Парикмахер обслуживает клиентов в порядке «первым пришел - первым обслужился». Время, затраченное на стрижку, составляет 18±6мин, а на бритье - 10±2 мин. Написать GPSS-модель парикмахерской, обеспечив сбор данных об очереди клиентов.

Построение модели

Необходимо реализовать отличие в обслуживании клиентов, которые только стригутся, и клиентов, которые стригутся и бреются.

Такую систему можно промоделировать с помощью двух сегментов. Один из них моделирует обслуживание только стригущихся клиентов, а второй - стригущихся и бреющихся. В каждом из сегментов пара QUEUE-DEPART должна описывать одну и ту же очередь. Таким же образом пара блоков SEIZE-RELEASE должна описывать в каждом из двух сегментов одно и то же устройство и моделировать работу парикмахера.

Единица модельного времени - 1 мин. Программа:

* HAIRCUT

GENERATE 35,10                   , Приход клиентов, которые только стригутся

QUEUE BARBERQ         ; Присоединение к очереди

SEIZE BARBER            ; Переход в кресло парикмахера

DEPART BARBERQ        ; Выход из очереди

ADVANCE 18,6                     ; Стрижка у парикмахера

RELEASE BARBER            ; Освобождение парикмахера

TERMINATE 0                          ; Уход из парикмахерской

* HAIRCUT AND SHAVING

GENERATE 60,20                   ; Приход клиентов, которые стригутся и бреются

QUEUE BARBERQ        ; Присоединение к очереди

SEIZE BARBER            ; Переход в кресло парикмахера

DEPART BARBERQ        ; Выход из очереди

ADVANCE 10,2                     ; Бритье у парикмахера

ADVANCE 18,6                     ; Стрижка у парикмахера

RELEASE BARBER           ; Освобождение парикмахера

TERMINATE 0                          ; Уход из парикмахерской

* TIMER - Сегмент таймера

GENERATE 480                      ; Транзакт-таймер приходит в момент 480

TERMINATE 1                          ; Завершение прогона

START 1

Пример 4.13 [10]

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

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

Дисциплина обслуживания «первый пришел - первый обслужился» для двух категорий запросов с соответствующим приоритетом изображена на рис. 4.1.

Построение модели

Эта система очень похожа на систему из примера 4.12. Есть два различных типа заявок, поступающих на обслуживание к одному устройству. Различаются распределения интервалов приходов и времени обслуживания для этих типов заявок. Трудность заключается в том, что один из типов имеет преимущество в обслуживании. Построить модель можно, используя тот же подход, что и в примере 4.12. Но при этом необходимо использовать средство задания заявкам различных приоритетов.

Итак, запросы первой категории будем моделировать одним сегментом, а запросы второй категории - другим. Разные относительные приоритеты задаются путем использования для операнда Е блока GENERATE запросов второй категории большего значения, чем для запросов первой категории.

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

Таким образом, сборщик работает в таком режиме:

1) собирает следующую деталь;

2) ожидает возможности использования печи по принципу FIFO;

3) использует печь;

4) возвращается к п. 1.

Время, необходимое на выполнение различных операций, приведено в табл. 4.16.

Необходимо построить на GPSS модель описанного процесса. Определить оптимальное число сборщиков, использующих одну печь, т.е. такое количество, которое дает наибольшую прибыль при моделировании в течение 40 часов модельного времени. Предполагается, что в течение рабочего дня нет перерывов, а рабочими днями являются все дни (без выходных).

Построение модели

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

Естественно для моделирования печи использовать понятие «устройство», также естественно отождествлять сборщиков с транзактами. Тогда можно считать, что сборщики «циркулируют» в системе, периодически осуществляя сборку и обжиг. Аналогично и транзакты должны циркулировать в GPSS-модели системы. Как видно из постановки задачи, модель представляет собой замкнутую СМО с одним устройством обслуживания.

В реальной системе, после того, как сборщик вынимает из печи обожженную деталь, он возвращается и начинает новый этап сборки. В модели после того, как транзакт завершает использование устройства, он должен быть перемещен с помощью блока TRANSFER в блок следующей сборки. Для ограничения общего количества транзактов, циркулирующих в модели, необходимо использовать операнд D блока GENERATE.

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

Единица модельного времени - 1 мин. Программа:

GENERATE ,„4 ; Определение количества сборщиков

ВАСК1               ADVANCE 30,5       ; Сборка следующей детали

SEIZE OVEN ; Занятие печи

ADVANCE 8,2         ; Использование печи

RELEASE OVEN  ; Освобождение печи

TRANSFER ,BACK1              ; Переход к сборке следующей детали

GENERATE 2400 ; Моделирование пяти дней роботы

TERMINATE 1 ; Завершение работы

START 1 ; Начало прогона модели

Пример 4.15 [10]

Морские судна двух типов прибывают в порт, где происходит их разгрузка. В порту есть два буксира, обеспечивающих ввод и вывод кораблей из порта. К первому типу судов относятся корабли малого тоннажа, которые требуют использования одного буксира. Корабли второго типа имеют большие размеры, и для их ввода и вывода из порта требуется два буксира. Из-за различия размеров двух типов кораблей необходимы и причалы различного размера. Кроме того, корабли имеют различное время погрузки-разгрузки. Исходные данные приведены в табл. 4.18.

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

Среднее время ожидания кораблями каждого типа входа в порт получаем в конце моделирования из стандартной статистики об очередях: оно равно показателю AVERAGE TIME соответствующей очереди. (Эти же значения дают СЧА QT$TYPE1 и QTSTYPE2).

4.12. Переменные

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

В GPSS имеется три типа переменных:

1) арифметические переменные;

2) арифметические переменные с «плавающей точкой»;

3) булевы переменные.

Значение арифметических переменных может использоваться как:

1) операнд блока; в этом случае значение арифметической переменной может представлять собой:

- номер объекта (устройства, МКУ, очереди и т. п.);

- номер параметра транзакта;

- значение стандартного числового атрибута;

3) операнд А функции;

4) операнд А таблицы;

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

+      алгебраическое сложение;

-      алгебраическое вычитание;

-      алгебраическое умножение;

/ алгебраическое деление (результатом операции является щелая часть частного);

@     деление по модулю;

^      возведение в степень;

| деление без остатка (перед делением у обоих операндов отбрасываются дробные части, результатом операции есть целая "часть частного).

Привычно используемый для умножения во многих языках знак -«*», зарезервирован в GPSS для обозначения косвенной адресации, однако в GPSS World есть возможность в меню настройки параметров переопределить для умножения знак «*», а для косвенной адресации - «#». Косвенная адресация является мощным средством для построения компактных и гибких моделей. Ее идея заключается в том, что можно обратиться к любому объекту или СЧА через параметры транзактов. Доступ же к параметрам транзактов осуществляется через СЧА Рj, где j - номер параметра транзакта (например, 10) или Р$имя, где имя - имя (идентификатор) параметра транзакта. Так как обращение к объекту возможно только через параметр транзакта, то символ Р может опускаться. Например, выражение Q*7 или Q*P7 определяет текущее значение длины очереди, номер которой задан в параметре 7 транзакта. Если в седьмом параметре хранится значение 3, то это будет текущее значение длины очереди с номером 3.

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

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

Арифметические переменные. Арифметические переменные аналогичны арифметическим выражениям в алгоритмических языках. Переменная задается оператором VARIABLE, называемым оператором описания переменной, который содержит арифметическое выражение. Формат оператора описания переменной:

Таблица 4.19

При обращении к переменной используется обозначение V<номер переменной> или V$<имя переменной>, т.е. V - это СЧА переменной.

Пример 4.16

Оператор описания VARIABLE определяет арифметическую переменную RSL:

RSL      VARIABLE       QT$WAITL+3-FN$DSTRB#P7

При любом обращении к переменной RSL (употребляется обозначение V$RSL) ее значение вычисляется как текущая длина очереди WAITL (QTSWAITL - СЧА регистратора очереди) плюс константа 3 и минус произведение значения функции DSTRB на значение параметра 7 транзакта, обрабатываемого в данный момент. В приведенном выражении FN - СЧА для обращения к функции, а Р - СЧА транзакта.

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

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

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

В GPSS World выражения, записанные в круглых скобках, обрабатываются вычислительной процедурой встроенного алгоритмического языка PLUS. Поэтому их можно использовать в качестве операндов блоков и операторов языка GPSS. Например, выражение, описанное в примере 4.16, может быть использовано таким образом:

ADVANCE        (QT$WAITL+3-EN$DSTRB#P7)

l. B GPSS/PC выражение может содержать не больше
пяти пар скобок (не считая скобок, используемых при описании элементов матриц).

2. Пробелы между символами в выражениях не допускаются. Левый пробел записи считается концом выражения. Для записи выражения, превышающего длину строки, можно ввести другой оператор VARIABLE с именем, отличным от имени первой переменной, и включить значение новой переменной в качестве одного из операндов в выражение первой арифметической переменной.

Пример 4.17

ADD     VARIABLE       PI 0+25

При обращении к арифметической переменной ADD ее значение вычисляется как сумма значений десятого параметра транзакта, обрабатываемого в данный момент, и константы 25.

Fl VARIABLE Q9+3#V$F2-V$F3#FN$IO

F2 VARIABLE 9+R13-FN19#Q10

F3 VARIABLE FN$TYPE1+S$PL#R$RC-Q$ENTRY

Выражение для Fl содержит как операнды переменные F2 и F3.

PROFIT VARIABLE       V*P*FN*P2

Переменная PROFIT будет вычислена следующим образом. Вначале определяется значение второго параметра текущего транзакта. Пусть в параметре Р2 хранится значение 3. Затем вычисляется значение функции 3. Пусть оно равно 10. После этого определяется значение параметра с номером 10. Пусть содержимым этого параметра будет число 5. Тогда переменной PROFIT присваивается значение переменной 5.

СОМР VARIABLE       X*P4/100

При обращении к арифметической переменной СОМР ее значение вычисляется как частное от деления значения сохраняемой величины (СЧА X), номер которой определяется четвертым параметром транзакта, обрабатываемого в данный момент, на константу 100. Сохраняемые величины позволяют хранить значения глобальных переменных, доступных из любой части модели. Такой прием используется для выделения старших разрядов чисел. Например, пусть в четвертом параметре текущего транзакта записано число 6. И пусть в сохраняемой величине 6 хранится число 12345. При обращении к переменной СОМР происходит следующее:

1) определение значения параметра 4 (получаем число 6);

2) определение значения 12345, которое хранится в ячейке
Х*Р4, т.е. в ячейке 6;

3) значение 12345 делится на 100 (с отбрасыванием остатка), в результате получается 123.

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

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

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

FLOAT FVARIABLE 10#(ll/3)
FIXED      VARIABLE                                                                                  10#(11/3)

Значение переменной FLOAT равно 36, так как константа 10
умножается на 3,67 и от результата 36,7 взята целая часть. Переменная
FIXED равна 30, так как результат промежуточной операции деления будет округлен до 3.
1. Для переменных с плавающей точкой не допускается оп
eрация деления по модулю.                                                             
2. Использование дробных констант допускается только при описании переменных с плавающей точкой.                                
3. Стандартный числовой атрибут
V$<имя переменной> используется для обращения к значениям как арифметических переменных, так и переменных с плавающей точкой. Способ вычисления переменной определяется оператором описания этой переменной.         

Булевы переменные. Булевы переменные позволяют принимать решения в зависимости от значений СЧА и состояния объектов GPSS, используя для этого только одно выражение.

Булевы переменные - это логические выражения, состоящие из различных СЧА и (или) других булевых переменных. В булевой переменной проверяется одно или несколько логических условий. Результатом проверки есть единица (истина), если условия выполняются, и ноль (ложь) - в противном случае.

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

Логические операторы связаны с такими ресурсами, как устройства, МКУ и логические ключи. Они используются для определения состояния данных объектов. Логические операторы, используемые в GPSS, представлены в табл. 4.20

Таблица 4.20

Операторы отношения выполняют алгебраическое сравнение операндов. Операндами могут быть константы или стандартные числовые атрибуты. Все операторы отношений записываются в кавычках:

"G" (Greater) - больше;

"L" (Less) - меньше;

"Е" (Equal) - равно;

"NE" (Not Equal) - не равно;

"LE" (Less than or Equal) - меньше или равно;

"GE"(Greater than or Equal) - больше или равно;                                    
Есть два булевых оператора: "OR" - оператор «или», и "AND" - оператор «и». Оператор «или» проверяет, выполняется ли хотя бы одно из проверяемых условий. Оператор «и» требует выполнения обоих условий.

Задания для самостоятельной работы:

1. Задайте переменную VAR2 = (2.8 * <значение переменной
VAR1>+128):3.

2. Задайте переменную VAR3 = (7/4)х100х<значение переменной VAR2> + 41.

3. Пусть переменная VAR4 содержит количество изделий первого сорта, а переменная VAR5 - количество изделий второго сорта. Задайте переменную VAR6, которая бы давала процент изделий первого сорта от общего числа изделий.

4. Задайте булеву переменную BVAR1, которая равна единице,
если  оба устройства  
FACIL1   и  FACIL2  находятся  в  состоянии ЗАНЯТЫЙ, и ноль - для всех других случаев (F$имя - СЧА, определяющий занятость устройства, выдает значение 1, если устройство занято, 0 - если свободно).

4.13. Определение функции в GPSS

В GPSS рассматриваются пять типов функций:

1) дискретная числовая (D),

2) непрерывная числовая (С),

3) табличная числовая (L),

4) дискретная атрибутивная (Е),

5) табличная атрибутивная (М).

Рассмотрим два первых типа функций.

Дискретная функция представляет собой кусочно-постоянную функцию, которая состоит из горизонтальных ступеней (рис. 4.2). Непрерывная функция представляет собой кусочно-непрерывную функцию. Непрерывная функция в GPSS состоит из соединенных между собой прямых отрезков и представляет собой ломаную линию (рис. 4.3). Чтобы задать дискретную функцию, необходимо задать координаты крайних правых точек горизонтальных отрезков. Для непрерывной функции необходимо задать координаты всех точек, которые являются концами отрезков.

Действия, необходимые для определения дискретной и непрерывной GPSS-функции:

1. Присвоить функции имя. Имя может быть числовым либо символьным.

2. Задать аргумент функции. Аргументом могут быть:

1) ссылка на генератор случайных чисел, используемый для розыгрыша в соответствии с распределением, заданным функцией;

2) стандартный числовой атрибут;

3) ссылка на любую другую функцию.

В первом случае аргумент задается в виде RNj, j - целое число (номер генератора). В GPSS/PC; = 1,..., 7, т.е. возможно обращение к семи идентичным генераторам случайных чисел. При этом генераторы выдают случайные числа в диапазоне 0... 0,999. В GPSS World количество генераторов случайных чисел неограниченно, а выдаваемые ими значения 0... 0,999999.

3. Задать тип функции и число крайних точек функции.

4. Задать значения аргумента (переменной) и соответствующие значения функции (т.е. координаты крайних точек функции).

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

Таблица 4.21

За каждым оператором описания FUNCTION следуют операторы задания координат точек функции (значений аргументов Хi и соответствующих им значений функции Yi,) - это операторы описания координат функции. Их формат:

1) если координаты всех точек расположены в одной строке оператора описания функции:

2) если координаты точек расположены в нескольких операторах описания функции:

где Хi и Yi - координаты iточки функции (в случае моделирования случайной величины Хi является i-и суммарной (кумулятивной) частотой, Yi - соответствующим значением случайной величины).

Особенности оператора описания координат функции:

1) основной единицей информации оператора описания координат функции является пара значений Хi ,Yi (координаты точки i);

2) значения координат Хi и Yi одной точки функции разделяются запятой;

3) последовательные наборы координат разделяются знаком «/»;

4) координаты Хi и Yi относящиеся к одной точке, задаются одним оператором, т.е. пара координат одной точки не должна разрываться;

5) все строки описания координат функции должны начинаться с первой позиции;

6) во всех случаях значения аргумента должны удовлетворять следующим неравенствам:

Значение функции является ее стандартным числовым атрибутом. Способ ссылки на этот атрибут зависит от того, как задано имя функции: в символьном или числовом виде. Если имя числовое, то к значению функции обращаемся через FNj (где j - номер функции), если имя символьное - через FN$<имя функции>.

1. Аргументом функции может быть и значение какой-либо другой функции.

2. Каждая функция должна иметь, по крайней мере, две
описанные точки.

Пример 4.18

Пусть необходимо смоделировать дискретную случайную переменную, заданную в табл. 4.22.

Таблица 4.22

GPSS-функцию можно определить таким образом:

SERV     FUNCTION       RN4,D5

.15,2/.35,5/.6,8/.82,9/1,12

Графическая интерпретация функции показана на рис. 4.4.

Особенности вычисления дискретных и непрерывных GPSS-функций:

1. В начальной фазе выполняемые действия при вычислении дискретной и непрерывной функции одинаковы. При обращении к функции определяется значение ее аргумента. Потом просматривается упорядоченный ряд значений X1<X2<...<Xi<...<Xn для определения интервала, в который попало значение аргумента (пусть это будет интервал между точками i - 1 и i ).

2. Если функция дискретная, то второй элемент соответствующей пары Xi, Yi является значением функции. Если функция непрерывная, выполняется линейная интерполяция для пары точек i - 1 и i, находящихся на краях интервала значений функции, на который указало значение аргумента. Целая часть результата интерполяции и является значением функции.

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

Пример 4.19

Моделирование случайной переменной, равномерно распределенной на интервале [2,5].

Эта случайная переменная может быть смоделирована функцией:

INN      FUNCTION       RN2,C2

0,2/1,6

Графическая интерпретация непрерывной функции показана на рис. 4.5.

Так как максимальное значение, которое может выдать генератор случайных чисел, равно 0,999, то фактические значения интервалов времени распределены равномерно на интервале [2, 5] и равны, соответственно, одному из значений: 2, 3, 4, 5. Если генератор выдаст число 0,999, функция, которая показана на рис. 4.5, примет значение 5,996, целая часть которого равна 5 (это и будет значением GPSS-функции INN). В случае, если генератор случайных чисел RN2 выдаст значение 0,4, GPSS-функция INN примет значение 3 (см. рис. 4.5).

GPSS-функция INN не может принять значение, равное 6 (несмотря на то, что второй элемент второй пары оператора описания координат функции 0,2/1,6 равен 6).

Точные граничные значения RN2, соответствующие возможным значениям функции INN, представлены в табл. 4.23.

Таблица 4.23

Равномерное распределение [2, 3, 4, 5] не может быть задано непосредственно с помощью операндов А и В блока GENERATE. Здесь имеем четыре возможных значения, тогда как интервал А ± В (А и В целые) всегда имеет нечетное число элементов.

Пример 4.20

Часто возникают ситуации, когда в процессе моделирования необходимо переходить в различные блоки программы в зависимости от логики работы модели. Стандартные блоки GPSS WORLD такие, как TEST (см. параграф 4.16) и TRANSFER, не всегда могут решить эту проблему, так как они позволяют распределять транзакты максимум по двум направлениям. В случае, когда осуществляется условный переход на одну из нескольких меток (если более двух, то в обычных языках программирования используется оператор CASE OF), необходимо построить переключающую функцию. Для вызова переключающей функции используется блок TRANSFER в режиме безусловного перехода.

Пример переключающей функции:

PEREKL FUNCTION   RN4,DS
0.2,
LB1/0.4,LB2/0.6,LB3/0.8,LB4/1,LB5

GENERATE ,„100

TRANSFER ,FN$PEREKL

LB1        QUEUE  STOR1

TERMINATE 0

LB2        QUEUE  STOR2

TERMINATE 0

LB3        QUEUE  STOR3

TERMINATE 0

LB4        QUEUE  STOR4

TERMINATE 0

LB5        QUEUE  STOR5

TERMINATE   О

GENERATE 1

TERMINATE I

START 1

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

Моделирование неравномерных случайных величин. Использование функций в блоках GENERATE и ADVANCE. Пусть распределение интервалов поступления через определенный блок GENERATE или время задержки в некотором блоке ADVANCE не является равномерным (либо является равномерным с «плавающими во времени», т.е. нефиксированными значениями среднего и половины поля допуска). Для входов транзактов в модель через этот блок GENERATE и для задания закона времени задержки в соответствующем блоке ADVANCE необходимо использовать функции и (или) СЧА. Использование функций, заданных в операндах блоков, зависит от контекста. От значения функции берется целая часть, за исключением тех случаев, когда это значение используется в качестве операнда В блоков GENERATE и ADVANCE или операнда С блока ASSIGN. В табл. 4.24 показаны различные варианты использования функций и СЧА в качестве операндов А и В блоков GENERATE и ADVANCE. Под результатом понимается значение интервала поступления или задержки.

Таблица 4.24

Пример 4.21

TIME   FUNCTION       RN3,D5 ,

.05,5/.15,6/.75,8/.93,9/1,10

К этой функции можно обратиться таким образом:

GENERATE      FNSTIME

ADVANCE        FNSTIME

Пример 4.22

Пусть в моделируемой системе время обслуживания некоторым устройством распределено равномерно на интервале А ± 2, где среднее время обслуживания А с вероятностью 0,4 принимает значение 5, а с вероятностью 0,6 - значение 7. Эту ситуацию можно смоделировать следующим образом.

Определим функцию AVERAGET:

AVERAGE_T    FUNCTION       RN1,D2

.4,5/1,7

Используем ее в блоке ADVANCE:

ADVANCE        FN$AVERAGE_T,2

Выполнение подпрограммы блока ADVANCE включает расчет функции AVERAGE_T. Это, в свою очередь, требует обращения к генератору случайных чисел RN1. Пусть генератор выдал значение меньшее, чем 0,4. Тогда соответствующее значение функции AVERAGE_T равно 5. Таким образом, время задержки текущего транзакта в устройстве будет равномерно распределено на интервале 5±2.

Непрерывные случайные переменные, рассматриваемые как дискретные. Как известно, дискретные случайные переменные могут принимать только фиксированное число значений. В противоположность этому, непрерывные (в классическом смысле этого термина) случайные переменные могут иметь неограниченное число различных значений.

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

Функции распределения случайных величин. В языке GPSS возможность задания функций распределения случайных величин ограничена заданием их в табличном виде путем аппроксимации непрерывными функциями. Поэтому можно задать только те функции, которые легко преобразовать для новых значений параметров. К таким функциям, например, относится функция экспоненциального распределения с параметром λ, = 1, а также функция стандартного нормального распределения с математическим ожиданием т = 0 и стандартным отклонением σ =1.

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

Моделирование пуассоновского потока. Рассмотрим табличный способ задания пуассоновского потока заявок. Пуассоновский входящий поток описывается таким образом: вероятность поступления k заявок пуассоновского потока в течение интервала t составляет

где λ - интенсивность потока.

Интервалы времени между соседними заявками пуассоновского потока распределены по экспоненциальному закону. Согласно методу обратной функции, можно получить ряд чисел, которые имеют экспоненциальное распределение, если ряд случайных чисел R, равномерно распределенных на интервале [0,1], преобразовать в соответствии с функцией, обратной к экспоненциальной функции распределения:

где tj - 7-й разыгранный интервал времени поступления; Т= 1/λ, -средний интервал времени поступления; rj - j-е число в последовательности случайных чисел R с равномерным распределением на интервале [0, 1].

Разработчиками    GPSS    была   осуществлена    аппроксимация функции F-1 (х), обратной к экспоненциальной функции распределения с параметром λ= 1. Таким образом, функция F-1 (х) была заменена 23 отрезками, которые использовались для преобразования значений RNj в значение - In(RNj).

Функция XPDIS определяет экспоненциальное распределение с интенсивностью  λ= 1:

XPDIS FUNCTION       RN1,C24 ; exponential distribution function
0,0/.
l,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915/.7,1.2/
.75,1.38/.8,1.6/.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.81/
,95,2.99/.96,3.2/.97,3.5/.98,3.9/.99,4.6/.995,5.3/.998,6.2/.999,7/.9998,8

Пуассоновский входящий поток с интенсивностью λ, отличной от единицы, моделируется с помощью блока GENERATE таким образом:

1) в качестве операнда А используют среднее значение интервалов времени Т= λ/k, где λ - интенсивность пуассоновского потока;

2) в качестве операнда В используют СЧА - значение функции XPDIS, операторы определения и описания которой приведены выше.

Пример 4.23

Пусть среднее значение интервалов поступления Т в пуассоновском потоке требований равно 2 ч, а единица времени в модели равна 1 мин, тогда поступление заявок моделируется блоком:

GENERATE      120,FN$XPDIS

Если необходимо моделировать задержку, распределенную по экспоненциальному закону со средним значением времени 345, то для этого используется блок:

ADVANCE        345,FN$XPDIS

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

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

GENERATE      5,FN$XPDIS

Если в результате обращения к функции XPDIS полученное значение меньше, чем 1/5, то целая часть произведения числа 5 и значения функции XPDIS равна нулю. Отсюда следует нарушение свойства ординарности. Во избежание этого рекомендуется, чтобы операнд А в блоке GENERATE был больше 50. Это легко достигается путем варьирования значения единицы модельного времени.

Моделирование гипер- и гипоэкспоненциального распределений. Экспоненциальную функцию распределения можно использовать также для моделирования гипер- и гипоэкспоненциального распределений.

Неэкспоненциальное распределение с коэффициентом вариации С* > 1 можно получить с помощью взвешенной суммы экспонент - гиперэкспоненциального распределения:

*Коэффициент вариации С - это отношение стандартного отклонения к математическому ожиданию случайной величины.

Если μiдля всех i, то С = 1 - имеем экспоненциальное распределение.

Гиперэкспоненциальное распределение можно получить при параллельном соединении k (рис. 4.6) экспоненциальных обслуживающих устройств с интенсивностью обслуживания μi и вероятностью ωi использования для обслуживания (i = 1,k). Причем в произвольный момент времени может быть занято не более одного устройства из k. Такое распределение хорошо описывает распределение времени работы центрального процессора компьютера.

Для моделирования гиперэкспоненциального распределения со средним значением 6,28 и стандартным отклонением 8,4 необходимо определить переменную

HYP     FVARIABLE    (410+(RN2 ‘L' 234)(#(1334 - 410)))#FN$XPDIS

Эту переменную можно использовать в блоке задержки так:

ADVANCE        VSHYP

Гипоэкспоненциолъное распределение с коэффициентом вариации С<1 описывается таким образом:

При равенстве всех коэффициентов μ распределение времени пребывания в обслуживающем центре (на рис. 4.7 обведен пунктирной линией) будет k-распределением Эрланга:

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

Моделирование эрланговского потока. Экспоненциальное распределение не всегда адекватно описывает время обслуживания и поступления требований в систему. Более реалистичным является распределение Эрланга. В то же время, это распределение является частным случаем гамма-распределения, которое описано ниже. Для потока Эрланга k-го порядка с интенсивностью λ математическое ожидание и дисперсия определяются так: E[x]=1/, d[x]=1/2. Для моделирования распределения Эрланга может также использоваться экспоненциальная функция распределения. Как было показано в главе 1, для этого достаточно просуммировать k случайных экспоненциально распределенных величин. С ростом k распределение Эрланга будет приближаться к нормальному распределению. Например, поток Эрланга второго порядка со средним значением времени поступления 180 можно задать таким образом:

GENERATE ,„1

SDFG   ADVANCE 90,FN$EXPDIS

ADVANCE 90,FN$EXPDIS

SPLIT 1,SDFG

TERMINATE    1

В нулевой момент времени в модель вводится транзакт. Этот транзакт в каждом их двух последующих блоков ADVANCE задерживается на экспоненциально распределенный промежуток времени. Блок SPLIT (подробнее см. в параграфе 4.19) создает копию транзакта и направляет ее на блок с меткой SDFG, исходный транзакт поступает в модель и т.д.

Пример 4.24

Для того, чтобы исследовать свойства распределения Эрланга можно воспользоваться следующей моделью:

EXPDIS FUNCTION       RN1,C24

0,0/.100,.104/.200,.222/.300,.355/.400,.509

.500,.690/.600,.915/.700,1.200/.750,1.380

.800,1.600/.840,1.830/.880,2.120/.900,2.300

.920,2.520/.940,2.810/.950,2.990/.960,3.200

.970,3.500/.980,3.900/.990,4.600/.995,5.300

.998,6.200/.999,7/1,8

ТР TABLE              X2,l,20,50

GENERATE      ,„1
SDFG ADVANCE        100,FN$EXPDIS

ADVANCE        100,FN$EXPDIS

ADVANCE        100,FN$EXPDIS

SPLIT 1,SDFG

SAVEVALUE    2,C1

SAVEVALUE    2-,Xl

SAVEVALUE    1,C1

TABULATE      TP

TERMINATE    1

Оператор TABLE, блоки SPLIT, SAVEVALUE и TABULATE использованы для сбора статистики об интервалах прихода транзактов в модель (об их назначении см. в параграфах 4.17, 4.19 и 4.21).

Построенная в результате моделирования гистограмма (при использовании оператора START 100000000) приведена на рис. 4.8. Читателю предлагается исследовать распределение Эрланга при различных значениях k, путем изменения количества блоков ADVANCE в приведенной программе.

Моделирование нормального закона распределения. Функция стандартного нормального закона распределения с параметрами m = 0, а = 1 задается в GPSS 24 отрезками следующим образом:

NOR     FUNCTION       RN1,C2S

0,-5/.00003,-4/.00135,-3/.00621,-2.5/.02275,-2

.06681,-1.5/.11507,-1.2/.15866,-1/.2П86,-.8/.27425,-.6

.34458,-.4/.42074,-.2/.5,0/.57926,.2/.65542,.4

.72575,.6/.78814,.8/.84134,1/.88493,1.2/.93319,1.5

.97725,2/.99379,2.5/.99865,3/.99997,4/1,5

Для того, чтобы получить функцию нормального распределения случайной величины X с математическим ожиданием тх ≠0 и среднеквадратичным отклонением σх 1, необходимо произвести вычисления по формуле

где Z - случайная величина со стандартной нормальной функцией распределения. Например, если случайная величина X имеет параметры mx=60 и σx=10, то в GPSS эта случайная величина моделируется так:

NOR1   FVARIABLE    60+10#FN$NOR

Если необходимо осуществить задержку по этому закону распределения, то используется блок

ADVANCE        VSNOR1

При использовании функции нормального распределения для  блоков  GENERATE  и ADVANCE  необходимо обеспечить неотрицательность значений интервалов поступления и задержки. Это можно сделать, если mx≥5 σх.

Моделирование других законов распределения. Все другие виды функций распределения случайных величин в GPSS/PC необходимо задавать табличным способом для конкретных значений параметров этих функций. Для этого можно использовать специальные программы, которые позволяют числовым способом вычислять необходимое значение числа отрезков аппроксимации этих функций, как это сделано, например, в системе ИСИМ [5]. Пример меню такой программы представлен на рис. 4.9.

Описание функции гамма-распределения для параметров (рис. 4.9):

GAMMA FUNCTION RN1,C26

0,0/0.24217,0.29471/0.33719,0. 89451/0.40669,0.88412

0.46254,1.17882/0.50946,1.47353/0.5499,1.76824/0.58536,2.06294

0.64503,2.65235/0.69351,3.24176/0.73373,3.83118/0.76758,4.42059

0.79637,5.01/0.83207,5.89412/0.86078,6.77824/0.88409,7.66235

0.90874,8.84118/0.9278,10.02/0.94583,11.49353/0.96139,13.26176

0.97381,15.32471/0.98307,17.68235/0.99062,20.92412/0.99575,25.34471

0.99878,32.41765/0.99992,48.33176/1,50.1

Моделирование вероятностных функций распределения в GPSS World. В GPSS World в библиотеку процедур включено 24 вероятностных распределений. При вызове вероятностного распределения требуется определить аргумент Stream (может быть выражением), который определяет номер генератора случайных чисел. При моделировании генераторы случайных чисел создаются по мере необходимости и их явное определение не обязательно. Большинство вероятностных распределений имеют некоторые параметры. Аргументы процедур, называемые обычно Locate, Scale и Shape, часто используются для этих целей. Аргумент Locate используется после построения применяемого распределения и прибавляется к нему. Это позволяет горизонтально перемещать функцию распределения по оси X. Аргумент Scale обычно меняет масштаб функции распределения, а Shape - ее форму.

Встроенная библиотека процедур содержит следующие вероятностные распределения:

1) бета (Beta);

2) биномиальное (Binomial);

3) Вейбулла (Weibull);

4) дискретно-равномерное (Discrete Uniform);

5) гамма (Gamma);

6) геометрическое (Geometric);

7) Лапласа (Laplace);

8) логистическое (Logistic);

9) логлапласово (LogLaplace);

10) логлогистическое (LogLogistic);

11) логнормальное (LogNormal);

12) нормальное (Normal);

13) обратное Вейбулла (Inverse Weibull);

14) обратное Гаусса (Inverse Gaussian);

15) отрицательное биномиальное (Negative Binomial);

16) Парето (Pareto);

17) Пирсона типа V (Pearson Type V);

18) Пирсона типа VI (Pearson Type VI);

19) Пуассона (Poisson);

20) равномерное (Uniform);

21) треугольное (Triangular);

22) экспоненциальное (Exponential);

23) экстремального значения A (Extreme Value A);

24) экстремального значения В (Extreme Value В).

В качестве примера покажем, как для генерации потока транзактов можно использовать библиотечную процедуру экспоненциального распределения с параметром X = 0,25 и использованием генератора случайных чисел RN1:

GENERATE (Exponential(1,0,(1/0.25)))

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

Логарифмически нормальное распределение. Логарифмически нормальное распределение (логнормальное) - это распределение случайной величины, натуральный логарифм которой нормально распределен. Это распределение пригодно для моделирования мультипликативных процессов так же, как нормальное - для аддитивных.

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

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

Функция плотности логнормального распределения:

если х > λ, в противном случае - (х) = 0.

Если после логарифмирования каждого элемента некоторого набора данных этот трансформированный набор данных нормально распределен, то исходные данные логарифмически нормально распределены.

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

Примерами использования этого распределения могут быть:

1) размеры и вес частиц, образуемых при дроблении;

2) доход семьи;

3) зарплата работников;

4) долговечность изделия, работающего в режиме износа и старения;

5) размер банковского вклада;

6) длины слов в языке;

7) длины передаваемых сообщений.

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

Математическое ожидание и дисперсия логнормально распределенной случайной величины таковы:

где параметр σ задает среднеквадратическое отклонение, μ, - математическое ожидание из нормального распределения, λ, - величину сдвига для определения местоположения распределения.

Для вызова логнормального распределения используется библиотечная процедура

LOGNORMAL(Stream, Locate, Scale, Shape),

где Stream - номер генератора случайных чисел, автоматиче ски преобразуется в целое число, которое должно быть больше или равно 1; Located=λ, Scale=σ; Shape=μ. Все параметры обязательные.

Гамма-распределение является обобщенным распределением Эрланга для случая, когда число а суммируемых величин -является нецелым. Гамма -распределенная величина имеет значения от 0 до °°, то есть неотрицательна. Если α - целое, то это будет распределение Эрланга.

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

Гамма-распределение можно интерпретировать как сумму квадратов нормально распределенных случайных величин, то есть как χ2-распределение.

Таким образом, χ2 -распределение, распределение Эрланга и экспоненциальное распределение являются частными случаями гамма - распределения.

Математическое ожидание и дисперсия гамма - распределенной случайной величины таковы:

Функция плотности гамма - распределения имеет вид:

где параметр α задает форму распределения, β - масштаб доя сжатия или растяжения распределения, λ - величину сдвига для определения местоположения распределения.

Для вызова гамма - распределения используется библиотечная процедура

GAMMA (Stream, Locate, Scale, Shape),

где Stream - номер генератора случайных чисел, автоматически преобразуется в целое число, которое должно быть больше или равно 1; Located=λ, Scale=β; Shape=α.. Все параметры обязательные.

Когда аргумент Shape равен 1, гамма-распределение вырождается в экспоненциальное. Это означает, что GAMMA (Stream, Locate, Scale, 1) имеет то же распределение, что и EXPONENTIAL (Stream, Locate, Scale).

Распределение Вейбулла. Это распределение используется при моделировании жизненного цикла сложного изделия или индивидуума.

Функция плотности распределения Вейбулла имеет вид:

где Г(α) - гамма-функция Эйлера, параметр α задает форму распределения, β - интенсивность отказов, λ - величину сдвига для определения местоположения распределения.

Для вызова распределения Вейбулла используется библиотечная процедура

WEIBULL (Stream, Locate, Scale, Shape),

где Stream номер генератора случайных чисел, автоматически преобразуется в целое число, которое должно быть больше или равно 1; Locate=λ; Scale=β; Shape=α. Все параметры обязательные.

На рис. 4.10 изображен «жизненный цикл» сложного изделия, в котором можно выделить три подцикла (им соответствуют три указанных на графике участка). Каждому периоду соответствует своя функция β(х) и, следовательно, свой закон распределения времени жизни изделия. Для участка приработки изделия α< 1, дл_я участка нормальной эксплуатации α = 1, для участка старения α > 1.

Когда аргумент Shape равен 1, распределение Вейбулла вырождается в экспоненциальное. Это означает, что WEIBULL (Stream, Locate, Scale, 1) имеет то же распределение, что и EXPONENTIAL (Stream, Locate, Scale).

Задание для самостоятельной работы:

1. Определите GPSS-функцию SERV для результатов розыгрыша дискретной случайной величины из табл. 4.25.

Таблица 4.25

2. Промоделируйте случайную величину PART, равномерно распределенную на интервале [0,9].

3. Приведите фрагмент программы, который моделирует процесс выбора товара в магазине. Время выбора товара равномерно распределено на интервале [5,8] мин. Единица модельного времени 1 мин.

4. Приведите фрагмент программы, который моделирует процесс прихода покупателей в магазин. Интервалы времени между приходом покупателей распределены равномерно на интервале [13,16] мин. Единица модельного времени - 1 мин.

5. Время обслуживания некоторым устройством распределено равномерно на интервале А ±4, где среднее время обслуживания А с вероятностью 0,5 принимает значение 3 и с такой же вероятностью - значение 5. Постройте модель процесса обслуживания устройством.

6. Среднее значение интервалов поступления в пуассоновском потоке требований равно 3 ч. Промоделируйте процесс поступления требований. Единица модельного времени - 1 мин.

7. Среднее значение интервалов поступления в пуассоновском потоке заявок равно 10 мин. Промоделируйте процесс поступления заявок. Единица модельного времени - 0,01 мин.

8. Время, необходимое для подгона деталей, распределено по нормальному закону с математическим ожиданием 90 и среднеквадратичным отклонением 10. Промоделируйте процесс подгона деталей.

9. Выполните задания 5-9 из главы 7.

4.14. Стандартные числовые атрибуты, параметры транзактов. Блоки ASSIGN, MARK, LOOP

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

Рассмотрим несколько примеров зависимости функционирования элементов модели от системных атрибутов, т.е. СЧА.

1. Интенсивность работы некоторого устройства зависит от длины очереди. Для определения времени обслуживания при каждом поступлении транзакта на обслуживание необходимо знать значение такого системного атрибута, как длина очереди.

2. Интенсивность обслуживания некоторого устройства зависит от общей продолжительности его функционирования (проявление усталости - интенсивность со временем уменьшается, разогрев устройства - интенсивность со временем увеличивается). Время обслуживания - функция, которая зависит от времени, прошедшего с начала работы.

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

Условно атрибуты можно поделить на две категории:

1) атрибуты системы;

2) атрибуты транзактов.

Атрибуты системы - это параметры, которые описывают состояние объектов модели. Такие количественные показатели, как «текущая длина очереди» или «коэффициент загрузки устройства» являются типичными системными атрибутами. Стандартный набор атрибутов, подобных указанным, автоматически поддерживается интерпретатором GPSS.

Транзакты также могут иметь некоторые числовые характеристики (например, уровень приоритета). Кроме того, транзакт снабжается некоторым числом параметров.

В языке GPSS атрибуты (свойства) объектов - это СЧА. Каждый объект GPSS имеет свой набор СЧА. Доступ к СЧА осуществляется при использовании специальных обозначений этих атрибутов. Имя СЧА состоит из двух частей:

1) групповое имя - состоит из одной или двух букв, идентифицирует тип объекта и тип информации о нем;

2) имя конкретного члена группы.

Объекты могут идентифицироваться с помощью числовых и символьных имен. Если объект идентифицируется с помощью номера (числовое имя), то ссылка на его стандартный числовой атрибут записывается как C4Aj, где j - номер объекта (целое число). При символьной идентификации объекта ссылка на его стандартный числовой атрибут записывается, как СЧА$<имя объекта> (в приведенных ссылках под «СЧА» понимается групповое имя).

Стандартные числовые атрибуты. В табл. 4.26 показаны СЧА устройств, в табл. 4.27 - СЧА МКУ, в табл. 4.28 -СЧА очередей. Полный список всех СЧА приведен в Приложении А.

СЧА блоков и системные СЧА. Блоки имеют два стандартных числовых атрибута (их подсчет ведется автоматически):

Wj (W$<метка блока>) - счетчик текущего содержимого блока с номером j (с меткой блока);

Nj (N$<метка блока>) - счетчик входов, т.е. общее число транзактов, вошедших в блоку с момента последнего действия операторов RESET и CLEAR (от начала работы модели, если не было операторов RESET и CLEAR).

Например, WSBL1 - это число транзактов, которые находятся в | блоке с меткой BL1; NSQP - число транзактов, вошедших в блок с меткой QP; W210 - значение текущего содержимого счетчика блока, который имеет 210-ю позицию в модели.

Важные системные СЧА:

С1 - текущее значение относительного модельного времени;

автоматически изменяется интерпретатором и устанавливается в О при выполнении операторов CLEAR и RESET;

АС1 - текущее значение абсолютного модельного времени; автоматически изменяется интерпретатором и устанавливается в 0 при выполнении оператора CLEAR;

TG1 - текущее значение счетчика завершения;

PR - приоритет транзакта, обрабатываемого в данный момент;

Ml - время пребывания в модели транзакта, обрабатываемого интерпретатором в данный момент.

Пример 4.25

Использование СЧА в блоках ENTER и ADVANCE.

ENTER 3,R3

При входе транзакта в блок ENTER, он занимает R3 каналов устройства с именем 3. Поскольку R3 - число доступных каналов МКУ 3, то транзакт занимает все каналы, которые остались свободными до его входа.

ENTER HS,R$SH

Войдя в блок ENTER, транзакт занимает R$SH каналов МКУ с именем HS.

ADVANCE        FCSPRIB

Задержка в этом блоке равна числу занятий устройства PRIB.

Параметры транзактов. Параметры транзактов - это свойства транзакта,   определяемые   пользователем.   Множество   параметров транзакта - набор стандартных числовых атрибутов, которые принадлежат транзакту. Параметры транзакта являются локальными переменными, которые доступны только данному транзакту.

В процессе перемещения транзакта по модели, его параметры ( могут задаваться и модифицироваться в соответствии с логикой работы модели.

Особенности параметров транзактов:

1. Доступ к параметрам транзактов осуществляется таким образом:

Р<номер> или Р$<имя>,

где Р - СЧА транзакта, определяющий его групповое имя, т.е. имя всех параметров транзакта.

2. Номера (имена) конкретных членов множества параметров задаются с помощью целых чисел 1, 2, ... или символьных имен. Например, Р22 - это 22-параметр транзакта, P$COLOR - параметр с именем COLOR.

3. При входе транзакта в модель начальное значение всех его параметров устанавливается в ноль.

4. Значения параметров транзактов и их изменение определяет пользователь.

5. Значениями параметров транзактов могут быть любые числа (в системе GPSS/PC - только целые числа). Параметры могут приобретать отрицательные значения.

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

7. Параметры можно использовать в качестве операндов блоков и в качестве аргументов функций.

8. Параметры позволяют организовать косвенную адресацию блоков. Это дает возможность агрегированного представления объектов моделирования в программе.

Пример 4.26

ААА     FUNCTION       P3,D3

-3,4/3,7/10,8

………...

ADVANCE        FN$AAA,3

………..

Выполнение подпрограммы блока ADVANCE предусматривает расчет функции ААА. Это в свою очередь требует определения значения аргумента функции, т.е. параметра РЗ. Пусть значение третьего параметра транзакта, вошедшего в блок ADVANCE, равно 4. Соответствующее значение функции ААА равно 8. Таким образом, время задержки будет равномерно распределено на интервале 8±3.

Пример 4.27

SEIZE PSPRIB

ADVANCE PSTSERV

RELEASE PSPRIB

Транзакт занимает устройство, номер которого задан параметром транзакта PRIB. Время обслуживания задается параметром TSERV.

Изменение      значений       параметров.      Блок      ASSIGN

(НАЗНАЧИТЬ). При входе транзакта в этот блок значения параметров могут задаваться или изменяться. Формат блока:

ASSIGN A[+,-],B[,C]

Блок ASSIGN может быть использован как в режиме замещения значения параметра (начальное значение всех параметров транзактов равно 0), так и в режиме увеличения и уменьшения. В режиме увеличения предшествующее значение параметра увеличивается на значение, стоящее в операнде В. В режиме уменьшения оно уменьшается на величину, стоящую в операнде В. Режимы увеличения и уменьшения определяются введением соответственно знаков «плюс» и «минус» перед запятой, которая разделяет операнды А и В.

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

Пример 4.28

Блок ASSIGN в режиме присваивания:

ASSIGN MEST,36

Параметру транзакта с именем MEST присваивается значение 36.

ASSIGN 3,25

Параметру РЗ присваивается значение 25.

ASSIGN P4,FR$BB

Параметру транзакта с номером, записанным в параметре Р4, присваивается значение величины загрузки устройства ВВ (оба операнда заданы косвенным образом).

Блок ASSIGN в режимах накопления и уменьшения:

ASSIGN 4+,Q5

Параметр 4 увеличивается на значение, равное текущей длине очереди 5.

ASSIGN Р2-,7

От значения параметра, номер которого задан параметром Р2, вычитается 7.

Отметка времени. При каждом входе транзакта в модель интерпретатор фиксирует для него текущее значение времени. Это значение времени называется отметкой времени. Она может быть интерпретирована как время «рождения» транзакта или время входа транзакта в модель. В явном виде отметка времени недоступна. Однако существует СЧА, который тесно связан со значением времени входа транзакта в модель. Его имя Ml, а значение определяется так:

Значение M1 для каждого транзакта изменяется в процессе моделирования. Сразу после входа транзакта в модель М1=0, через 10 единиц модельного времени М1=10 и т.д.

Пример 4.29

Пусть в устройстве, номер которого хранится в параметре CLR_1 транзакта, продолжительность обслуживания зависит от времени, которое прошло с момента входа транзакта в модель. Предполагается, что это время не может превышать 1000 ед. времени. Для этого в модели можно использовать такие блоки:

ZATR   FUNCTION       M1,C2

1,4/1000,80

…….

SEIZE P$CLR_1

ADVANCE FNSZATR

RELEASE P$CLR_1

…….

Транзитное время. Блок MARK (ОТМЕТИТЬ). Стандартный числовой атрибут M1 измеряет время, которое прошло с момента входа транзакта в модель. Однако очень часто требуется знать время, затраченное на перемещение транзакта между двумя произвольными точками модели. Для этого используется блок MARK.

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

MARK A

Таблица 4.30

Операнд

Значение

Результат по умолчанию

А

Номер параметра, в который записывается значение абсолютного времени (целое число, СЧА)

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

Пусть необходимо определить интервал времени, на протяжении которого транзакт проходит от точки Т1 к точке Т2. Для этого нужно выполнить два действия:

1) в точку T1 поместить блок MARK j, где j - номер параметра, в который записывается значение абсолютного времени в момент записи;

2) в точке Т2 обратиться к СЧА с именем MPj, где j - номер параметра, в котором сделана отметка времени транзакта; СЧА MPj будет иметь такое значение:

Организация циклов. Блок LOOP (ЦИКЛ). С помощью параметров транзактов в программе можно организовать циклы. Для этого используется блок LOOP. Он управляет количеством повторных прохождений транзактом определенной последовательности блоков модели.

Формат блока:

LOOP A[,B]

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

Переменная блока LOOP может только уменьшаться.

Пример 4.30

ASSIGN 1,3
SIS        SEIZE                PC

RELEASE              PC
LOOP 1,SIS

Цикл организован по первому параметру транзакта. Его начальное значение равно 3. После освобождения устройства проверяется значение первого параметра. Если оно не равно нулю, то транзакт возвращается к блоку, помеченному меткой SIS, т.е. занимает устройство с именем PC. Всего каждый транзакт будет занимать это устройство три раза.

Примеры фрагментов GPSS-моделей с использованием СЧА и параметров транзактов

Пример 4.31

Определение функции, значения которой зависят от текущего содержимого блока с именем РРР. Вид зависимости задан в табл. 4.32.

FFF         FUNCTION      W$PPP,D5

0,1/3,4/5,2/6,4/7,5

Пример 4.32

Определение функции, значения которой были бы вдвое больше текущей длины очереди ALPHA для значений 0, 1,2, 3, 4. Для остальных значений содержимого очереди значение функции должно быть равно 10.

Это можно сделать двумя способами:

1) с помощью дискретной функции, определяемой 6 значениями;

2) с помощью непрерывной функции, определяемой 2 значениями.

Первый способ:

LONG FUNCTION       Q$ALPHA,D6

0,0/1,2/2,4/3,6/4,8/5,10

Второй способ:

SHORT FUNCTION       Q$ALPHA,C2

0,0/5,10

Пример 4.33 [10]

В СМО с одним устройством и очередью поступает пуассоновский поток заявок с интенсивностью 12 приходов за 1 ч. Обслуживание имеет экспоненциальное распределение, но среднее время обслуживания зависит от числа заявок, которые находятся в очереди к устройству. Эта зависимость приведена в табл. 4.33. Промоделировать обслуживание 500 заявок.

Таблица 4.34 (Таблица определений)

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

Программа:

MEAN    FUNCTION       Q$WAIT,D4

0,330/2,300/5,270/6,240

XPDIS    FUNCTION       RN1,C24

0,0/.l,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915/.7,1.2/ .75,1.38/.8,1.6/.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.81/ .95,2.99/.96,3.2/.97,3.5/.98,3.9/.99,4.6/.995,5.3/.998,6.2/

.999,7/.9998,8

GENERATE 300,FN$XPDIS                       

QUEUE WAIT

SEIZE SURVR

DEPART WAIT

ADVANCE FN$MEAN,FN$XPDIS

RELEASE SURVR

TERMINATE 1

START 500                

Пример 4.34 [10]

Устройство с экспоненциальным временем обслуживания имеет свойство уменьшать интенсивность своей работы на протяжении восьмичасового рабочего дня. В течение первых двух часов ему требуется в среднем 12 мин для выполнения обслуживания. В течение последующих двух часов среднее время обслуживания составляет 15 мин. В течение пятого, шестого и седьмого часа - 17 мин, в течение восьмого часа - 20 мин. Предполагая, что единица времени в модели равна 0,1 мин, определить функцию, значения которой давали бы среднее время, необходимое устройству для выполнения обслуживания. Также показать, как эту функцию нужно использовать в блоке ADVANCE. (СЧА С1 - текущее значение относительного времени работы модели).

Фрагмент программы:

LAMDA FUNCTION       C1,D4

1200,120/2400,150/4200,170/4800,200

XPDIS                  FUNCTION       RN1,C24

0,0/.1,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915/.7,1.2/
.75,1.38/.8,1.6/.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.81/
.95,2.99/.96,3.2/.97,3.5/.98,3.9/.99,4.6/.995,5.3/.998,6.2/
.999,7/.9998,8

ADVANCE          FN$LAMBDA,FN$XPDIS

Пример 4.35 [101

Ситуация, описанная в примере 4.34, предполагает, что среднее
время обслуживания увеличивается скачкообразно. Более реально
полагать, что среднее время возрастает постепенно в течение дня.
Определить непрерывную функцию, которая описывала бы увеличение времени обслуживания в соответствии с правилом: в нулевой
момент времени среднее время равно 12 мин, к концу второго часа
оно увеличивается до 15 мин, к концу четвертого часа - до 17 мин, к
концу седьмого - до 20 мин, а к концу восьмого - до 25 мин. Считать,
что среднее время обслуживания на указанных интервалах времени
увеличивается непрерывно и равномерно.

Фрагмент программы:

MEAN                  FUNCTION       C1,C5
         0,120/1200,150/2400,170/4200,200/4800,250

XPDIS                  FUNCTION       RN1,C24

0,0/.1,.104/.2,.222/.3,.355/.4,.509/.5,.69/.6,.915/.7,1.2/ .75,1.38/.8,1.6/.84,1.83/.88,2.12/.9,2.3/.92,2.52/.94,2.81/ .95,2.99/.96,3.2/.97,3.5/.98,3.9/.99,4.6/.995,5.3/.998,6.2/ .999,7/.9998,8

…………..

ADVANCE        FNSMEAN, FNSXPDIS

…………..

Задание для самостоятельной работы:

1. Приведите фрагмент программы, который иллюстрирует занятие транзактом устройства. Транзакт занимает все свободные каналы устройства PRIB.

2. Время обработки детали на станке STAN равно половине числа занятий станка. Промоделируйте процесс обработки детали на станке.

3. Промоделируйте задержку, которая равна целой части среднего времени пребывания транзакта в устройстве PRJB.

4. Время задержки в устройстве равномерно распределено на интервале А±В, где А и В - значения параметров TIME1 и TIME2, соответственно. Приведите фрагмент программы, моделирующий эту ситуацию.

5. Транзакт занимает устройство, номер которого задан вторым параметром транзакта. Время обслуживания в устройстве задается в параметре TIMEZ. Приведите соответствующий фрагмент программы.

6. Параметру с номером, который записан в параметре ZERO, присвойте значение, которое равно числу нулевых входов в очередь 1.

7. Параметру четвертого транзакта присвойте значение 14.

8. Параметру SPEED транзакта присвойте значение 10.

9. Значение параметра, номер которого задан параметром Р5, увеличьте на 3.

10. Значение параметра WEIGHT уменьшите на 10.

11. Деталь последовательно обрабатывается на трех станках за время 5+2 мин, 15±2 мин, 3±1 мин, соответственно, а потом красится за время 10±2 с. Определите время между окончанием обработки на первом станке и началом покраски.

12. На соревнованиях по бегу каждый спортсмен выполняет две попытки. Результат (время преодоления дистанции) подчинен нормальному закону с параметрами тх=16 с, σ=3 с. Приведите фрагмент программы, которая моделировала бы эту ситуацию. 13. Выполните задание 10 из главы 7.

4.15. Изменение приоритета транзактов. Блок PRIORITY

Блок  PRIORITY  (НАЗНАЧИТЬ  ПРИОРИТЕТ)присваивает

или  изменяет  приоритет  транзакта,  если  он  был  задан  блоком GENERATE (по умолчанию приоритет транзакта равен нулю). Его