Лекции (DOC) (Лекции (DOC))

Посмотреть архив целиком

  • Общие вопросы моделирования

    1. Предмет теории моделирования.

    Моделирование - это замещение одного объекта (оригинала) другим (моделью) и фиксация и изучение свойств модели. Замещение производится с целью упрощения, удешевления, ускорения изучения свойств оригинала.

    В общем случае объектом-оригиналом может быть естественная или искусственная, реальная или воображаемая система. Она имеет множество параметров S0 и характеризуется определёнными свойствами. Количественной мерой свойств системы служит множество характеристик Y0, система проявляет свои свойства под влиянием внешних воздействий Х.

    Множество параметров S и их значений отражает её внутреннее содержание - структуру и принципы функционирования. Характеристики S - это в основном её внешние признаки, которые важны при взаимодействии с другими S.

    Характеристики S находятся в функциональной зависимости от её параметров. Каждая характеристика системы y0Y0 определяется в основном ограниченным числом параметров {S0k}S0. Остальные параметры не влияют на значение данной характеристики S. Исследователя интересуют, как правило, только некоторые характеристики S: {y}Y0 при конкретных воздействиях на систему {xmn}X.

    Модель — это тоже система со своими множествами параметров Sm и характеристик Ym. Оригинал и модель сходны по одним параметрам и различны по другим. Замещение одного объекта другим правомерны если интересующие исследователя характеристики оригинала и модели определяются однотипными подмножествами параметров и связаны одинаковыми зависимостями с этими параметрами:

    yok=f({Soi},{xon},T); (1.1)

    ymn=f({Smi},{xmn},Tm) (1.2)

    где, ymn - к-ая характеристика модели, ymnYm

    xmn - внешнее воздействие на модель, xmnX

    Tm - модельное время.

    При этом soi=(Smi); xon(xmn), T=mTm (где m - масштабный коэффициент) на всём интервале [0-Tm] или в отдельные периоды времени. Тогда с некоторым приближением можно сделать вывод о том, что характеристики Ор, связаны с характеристиками М зависимостями yok=(ymk). Множество характеристик модели Ymk={ymk} является отображением множества интересующих характеристик оригинала yok={ yok}, т.е. : Yokymk, т.е. : YokYmk.

    При исследовании сложных естественных S, у которых известны Yok, но мало изучен состав элементов и принципы их взаимодействия с помощью моделирования может решаться обратная задача. Строят предположительную модель, определяющая её характеристики Ymk при эквивалентных внешних воздействиях {xmn} (: {xon} {xmn}) и, если оказывается, что имеет место отображение : Y­ok Ymk с некоторой известной функцией , то считается, что система-оригинал имеет такие же параметры.

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

    Теория моделирования — взаимосвязанная совокупность положений, определений, методов и средств создания моделей. Сами модели являются предметом теории моделирования.

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

      1. Роль и место моделирования в исследовании систем.

    Познание любой системы (S) сводится по существу к созданию её модели. Перед изготовлением каждого устройства или сооружения разрабатывается его модель - проект. Любое произведение искусства является моделью, фиксирующее действительность.

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

    На качественно новую ступень поднялась моделирование в результате разработки методологии имитационного моделирования на ЭВМ.

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

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

    Сами ВС как сложные и дорогостоящие технические системы могут являться объектами моделирования.

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

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

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

      1. Классификация моделей.

    Физические модели. В основу классификации положена степень абстрагирования модели от оригинала. Предварительно все модели можно подразделить на 2 группы — физические и абстрактные (математические).

    Ф.М. обычно называют систему, эквивалентную или подобную оригиналу, но возможно имеющую другую физическую природу. Виды Ф.М.:

    • натуральные;

    • квазинатуральные;

    • масштабные;

    • аналоговые;

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

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

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

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

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

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

    Аналитической моделью называется такое формализованное описание системы, которое позволяет получить решение уравнения (1.2) в явном виде, используя известный математический аппарат.

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

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

    1. Математические схемы моделирования систем.

      1. Основные подходы к построению ММ систем.

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

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

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

    Например, представление процесса функционирования ИВС коллективного пользования в виде сети схем массового обслуживания даёт возможность хорошо описать процессы, происходящие в системе, но при сложных законах входящих потоков и потоков обслуживания не даёт возможности получения результатов в явном виде.

    Математическую схему можно определить как звено при переходе от содержательного к формализованному описанию процесса функционирования системы с учётом воздействия внешней среды. Т.е. имеет место цепочка: описательная модель — математическая схема — имитационная модель.

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

    При построении ММ системы S необходимо решить вопрос о её полноте. Полнота моделирования регулируется, в основном, выбором границ "Система S — среда Е". Также должна быть решена задача упрощения ММ, которая помогает выделить основные свойства системы, отбросив второстепенные в плане цели моделирования.

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

    - совокупность Х - входных воздействий на S хiХ, i=1…nx;

    - совокупность воздействий внешней среды vlV, l=1…nv;

    - совокупность внутренних (собственных) параметров системы hkH, k=1…nh;

    - совокупность выходных характеристик системы yjY, j=1…ny.

    В перечисленных множествах можно выделить управляемые и неуправляемые величины. В общем случае X, V, H, Y не пересекаемые множества, содержат как детерминированные так и стохастические составляющие. Входные воздействия Е и внутренние параметры S являются независимыми (экзогенными) переменными, Выходные характеристики - зависимые переменные (эндогенные) . Процесс функционирования S описывается оператором FS:

    (1)

    - выходная траектория. FS - закон функционирования S. FS может быть функция, функционал, логические условия, алгоритм, таблица или словесное описание правил.

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

    Соотношение (1) является математическим описанием поведения объекта S моделирования во времени t, т.е. отражает его динамические свойства. (1) - это динамическая модель системы S. Для статических условий ММ есть отображения X, V, H в Y, т.е. (2)

    Соотношения (1), (2) могут быть заданы формулами, таблицами и т.д.

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

    Состояния системы S характеризуются векторами:

    и , где в момент tl(t0, T)

    в момент tll(t0, T) и т.д. к=1…nZ.

    Z1(t), Z2(t)… Zk(t) - это координаты точки в к-мерном фазовом пространстве. Каждой реализации процесса будет соответствовать некоторая фазовая траектория.

    Совокупность всех возможных значений состояний {} называется пространством состояний объекта моделирования Z, причём zkZ.

    Состояние системы S в интервале времени t0Tl полностью определяется начальными условиями , где входными , внутренними параметрами и воздействиями внешней среды , которые имели место за промежуток времени t* - t0 c помощью 2-х векторных уравнений:

    ; (3)

    . (4)

    иначе: . (5)

    Время в мод. S может рассматриваться на интервале моделирования (t0, T) как непрер., так и дискретное, т.е. квантованное на отрезке длин. t.

    Таким образом под ММ объекта понимаем конечное множество переменных {} вместе с математическими связями между ними и характеристиками .

    Моделирование называется детерминированным, если операторы F, Ф детерминированные, т.е. для конкретного входа выход детерминированный. Детерминированное моделирование - частный случай стохастического моделирования. В практике моделирование объектов в области системного анализа на первичных этапах исследования рациональнее использовать типовые математические схемы: диф. уравнения, конечные и вероятностные автоматы, СМО и т.д.

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

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

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

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

      1. Непрерывно детерминированные модели (Д - схемы).

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

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

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

    Математическое соотношение для детерминированных систем в общем виде:

    (7).

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

    Диф. уравнения, Д - схемы являются математическим аппаратом теории систем автоматического регулирования, управления.

    При проектировании и эксплуатации систем САУ необходимо выбрать такие параметры системы, которые бы обеспечивали требуемую точность управления.

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

      1. Дискретно – детерминированные модели (F-схемы)

    ДДМ являются предметом рассмотрения теории автоматов (ТА). ТА - раздел теоретической кибернетики, изучающей устройства, перерабатывающие дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени.

    Конечный автомат имеет множество внутренних состояний и входных сигналов, являющихся конечными множествами. Автомат задаётся F- схемой: F=,,z0>, (1)

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

    В момент t, будучи в состоянии z(t), автомат способен воспринять сигнал x(t) и выдать сигнал y(t)=[z(t),x(t)], переходя в состояние z(t+1)=[z(t),z(t)], z(t)Z; y(t)Y; x(t)X. Абстрактный КА в начальном состоянии z0 принимая сигналы x(0), x(1), x(2) … выдаёт сигналы y(0), y(1), y(2)… (выходное слово).

    Существуют F- автомат 1-ого рода (Миля), функционирующий по схеме:

    z(t+1)= [z(t),z(t)], t=0,1,2… (1)

    y(t)=[z(t),x(t)], t=0,1,2… (2)

    1. автомат 2-ого рода:

    z(t+1)= [z(t),z(t)], t=0,1,2… (3)

    y(t)=[z(t),x(t-1)], t=1,2,3… (4)

    Автомат 2-ого рода, для которого y(t)=[z(t)], t=0,1,2,… (5)

    т.е. функция выходов не зависит от входной переменной x(t), называется автоматом Мура.

    Т.о. уравнения 1-5 полностью задающие F- автомат, являются частным случаем уравнения

    (6)

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

    когда система S - денорминированная и на её вход поступает дискретный сигнал x.

    По числу состояний конечные автоматы бывают с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом согласно (2), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определённый выходной сигнал y(t), т.е. реализует логическую функцию вида:

    y(t)=[x(t)], t=0,1,2,…

    Эта функция называется булевой, если алфавиты X и Y, которым принадлежат значения сигналов x и y состоят из 2-х букв.

    По характеру отсчёта времени (дискретному) F- автоматы делятся на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые автомат "считывает" входные сигналы, определяются принудительно синхронизирующими сигналами. Реакция автомата на каждое значение входного сигнала заканчивается за один такт синхронизации. Асинхронный F- автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный водной сигнал постоянной величины x, он может, как это следует из 1-5, несколько раз изменить своё состояние, выдавая соответствующее число выходных сигналов, пока не перейдёт в устойчивое.

    Для задания F- автомата необходимо описать все элементы множества F=,,z0>, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Для задания работы F- автоматов наиболее часто используются табличный, графический и матричный способ.

    В табличном способе задания используется таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. При этом обычно 1-ый столбец слева соответствует начальному состоянию 0. На пересечении i-ой строки и j-ого столбца таблицы переходов помещается соответствующее значение (zk,xi) функции переходов, а в таблице выходов - (zk, xi) функции выходов. Для F- автомата Мура обе таблицы можно совместить, получив т.н. отмеченную таблицу переходов, в которой над каждым состоянием zk автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию, согласно (5), выходной сигнал (zi).

    Описание работы F- автомата Мили таблицами переходов и выходов иллюстрируется таблицей (1), а описание F- автомата Мура - таблицей переходов (2).

    Таблица 1

    xj

    zk


    z0

    z1

    zk

    Переходы

    x1

    (z0,x1)

    (z1,x1)

    (zk,x1)

    x2

    (z0,x2)

    (z1,x2)

    (zk,x2)

    …………………………………………………………

    xl

    Выходы

    x1

    (z0,x1)

    (z1,x1)

    (zk,x1)

    …………………………………………………………

    xl

    (z0,xl)

    (z1,xl)

    (zk,xl)

    Таблица 2


    (zk)

    xi

    (z0)

    (z1)

    (zk)


    z0

    z1

    zk

    x1

    (z0,x1)

    (z1,x1)

    (zk,x1)

    x2

    (z0,x2)

    (z1,x2)

    (zk,x2)

    …………………………………………………………

    xl

    (z0,xl)

    (z1,xl)

    (zk,xl)

    Примеры табличного способа задания F- автомата Мили F1 с тремя состояниями, двумя входными и двумя выходными сигналами приведены в таблице 3, а для F- автомата Мура F2 - в таблице 4.

    Таблица 3

    xj

    z0


    z0

    z1

    z2

    Переходы

    x1

    z2

    z0

    z0

    x2

    z0

    z2

    z1

    Выходы

    x1

    y1

    y1

    y2

    x2

    y1

    y2

    y1

    Таблица 4


    y

    xi

    y1

    y1

    y3

    y2

    y3


    z0

    z1

    z2

    z3

    z4

    x1

    z1

    z4

    z4

    z2

    z2

    x2

    z3

    z1

    z1

    z0

    z0

    При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi с вершиной zj обозначается xk. Для того, чтобы задать функцию переходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производиться так: если входной сигнал xk ­действует на состояние zi, то согласно сказанному получается дуга, исходящая из zi­ и помеченная xk; эту дугу дополнительно отмечают выходным сигналом y=(zi, xk). Для автомата Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние автомата, вызывает переход в состояние zj, то дугу, направленную в zj и помеченную xk, дополнительно отмечают выходным сигналом y=(zj, xk). На рис. 1 приведены заданные ранее таблицами F- автоматы Мили F1 и Мура F2 соответственно.

    Рис. 1. Графы автоматов Мили (а) и Мура (б).

    При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=|| cij ||, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент cij­­=xk/yS в случае автомата Мили соответствует входному сигналу xk, вызывающему переход из состояния zi в состояние zj и выходному сигналу yS, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:

    Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар "вход/выход" для этого перехода, соединённых знаком дизъюнкции.

    Для F- автомата Мура элемент cij равен множеству входных сигналов на переходе (zizj), а выход описывается вектором выходов:

    i-ая компонента которого выходной сигнал, отмечающий состояние zi

    Пример. Для рассмотренного ранее автомата Мура F2 запишем матрицу состояний и вектор выходов:

    ;

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

    Рассмотрим вид таблицы переходов и графа асинхронного конечного автомата. Для F- автомата состояние zk называется устойчивым, если для любого входа xiX, для которого (zk,xi)=zk имеет место (zkxi)=yk. Т.о. F- автомат называется асинхронным, если каждое его состояние zkZ устойчиво.

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

    Пример. Рассмотрим асинхронный F- автомат Мура, который описан в табл. 5 и приведён на рис. 2.

    Таблица 5


    y

    xi

    y1

    y2

    y3


    z0

    z1

    z2

    x1

    z1

    z1

    z1

    x2

    z2

    z1

    z2

    x3

    z0

    z0

    z2

    Рис. 2.Граф асинхронного автомата Мура.

    Если в таблице переходов асинхронного автомата некоторое состояние zk стоит на пересечении строки xS и столбца zS(Sk), то это состояние zk обязательно должно встретиться в этой же строке в столбце zk.

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

    1. Непрерывно-стохастические модели (Q - схемы).

    К ним относятся системы массового обслуживания ( англ. queuing system), которые называют Q- схемами.

      1. Методы теории массового обслуживания.

    Предмет ТМО — системы массового обслуживания (СМО) и сети массового обслуживания. Под СМО понимают динамическую систему, предназначенную для эффективного обслуживания случайного потока заявок при ограниченных ресурсах системы. Обобщённая структура СМО приведена на рисунке 3.1.

    Рис. 3.1. Схема СМО.

    Поступающие на вход СМО однородные заявки в зависимости от порождающей причины делятся на типы, интенсивность потока заявок типа i (i=1…M) обозначено i. Совокупность заявок всех типов - входящий поток СМО.

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

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

    Q - схемы можно исследовать аналитически и имитационными моделями. Последнее обеспечивает большую универсальность.

    Рассмотрим понятие массового обслуживания.

    В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и собственно обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания Пi, состоящего из накопителя заявок, в котором может находится одновременно li=0…LiH заявок, где LiH - ёмкость i-ого накопителя, и канала обслуживания заявок, ki.

    Рис. 3.2. Схема прибора СМО

    На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi , на канал ki - поток обслуживания ui.

    Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Различают потоки однородных и неоднородных событий. Однородный ПС характеризуется только моментами поступления этих событий (вызывающими моментами) и задаётся последовательностью {tn}={0t1t2tn…}, где tn - момент поступления n- ого события - неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени между n-ым и n-1-ым событиями {n}.

    Неоднородным ПС называется последовательность {tn, fn} , где tn- вызывающие моменты; fn- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п.

    Рассмотрим ОПС, для которого i{n}- случайные величины, независимые между собой. Тогда ПС называется потоком с ограниченным последействием.

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

    Если для любого интервала t событие P0(t, t) + P1(t, t) + Р1(t, t)=1, P1(t, t) - вероятность попадания на интервал t ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P0(t, t) + P1(t, t) 1, Р1(t, t)=(t), где (t)- величина, порядок малости который выше, чем t, т.е. lim((t))=0 при t0.

    Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени зависит от длины этого участка и не зависит от того, где на оси времени 0 - t взят этот участок. Для ОПС справедливо 0*P0(t, t) + 1*P1(t, t)= P1(t, t) - среднее число событий на интервале t. Среднее число событий, наступающих на участке t в единицу времени составляет P1(t, t)/t. Рассмотрим предел этого выражения при t0

    lim P1(t, t)/t=(t)*(1/един.вр.).

    Если этот предел существует, то он называется интенсивностью (плотностью) ОПС. Для стандартного ПС (t)==const.

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

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

    Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементов во времени Zi(t). Переход в новое состояние для Пi означает изменение кол-ва заявок, которые в нём находятся (в канале ki и накопителе Hi). Т.о. вектор состояний для Пi имеет вид : , где - состояния накопителя, (=0 - накопитель пуст, =1- в накопителе одна заявка…, =- накопитель занят полностью; - состояние канала ki (=0 - канал свободен, =1 канал занят).

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

    Т.о. для задания Q-схемы необходимо оператор сопряжения R, отражающий взаимосвязь элементов структуры.

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

    Собственными (внутренними) параметрами Q-схемы будут являться кол-во фаз LФ, количество каналов в каждой фазе, Lkj, j=1… LФ, количество накопителей каждой фазы Lkj, k=1… LФ, ёмкость i-ого накопителя LiH. Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию:

    • системы с потерями (LiH=0, накопитель отсутствует);

    • системы с ожиданием (LiH);

    • системы с ограниченной ёмкостью накопителя Нi (смешанные).

    Обозначим всю совокупность собственных параметров Q-схемы как подмножество Н.

    Для задания Q-схемы также необходимо описать алгоритмы её функционирования, которые определяют правила поведения заявок в различных неоднозначных ситуациях.

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

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

    Необходимо также знать набор правил, по которым заявки покидают Нi и ki: для Нi – либо правила переполнения, либо правила ухода, связанные с истечением времени ожидания заявки в Нi­; для ki – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале ki, т.е. правила блокировок канала. При этом различают блокировки ki по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q‑схеме, регулирующих поток заявок в зависимости от состояний Q‑схемы. Набор возможных алгоритмов поведения заявок в Q‑схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А.

    Т.о. Q‑схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = .

    1. Имитационное моделирование систем.

      1. Процедура имитационного моделирования.

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

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

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

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

    Основная идея метода ИМ состоит в следующем. Пусть необходимо определить функцию распределения случайной величины y. Допустим, что искомая величина y может быть представлена в виде зависимости: y=f( где  случайные величины с известными функциями распределения.

    Для решения задач такого вида применяется следующий алгоритм:

    1. по каждой из величин  производится случайное испытание, в результате каждого определяется некоторое конкретное значение случайной величины iii;

    2. используя найденные величины, определяется одно частное значение y­­­­i по выше приведённой зависимости;

    3. предыдущие операции повторяются N раз, в результате чего определяется N значений случайной величины y;

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

      1. Имитация функционирования системы.


    Предположим, исследуется вычислительная система (ВС), состоящая из процессора 1 с основной памятью, устройство вода перфокарт 4, АЦПУ 2 и дисплея 3 (рис. 4.1.).

    Рис. 4.1. Упрощённая схема моделируемой системы.

    Через устройство 4 поступает поток заданий Х1. Процессор обрабатывает задания и результаты выдаёт на АЦПУ 2. Одновременно с этим ВС используется, например, как информационно-справочная система. Оператор-пользователь, работающий за дисплеем, посылает в систему запросы Х2, которые обрабатываются процессором и ответы выводятся на экран дисплея. Процессор работает в 2-х программном режиме: в одном разделе обрабатываются задания Х1, в другом, с более высоким относительным приоритетом запросы Х2. Представим данную ВС в упрощённом варианте в виде стохастической сети из 4-х СМО. Потоки заданий и запросы будем называть потоками заявок. Считаем потоки Х1 и Х2 независимыми. Известны ф.р. периодов следования заявок 1 и 2 и длительность обслуживания Т, T заявок в к-ом устройстве. Требуется определить времена загрузки каждого устройства и времена реакции по каждому из потоков.

    Вначале определяется момент поступления в систему 1-ой заявки потока Х1 по результатам случайного испытания в соответствии с ф.р. периода следования заявок.

    Рис. 4.2. Временная диаграмма функционирования ВС.

    На рис. 2 это момент времени t1=0+11 (здесь и далее верхний индекс обозначает порядковый номер заявки данного потока). То же самое делается для потока Х2. На рис.2 момент поступления 1-ой заявки потока Х2 t2=0+21. Затем находится минимальное время, т.е. наиболее раннее событие. В примере это время t1. Для 1-ой заявки потока Х1определяется время обслуживания устройством ввода перфокарт Т114 методом случайного испытания и отмечается момент окончания обслуживания t4=t1+ Т114. На рис. показан переход устройства 4 в состояние "занято". Одновременно определяется момент поступления следующей заявки потока Х1: t12=t1+12. Следующее минимальное время это момент поступления заявки потока Х2 - t2. Для этой заявки находится время обслуживания на дисплее Т123 и отслеживается время окончания обслуживания t3=t2+ Т123 . Определяется момент поступления второй заявки потока Х2: t7=t2+22 . Снова выбирается минимальное время — это t3. В этот момент заявка потока Х2 начинает обрабатываться процессором. По результату случайного испытания определяется время её обслуживания T121 и отмечается момент t5=t3+ T121 окончания обслуживания. Следующее минимальное время t4 - момент завершения обслуживания заявки потока Х1 устройством 4. С этого момента заявка может начать обрабатываться процессором, но он занят обслуживанием потока Х2. Тогда заявка потока Х1 переходит в состояние ожидания, становиться в очередь. В следующий момент времени t5 освобождается процессор. С этого момента процессор начинает обрабатывать заявку потока Х1, а заявка потока Х2 переходит на обслуживание дисплеем, т.е. ответ на запрос пользователя передаётся из основной памяти в буферный накопитель дисплея. Далее определяются соответствующие времена обслуживания: T111 и T123 и отмечаются моменты времени t9=t5+ T111 и t6=t5+ T123. В момент t6 полностью завершается обработка первой заявки потока Х2. По разности времени t6 и t2 вычисляется время реакции по этой заявке u12= t6- t2. Следующий минимальный момент t7 - это наступление 2-ой заявки потока Х2. Определяет время поступления очередной заявки этого потока t15= t7+23. Затем вычисляется время обслуживания 2-ой заявки на дисплее T223 и отмечается момент t8=t7+ T223, после чего заявка становится в очередь, т.к. процессор занят. Эта заявка поступит на обслуживание в процессор только после его освобождения в момент t9 . В этот момент заявка потока Х1 начинает обслуживаться в АЦПУ. Определяются времена обслуживания Т221 и Т112 по результатам случайных испытаний и отмечаются моменты окончания обслуживания t11= t9223 и t10= t9112. В момент времени t10 завершается полное обслуживание 1-ой заявки потока Х1. Разность между этим моментом и моментом времени t1 даёт 1-ое значение времени реакции по потоку Х1 u11= t10- t1.

    Указанные процедуры выполняются до истечения времени моделирования. В результате получается некоторое количество (выборка) случайных значений времени реакции (u1) и (u2) по 1-ому и 2-ому потокам. По этим значениям могут быть определены эмпирические функции распределения и вычислены количественные вероятностные характеристики времени реакции. В процессе моделирования можно суммировать продолжительности занятости каждого устройства обслуживанием всех потоков. Например, на рис. 2 занятость процессора 1 выделена заштрихованными ступеньками. Если результаты суммирования разделить на время моделирования, то получатся коэффициенты загрузки устройств.

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

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

    • снятие заявки без возврата;

    • помещение заявки в очередь и дообслуживание после восстановления;

    • поступление на повторное обслуживание из очереди;

    1. Обобщённые алгоритмы имитационного моделирования.

      1. Алгоритм моделирования по принципу особых состояний.

    Оно использовалось в приведённом выше примере. В качестве событий выделены:

    • поступление заявки в систему;

    • освобождение элемента после обслуживания заявки;

    • завершения моделирования;


    • возникновение отказа устройств другие типы

    • завершение восстановления устройств событий

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

    1. определяется событие с минимальным временем — наиболее раннее событие;

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

    3. определяется тип события;

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

    5. перечисленные действия повторяются до истечения времени моделирования.

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

    Рис. 5.1. Обобщённый алгоритм моделирования систем по принципу особых состояний

      1. Алгоритм моделирования по принципу t.

    Укрупнённая схема моделирующего алгоритма, который реализует принцип постоянного приращения модельного времени (принципа t), представлен на следующем рисунке:

    Рис. 5.2. Обобщённый алгоритм моделирования систем по принципу приращений "t"

    В начале инициализируется программа, в частности вводятся значения Zi(t­0), i=1,2,…k. Которые характеризуют состояние системы в k-мерном фазовом пространстве состояний в начальный момент времени t0. Модельное время устанавливается t = t0= 0. Основные операции по имитации системы осуществляется в цикле. Функционирование системы отслеживается по последовательной схеме состояний Zi(t­). Для этого модельному даётся некоторое приращение dt. Затем по вектору текущих состояний определяются новые состояния Zi(t + dt), которые становятся текущими. Для определения новых состояний по текущим в формализованном описании системы должны существовать необходимые математические зависимости. По ходу имитации измеряются, вычисляются, фиксируются необходимые выходные характеристики. При моделировании стохастических систем вместо новых состояний вычисляются распределения вероятностей для возможных состояний. Конкретные значения вектора текущих состояний определяются по результатам случайных испытаний. В результате проведения имитационного эксперимента получается одна из возможных реализаций случайного многомерного процесса в заданном интервале времени (t0 , Tk).

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

    1. Методы определения характеристик моделируемых систем.

      1. Измеряемые характеристики моделируемых систем.

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

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

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

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

    k=Vk*Nok/Tm (1)

    Vk- среднее время обслуживания одной заявки к-ым устройством;

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

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

      1. Расчёт математического ожидания и дисперсии выходной характеристики.

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

    mn=mn-1*(n-1)/n + y/n; (2)

    где mn-1 - математическое ожидание, вычисленное на предыдущем шаге.

    dn=dn-1*(n-2)/(n-1) + 1/n*(yn-mn-1)2 (3)

    здесь dn-1 - дисперсия, вычисленная на предыдущем шаге.

    При большом количестве измерений эти оценки являются состоятельными и несмещёнными.

      1. Расчёт среднего по времени значения выходной характеристики.

    Например, средняя длина очереди к каждому устройству вычисляется по формуле:

    (4)

    где i - номер очередного изменения состояния очереди (занесение заявки в очередь или исключение из очереди); N - количество изменений состояния очереди; - интервал времени между двумя последними изменениями очереди.

    Ёмкость накопитель: (5)

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

      1. Построение гистограммы для стационарной системы.

    Г - эмпирическая плотность распределения вероятностей. Задаются границы изменения интересующей характеристики. уi[yнв], числом интервалов Ng. Определяется ширина интервала =( yн -­ ув)/Ng.

    Затем в процессе моделирования по мере появления значений уi определяется число попаданий этой случайной величины в каждый из интервалов Ri гистограммы. По этим данным вычисляется относительная частота по каждому интервалу: Gi=Ri/(N*), где N - общее число измерений у. Площадь гистограммы равна единице, равна сумме площадей:

    , т.к.

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

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

    (7).

    Из теоремы Пирсона следует, что для любой функции распределения F(y) случайной величины у при N распределения величины 2 имеет вид:

    , где z - значение случайной величины 2 ,

    k=Ng-(r +1) - число степеней свободы распределения 2 . r - количество параметров теоретического распределения, Г(к/2) - гамма функция.

    Функция распределения 2 табулирована. По вычисленному значению 2 и числу степеней свободы с помощью таблиц определяется вероятность Р(2. Если она превышает заданный уровень значимости С, то выдвинутая гипотеза принимается.

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

    Важной задачей в практике имитационного моделирования систем на ЭВМ является расчёт случайных величин. В языках программирования существуют датчики равномерно распределённых псевдослучайных величин в интервале {0,1}. Остановимся на вопросах преобразования последовательности псевдослучайных величин {Xi} в последовательности {Yi} с заданным законом распределения и моделировании различных случайных событий.

      1. Рассмотрим особенности моделирования случайных событий.

    Пусть имеются случайные числа xi, т.е. возможные значения случайной величины , равномерно распределённой в интервале {0,1}. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью Р. Определим А как событие, состоящее в том, что выбранное значение xi удовлетворяет неравенству:

    xi­Р (1)

    Тогда вероятность события А будет : . Противоположное событию А состоит в том, что xi­>р. Тогда . Процедура моделирования состоит в этом случае в выборе значений xi и сравнение их с р. При этом, если условие (1) удовлетворяется, то исходом испытания будет событие А.

    Таким же образом можно рассмотреть группу событий. Пусть А1, А2…Аn – полная группа событий, наступающая с вероятностями Р1, Р2, … Рn соответственно. Определим Аm как событие, состоящее, в ом, что выбранное значение xi случайной величины удовлетворяет неравенству:

    lm-1­im, где (2)

    Тогда . Процедура моделирования испытаний в этом случае состоит в последовательности сравнений случайных чисел xi со значениями lk. Исходом испытания оказывается событие Am, если выполняется условие (2). Эту процедуру называют определением исхода по жребию в соответствии с вероятностями Р1, Р2, … Рn.

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

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

    Рассмотрим случай, когда события А и В являются зависимыми и наступают с вероятностями РА и РВ. Обозначим через Р(В/А) условную вероятность события В при условии, что событие А произошло. Считаем, что Р(В/А) задана. Из последовательности случайных чисел {X} извлекается определённое число xm и проверяется справедливость неравенства xmA. Если это неравенство справедливо, то наступило событие А. Для испытания, связанного с событием В используется вероятность Р(В/А). Из совокупности чисел {X} берётся очередное число xm+1 и проверяется условие xm+1 Р(В/А). В зависимости от того выполняется или нет это неравенство, исходом испытания является АВ или . Если неравенство xmA не выполняется, то наступило событие . Поэтому для испытания, связанного с событием В необходимо определить вероятность:

    Выберем из совокупности {X} число xm+1 и проверим справедливость неравенства . В зависимости от того, выполняется оно или нет, получаем исходы испытания . Алгоритм вычислений можно представить в виде схемы, которая изображена на рисунке 7.1.

    Рис.7.1. Схема моделирования группы случайных событий

      1. Преобразование случайных величин.

    Дискретная случайная величина принимает значения y1 y2 y3… yl с вероятностями P1, P2…, Pl составляющими дифференциальное распределение вероятностей:

    y y1 y2…… yj

    P(=y) P1, P2……Pj (3)

    При этом интегральная функция распределения ymym+1; m=1,2,...

    F(y)=0, y1. (4)

    Для получения дискретных случайных величин можно использовать метод обратной функции. Если - равномерно распределённая на интервале (0, 1), случайная величина получается с помощью преобразования

    =F-1(), где F-1 - функция, обратная F. (5)

    Алгоритм вычисления по (4) и (5) сводится к выполнению следующих действий:

    если х1<Р1 то =y1 иначе,

    если х2<Р12 то =y2 иначе,

    (6)

    если хj< то =ym иначе

    При счёте по (6) среднее число циклов сравнения равняется

    Пример 1. Необходимо методом обратной функции на основании базовой последовательности случайных чисел {xi}, равномерно распределённых в интервале (0,1), получить последовательность чисел {yi}, имеющих биноминальное распределение, задающее вероятность у удачных исходов в N реализациях некоторого эксперимента:

    P(i=y)=PN(y)=CNyPy(1-P)N-y , где P=0.5 и N=6; CNy=N!/y!(N-y)!

    Математическое ожидание и дисперсия биноминального распределения соответственно будут М[y]=np(1-P). Используя для Рj обозначения, принятые в (6), вычислим:

    j …

    1

    2

    3

    4

    5

    6

    7

    yj

    0

    1

    2

    3

    4

    5

    6

    Pj

    0.01562

    0.09375

    0.23438

    0.3125

    0.23438

    0.09375

    0.01562


    0.01562


    0.10937


    0.34375


    0.65625


    0.89063


    0.98438


    1.0000

    Например, получив из равномерного распределения число Х­i=0.89063 и проведя сравнения по алгоритму (6), найдём, что 0.85393<0.89063, т.е. yi=4. При этом среднее число циклов сравнения =1*0.01562+2*0.09375+3*0.23438+4*0.31250+5*0.23438+6*(0.09375+0.01562)3.98.

      1. Вычисление непрерывных случайных величин.

    Непрерывная случайная величина задана интегральной функцией распределения:

    , где - плотность вероятностей.

    Для получения непрерывных случайных величин с заданным законом распределения, как и для дискретных величин можно использовать метод обратной функции. Взаимно однозначная монотонная функция =F-1(), полученная решением относительно управления F(y)= преобразует равномерно распределённую на интервале (0,1) величину в с требуемой плотностью (y).

    Действительно, если случайная величина имеет плотность распределения (y), то распределение случайной величины является равномерным.

    Т.о. чтобы получить число, принадлежащее последовательность случайных чисел {y}, имеющих функцию плотности (y), необходимо разделить относительно yi управление

    (7)

    Пример 2. Необходимо получить случайные числа yi с показательным законом распределения.

    f(y)=e-y, y>0.

    В силу соотношения (7) получим , где xi - случайное число, имеющее равномерное распределение в интервале (0,1), тогда

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

    При моделировании случайной величины y с плотностью распределения вероятностей f(y) в интервале ayb независимые значения xm и xm+1 преобразуются в значения

    y1m=a+(b-a)*xm (8)

    z1m+1=f1(y)* xm+1 (9)




    где f1(y)=max| f(y)|. При этом y1m и z1m+1 - значения случайных величин, равномерно распределенных на интервале (a,b) и (0,f1m). Эти значения можно рассматривать как абсциссы и ординаты случайных точек, равномерно распределяющихся внутри прямоугольника со сторонами b-a и f1m, охватывающего кривую распределения f(y) (см. рисунок 7.2.).

    Рис. 7.2. Иллюстрация метода исключений

    Если z1m+1f(ym1), (10)

    тогда пара y1m, z1m+1 определяет случайную точку под кривой f. Вероятность попадания случайной точки, удовлетворяющей условию (10) под кривую f равна единице, а вероятность попадания в заштрихованную элементарную площадку равна f(y1m)*y1m­. Это обозначает, что абсциссы y1m случайных точек, попадающих под кривую f - значения случайной величины y с заданной плотностью вероятности f(y). Моделируемый алгоритм состоит из функций : 1) получения xm1 и xm+1 от датчика; 2) расчёта y1v и z1m+1 согласно (8) и (9); 3) вычисления f(y1m); 4) сравнения z1m+1 с f(y1m). Если условия (10) выполняются, то y=y1m; если нет, то значения y1m и z1m+1 исключаются и процесс повторяется, начиная с пункта 1. При моделировании системы 2-х случайных величин (y1y2) с плотностью вероятности f(y1,y2), a1y1b1; a2y2b2, аналогично моделированию одной случайной величины, три значения: xm, xm+1, xm+2, выданные датчиком Е, преобразуются в значения:

    y1m=a1+(b1-a1)xm (11)

    y2m=a2+(b2-a2)xm+1 (12)

    z3m=fmxm+2, где fm=max[f(x1,x2)] (13)

    Если z3mf(y1m,y2m) (14)

    то y1=y1m; y2=y2m.

    В этом случае случайные точки с координатами y1m, y2m, z3m - равномерно распределены в пределах параллепипеда со сторонами, равными (b1-a1)(b2-a2), fm и условие (14) означает попадание точки под поверхность f. Аналогично моделируется система n случайных величин (y1,y2,…,yn).

      1. Моделирование нормально распределённой случайной величины y.

    Оно может быть осуществлено на основании центральной предельной теоремы, согласно которой закон распределения суммы независимых случайных величин стремится к нормальному с увеличением числа слагаемых. Для решения некоторых задач практически сумму значений, выданных с генератором случайных чисел с характеристиками f(xi)=1, 0xi1, mx=0.5, .

    Можно считать значениями распределённой случайной величины при n8. Так как все слагаемые xi имеют одинаковые математические ожидания mx и дисперсии Dx, то my=nmx, Dy=nDx. В таблице 1 приведены формулы для расчёта случайных величин для различных видов распределений на базе случайной величины с равномерным распределением.

    Получение случайной величины с различными распределениями.

    Таблица 1.

    Нужное распределение

    Плотность распределения

    Способ получения случайной величины

    Экспоненциальное

    f(y)=e-(y-), y

    Гамма распределение (целочисленные значения )

    Распределение 2

    RN - нормированная случ. величина с нормальным законом распределения

    Логарифмические норм. Распределение

    Вейбулла

    1. Моделирование систем с использованием типовых математических схем

      1. Блочные иерархические модели процессов функционирования систем

    Рассмотрим машинную модель Mm, системы S как совокупность блоков {mi}, i=1,2…n. Каждый блок модели можно охарактеризовать конечным набором возможных состояний {Z0}, в которых он может находиться. Пусть в течение рассматриваемого интервала времени (0,Т) блок i изменяет состояние в моменты времени tijТ , где j - номер момента времени. Момент времени можно разделить на три группы:

    • случайные, связанные с внутренними свойствами блока;

    • случайные, связанные с изменением состоянием других блоков, имитирующая воздействие среды Е;

    • детерминированные моменты, связанные с заданным расписанием функционирования блока.

    Моментами смены состояний модели Мм в целом t(k) Т будем считать все моменты изменения блоков {mi}, рис. 8.1. см. ниже.

    Рис. 8.1. Смена состояний модели для случаев 3-х блоков

    При этом моменты ti(j) и tk являются моментами системного времени, т.е. времени, в котором функционирует система S. При машинной реализации модели Мм её блки представляются соответствующими программными модулями.

      1. Особенности реализации процессов с использованием Q-схем

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

    Рассмотрим фрагмент Q-схемы (Рис. 8.2.):

    Рис. 8.2. Фрагмент Q-схемы.

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

    Моделирующий алгоритм должен отвечать следующим требованиям:

    • обладать универсальностью относительно структуры, алгоритмов функционирования и параметров системы S;

    • обеспечивать одновременную и независимую работу системы S;

    • укладываться в приемлемые затраты ресурсов ЭВМ. (памяти, времени расчёта для реализации машинного эксперимента);

    • проводить разбиение на достаточно автономные логические части (блоки);

    • гарантировать выполнение рекуррентного правила расчётов;

    При этом необходимо иметь виду, что появление одной заявки входящего потока в некоторый момент времени ti может вызвать изменение состояния не более чем одного из элементов Q-схемы, а окончание обслуживания заявки в момент ti в некотором канале К может привести в этот момент времени к последовательному изменению состояний нескольких элементов (Н,К), т.е. будет иметь место процесс распространения смены состояний в направлении противоположном движению заявки в системе S. Поэтому просмотр элементов Q-схемы должен быть противоположным движению заявок.

    Все виды моделирующих алгоритмов Q-схемы можно классифицировать следующим образом (см. Рис. 8.3.):

    Рис. 8.3. Виды моделирующих алгоритмов Q-схемы.

    Алгоритмы моделирующие Q-схему по принципу "t" являются детерминированными (по шагу), а по принципу особых состояний – стохастические. Последние могут быть реализованы синхронным и асинхронным способами.

    При синхронном способе один из элементов Q-схемы (И, Н или К) выбирается в качестве ведущего и по нему "синхронизируется" весь процесс моделирования.

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

      1. Построение и реализация моделирующих алгоритмов Q-схем

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

    Пример. Рассмотрим Q-схему (Рис. 8.4.):

    Рис. 8.4. Трехфазная Q-схема.

    Примем обозначения:

    Р - вероятность потери заявки (Р=N1/(N1+N3));

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

    tk,j - время окончания обслуживания заявки каналом Кк,j, k=1,2,3…; j=1,2…;

    zi, zk,j - состояния накопителей и каналов обслуживания;

    tn - текущее время моделирования;

    Li - ёмкость i-ого накопителя;

    Lkm - число каналов в к-ой фазе;

    N1, N­2 - число выходных заявок;

    Т - интервал моделирования;

    При имитации Q-схемы на ЭВМ требуется организовать массив состояний:

    zk,j, tk,j, j=1, Lkm; zi­ - число заявок в накопителе H; i=1,2; ti - i-ая заявка из источника.

    zk,j = {1- канал занят; 0 - канал свободен; 2 - заблокирован};

    Укрупнённая схема детерминированного МА Q-схемы, построенного по "принципу t" представлена на рисунке 8.5.

    Рис. 8.5. Блок схема моделирования Q-схемы по принципу "t".

    А далее более подробно рассмотрены алгоритмы блоков 4-9.

    1. Программные и технические средства моделирования систем.

      1. Моделирование систем и языки программирования.

    Большое значение при реализации модели на ЭВМ имеет вопрос правильного выбора языка программирования.

    Язык программирования должен отражать внутреннюю структуру понятий при описании широкого круга понятий. Высокий уровень языка моделирования значительно упрощает программирование моделей. Основными моментами при выборе ЯМ является:

    • проблемная ориентация;

    • возможности сбора, обработки, вывода результатов;

    • быстродействие;

    • простота отладки;

    • доступность восприятия.

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

    Более удобными являются ЯИМ. Они обеспечивают:

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

    • проблемная ориентация.

    Недостатки ЯИМ:

    • неэффективность рабочих программ;

    • сложность отладки;

    • недостаток документации.

    Основные функции языка программирования:

    • управление процессами (согласование системного и машинного времени);

    • управление ресурсами (выбор и распределение ограниченных средств описываемой системы).

    Как специализированные языки, ЯИМ обладают некоторыми программными свойствами и понятиями, которые не встречаются в ЯОН. К ним относятся:

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

    Размер. ЯИМ используют динамическое распределение памяти (компоненты модели системы М появляются в ОЗУ и исчезают в зависимости от текущего состояния. Эффективность моделирования достигается так же использованием блочных конструкций: блоков, подблоков и т.д.

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

    Взаимосвязь. Для отражения большого количества между компонентами модели в статике и динамике ЯИМ включаем системно организованные логические возможности и реализации теории множеств.

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

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

    Наиболее известными языками моделирования являются SIMULA, SIMSCRIPT, GPSS, SOL, CSL.

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

    Рис. 9.1. Классификация языков моделирования.

    Язык DYNAMO используется для решения разностных уравнений.

    Представление системы S в виде типовой схемы, в которой участвуют как дискретные, так и непрерывные величины, называются комбинированными. Предполагается, что в системе могут наступать события двух видов: 1) события, от состоянии Zi; 2) события, зависящие от времени t. При использовании языка GAPS на пользователь возлагается работа по составлению на яз. FORTRAN подпрограмм, в которых описываются условия наступления событий, законы изменения непрерывной величины, правил перехода из одного состояния в другое. SIMSCRIPT - язык событий, созданный на базе языка FORNRAN. Каждая модель Mj состоит из элементов, с которыми происходят события, представляющие собой последовательность формул, изменяющих состояние моделируемой системы с течением времени. Работа со списками, определяемые пользователем, последовательность событий в системном времени, работа с множествами. FORSIT - пакет ПП на языке FORNRAN позволяет оперировать только фиксированными массивами данных, описывающих объекты моделируемой системы. Удобен для описания систем с большим числом разнообразных ресурсов. Полное описание динамики модели можно получить с помощью ПП.

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

    GPSS- интегрирующая языковая система, применяющаяся для описания пространственного движения объектов. Такие динамические объекты в языке GPSS называются транзактами и представляют собой элементы потока. Транзакты "создаются" и "уничтожаются". Функцию каждого из них можно представить как движение через модель М с поочерёдным воздействием на её блоки. Функциональный аппарат языка образуют блоки, описывающие логику модели, сообщая транзактам, куда двигаться и что делать дальше. Данные для ЭВМ подготавливаются в виде пакета управляющих и определяющих карт, которым составляется по схеме модели, набранной из стандартных символов. Созданная программа GPSS, работая в режиме интерпретации, генерирует и передаёт транзакты из блока в блок. Каждый переход транзакта приписывается к определенному моменту системного времени.

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

    Баллы

    Возможности

    Простота применения

    Предпочтение пользователя

    5

    SIMULA

    GPSS

    SIMSCRIPT

    4

    SIMSCRIPT

    SIMSCRIPT

    GPSS

    3

    GPSS

    SIMULA

    SIMULA

    Суммарный бал:

    SIMULA -11

    SIMSCRIPT -13

    GPSS -12

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

    1. Язык программирования GPSS

    Этот язык с 1968 года входит в математическое обеспечение машин фирмы IBM, один из наиболее популярных языков ИМ.

    Общие сведения.

    GPSS составлен из объектов и операций (логических правил). Объекты делятся на семь классов:

    • динамические (ДО);

    • аппаратно-ориентированные (АО);

    • статические (СО);

    • операционные (ОО);

    • вычислительные (ВО);

    • запоминающие (ЗО);

    • группирующие (ГО).

    До — элементы потока обслуживания заявки или "транзакты". Они создаются и уничтожаются, с каждым транзактом может быть связано некоторое число "параметров"

    АО — соответствуют элементам оборудования, которые управляются ДО.

    К ним относятся:

    • накопители;

    • устройства;

    • логические переключатели.

    СО:

    • очереди;

    • таблицы.

    ЗО:

    ячейки;

    матрицы ячеек.

    ГО:

    • группы;

    • списки.

    ВО:

    • арифметические и булевы переменные;

    • функции.

    Каждой очереди соответствует перечень транзактов, задержанных ы какой-либо точке системы и запись длительности этих задержек: Tз={iз}.

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

    ОО - блоки – формируют логику системы, давая транзактам указания, куда идти дальше.

    Для того чтобы смоделировать систему, необходимо составить её описание в терминах GPSS, затем симулятор генерирует транзакты, продвигает через заданные блоки и выполняет действия соответствующие блокам. Продвижение создаёт блок GENERATE. Каждое продвижение транзакта является событием, которое должно произойти в определённый момент времени. Симулятор регистрирует время наступления каждого события, затем производит обработку событий в правильной хронологической последовательности.

    Если транзакты заблокированы, то симулятор продвинет их тогда, когда изменятся блокирующие правила. Симулятор моделирует часы, их показания в любой момент времени называют абсолютным временем. Относительное время показывает текущее время в модели. При помощи специальной операции относительное время может устанавливаться в нуль и последующий счёт времени будет производиться от этой точки. Другой операцией в нуль могут устанавливаться оба значения времени. Все времена в модели изображаются целыми числами. Симулятор рассчитывает схему по принципу ближайшего события. Центральной задачей симулятора является просмотр и проверка всех возможных событий. Транзакты входят в цепи. Существует пять видов цепей:

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

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

    3. Цепь прерванных событий.

    4. Цепь парных транзактов – в текущий момент времени имеют статус парности (ожидают прибытия синхронизирующих транзактов).

    5. Цепь пользователя включает транзакты, которые пользователь удалили из цепи текущих транзактов.

    Цепь текущих событий организуется в порядке убывания приоритетов транзактов и в порядке очерёдности поступления.

    В зависимости от различных условий и требований пользователь система помещает транзакты в те или иные цепи.

    Программа на GPSS создаётся в текстовом редакторе в определённом формате. Формат ввода содержит 3 различные поля: поле метки (позиции 5-9), поле операции (позиции 13-23) и поле переменных (позиции 26-80). Поле переменных содержит подполя, которые обозначены A, B, C, D, …,H. Последующие отделяются от предыдущих запятыми. Пропущенное значение в поле переменных выделяется запятыми (кроме конца поля).

    Каждый из объектов требует определённого числа ячеек ОЗУ, в которых во время моделирования хранятся атрибуты объекта (АТО). АТО, к которым может обращаться программист, называются стандартными числовыми атрибутами (СЧА). Все СЧА имеют одно- или 2-х буквенные мнемонические обозначения. Мнемонические обозначения указывают на тип СЧА, а целочисленное значение – на конкретный СЧА.

    Номера блоков можно определять символическими обозначениями. При этом обозначение должно включать от 3-х до 5-ти знаков, отличных от пробела, первые три из которых должны быть буквами. Эти ограничения необходимы для того, чтобы избежать смешивания атрибутов системы и символов. Дополнительным ограничением является недопустимость таких специальных знаков, как "–", "+", " " и т.д.

    Если в полях А, В, С блока представлены стандартные числовые атрибуты Nj или Wj, то необходимо, чтобы номер блока был представлен в качестве аргумента. Если этот номер блока определяется символически, то такое представление должно быть отличным от мнемонических обозначений, указанных СЧА (N или W). В префикса символического имени используется знак доллара $. Пользователь может относительную адресацию. В символической записи CROSSn символ CROSS указывает на нужный блок, а число n–на номер блока, отсчитываемого от номера блока CROSS. При косвенной адресации предполагается, что нужный аргумент представлен некоторым параметром. Последний обозначается *, за которой следует целое число. Например, S*10 соответствует текущему значению накопителя, номер которого задан параметром 10 (буква S - означает накопитель). Косвенная адресация неприменима только для СЧА С1, М1, RNn.

      1. Аппаратно - ориентированные блоки.

    К группе АО - блоков относятся:

    SEIZE - блок занятия прибора;

    RELEASE - освобождение прибора;

    PREEMT - захват устройства;

    RETURN - возврат захваченного прибора старому транзакту;

    ENTER - вход в устройство (накопитель);

    LEAVE - выход из накопитель;

    LOGIG - изменение логических переключателей.

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

    Для управления ключами используется оператор LOGIG. Предусмотрено три режима изменения состояния ключа: сброс в "0", установка в "1", инвертированное изменение состояния ключа на противоположное.

      1. Динамически - ориентированные блоки.

    В процесс моделирования транзакты создаются, порождают другие транзакты, собираются и уничтожаются. Каждому сообщению соответствует набор параметров, количество которых может быть установлено до 100. По умолчанию количество параметров принимается равным 12. Сообщениям можно присваивать приоритет от 0 до 127. По умолчанию приоритет равен 0. С динамической категорией объектов связаны блоки, которые можно разделить на пять групп: задержки, создания и уничтожения, изменения маршрутов, синхронизация, изменения атрибутов сообщений.

    Группы: задержки: ADVANCE ;

    создания: GENERATE;

    уничтожения: TERMINATE, SPLIT, ASSEMBLE;

    изменения маршрутов: TRANSFER, LOOP, GATE, TEST;

    синхронизации: MATCH, GATHER;

    изменения атрибутов сообщений: ASSIGN, INDEX, MARK, PRIORITY.

    Функции блоков:

    ADVANCE - задержка транзактов;

    GENERATE - генерации;

    TERMINATE - уничтожения;

    SPLIT - расщепления;

    ASSEMBLE - соединения;

    TRANSFER - передачи;

    LOOP -организации цикла;

    GATE - проверка состояния;

    TEST - сравнения атрибутов;

    MATCH - синхронизации;

    GATHER - сбора;

    ASSIGN - изменений значений параметров;

    INDEX - увеличение индекса;

    MARK - ;

    PRIORITY - изменение приоритета;

      1. Вычислительная категория

    В вычислительной категории используются объекты 3-х видов: арифметические, логические, и функции. Арифметические объекты описываются блоком variable в режиме целых чисел и FVARIABLE в режиме с плавающей точкой. Название карты описывают арифметические действия над СЧА. Аргументы и результаты рассматриваются как целые числа. При вычислении используются операции: +, –, *, / (с отбрасыванием остатка, d - деление по модулю (остаток считается положительным ). Допускается использование не более 5-ти скобок.

    FVARIABLE - описывает арифметические сочетания различных СЧА, вычисляемых в режиме с плавающей запятой. От аргументов и промежуточных результатов не берётся целая часть, а только от конечного результата.

    Блок - BVARIABLE - логическое высказывание, состоящее из некоторой совокупности СЧА и логических атрибутов. При вычислении используется 3 типа операторов: логические, условные и булевы, например, 2 BVARIABLE М1 'LE' P6.

    Функции описываются с помощью блока FUNCTION в виде совокупности диапазонов, например:

    3 FUNCTION RN1,C5

    0,0/.35,11/.42,1.7/.75,2.2/1.0,3.8

      1. Статическая категория

    К ней относятся блоки:

    QUEUE - для занятия очереди;

    DEPART - для освобождения из очереди;

    TABULATE - для регистрации частоты попадания заданного СЧА;

    TABLE - для вывода характеристик таблицы;

    SAVEVALUE - для сохранения информации в специальных ячейках ОЗУ;

    MSAVEVALUE - для сохранения информации в ячейках ОЗУ;

    MATRIX - для описания матрицы;

    INITIAL - для присвоения ячейкам и матрицам начальных значений.

      1. Группирующая категория

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

      1. Специальные типы блоков

    Они используются для составления сложных моделей. К ним относятся блоки вывода статистики (PRINT, TRACE, UNTRACE), изменения модели (EXECUTE, CHANGE) блоки BUFFER и HELP, а так же блоки управления группами транзактов (JOIN, REMOVE, EXAMINE, SCAN, ALTER).

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

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

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

    REMOVE - обратная функция JOIN.

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

    SCAN - для анализа получения значений атрибутов транзактов и изменения их пути.

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

      1. Примеры решения задач моделирования на GPSS

    Пример 1. Моделирование непрерывной случайной величины распределённой по экспоненциальному закону с = 0.1.

    10 SIMULATE

    20 EXPON FUNCTION RN1, C24

    30 0.0/.1,.104/.2,.222/.3,.365/.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/.995,6.2/.999,7.01.9997,8.0

    40 GENERATE 10,FN$EXPON

    50 MARK1

    60 TABULATE XTIME

    70 TERMINATE 1

    80 XTIME TABLE P1,0,2,100

    90 START 200

    100 END

    Модель включает 4 блока, выполняющие следующие функции:

    40 - генерирование транзакта;

    50 - присвоение параметру 1 транзакта значения, равного текущему значению часового времени;

    60 - уничтожение транзакта;

    10 - признак, необходимый для прогона модели;

    20 - описание функции (EXPON - метка, RN1 - генератор случайной функции, число пар координат-24);

    30 - задание значений пар координат функции;

    80 - определение таблицы; XTIME - метка, табулируемой величиной является Р1 значение параметров последовательных транзактов, верхний предел первого интервала равен 0, ширина интервала - 2, общее число интервалов - 100;

    90 - признак ввода данных, необходимый для выполнения моделирования; прогон модели должен завершится после прохождения через неё 200 транзактов;

    100 - признак конца программы.

    Пример 2. Составить модель композиции двух случайных величин X1 и X2 имеющих экспоненциальные распределения с параметрами 1 и 2 (Х= X1 + X2), удовлетворяющих обобщённому закону Эрланга 1-ого порядка: g(t)= 12(e-1- e-2)/(1­-2).

    Рис. 10.1. К задаче моделирования композиции 2-х случайных величин.

    10 SIMULAT

    20 EXPON FUNCTION RN1, C24

    30 0.0/.1,.104/.2,.222/.3,.365/.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/.995,6.2/.999,7.01.9997,8.0


    40 GENERATE 0,0,,1

    50 ASSIGN 1,K500

    60 INPUT ADVANCE 10,FN$EXPON

    70 ADVANCE 20, FN$EXPON

    80 TABULATE XTIME

    90 LOOP 1,INPUT

    100 TERMINATE 1

    110 XTIME TABLE M1,0,5,100

    120 START 1

    130 END.

    Функции блоков:

    40 - генерирование 1-ого транзакта в момент времени t=0;

    50 - присвоение параметру 1 значения, равного 500;

    60 - моделирование экспоненциального распределённых временных интервалов с параметром 1;

    70 - моделирование экспоненциального распределённых временных интервалов с параметром 2;

    80 - формирование таблиц частот XTIME для суммарных интервалов;

    90 - контроль числа прохождений транзактов через сегмент блоков, начинающийся с блока INPUT;

    100 - уничтожение транзакта.

    Пример 3. Моделирование однолинейной системы с пуассоновским входящим потоком с параметром = 0.1 1/сек. И экспоненциальным временем обслуживания с параметром = 0.2 1/сек.

    10 SIMULATE

    20 LINE EQU 1

    30 EXPON FUNCTION RN1,C24

    40 0.0/.1,.104/.2,.222/.3,.365/.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/.995,6.2/.999,7.01.9997,8.0

    50 GENERATE 10, FN$EXPON

    60 ASSIGN 1,LINE

    70 QUEUE O1

    80 SEIZE LINE

    90 DEPART O1

    100 ADVANCE 5,FN$EXPON

    110 RELEASE LINE

    120 TABULATE XTIME

    130 TERMINATE 1

    140 XTIME TABLE M1,0,10,100

    150 START 500

    160 END.

    9 блоков: 50 - генерирование транзактов;

    60 - назначение параметру 1 транзакта номера, соответствующего прибору LINE;

    70 - вхождение транзакта в очередь на прибор;

    80 - занятие прибора;

    90 - выход из очереди;

    100 - моделирование обслуживания;

    110 - освобождения прибора;

    120 - формирование таблицы частот XTIME для времени прохождения транзакта;

    130 - уничтожение транзакта;

    20 - назначение величины 1 переменной LINE.

    Пример 4. Моделирование работы однолинейной системы, имеющей 3 Пуассоновских потока требований с относительными приоритетами и параметрами 1=0.01 1/сек., 2=0.04 1/сек., 3=0.05 1/сек. Экспоненциальный закон обслуживания 1=0.2 1/сек.

    10 SIMULATE

    20 LINE EQU 1

    30 EX FUNCTION

    40 0.0/.1,.104/.2,.222/.3,.365/.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/.995,6.2/.999,7.01.9997,8.0

    50 GENERATE 100, FN$EX,,,3

    60 TRANSFER ,INPUT

    70 GENERATE 25, FN$EX,,,2

    80 TRANSFER ,INPUT

    90 GENERATE 20, FN$EX,,,1

    100 INPUT ASSIGN 1,LINE

    110 QUEUE LINE

    120 SEIZE LINE

    130 DEPART LINE

    140 ADVANCE 5,FN$EX

    150 RELEASE LINE

    160 TERMINATE 1

    170 START 1000

    60, 80 - безусловная передача транзактов;

    50, 70, 90 - генерирование транзактов с приоритетами 3, 2, 1.

    1. Планирование машинных экспериментов с моделями систем.

      1. Методы планирования эксперимента на модели.

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

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

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

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

    Рассмотрим основные понятия теории планирования эксперимента. В планировании эксперимента различают входные (изогенные) и выходные (эндогенные) переменные: х1, х2,…, хк; y1, y2…, ye. Входные переменные в ТПЭ называют факторами а выходные — реакциями. Каждый фактор xi, i=1,2,…,k может принимать в эксперименте одно или несколько значений, называемых уровнями. Фиксированный набор уровней факторов определяет одно из возможных состояний рассматриваемой системы. Одновременно этот набор представляет собой условия проведения одного из возможных экспериментов.

    Каждому фиксированному набору уровню факторов соответствует определённая точка в многомерном пространстве, называемая факторным пространством. Эксперименты не могут быть реализованы во всех точках факторного пространства, а лишь в принадлежащих допустимой области, как это например оказано для случая двух факторов Х1 и Х2 на рисунке (см. ниже рис. 11.1.).

    Рис. 11.1. Геометрическое представление поверхности реакции.

    Реакцию (отклик) системы можно представить в виде зависимости: yl=l(x1, x2,…,xk); e=1…m. Функцию e, связанную с факторами, называют функцией отклика, а её геометрический образ – поверхностью отклика. Исследователь заранее не известен вид зависимостей l, l=1…m, поэтому используют приближение соотношения:

    Зависимость и l находятся по данным эксперимента. Последний необходимо поставить так, чтобы при минимальных затратах ресурсов (числе испытаний), варьируя выходные значения по специально сформулированным правилам, построить математическую модель системы и оценить её характеристики. Факторы при проведении эксперимента могут быть управляемыми и неуправляемыми, количественными или качественными, фиксированными и случайными. Фактор относится к изучаемым, если он включён в модель для изучения свойств системы. Количественными факторами являются интенсивности входящих потоков заявок, интенсивности потоков обслуживания, ёмкости накопителей, количество обслуживающих каналов и другие. Качественным факторам не соответствует числовая шкала (дисциплины постановки на очередь, обслуживание каналов и другие).

    Фактор является управляемым, если его уровни целенаправленно выбираются экспериментатором.

    При планировании эксперимента обычно изменяются несколько факторов.

    Основными требованиями, предъявляемыми к факторам - независимость и совместимость. Совместимость означает, что все комбинации факторов осуществимы.

    Для выбора конкретной модели планирования эксперимента необходимо сформулировать такие её особенности, как адекватность, содержательность, простота.

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

    Предполагаем, что изучается влияние К количественных факторов хi на некоторую в отведённый для экспериментирования локальной области факторного пространства ограниченного хi min—xi max, i=1…k.

    Функцию отклика обычно выбирают линейной или квадратичной.

    (1)

    где вектор с элементами , входящих в исходный полином; - вектор коэффициентов. Для двух факторов имеем: f0=1, f1=x1, f2=x2, f12=x1x2, f11=x12, f22=x22. (b0,b1,b2,b12,b11,b22).

    Так как полином (1) содержит d коэффициентов, то план эксперимента должен содержать Nd различных экспериментальных точек:

    где xin­ - значение, которое принимает i-ая переменная в u-ом испытании. i=1…k, u=1...N. Матрица D называется планом эксперимента.

    Реализовав испытания в N очках области факторного пространства, определённом планом эксперимента, получим вектор наблюдений имеющий следующий вид:

    где yu - реакция соответствующей u-ой точке плана.

    Плану эксперимента поставим в соответствие матрицу планирования:

    где fil, fijl - координатные функции при соответствующих коэффициентах модели, в l - ом эксперименте.

    Построению плана эксперимента предшествует проведение ряда неформализованных действий (принятия решения) направленных на выбор локальной области факторного пространства G.

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

    После определения области G необходимо найти нулевые (основные) уровни факторов и интервалы варьирования xi, i=1…k.

    Эксперимент, в котором реализуются все возможные сочетания уровней факторов, называется полным факторным экспериментом (ПЭФ). Если выбранная модель включает только линейные члены полинома и их произведения, то для оценки коэффициентов модели используется ПЭ с варьированием всех k факторов на двух уровнях, т.е. q=2. Такие планы называются планы типа 2k, где n=2k- число всех возможных испытаний.

    Начальным этапом ПЭ для получения коэффициентов линейной модели основан на варьировании факторов на двух уровнях: нижнем xiн и верхнем xiв, симметрично расположенных относительно основного уровня xi0, i=1…k. Геометрическая интерпретация показана ниже на рис. 11.2.:

    Рис. 11.2. ПЭФ типа 22.

    Для упрощения записи условий каждого эксперимента факторы кодируют в виде безразмерных величин .Средний уровень кодированного фактора является нулём 0, граничные значения соответственно +1 и -1.

      1. Стратегическое планирование машинных экспериментов с моделями систем

    Можно выделить стратегическое и тактическое ПЭ на моделях систем.

    Стратегическое планирование – ставит своей целью получение необходимой информации о системе S с помощью модели MM, реализованной на ЭВМ. Оно аналогично внешнему проектированию при создании системы S.

    Тактическое планирование – определяет способы проведения каждой серии испытаний машинной модели MM. Оно аналогично внутреннему проектированию системы S.

    Рассмотрим элементы стратегического планирования ПЭ. Его целью может быть:

    1. Получение функции реакции системы от независимых фактов: y=f(b0,b1…,x1,x2,…xk)

    2. Нахождение экстремума: f(b0,b1…,x1,x2,…xk).

    Во 2-ом случае для определения наилучшей комбинации фактов могут быть использованы методы систематической или случайной выборки.

    К систематическим относятся методы:

    • одного фактора;

    • предельного анализа;

    • наискорейшего спуска;

    • равномерной сетки.

    Проблемой является большое количество факторов. Для k=10 ПЭФ должен состоять из 1024 точек. Используют неполные планы, метод "поверхности реакции".

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

    Другой проблемой является стохастическая сходимость результатов ПЭ. В качестве результатов ПЭ используется средние некоторых распределений, для оценки которых применяют выборочные средние, найденные путём многократны прогонов модели на ЭВМ. Сходимость выборочных средних с ростом объема выборки называется стохастической. Эта сходимость, как правило, медленная. Если - стандартное отклонение среднего N наблюдений будет равно /, т.е. для уменьшения случайной выборки в k раз требуется увеличить объем выборки в k2 раз.

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

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

    1. построение структурной модели;

    2. построение функциональной модели.

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

    Ортогональное распределение плана упрощает определение коэффициентов аппроксимации. Упрощение дает принятие числа уровней всех факторов одинаковыми (не больше 3). Функциональная модель ПЭ определяет количество элементов структурной модели Nф, т.е. необходимое число различных информационных точек Nф. Причём Nфс, где Nс=q1,q2…qkчисло экспериментов ПФЭ.

      1. Тактическое планирование машинных экспериментов с моделями систем

    Здесь решают проблемы:

    • определения начальных условий и их влияния на достижения установившегося результата при моделировании;

    • обеспечения точности и достоверности результатов моделирования;

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

    • выбора правил автоматической остановки имитационного эксперимента с моделями.

    Рассмотрим ПФЭ типа 23:

    номер испытания

    1

    2

    3

    4

    5

    6

    7

    8

    -1

    -1

    -1

    -1

    +1

    +1

    +1

    +1

    -1

    -1

    +1

    +1

    -1

    -1

    +1

    +1

    -1

    +1

    -1

    -1

    -1

    +1

    -1

    +1

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

    Для оценки свободного члена b0 и определения эффектов взаимодействия b12, b13, …,b123план эксперимента D расширяют до матрицы планирования X путём добавления соответствующей фиктивной переменной: единичного столбца и столбцов произведений как показано, например, для ПЭФ типа 23 в таблице (см. ниже):

    Номер испытания

    План ПЭФ

    Реакция y








    1

    +1

    +1

    +1

    +1

    +

    +

    +

    +

    y1

    2

    +1

    1

    +1

    +1

    +

    y2

    3

    +1

    +1

    1

    +1

    +

    y3

    4

    +1

    1

    1

    +1

    +

    +

    y4

    5

    +1

    +1

    +1

    1

    +

    y5

    6

    +1

    1

    +1

    1

    +

    +

    y6

    7

    +1

    +1

    1

    1

    +

    +

    y7

    8

    +1

    1

    1

    1

    +

    +

    +

    y8

    Как видно из рассмотренных ПЭ типа 22 b 23 количество испытаний ПЭФ значительно превосходит число определяемых коэффициентов линейной модели плана эксперимента, что увеличивает расход ресурсов ЭВМ по времени. Возникает проблема сокращения количества экспериментов.

    С этой целью рассмотрим построение планов так называемого дробного факторного эксперимента (ДФЭ). Пусть имеется ПЭФ типа 22. Используя матрицу планирования X, например приведённую в предыдущей таблице, можно вычислить коэффициенты и предусмотреть результаты в виде уравнения:

    N/n

    План ПЭФ


    Отклик y





    1

    1

    +1

    +1

    +1

    y1

    2

    1

    1

    +1

    1

    y2

    3

    1

    +1

    1

    1

    y3

    4

    1

    1

    1

    +1

    y4

    Если в выбранных интервалах варьирования уровня процесс можно описать линейной моделью, то достаточно определить три коэффициента b0, b1,b2. Т.о. остаётся одна степень свободы, которую можно использовать для построения плана эксперимента D для 3-х переменных, в которых уровни 3-его фактора изменяются как в таблице рассмотренной немного раньше для столбца (эффектов взаимодействия).

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

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

    При проведении эксперимента из 4-х испытаний для оценки влияния 3-х факторов пользуются половинный ПЭФ типа 23, так называемой "полу репликой". Если приравнять x3 и x1x2, что можно получить 2-ую "полу реплику".

    Для обозначения дробных реплик, в которых линейных эффектов приравнены к эффектам взаимодействия, пользуются условным обозначением 2k-. Например, "полу реплика" от 26 записывается в виде 26-1, а "четверть реплика" 26-2.

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

    Следует иметь в виду, что малый шаг варьирования x; (j=1…n) может повлечь статистическую не значимость оценки коэффициента уравнения регрессии. В случае, если полученная мат. модель окажется неадекватной, проводятся эксперименты с меньшим шагом варьирования.

    Если линейные модели, построенные с помощью ПЭФ и ДФЭ, неадекватны, то переходят к построению квадратичных моделей.

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


  • Случайные файлы

    Файл
    000-0001.DOC
    77637.doc
    138769.rtf
    163171.rtf
    72844.rtf




    Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
    Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
    Это можно сделать совершенно бесплатно. Читайте подробности тут.