WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 20 |
Т.И. Алиев, Л.А. Муравьева-Витковская, В.В.Соснин МОДЕЛИРОВАНИЕ:

ЗАДАЧИ, ЗАДАНИЯ, ТЕСТЫ П Санкт-Петербург 2011 Алиев Т.И., Муравьева-Витковская Л.А., Соснин В.В. Моделирование:

задачи, задания, тесты. – СПб: НИУ ИТМО, 2011. – 197 с.

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

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

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

Рекомендовано к печати Советом факультета компьютерных технологий и управления 15 ноября 2011 г., протокол № 9.

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория «Национальный исследовательский университет».

Министерством образования и науки Российской Федерации была утверждена программа его развития на 2009–2018 годы. В 2011 году Университет получил наименование «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, 2011 Алиев Т.И., Муравьева-Витковская Л.А., Соснин В.В., Введение Математическое моделирование заключается в применении адекватных моделей исследуемых систем для решения задач анализа и синтеза с использованием аналитических и имитационных методов. В процессе моделирования решаются задачи разработки модели, анализа свойств и выработки рекомендаций по модернизации существующей или проектированию новой системы.

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

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

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

Структура сборника. Сборник содержит 4 раздела и Список литературы.

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

Второй раздел содержит простейшие задачи, решение которых базируется на аналитических методах расчета систем (СМО) и сетей (СеМО) массового обслуживания, методах Марковских случайных процессов и имитационного моделирования в среде GPSS World. Основное назначение этих задач – закрепление теоретического материала и грамотное применение основных математических зависимостей, методов и средств моделирования в процессе решения конкретных задач.

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

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

ITMOdel – аналитический расчет моделей массового обслуживания;

MARK – расчт Марковских процессов.

Имитационное моделирование предполагает использование следующих систем имитационного моделирования:

GPSS World фирмы Minuteman Software;

Any Logic фирмы XJ Technologies.

В четвёртом разделе представлен примерный перечень вопросов по компьютерному тестированию, охватывающих все разделы пособия [1].

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

по аналитическим и численным методам моделирования систем и сетей массового обслуживания [1-3];



по имитационному моделированию систем и сетей массового обслуживания в среде GPSS World [4, 5].

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

Раздел 1. Краткие теоретические сведения Раздел 1. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 1.1. Элементы теории вероятностей Закон распределения случайной величины – соотношение, устанавливающее связь между возможными значениями случайной величины и соответствующими им вероятностями.

Закон распределения дискретной случайной величины может быть задан:

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

таблично в виде ряда распределения;

графически в виде многоугольника распределения.

Закон распределения непрерывной случайной величины может быть задан в виде:

функции распределения F(x) случайной величины X, представляющей собой вероятность того, что случайная величина X примет значение меньшее, чем некоторое заданное значение x:

F(x) P(X x);

плотности распределения f(x), определяемой как производная от функции распределения F(x) по x: f (x) F (x).

Функция распределения однозначно определяется через плотность распределения как x F(x) f (x)dx.

Свойства функции распределения:

F(x) – неубывающая функция: если xj > xi, то F(xj ) F(xi );

функция распределения принимает значения от 0 до 1, причм:

F() 0 и F() 1.

Свойства плотности распределения:

плотность распределения принимает только неотрицательные значения: f (x) 0;

площадь на графике, ограниченная плотностью распределения и осью абсцисс, всегда равна единице: f (x)dx 1.

Числовые характеристики случайных величин:

начальные s[X ] моменты:

n s x pi для дискретной случайной величины;

i i s[X ] (1) xs f (x)dx для непрерывной случайной величины;

центральные s[X ] моменты:

Раздел 1. Краткие теоретические сведения n для дискретной величины;

(x M[X ])s pi i i s[X ] (2) (x M[X ])s f (x)dx для непрерывной величины.

Первый начальный момент случайной величины Х называется математическим ожиданием и характеризует среднее значение случайной величины:

n для дискретной величины;

x pi i i M[X ] 1[X ] (3) x f (x)dx для непрерывной величины.

Второй начальный момент 2 [X ] случайной величины X характеризует разброс значений случайной величины относительно начала координат.

