GPSS / Simulation

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	61

2.Однородность потока запросов. В моделях, основанных на СеМО все ДО заменяются на дисциплину в порядке поступления (FIFO).

3.Невозможность отображения одновременной занятости (блокировки) нескольких узлов одной заявкой.

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

Например, для узла общего типа G/G/1 среднее время ожидания находится в пределах:

ρ 2ν 2	ρ ρ 2		w	ν 2	ν 2ρ 2
b				a	b	,	(63)
2λ 1 ρ				2λ 1 ρ

где a и b — интервал времени между поступлениями заявок и среднее время обслуживания соответственно.

В целом, в двух- - трехфазных моделях неэкспоненциальность одного из узлов приводит к погрешностям, не превышающим 4%.

Для отображения блокировки приборов соответствующие узлы заменяются толерантным,

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

Что касается неоднородности, отметим, что в настоящее время разработаны выражения для частных случаев неоднородных потоков в СеМО, а также доказано, что теорема Нортона

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

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	62

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

Мы рассмотрели подход к аналитическому и имитационному моделированию,

основанный на применении марковских процессов и СеМО.

Другим направлением является сетевое представление моделей объектов управления и их анализ с помощью методов теории графов и сетей и ее расширений.

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

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

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

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

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

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

Элементы сетей.

Идея метода временнóго моделирования заключается в

реализации принципа распространения волны в некоторой среде.

Средой в данном случае является исследуемая сеть.

В теории данного метода используется ряд понятий.

Рис. 49. Сетевой график

f aij ,

Определим понятие функции ветви

где aij A :

технологического процесса.

1, если T

T

t

ij

T

xi

f aij

T

t

,

(64)

0, если T

ij

T

xi

где TТ — текущее значение времени моделирования сети, при условии, что T0 = 0 (начало

моделирования); Txi —момент выполнения функции xi -го узла сети; tij dij

tД , где dij —

весовые коэффициенты ветвей, tД — дискрет времени (секунда, минута и т.п.).

Множество A aij можно разделить на 2 подмножества: ветви, входящие в xi-й узел, —

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

	Е.В.Малахов. Имитационное моделирование. Конспект лекций.		63
	n	n
mi	и ветви, выходящие из него, — mi . При этом mi mi A , где n —число узлов в сети.
	i 1	i 1

В связи с тем, что ветвям и узлам присваиваются весовые козффициенты и функции,

очевидно, что существуют входная и выходная функции узлов.Входная функция FВХ(xj) зависит от функций ветвей, входящих в этот узел:

F	x				n	f a			(65)
		j		F			ij
ВХ				j
				i 1
Выходная функция FВЫХ(xj) определяется значением входной функции и весового
коэффициента dxj узла xj:
FВЫХ x j F FВХ x j , dxj									(66)

В большинстве случаев узлы моделируемых сетей имеют коэффициенты равные нулю

(dxj = 0). Для таких сетей входная и выходная функции совпадают и рассматриваются как единая функция узла

F x j FВХ x j FВыХ x j

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

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

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

К однородным сетям относятся конъюнктивные сети, для которых

n	,
F x f aij		(67)
i 1
и дизъюнктивные, где
n	,
F x f aij		(68)
i 1

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

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

во-вторых,от значений функций ветвей,составляющих этот путь.

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

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	64

С другой стороны, значение функции узла F(xj) зависит от значений функций ветвей f aij , входящих в этот узел. В свою очередь, значение функции узла зависит от весового коэффициента ветви dij, который моделируется продолжительностью прохождения волнового сигнала по ветви aij и определяет временную составляющую функции ветви tij.

Определим еще одну функцию — функцию состояния ветви fС aij :

0 , при Tx0 TT Txi

f

a

T

t , при T

T

T

t

T

(69)

С

ij

T

xi

ij

xi

T

xi

ij

1 , при Txi

tij TT

TM

где Tx0 — время выполнения функции начального узла сети (момент начала моделирования сети); TТ — текущее время моделирования сети; Txi — время выполнения функции начального узла ветви aij; tij dij t Д — время моделирования веса dij ветви aij с дискретом времени tД;

TМ — момент выполнения функций конечного узла сети (завершение моделирования сети).

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

выражение TT Txi tij или TT Txi dij t Д определяет длину той части ветви aij, которую уже прошел сигнал моделирования. Функция состояния обеспечивает переход функции ветви из нулевого в единичное состояние.

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

изменение значения функции ветви f(aij) из 0 в 1 в момент времени TT T xi tij ;

сохранение этого значения до момента TТ = Txj.

