Операторы управления движением заявок

Расширение возможностей управления движением транзактов достигается благодаря таким операторам, как LOGIC(рис. 8.15)иGATE (рис. 8.16). Оператор

LOGIC X А

при Х=S устанавливает переключатель А в единичное состояние, а при Х=К сбрасывает его в нулевое состояние.

Рис. 8.15. Обозначение блока LOGIC

Оператор

GATE XX А, В

при X = LR и А =1 или при X = LS и А = 0 передает транзакт оператору с меткой В (или задерживает его в блоке GАТЕ, если поле В пусто), а при других сочетаниях Х и А направляет к следующему оператору.

Рис. 8.16. Обозначение блока GATE

Вычислительный оператор VARIABLE

Вычислительный оператор

М VARIABLE А

присваивает переменной с номером М значение арифметического выражения А, например в операторе

3 VARIABLE К216-S$MEM2

переменной № 3 присваивается разность числа 216 и объема занятой памяти в накопителе МЕМ2.

Оператор синхронизации МАТСН

Оператор синхронизации (рис. 8.17), имеющий, например, вид

LBL МАТСН NUMB

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

NUMB МАТСН LBL

не войдет транзакт того же семейства.

Рис. 8.17. Обозначение блока MATCH

Пример программы на языке GPSS для СМО

Пример. Заказы, поступающие в СМО в случайные моменты времени в диапазоне [20, 40], выполняет сначала бригада BR1, затем параллельно работают бригады BR2 и BR3, каждая над своей частью заказа.

Заданы экспоненциальные законы для времен выполнения работ бригадами BR1, BR2 и BR3 с интенсивностями 0,05, 0,1 и 0,125 соответственно. Моделирование нужно выполнить на временном отрезке, соответствующем выполнению 1000 заказов.

В этом примере использован экспоненциальный закон распределения с плотностью

w(T) = λ ехр(- λТ),

где λ — интенсивность.

Функция распределения экспоненциального закона:

Рис. 8.18. Время выполнения работ распределено по экспоненциальному закону

Из рисунка 8.18 видно, что поскольку искомыми являются значения β случайной величины Т, то, задавая значение α как равномерно распределенной в диапазоне [0, 1] случайной величины, по формуле

находим искомое значение. Именно в соответствии с этой формулой в операторах ADVANCE (см. далее программу) множителями были значения 1/λ.

Программа к примеру СМО

SIMULATE

EXP FUNCTION RN1,С12 0,0/.2,.22//.4,.51/.5,.6/.6,.92/.7,1.2/.8,1.61/.9,2.3/.95,3/.99,4.6/.999,6.9/1,1000

GENERATE 30,10

SEIZE BR1

ADVANCE 20,FN$EXP

RELEASE BR1

SPLIT 1,МЕТ1

SEIZE BR2

ADVANCE 10,FN$EXP

RELEASE BR2

TRANSFER,MET2

МЕТ1 SEIZE BR3

ADVANCE 8,FN$EXP

RELEASE BR3

МЕТ2 ASSEMBLE 2

TERMINATE 1

START 1000„1000

END.

Вопросы к главе 8

1. Почему язык GPSS является ориентированным на процессы?
2. Напишите на языке GPSS модель системы, показанной на рис. 5.17 в виде сети Петри.
3. Опишите на языке GPSS модель системы, состоящей из двух станков, обрабатывающих детали с разными интенсивностями μ₁ и μ₂, если интенсивность поступления деталей в систему задана и равна λ.

ПЛАНИРОВАНИЕ КОМПЬЮТЕРНЫХ ЭКСПЕРИМЕНТОВ С МОДЕЛЯМИ СИСТЕМ

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

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

Наибольшее значение при планировании компьютерного эксперимента имеют следующие факторы: 1) простота воспроизведения на компьютере условий эксперимента с моделью исследуемой системы; 2) возможность управления экспериментом с моделью системы, включая его прерывание и возобновление; 3) удобство изменения условий проведения эксперимента, включая учет воздействия внешней среды; 4) наличие связи, или корреляции между отдельными значениями величин, вычисляемых в процессе моделирования; 5) определение временного интервала моделирования.

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

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

9.1. Основные понятия теории планирования экспериментов

