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

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

N _набл – количество наблюдений, которое предполагается провести в ходе моделирования;

I _набл – текущее количество наблюдений, накапливаемое в ходе моделирования;

I _прог – текущее количество прогонов, накапливаемое в ходе моделирования;

К _набл – количество наблюдений в одном прогоне модели.

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

- дуга, задающая направление передачи управления;

- оператор;

- заголовок оператора CASE;

- условие;

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

- точка разрыва дуги;

- хранилище информации;

- вход в хранилище для записи или чтения данных и выход из него.

Блок-схема изображена на рис.3. Дадим краткие пояснения.

В блок схеме в целом выделим два глобальных цикла:

· цикл по прогонам модели. На каждом щаге этого цикла из данного прогона выделяют K _набл наблюдений. Предполагается, что общее требуемое число наблюдений N _набл задано. Цикл заканчивается, если реальное число наблюдений равно или превышает N _набл. Возможны более сложные условия окончания этого цикла, например, по достижении заданной точности расчета среднего значения какой-либо наблюдаемой переменной;

· цикл, в котором последовательно (по шагам) формируется один прогон модели. Этот цикл вложен в предыдущий.

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

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

Пусть, например, закон распределения времени обслуживания одного клиента является асимметричным "колоколообразным" бета-распределением с медианой m_b и пределами изменения значений случайной переменной [ a, b ], причем выполняется условие: m_b «(a + b)/2. Последнее обусловливает наличие длинного "хвоста" в распределении (см. рис.4):

Начало цикла по прогонам

Начало основного цикла: формирования

одного (очередного) прогона модели

0:

1, 2:

Окончание шага цикла формирования прогона модели

Окончание шага цикла по числу наблюдений

Рис.3. Блок схема имитационной модели двухканальной СМО.

f (t _об)

|

a m_b b t _об

Рис.4.

Пусть мы оцениваем время обслуживания одного клиента на уровне медианы. Тогда, если в банке к моменту прибытия очередного клиента находится L клиентов, то очередного клиента можно допустить в банк, если (L × m_b / N _касс) £ (t _ост - m_b), где t _ост – остаток времени работы банка до окончания рабочего дня, N _касс – число кассиров в банке.

Однако при таком решении (если удлинение рабочего дня не допускается) для последнего клиента велика вероятность напрасно потерять время. Более того, при наличии длинной очереди внутри банка такому риску могут подвергаться несколько клиентов.

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

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

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

В блоках обработки основных событий разных типов (см. различные ветви оператора CASE) необходимо предусмотреть вызов алгоритмов определения моментов реализации различных случайных событий. Кроме того, необходимо предусмотреть занесение в ХРАНИЛИЩЕ-1 всех данных, необходимых для определения значений наблюдаемых переменных.

Следует учитывать, что ХРАНИЛИЩЕ-1 должно размещаться в оперативной памяти ЭВМ. Размещение его на внешних носителях может чрезвычайно увеличить затраты машинного времени на моделирование. Если размещение ХРАНИЛИЩА-1 на внешних носителях неизбежно, то для передачи данных в него следует использовать буферизацию и/или параллельные процессы.

В конце каждого шага цикла по прогонам должна быть предусмотрена передача данных в ХРАНИЛИЩЕ-2 и очистка ХРАНИЛИЩА-1.

Для того, чтобы быть удобным в работе (в блоке статистической обработки результатов наблюдений), ХРАНИЛИЩЕ-1 должно быть хорошо структурированным. Этот вопрос в общем случае нетривиален. Фактически ему присущи проблемы, характерные для формирования базы данных, в том числе вопросы выбора числа различных таблиц и организации взаимосвязи между ними. Простейший путь – размещать все данные в единой таблице – может привести к очень сложной таблице, которую будет трудно обрабатывать в блоке статистической обработки результатов наблюдений. Чрезмерная детализация потребует больше памяти и породит задачу организации связи между таблицами. В качестве простейшего принципа структурирования можно принять, например, следующий: в хранилище организуется столько динамических таблиц, сколько типов основных событий учитывается в модели (в рассматриваемом примере – три).

Другой простейший принцип организации ХРАНИЛИЩА-1 – это организация таблиц, соответствующих отдельным типам объектов, входящих в моделируемую систему.

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

Пусть организованы таблицы 3 и 4.

Таблица 3

Таблица клиентов (упорядочена в порядке прибытия клиентов в банк)

К кл, № клиента п/п	k 1, признак обсл. клиента	t 1, приход кл. в банк	t 2, начало обсл.	t 3, окончан. обсл.	i, номер кассира	k 2, признак перех. клиента из оч. в оч.
		t	t	t
		t	t	t
		-	-	-	-	-
		t	t	t
		t	t	t
..............................................................
N кл - 1		-	-	-	-	-
N кл		t	t	t

Таблица 4

Таблица кассиров (хронологически упорядочена)

Момент времени	i, номер кассира	Тип момента времени (-1 – переход в сост отдыха; 0 – переход в сост. "готовность"; 1 – переход в сост "обслуживание")
t
t
t
t		-1
...................................................
t
t		-1

В этих двух таблицах размещена практически вся информация, которая может быть получена о системе в рамках построенной модели. Однако, полнота таблиц не означает, что любая интересующая нас наблюдаемая переменная может быть получена из таблиц "элементарно". Возможно, для этого понадобится нетривиальная их обработка – при передаче информации их ХРАНИЛИЩА-1 в ХРАНИЛИЩЕ-2 после каждого прогона.

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

· количество клиентов, обслуженных за рабочий день;

· среднее время пребывания клиента в банке;

· среднее время обслуживания клиента;

· средняя длина очереди в банке;

· доля времени, когда очередь имела максимальную длину;

· количество клиентов, которым отказано в обслуживании в течение одного рабочего дня;