Второй центральный момент называется дисперсией случайной величины: D[X ] 2[X ] и характеризует разброс значений случайной величины относительно математического ожидания:

n для дискретной величины;

(x M[X ])2 pi i i D[X ] (4) (x M[X ])2 f (x) dx для непрерывной величины.

Дисперсия и второй начальный момент связаны зависимостью D[X ] 2[X ] (M[X ])2. (5) Среднеквадратическое отклонение [X ] – характеристика разброса, размерность которой совпадает с размерностью случайной величины:

[X ] D[X ]. (6) Коэффициент вариации [X ] – безразмерная характеристика разброса случайных величин, определенных в области положительных значений:

[X ] [X ]/ M[X ] ( M[X ] 0). (7) В моделях дискретных систем наиболее широко применяются следующие законы распределений случайных величин:

распределение Пуассона (дискретный закон):

ak pk P(X k) ea (k 0,1, 2,), (8) k! где a – параметр распределения ( a 0);

геометрическое распределение (дискретный закон):

Раздел 1. Краткие теоретические сведения pk P(X k) k (1 ) k 0,1, 2,, (9) где – параметр распределения (0 1);

равномерное распределение (непрерывный закон) с плотностью при a x b;

f (x) (10) b a при x b;

экспоненциальное распределение (непрерывный закон) с функцией и плотностью F(x) 1 ex; f (x) ex, (11) где 0 параметр распределения; x 0; эксп[X ] распределение Эрланга k-го порядка (непрерывный закон) с функцией и плотностью:

i k (x)k Fk (x) 1 ex fk (x) ex, (12) (ix) ;

! (k 1)! iгде и k – параметры распределения ( 0; k 1, 2,) ; x 0;

Эk [X ] 1математическое ожидание распределения Эрланга k зависит от значения параметра k;

нормированное распределение Эрланга (непрерывный закон) с функцией и плотностью:

i k k(k x)k 1 x Fk (x) 1 ekx fk (x) ek ; (13) (k!x) ;

i (k 1)! iкоэффициент вариации нормированного распределения Эрланга также меньше или равен единице: нЭk [X ] 1, но математическое k ожидание не зависит от значения параметра k;

гипоэкспоненциальное распределение (непрерывный закон), преобразование Лапласа которого определяется как:

k k k * i F*(s) F (s) s 11sx, i i1 i1 i i1 i i где Fi*(s) – преобразование Лапласа экспоненциального i s 1 sxi распределения (i-й составляющей) с параметром i и математическим ожиданием xi 1/i ;

математическое ожидание, дисперсия и коэффициент вариации гипоэкспоненциального распределения равны:

k k k k 2 Mk ; Dk ; k x x x x, (14) i i i i i1 i1 i1 iРаздел 1. Краткие теоретические сведения причм коэффициент вариации гипоэкспоненциального распределения k может принимать любые значения в интервале (0; 1), в том числе, в отличие от распределения Эрланга, нецелочисленные значения;

гиперэкспоненциальное распределение (непрерывный закон):

n n F(x) (1 ei x ) 1 ei x;

q q i i i1 i. (15) n f (x) i ei x q i iДля аппроксимации реальных распределений по двум первым моментам – математическому ожиданию t и коэффициенту вариации – могут использоваться следующие аппроксимирующие распределения:





если коэффициент вариации случайной величины меньше единицы ( ) – гипоэкспоненциальное распределение, параметры которого рассчитываются по формулам:

1 t k2 2 t k1 k ; t1 k k 1 k1 1; t2 k 1 k2 ; (16) k если коэффициент вариации временного интервала больше единицы ( ) – гиперэкспоненциальное распределение, параметры которого рассчитываются по формулам:

q 1 q q ; t1 ; t1 2(1 q) ( 1)t. (17) 1 2q ( 1)t 1.2. Параметры и характеристики моделей массового обслуживания Ниже рассматриваются модели массового обслуживания, представляющие собой системы (СМО) и сети (СеМО) массового обслуживания.

1.2.1. СМО с однородным потоком заявок Для компактного описания систем массового обслуживания (СМО) используются обозначения в виде A/B/N/L, где A и В – задают законы распределений соответственно интервалов времени между моментами поступления заявок и длительностей обслуживания в приборе; N – число обслуживающих приборов в системе; L – число мест в накопителе.

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