После TТ = Txj значения функций ветвей, входящих в узел xj не влияют на процесс моделирования. Из этого следует, что функции состояния ветвей достаточно рассматривать на фиксированных интервалах. Например, для ветви aij функцию fС aij рассматривать на отрезке

T 0 TT T xj .

Временнóе моделирование сетей.

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

общем случае mj ), выходящих из этого узла ветвей и выполнении операций с необходимым

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	65

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

Время, затрачиваемое на подготовку ветвей:

n
TП TПi	(70)

i 1

где TПi — время подготовки ветвей,выходящих из i-го узла. Формула справедлива для тех алгоритмов, для которых подготовка ветвей выполняется последовательно.

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

fС aij TT Txi dij t Д

Значения этой функции, которые будут находиться в интервале от 0 до 1, определяют

понятие "фронта распространения сигнала моделирования" или "фронта моделирования".

Фронт моделирования T			— это подмножество ветвей, для которых значение функции
		K
состояния fС aij в момент времени T0 TT TM лежит в интервале ]0;1[:
T aij		0 fС aij 1 , F xi 1 ппри T TK ,
K
где TТ — текущее время моделирования сети.
Время моделирования	весового			коэффициента	ветви	aij:	tij dij t Д . При этом
моделирование весов ветвей			aij T	непрерывно до	тех	пор,	пока значение функций
			K

состояния каких-либо из этих ветвей не станет равно 1.

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

1)значение функции узла остается равным 0 (узел не "свершился");

2)значение функции узла меняется на 1 ("свершение" узла);

3)"свершение" конечного узла сети — единице равно значение функции узла, конечного для данной сети.

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

результата появления единичного значения fС aij . Кроме того, это означает, что

моделирование весового коэффициента ветви продолжаться не будет, значение функции ветви f(aij) в момент времени TT Txi tij станет равно 1, и ветвь будет удалена из фронта моделирования TK .

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	66

Рассмотрим подробнее каждый из трех возможных результатов.
В начальный момент	времени TT T0 фронт моделирования формируется из
подмножества m ветвей, выходящих из начального узла сети					T	m , либо из q начальных
0						0
					0
	q
узлов, если их несколько T0	m p .
	p 1

Если после завершения временнóго моделирования весовых коэффициентов ветвей

получен первый результат, это означает, что в

момент

времени

TT T0

tij

фронт

моделирования

T

будет

равен

T a0 j . Это

справедливо

при условии,

что весовой

1

0

коэффициент d0j

ветви a0j минимален среди весовых коэффициентов ветвей, составляющих

M

n

фронт T0 : doj MIN d0i

, при a0i T0 .

i 1

i 1

Принимая во внимание тот факт, что при временнóм моделировании анализ ветвей

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

функции

состояния ветвей

a0 j

T

, входящих в новый

фронт

0

моделирования T , приобретают значения, равные:

1

f TK a

T

T t

0 j

d TK t

Д

(71)

С

0i

T

0

0i

причем весовые коэффициенты этих

ветвей

d TK

d

0i

d

0 j

, при условии, что момент

0i

начала продолжения моделирования T1

принимается

равным

0. Время

T0 t0 j — момент

получения единичного значения функции

fС a0 j .

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

моделирования,

теперь уже

T , ветви a0j

с минимальным весовым коэффициентом, теперь

1

d0T1j MIN d0Ti1 , и получению одного из трех описанных выше результатов.

a0 j TK

Второй результат моделирования весов ветвей, как было сказано, приводит к свершению узла сети F x j 1 . Это означает, что при дальнейшем моделировании необходимо:

1)Из множества ветвей, составляющих фронт моделирования TK 1 , должны быть исключены ветви, для которых функции состояния равны 1, и получен новый фронт 'TK :

		n	n
'
TK	TK 1	aij , где aij TK 1			и f(aij) = 1, при TT Txi	tij
		i 1	j 1

2) Определить подмножество узлов xj, для которых их функции F(xj) равны 1:

XT	X и X T	x j		F x j 1, п приT	TK
K	K

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	67

3) Включить в новый фронт моделирования TK ветви, выходящие из "свершенных" узлов:

			n
TK	'
	TK		m j	,
		j 1

где mj — ветви, выходящие из узла xj, при F(xj) = 1 в момент TТ = TК. Для осуществления операции (3) следует выполнить процедуру подготовки ветвей из подмножества mj к

моделированию, как описано выше.

Если перед каждым выполнением процедуры моделирования проводить преобразование весовых коэффициентов в соответствии с выражением (71), то саму процедуру можно описать следующим алгоритмом:

1)из подмножества ветвей ветвей aij, составляющих фронт моделирования TK , выделяются элементы с минимальными значениями весовых коэффициентов dminTK MIN dij .

aij TK

2)весовые коэффициенты dij ветвей aij TK преобразуются в относительные весовые коэффициенты dijTK по следующим формулам:

пусть множество

D

d TK

a

ij

T

T

ij

K

K

TK 1

TK

ΦTK

T

dij

dmin, е еслиij

1

dijK

, е, есл

Φ

ии

d

ij

ij

TK

ij

TK 1

Это позволит удалить из фронта TK ветви, функции состояния которых равны 1, за счет того, что их относительные весовые коэффициенты станут равны 0. Иначе говоря, временнóе

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

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

1)вычитать в реальном масштабе времени (РМВ), т.е. через интервал t = tД, единицы из значений коэффициентов ветвей aij TK до получения нулевого значения;

2)выполнять преобразования аналогично способу (1), но в ускоренном масштабе времени, то есть через интервал t t Д kM , где kM — временнóй коэффициент моделирования;

3)	определять	d TK	D	и вычитать это значение из весовых коэффициентов всех ветвей,
		min	T
			K
	составляющих фронт моделирования, с интервалом T dminTK				t Д ;
4)	аналогично способу (3), но без временнóй задержки на T.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	68

Для первого и третьего способов моделирования

r
TM dminTK	t Д	(72)

k 0

где r — количество различных фронтов моделирования. При этом

r LGДП t Д ,

где LGДП — величина длиннейшего пути от начального к конечному узлу сети G.

При втором способе TM LGДП t Д kM .

И наконец, в четвертом случае

				r			,
			TM	T T	K	TDT
				k 0			K
где T T		и TDT	время, затрачиваемое на формирование соответственно множеств TK и DTK и
	K		K

зависящее от алгоритма, по которому выполняется это формирование.

r 1

Очевидно, что LGДП dminTK . Следовательно, для первого случая

k 0

TM t Д LGДП .

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

LGДП TM t Д

Для второго и третьего случаев:

LGДП TM t Д k2 — для второго случая,

LGДП TM t Д — для третьего.

Если для первых трех случаев в качестве "инструмента" для получения характеристики сети используется время (отсюда термин временнóе моделирование), то четвертый способ анализа сети определен в работе А.Г.Додонова как псевдовременнóе моделирование. И

последнее, способы (2) и (4) можно применять при планировании каких-либо технологических процессов, технических и других проектов и т.п., способы (1) и (3) логично использовать для контроля выполнения планов в РМВ.

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

—прекращение процесса моделирования, если в сети один конечныйузел;

—исключения из множества конечных узлов "свершившегося" узла и проверку условия

q F x j 1 ,

j 1

где F(xj) — функция j-го из q конечных узлов сети. Если условие выполнено, то

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	69

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

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

F x j 1 и определению, является ли xj конечным узлом.

Разница в оценке свершения узла при моделировании конъюнктивных и дизъюнктивных сетей заключается в условии получения единичного значения функции узла:

—для конъюнктивных — с помощью выражения (67), то есть когда равны единице функции всех узлов, входящих в узел;

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

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

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

—при получении единичного значения функции какой-либо ветви (ветвей) и, соответственно,

функции узла (узлов), конечного для этой ветви (ветвей), необходимо:

—зафиксировать единичное значение функции узла (узлов);

—прекратить моделирование весовых коэффициентов всех ветвей aij TK , входящих в

"свершившийся" узел (узлы), например, путем их удаления из фронта моделирования.

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

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.

Е.В.Малахов. Имитационное моделирование. Конспект лекций.	70

Литература

1.Основы теории вычислительных систем./ Под ред. С.А.Майорова.- М.: Высшая школа, 1978.

2.Райс Л. Эксперименты с локальными сетями микроЭВМ. - М.: Мир, 1990.

3.Вагнер С. Основы исследования операций. Т.3. М.: Мир, 1973.

4.Клейнрок Л. Теория массового обслуживания. - М.: Машиностроение, 1979.

5.Клейнрок Л. Вычислительные системы с очередями. - М.: Мир, 1979.

6.Шрайбер Т.Дж. Моделирование на GPSS. - М.: Машиностроение, 1980.

7.Феррари Д. Оценка производительности вычислительных систем. - М.: Мир, 1981.

8.Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. - М.: Радио и связь,

1988.

Кафедра математического обеспечения компьютерных систем. ОНУ им. И.И. Мечникова.