В качестве модели эксперимента используется уже знакомая из параграфа 1.6.1 пособия учебника кибернетическая модель типа «черный ящик». В этой модели различают входные переменные x_i, i=1,…, k и выходные y_j, j=1,…, m. Каждая из переменных в проводимом эксперименте может быть либо фактором, либо реакцией – в зависимости от той роли, которая ей отводится. В компьютерных экспериментах факторявляется входной переменной, а реакция – выходной переменной.

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

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

Между уровнями факторов и реакцией системы существует связь, задаваемая соотношением

y_j=ψ_j(x₁,x₂,…x_k), j=1,…, m.

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

Вид зависимостей ψ_j, j=1,…, m исследователю заранее не известен, поэтому используются приближенные соотношения:

ỹ_j=φ_j(x₁,x₂,…x_k), j=1,…, m.

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

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

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

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

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

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

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

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

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

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

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

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

Для этого необходимо отобрать факторы х_i i =1,2,…,k, влияющие на искомую характеристику, и описать функциональную зависимость; установить диапазон изменения факторов [х_imin, х_imax]; определить координаты точек {х₁, х₂,…, х_k} факторного пространства, в которых следует проводить эксперимент; оценить необходимое число реализаций и их порядок в эксперименте.

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

Наиболее широкое применение для планирования нашли модели в виде алгебраических многочленов. Рассмотрим влияние k количественных факторов х_i i =1,2,…,k на некоторую реакцию в ограниченной [х_imin, х_imax], i=1,2,…,k по условию проведения эксперимента локальной области факторного пространства G. На рис. 9.1 показан случай для k = 2.

Пусть функция реакции ψ(x₁,x₂,…x_k) может быть представлена с некоторой степенью точности полиномом степени d от k переменных факторов:

причем этот полином включает коэффициентов, где – число сочетаний из k+d элементов по d.

Рис. 9.1. Поверхность реакции Ψ(x₁,x₂)

Иначе данный полином можно представить в виде:

где – вектор с компонентами , входящими в исходный полином; – вектор коэффициентов. Таким образом,

Если ввести фиктивные переменные x₀=1, а также

то можно записать функцию реакции в виде однородного линейного уравнения:

где

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

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

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

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

можно преобразовать к линейному виду путем введения фиктивных переменных x_ij=x_ix_j. В результате получается модель множественной линейной регрессии:

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

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

где x_ij – значения, которые принимает i-я переменная в j-м испытании,

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

где y_j – реакция, соответствующая j-й точке плана

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

где e_j – случайная ошибка испытания (шум, флуктуация), относительно которой действует предположение о нормальности распределения вероятности с нулевым математическим ожиданием M[e_j]=0 и постоянной дисперсией D[e_j]=σ_j²=const.

Совокупность аналогичных соотношений для всех точек плана получим матрицу планирования размерностью N×(k′+1):

Рассмотрим этапы планирования эксперимента для случая линейной аппроксимации поверхности реакции. Вначале выбирается локальная область факторного пространства G, в которой будет проводиться эксперимент. Для этого, исходя из свойств исследуемого объекта, определяют верхние и нижние границы каждого фактора x_{i min} и x_{i max}. Например, такой параметр, как коэффициент передачи разомкнутой системы управления, с одной стороны, не может быть нулевым (это означает разрыв цепи), а с другой стороны, не может быть равным, а тем более превышающим критическое значение, связанное с границей устойчивости системы. Подобные ограничения обычно существуют и для других переменных, участвующих в эксперименте, таких как температура, давление, напряжение, сила тока, перемещение, скорость, ускорение и т.п.

Затем определяется локальная подобласть планирования эксперимента путем выбора основного уровня x_i0 и интервалов варьирования Δx_i, i=1,…,k. В качестве исходной точки x_i0 выбирают точку, соответствующую наилучшим условиям, полученным с помощью анализа априорной информации о системе, причем эта точка не должна располагаться вблизи границ области определения факторов x_{i min} и x_{i max}. Интервалы варьирования Δx_i также не могут выбираться произвольно: снизу они ограничены величиной ошибки фиксирования уровня фактора, а сверху – условием, что и нижний, и верхний уровни фактора должны оставаться в пределах области определения G.

Далее в рамках выбранной модели планирования, представляющей собой алгебраические полиномы, строится план эксперимента путем варьирования каждого из факторов x_i, i=1,…,k на нескольких уровнях q относительно исходной точки x_i0, представляющей центр эксперимента.