· количество клиентов, обслуженных первым кассиром;

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

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

Рассмотрим, например, как можно определить среднюю длину очереди в банке.

Для этого вначале построим зависимость L (t). Перенесем из таблицы клиентов во вспомогательную таблицу моменты "приход клиента в банк" и "окончание обслуживания клиента" и хронологически упорядочим эту таблицу. Пусть все моменты вытянуты в строку. Если первый из моментов не равен нулю, то дополним эту строку нулевым моментом – начало рабочего дня. Вторая строка пусть содержит признак типа момента времени (1 – приход, 2 – окончание обслуживания).

Дополним вспомогательную таблицу еще одной строкой, в которой будем помещать значения функции L (t), причем значение будем понимать, как "предел справа". Таким образом, вспомогательная строка будет иметь вид (случай, когда нулевой момент времени внесен в таблицу принудительно):

Таблица 5

	t 1	t 2	t 3	t 4	t 5	t 6	t 7	...
-								...
L (0)	L (t 1)	L (t 2)	L (t 3)	L (t 4)	L (t 3)	L (t 4)	L (t 5)	...

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

· если нулевой момент времени вносился в таблицу принудительно, то L (0):= 0, иначе L (0):= 1;

· далее организуем цикл перебора столбцов таблицы и на каждом k -м шаге выполняем оператор: если k -й момент времени – момент прихода, то L (t_k):= L (t_{k -1}) + 1, в противном случае L (t_k):= L (t_{k -1}) - 1.

После выполнения этого алгоритма таблица 5 примет вид:

Таблица 5а

	t 1	t 2	t 3	t 4	t 5	t 6	t 7	...
-								...
								...

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

Выше предполагалось, что обработка данных, размещенных в ХРАНИЛИЩЕ-1 и передача результатов обработки в ХРАНИЛИЩЕ-2 ведется после каждого прогона модели. Однако, следует также учитывать, что в сложных моделях при большом числе наблюдений потребная емкость ХРАНИЛИЩА-1 может оказаться неприемлемо большой. В этом случае может понадобится принципиально иная и существенно более сложная организация модели - немедленная обработка данных, получаемых на отдельных шагах цикла формирования прогона модели без запоминания этих данных.

Вопрос разбиения прогона модели на наблюдения уже обсуждался в п.1.6. Напомним, что при реализации метода повторений наблюдение совпадает с прогоном.

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

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

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

Простейший путь – создать единственный класс – инкапсулирующий все поля, свойства и методы, описывающий функционирование моделируемой системы в заданной внешней среде. (В рассматриваемом примере – это класс TBank).

При более сложной организации программы можно создать, например, двухуровневую иерархию классов: низший уровень – классы TClient и TKassir, высший – класс TBank, отдельные свойства которого относятся к типам TClient и TKassir.

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

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

О некоторых возможных усложнениях говорилось в п. 1.2.

Обязательными дополнительными усложнениями должны быть:

· использование отдельных способов понижения погрешностей выборочных оценок расчетных параметров (см. раздел 3 данных лекций);

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

Желательно придумать свою СМО (не банк) с соответствующими особенностями.

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

3. Способы понижения погрешностей выборочных оценок
расчетных параметров

Выше (п.1.6.1) уже приводилось расчетное соотношение для определения доверительного интервала для истинного (из генеральной совокупности) значения математического ожидания наблюдаемой переменной х - см. формулу (6) с учетом (5). Эта формула основана на том, что выборочное среднее наблюдаемой переменной является результатом усреднения значений переменной, " непосредственно " наблюдаемых в процессе имитационного эксперимента. Если эту исходную "расчетную установку (непосредственного наблюдения)" не менять, то уменьшения дисперсии среднего значения можно достичь только за счет увеличения числа наблюдений - n (или увеличения длительности прогона, если объектом наблюдения является процесс с существенной стационарной фазой).

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

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

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

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

Рассмотрим некоторые из таких методов[9]. Однако предварительно напомним некоторые понятия из теории случайных процессов (или более узко – случайных временных рядов), применяемые в теории имитационного моделирования. В частности, основываясь на этих понятиях, поясним приведенные выше соотношения для оценок дисперсии s_x наблюдаемой величины х (см., например, формулу (5)), которые используются в формулах для определения доверительного интервала.

Пусть наблюдается последовательность значений х ₁, х _2, … случайной величины х. Для рассматриваемого примера это могут быть, например, значения длины L очереди, оцениваемые в отдельных наблюдениях.

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

При такой интерпретации выборочное среднее величины х определяется как среднее значение случайных значений величин x_i, i =1,…, n:

(11)

В теории вероятностей доказано, что такая оценка является несмещенной.

Истинная (по генеральной совокупности) дисперсия величины х при условии, что она определяется как сумма n случайных величин, то есть как зависящая от других случайная переменная:

x = (x ₁ + x ₂ + … + x_n)/ n, (12)

определяется соотношением:

. (13)

Величина ковариации определяется характером взаимозависимостей величин x ₁, x ₂, …, x_n. Следовательно, специальным выбором этих величин можно сделать ковариацию нулевой или даже отрицательной и тем самым уменьшить дисперсию наблюдаемой зависимой переменной.

Фактически выше (п.1.6) эта идея уже была реализована.

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

С другой стороны, в методе интервалов значения наблюдаемой переменной, соответствующие различным наблюдениям, в силу специфики организации имитационного эксперимента, зависимы. Это приводит к необходимости учета ковариаций в формуле для расчета дисперсии – формула (7). При этом, как правило, корреляция соседних переменных x_i и x_{i +1} положительна, что приводит к положительным ковариациям и, соответственно, к увеличению дисперсии наблюдаемой переменной х.

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

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

Дата добавления: 2014-01-11