Metod_B1.V.DV.23.01_09.03.01_04.06.2016_kp

3. Алгоритмизация модели и ее машинная реализация

3.1. Выбор технических и программных средств моделирования.

В качестве технических средств для выполнения курсовой работы по моделированию можно использовать ПЭВМ IBM PC/AT, принтер, в качестве программных федств - пакет Turbo C++ и разработанные на кафедре ЭВМ КГТУ им. А.Н.Туполева автоматизированную информационную систему формирования последовательностей псевдослучайных чисел (ПСЧ) с

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

MATHLAB, MATHCAD, MATHEMATIKA.

3.2. Составление алгоритма моделирующей программы.

Алгоритм моделирующей программы представляется в виде блок-

схемы по аналогии с представлением в работе /3/.

3.3.Описание моделирующей программы для детерминированного варианта модели Данный раздел содержит текст (листинг) моделирующей программы для детерминированной модели.

3.4. Верификация (тестирование) программы.

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

полученным при реализации программы.

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

3.5.1. Моделирование случайных воздействий, имеющих равномерное распределение.

21

3.5.1.1. Аппаратный способ.

Для формирования файлов ПСЧ воспользуемся автоматизированной системой GENERATO, разработанной на кафедре ЭВМ. Данная система моделирует работу генератора псевдослучайных чисел (ГПСЧ), построенного на основе регистра сдвига. Запустив файл с системой GENERATO,

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

разрядность и количество генерируемых чисел и др. Сформируем данным способом 2 файла равномерно распределенных ПСЧ. Определим структуру ГПСЧ для создания первого файла ПСЧ. Число разрядов ГПСЧ - 50,

разрядность ПСЧ - 25, количество генерируемых ПСЧ - 1000, количество сдвигов - 25, количество обратных связей - 30, номера разрядов: 1, 3, 4, 5, 23,

31, 13, 14, 12, 34, 7, 9, 10, 21, 25, 35, 36, 37, 41, 43, 46, 47, 48, 49, 50, 8, 2, 6, 17,

11. Определим структуру ГПСЧ для создания второго файла ПСЧ: число разрядов ГПСЧ - 50, разрядность ПСЧ - 25, количество генерируемых ПСЧ -

1000, количество сдвигов - 15, количество обратных связей - 20: номера разрядов: 1, 2, 4, 6, 8, 9, 13, 14, 22, 27, 30, 31, 35, 36, 42, 44, 45, 48, 49, 50. С

помощью одной из систем статистического анализа, например, STAN

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

Числовые характеристики. 1 -й файл: m = 0,493; D = 0,0815. 2-й файл: m = 0,52; D = 0,077. Период не обнаружен ни в одном из двух файлов.

Гистограмма распределения и график автокорреляционной функции ρ(τ), из 1

-го файла представлены на рис. 3а, 3б, из 2-го файла - на рис. 4а, 4б, (n-число интервалов разбиения отрезка (0,1), τ - расстояние между элементами последовательности ПСЧ).

Количественное расхождение статистического равномерного распределения от теоретического определим по критериям согласия Хи-

квадрат и Колмогорова, пользуясь системой STAN.

Результаты для первого файла.

22

Критерий Хи-квадрат: χ2= 2,126, с доверительной вероятностью 0,95

можно утверждать о согласованности статистического закона и теоретического равномерного закона.

Критерий Колмогорова: максимальная разность max|F(x)- F*(x)| = 0,016

теоретические и статистические данные согласуются с доверительной вероятностью 0,95.

Результаты для второго файла.

Критерий Хи-квадрат: χ2= 2,017, с доверительной вероятностью 0,75

можно утверждать о согласованности статистического закона и теоретического равномерного закона.

Критерий Колмогорова: максимальная разность max|F(x)- F*(x)| = 0,029

теоретические и статистические данные согласуются с доверительной вероятностью 0,92.

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

и 4, можно сказать, что 1-й файл ПСЧ в большей мере удовлетворяет требованиям равномерности распределения чисел и их некоррелированности,

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

определяя структуру ГПСЧ, при формировании 1-го файла задано большее количество сдвигов, нежели при формировании 2-го файла.

3.5.1.2. Программный способ.

Программный способ получения ПСЧ сводится к реализации одного из известных методов /1/ генерирования ПСЧ, предлагаемого преподавателем.

Например, пусть задан метод "середины квадрата", заключающийся в следующем: вводим произвольное n-разрядное число х, возводим его в квадрат: у= х2, у – 2n - -разрядное число, берем из середины числа у 2n

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

23

анализа, например, STAN. Пусть полученные числа по результатам анализа имеют, например, следующие характеристики.