9.3. Виды планов экспериментов

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

Планирование эксперимента для получения коэффициентов линейной модели начинают с варьирования факторов на нижнем и верхнем x_iв уровнях, которые расположены симметрично относительно основного уровня x_i0 , i=1,…, k (рис. 9.2).

Рис. 9.2. Геометрическая интерпретация ПФЭ вида 2²

С помощью масштабирования

где Δx_i=(x_iв–x_iн)/2– интервал варьирования фактора; x_i0 – нулевой (основной) уровень, x_i – натуральное значение фактора, масштабы по осям факторов приводятся к значениям: –1 для нижнего уровня, +1 для верхнего уровня и 0 для основного уровня (рис. 9.3).

Рис. 9.3. Геометрическая интерпретация ПФЭ вида 2² с учетом масштабирования по осям

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

Таблица 7

Номер испытания
	-1	+1	-1	+1
	-1	-1	+1	+1
Обозначения строк	(1)	a	b	ab

В таблице 7 использована сокращенная запись плана с помощью условных буквенных обозначений строк. При этом порядковым номерам факторов сопоставлены строчные буквы латинского алфавита: x₁→a, x₂→b, x₃→c и т.д. Для каждой строки плана выписаны латинские буквы только для факторов, находящихся на верхних уровнях. Испытание со всеми факторами, находящимися на нижних уровнях, обозначено как (1). Запись плана в буквенных обозначениях показана в последней строчке.

Для оценки свободного члена b₀ и определения эффектов взаимодействия b₀ план эксперимента D расширяется до матрицы планирования X путем добавления «фиктивной переменной», представленной единичным столбцом и столбцами произведений, как показано для ПФЭ вида 2² в таблице 8.

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

Пусть имеется простейший ПФЭ типа 2². Используя матрицу планирования, соответствующую таблице 8, можно вычислить коэффициенты b_i и представить результаты в виде уравнения

Таблица 8

Номер испытания		План ПФЭ		Реакция y
	+1	-1	-1	+1	y1
	+1	+1	-1	-1	y2
	+1	-1	+1	-1	y3
	+1	+1	+1	+1	y4

Если можно использовать линейную модель для описания процесса в пределах выбранных интервалов варьирования уровня, то достаточно определить всего три коэффициента уравнения: b₀ , b₁ и b₂. Таким образом, остается одна степень свободы, которую можно использовать для минимизации количества испытаний. При использовании линейной модели коэффициент b₁₂=0, так что вектор-столбец в таблице 8 может быть использован для нового фактора . При этом раздельных оценок, которые имели место в ПФЭ типа 2^k, уже не будет, и оценки сместятся:

При использовании линейной модели все парные взаимодействия не учитываются, поэтому, например, вместо восьми испытаний в ПФЭ типа 2³ необходимо провести только четыре испытания.

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

При проведении эксперимента из четырех испытаний для оценки влияния трех факторов пользуются половиной ПФЭ типа 2³, так называемой «полурепликой». Если приравнять x₃ и –x₁x₂, то можно получить вторую «полуреплику». Для обозначения дробных реплик, в которых d линейных эффектов приравнены к эффектам взаимодействия, пользуются условным обозначением 2^k–d. Например, «полуреплика» от 2⁶ записывается в виде 2^6–1, а «четвертьреплика» – в виде 2^6–2.

Пример. При построении «полуреплики» 2^3–1можно приравнять или . Соответствующие две «полуреплики» 2^3–1показаны в таблице 9. Произведение элементов соответствующих строк трех столбцов для первой из матриц этой таблицы равно +1, а для второй –1.

Таблица 9

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

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

При планировании экспериментов, кроме двухуровневых симметричных планов типа 2^k, используют также многоуровневые планы, в которых факторы варьируются на 3, 4, …, m-м уровнях и соответственно обозначаются как 3^k, 4^k, …, m^k-планы. Многоуровневые несимметричные планы, в которых факторы варьируются на различных уровнях, строятся различными способами: комбинированием полных и дробных факторных планов типа 2^k, методом преобразования симметричных планов в несимметричные и т.д. Такие планы называются планами регрессионного анализа для многофакторного эксперимента.

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

Вопросы к главе 9