количество обслуживающих приборов K;

количество k и емкости накопителей Ej ( j 1, k) ;

количество поступающих в систему классов заявок H;

интенсивность i потока и коэффициент вариации интервалов ai времени между поступающими в систему заявками класса i 1, H ;

Раздел 1. Краткие теоретические сведения среднее значение bi и коэффициент вариации длительности bi обслуживания заявок класса i 1, H ;

дисциплина буферизации и дисциплина обслуживания заявок.

В режиме перегрузки, когда система не справляется с нагрузкой, характеристики функционирования СМО с накопителем неограниченной емкости с течением времени растут неограниченно.

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

В качестве основных характеристик СМО с однородным потоком заявок используются:

нагрузка системы:

y / b ; (18) вероятность потери заявок (для СМО с накопителем ограниченной мкости):

Nп (T) lim ; (19) п T N(T) вероятность того, что заявка будет обслужена, т.е. не потеряна (для СМО с накопителем ограниченной мкости):

о (1п); (20) загрузка системы:

(1 )y min п ;1 ; (21) K коэффициент простоя системы:

; (22) производительность системы:

' о (1п) ; (23) интенсивность потока потерянных заявок:

" п (1о) ; (24) среднее время ожидания заявок в очереди:

w (подлежит определению для каждой конкретной СМО);

среднее время пребывания заявок в системе:

u w b ; (25) средняя длина очереди заявок:

l 'w ; (26) среднее число заявок в системе:

m 'u. (27) Раздел 1. Краткие теоретические сведения 1.2.2. СМО с неоднородным потоком заявок Для СМО с неоднородным потоком заявок определяются две группы характеристик обслуживания заявок: характеристики по каждому классу заявок по формулам (18) – (27) и характеристики суммарного (объединенного) потока заявок:

суммарная интенсивность поступления заявок в систему (интенсивность суммарного потока):

H ; (28) i i суммарная нагрузка Y и суммарная загрузка R системы:

H Y yi ; (29) iH R min( i;1), (30) iгде i, yi и i – соответственно интенсивность поступления, нагрузка и загрузка, создаваемые заявками класса ; – количество классов заявок; причем условие отсутствия перегрузок в СМО с неоднородным потоком заявок и накопителем неограниченной мкости имеет вид:

R 1; (31) коэффициент простоя системы:

1 R (32) среднее время ожидания W и среднее время пребывания U заявок объединнного потока в системе:

H H W wi ; U ui, (33) i i i1 iгде i i / – коэффициент, учитывающий долю заявок класса i в суммарном потоке, который может трактоваться как вероятность того, что поступившая в систему заявка принадлежит классу i;

суммарная длина очереди и суммарное число заявок в системе:

H H L ; M. (34) l m i i i 1 iДля характеристик объединнного (суммарного) потока справедливы те же фундаментальные соотношения (25) – (27), что и для однородного потока:

U W B; L W ; M U, где B – среднее время обслуживания любой заявки суммарного потока:

H B bi.

i iРаздел 1. Краткие теоретические сведения 1.2.3. СеМО с однородным потоком заявок Для описания линейных разомкнутых и замкнутых однородных экспоненциальных СеМО необходимо задать следующие параметры:

число узлов в сети ;

n число обслуживающих приборов в узлах сети K1,...,Kn;

матрицу вероятностей передач P [ pij i, j 0,1,,n];

интенсивность 0 источника заявок, поступающих в РСеМО, M или число заявок, циркулирующих в ЗСеМО;

средние длительности обслуживания заявок в узлах сети b1,...,bn.

Условие отсутствия перегрузок в разомкнутой СеМО предполагает отсутствие перегрузок в каждом из узлов сети. В замкнутой СеМО перегрузки не возникают.

Характеристики СеМО делятся на узловые и сетевые.

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

На основе узловых характеристик рассчитываются средние значения сетевых характеристик СеМО:

суммарная нагрузка и загрузка:

Pages:     || 2 | 3 | 4 | 5 |   ...   | 20 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.