Числовые характеристики. 1-й файл: m=0,48; D=0,081. 2-й файл: m=0,51; D=0,074. Гистограммы и графики корреляции чисел из сформированных файлов представлены на рис. 5а. 5б и 6а, 6б.

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

3.5.1.3.Выбор генератора равномерно распределенных ПСЧ Проанализировав п.3.5.1.1. и п. 3.5.1.2., определимся в выборе

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

а потому и будем использовать файлы ПСЧ, полученные с использованием системы GENERATO.

3.5.2.Моделирование случайных воздействий, имеющих неравномерное распределение

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

24

Рис. 5а

Рис. 5б

25

а) алгоритм для нормального закона распределения: (для m=0, D= 1)

	12
x
	k
i

k
	z
j 1

j

k

2

   

,

где: Xi-очередное число последовательности,

zj -равномерно распределенное число из интервала (0,1),

к= 12, 24.

б) алгоритм для закона распределения Лапласа

x i

		1

Sign

1		1
				ln
z		2

z 2

,

где: хi - очередное число последовательности,

μ - математическое ожидание последовательности,

λ - находят из формулы

	D	2
		2

(D - дисперсия),

z1, z2 - равномерно распределенные числа из интервала (0,1).

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

В таблице 1 определены числовые характеристики данных ПСЧ.

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

f (x)		1	e	(x m)		2
		2		2	2
Область			значений случайной величины:

( , )

. Параметры

закона: m , 0. С помощью системы статистического анализа

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

26

Критерий Хи-квадрат: χ2=2,7094, с доверительной вероятностью 0,95 можно утверждать о согласованности теоретических и статистических данных.

Критерий Колмогорова: максимальная разность max|F(x)-F*(x)| =0,014,

теоретические и статистические данные согласуются с доверительной вероятностью 0,987.

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

Таблица 1

№	Характеристика				Теоретич.	Статистическое
П/П					значение	значение
1	Наименьшее	значение	среди	1		-0,0476
	совокупности
2	Наибольшее	значение	среди	13		12,4767
	совокупности
3	Математическое ожидание			7		6,9428
4	Дисперсия			4		4,0236
5	Среднеквадратическое			2		2,0059
	отклонение
6	Коэффициент ассиметрии			0		-0,023
7	Эксцесс			0		-0,0807

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

3.5.2.2. Обработка файла чисел, имеющих закон распределение Лапласа В таблице 2 определены числовые характеристики данных ПСЧ.

27

вид:

Плотность распределения для закона распределения Лапласа имеет

f (x)		e	x	.
	2
Область значений случайной величины:					( , ), параметры закона:

0,

0

.

На

рис.8а

изображена

гистограмма

и

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

Таблица 2

№	Характеристика			Теоретич.	Статистическое
П/П				значение	значение
1	Наименьшее	значение среди		0,77	-0,610
	совокупности
2	Наибольшее	значение	среди	9,23	11,427
	совокупности
3	Математическое ожидание			5	5,092
4	Дисперсия			2	1,86
5	Среднеквадратическое			1,41	1.32
	отклонение
6	Коэффициент ассиметрии				0,301
7	Эксцесс			0	2,649
	Критерий Хи-квадрат: χ2		= 5,147, доверительная		вероятность 0,84.

Критерий Колмогорова: Максимальная разность max |F(x) - F*(x)| = 0,03, с доверительной вероятностью р =0,728 теоретические и статистические данные согласуются. Полученная нами последовательность ПСЧ, имеющих закон распределения Лапласа, удовлетворяет предъявляемым требованиям по качеству и может быть использована в стохастической моделирующей программе, т.к. числовые характеристики имеют незначительное отклонение от теоретических значений; по критериям согласия получены

28

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

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

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

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

2). Возьмем за единицу модельного времени емв = 0,1 мин.

4. Получение и интерпретация результатов моделирования

4.1. Планирование машинного эксперимента Условимся считать некоторую систему оптимальной, если она в

процессе работы удовлетворяет следующим условиям:

-не имеет простоя оборудования;

-не имеет очередей пользователей;

-не имеет очередей заявок.

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

нужно добиться выполнения следующих требований: время работы на 1 -м и

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

4.2.Проведение прогонов модели Результаты прогонов модели представлены в таблице 3.

29

Усредненные результаты прогонов будут следующими: количество заданий, поступивших на обе ЭВМ - 203; количество обработанных заданий -

142; количество необработанных заданий - 61.

		Таблица 3
Колич. заданий,	Колич. обработанных	Колич. не обработанных
поступивших на обе	заданий	заданий
ЭВМ
202	38	64
208	143	65
193	140	53
204	145	59
205	146	59
203	139	64
199	137	62
201	150	51
210	144	66
205	146	59

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

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

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

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

сократить простой оборудования.

30