Математическое моделирование
Изучение современных принципов, подходов и методов моделирования сложно формализуемых объектов. Решение задач структурной и параметрической идентификации. Характеристики вычислительных систем как сложных систем массового обслуживания. Теория потоков.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курс лекций |
| Язык | русский |
| Дата добавления | 18.02.2012 |
| Размер файла | 2,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
2. Характеристики вычислительных систем как стохастических сетей
Описание стохастической сети. Обычно ВС представляется не отдельной СМО, а стохастической сетью. Для описания ВС в виде стохастической сети определяются следующие параметры:
1) число СМО, образующих сеть (S1, S2, ..., Sn);
2) число каналов каждой СМО (т1 ..., mn);
3) матрица вероятностей передач Р = [pij], где рij -- вероятность того, что заявка, покидающая систему Si, поступает в систему Sj (i, j=0,1,...n);
4) интенсивность источника заявок S0 в разомкнутой сети или число М заявок в замкнутой сети;
5) средние длительности обслуживания заявок в системах S1,...Sn.
Рассмотрим характеристики экспоненциальных сетей. Экспоненциальная стохастическая сеть имеет простейшие входные потоки и распределенные по экспоненциальному закону длительности обслуживания заявок в различных системах сети. В установившемся режиме вероятность передачи заявки из системы Si; в систему Sj равна доле потока, поступающего из системы Si; в систему Sj. Если система без потерь, то на входе системы Si; имеется поток с интенсивностью
1, ..., n. (1)
Из этой системы уравнений находятся соотношения интенсивностей потоков и в виде
(2)
где -- коэффициент передачи, который определяет среднее число этапов обслуживания одной заявки в системе Sj.
Для замкнутой сети принимается .
Определение вероятности состояний. В стационарном установившемся режиме вероятность того, что в системе Sj находится Мj заявок, определяется из выражения
(3)
где
(4)
(5)
(6)
Вероятность состояния замкнутой сети Р (M1, ..., Mn), характеризующая вероятность того, что в системе S1 находится М1заявок,
и т. д., вычисляется по формуле
(7)
где -- символ суммирования по всем возможным состояниям, для которых
(8)
По вероятностям состояний определяются характеристики сети.
Вычисление характеристик разомкнутой сети. В разомкнутой экспоненциальной сети в стационарном режиме согласно теореме Джексона можно считать, что сеть состоит из совокупности независимых СМО с простейшими входными потоками. Для каждой СМО характеристики определяются отдельно. Для каждой Sj СМО сети средняя длина очереди
(9)
среднее число в системе
(10)
а среднее время ожидания в очереди , и пребывания в системе uj определяется по формулам Литтла из (9) и (10). Тогда характеристики сети в целом: среднее число заявок во всех очередях
(11)
среднее число заявок в сети
(12)
среднее время ожидания в очередях
(13)
среднее время реакции сети
(14)
Вычисление характеристик замкнутой сети. Для любой Sj СМО сети средняя длина очереди
(15)
среднее число заявок в СМО
(16)
средние времена ожидания и пребывания uj вычисляются по формулам Литтла. Среднее время цикла сети, т. е. интервал времени между двумя последовательными выходами одной и той же заявки из СМО Si составляет Uj = M/j.
В заключение отметим, что простые аналитические выражения для определения характеристик ВС как сетевых моделей имеются лишь для узкого круга систем. В ряде случаев приходится прибегать к численным моделям.
Существенный недостаток сетевых моделей -- трудность учета таких ситуаций, когда заявке требуется одновременно несколько ресурсов. В теории массового обслуживания слабо учитывается использование накопителей, неоднородность потока заявок. Считается, что заявка обслуженная одной СМО, поступает на другую, в то время как в ВС в передаче одновременно участвуют передающее устройство, коммуникатор и принимающее устройство. Применение аналитического моделирования целесообразно для предварительной оценки характеристик ВС.
Контрольные вопросы
Основные подходы исследования характеристик ВС в нестационарном режиме.
Исследование характеристик в режиме перегрузок.
Описание стохастической сети применительно к ВС.
Определение вероятности состояний.
Определение характеристик разомкнутой и замкнутой сети.
Литература
1. Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.
2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.
3. Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.
4. Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.
Лекция 12. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)
План
1. Процедура имитационного моделирования
2. Обобщенные алгоритмы имитационного моделирования
1. Процедура имитационного моделирования
Метод имитационного моделирования заключается в создании логико-аналитической (математической) модели системы и внешних воздействий, в имитации функционирования системы, т. е. в определении временных изменений состояния системы под влиянием внешних воздействий, и в получении выборок значений выходных параметров, по которым определяются их основные вероятностные характеристики. Данное определение справедливо для стохастических систем. При исследовании детерминированных систем отпадает необходимость в получении выборок значений выходных параметров.
Модель системы со структурным принципом управления представляет собой совокупность моделей элементов и их функциональные взаимосвязи. Модель элемента (агрегата, обслуживающего прибора) -- это, в первую очередь, набор правил (алгоритмов) поведения устройства по отношению к входным воздействиям (заявкам) и правил изменения состояний элемента. При моделировании ВС на системном уровне элемент отображает функциональное устройство на том или ином уровне детализации.
В простейшем случае устройство может находиться в работоспособном состоянии или в состоянии отказа. В работоспособном состоянии устройство может быть занято, например, выполнением операции по обслуживанию заявки или свободно. К правилам поведения устройства относятся правила выборки заявок из очереди; реакция устройства на поступление заявки, когда устройство занято или к нему имеется очередь заявок; реакция устройства на возникновение отказа в процессе обслуживания заявки и некоторые другие.
Функциональные взаимосвязи устройств определяют возможные пути продвижения заявок по системе от входных устройств к выходным. Они формируют функциональную структуру ВС.
Модель внешних воздействий -- это правила определения моментов поступления входных сигналов (заявок) в систему, маршрута заявок в системе по каждому из потоков в соответствии с алгоритмами обработки, приоритетов обслуживания заявок одних потоков по отношению к другим, трудоемкости обслуживания заявок устройствами, допустимого времени пребывания заявок в системе и др.
В процессе имитации функционирования системы измеряются те выходные характеристики, которые интересуют исследователя. При изучении стохастических систем измерения производятся многократно с тем, чтобы можно было с достаточной точностью определить вероятностные характеристики системы.
Модель системы с программным принципом управления представляет собой, в основном, формализованное описание параллельно протекающих процессов с указанием используемых ресурсов и алгоритмов управления процессами.
Имитационное моделирование -- это метод исследования, который основан на том, что анализируемая динамическая система заменяется имитатором и с ним проводятся эксперименты для получения информации об изучаемой системе. Роль имитатора зачастую выполняет специальная программа ВС.
Основная идея метода имитационного моделирования стохастических систем во многом исследована методом вычисления случайных величин, который называется методом статистических испытаний или методом Монте-Карло. Заключается он в следующем. Пусть необходимо определить функцию распределения случайной величины у. Допустим, что искомая величина у может быть представлена в виде зависимости
где -- случайные величины с известными функциями распределения.
Для решения задач такого вида применяется следующий алгоритм:
1) по каждой из величин производится случайное испытание, в результате которого определяется некоторое конкретное значение случайной величины (способы проведения случайного испытания описаны ниже);
2) используя найденные величины, определяется одно частное значение yi по вышеприведенной зависимости;
3) предыдущие операции повторяются N раз, в результате чего определяется N значений случайной величины у;
4) на основании N значений величины у находится ее эмпирическая функция распределения.
Имитация функционирования системы. Предположим, что ВС состоит из процессора 1 с основной памятью, устройства ввода 4, печатающего устройства 2 и монитора 3. Через устройство ввода поступает поток заданий X1. Процессор обрабатывает задания и результаты обработки выдает на печатающее устройство (принтер). Одновременно с этим ВС используется, например, как информационно-справочная система. Оператор-пользователь, работающий за монитором, посылает в систему запросы X2, которые обрабатываются процессором, и ответы выводятся на монитор. Процессор работает в двух программном режиме: в одном разделе обрабатываются задания X1, в другом, с более высоким относительным приоритетом, -- запросы Х2.
Представим данную ВС в упрощенном варианте в виде стохастической сети из четырех СМО. Потоки заданий и запросов будем называть потоками заявок. Считаем потоки X1 и X2 независимыми. Известны функции распределения периодов следования заявок и и длительностей обслуживания Т1k и Т2k заявок k-м устройством. Требуется определить времена загрузки каждого устройства и времена реакции по каждому из потоков.
Рис. 1. Временная диаграмма функционирования ВС
В начале определяется момент поступления в систему первой заявки потока Х1 по результатам случайного испытания в соответствии с функцией распределения периода следования заявок. На рис. 1 это момент времени (здесь и далее верхний индекс обозначает порядковый номер заявки данного потока). То же самое делается для потока Х2. На рис. 1. момент поступления первой заявки потока . Затем находится минимальное время, т.е. наиболее раннее событие. В примере-- это время t1. Для первой заявки потока X1 определяется путем случайного испытания время обслуживания устройством ввода T114 и отмечается момент окончания обслуживания На рисунке показан ступенькой переход устройства 4 в состояние «занято». Одновременно определяется момент поступления следующей заявки потока .
Следующее минимальное время -- это момент поступления заявки потока X2-t2. Для этой заявки находится время обслуживания на мониторе T123 и отмечается время окончания обслуживания . Определяется момент поступления второй заявки потока . Снова выбирается минимальное время-- это tз. В этот момент заявка потока Х2 начинает обрабатываться процессором. По результату случайного испытания определяется время ее обслуживания T123 и отмечается момент окончания обслуживания. Следующее минимальное время t4 -- момент завершения обслуживания заявки потока X1 устройством 4. С этого момента заявка может начать обрабатываться процессором, но он занят обслуживанием заявки потока Х2. Тогда заявка потока X1 переходит в состояние ожидания, становится в очередь.
В следующий минимальный момент времени t5 освобождается процессор. С этого момента процессор начинает обрабатывать заявку потока X1, а заявка потока X2 переходит на обслуживание монитором, т. е. ответ на запрос пользователя передается из основной памяти в буферный накопитель монитора. Далее определяются соответствующие времена обслуживания и отмечаются моменты времени . В момент t6 полностью завершается обработка первой заявки потока Х2. По разности времен t6 и t2 вычисляется время реакции по этой заявке:
Следующий минимальный момент времени t7 -- это поступление второй заявки потока Х2. Определяется время поступления очередной заявки этого потока . Затем вычисляется время обслуживания второй заявки на мониторе Т223 и отмечается момент после чего заявка становится в очередь, так как процессор занят. Эта заявка поступает на обслуживание в процессор только после его освобождения в момент времени t9. В этот же момент заявка потока Х1 начинает обслуживаться принтер. Определяются времена обслуживания Т221 и T112 по результатам случайных испытаний и отмечаются моменты окончания обслуживания . В момент времени t10 завершается полное обслуживание первой заявки потока X1. Разность между этим моментом и моментом времени t1 дает первое значение времени реакции по потоку .
Вторая заявка потока Х2 в момент t11 поступает с процессора на- монитор и обслуживается им в течение времени Т223, которое завершается в момент Снова определяется очередное минимальное время. Это время -- t12 когда в систему поступает вторая заявка из потока Х1. Тогда вычисляется время поступления третьей заявки потока . Вторая заявка обслуживается устройством ввода в течение времени Т214 (момент завершения -- ) и процессором -- T211 (момент завершения -- ). В момент t13 состояние системы не изменяется, но вычисляется второе значение времени реакции по потоку Х2:
В момент времени t15 систему поступает третья заявка потока Х2. Определяется момент поступления четвертой заявки потока (предполагается, что пользователь может посылать запросы, не дожидаясь ответов на предыдущие запросы). Третья заявка обслуживается монитором в течение времени T323, но с момента окончания обслуживания () переходит в состояние ожидания, так как занят процессор.
Следующее минимальное время t17, -- это время поступления четвертой заявки потока Х2. После ее обслуживания монитором (момент завершения ) она также переходит в ожидание, т. е. образуется очередь из двух заявок. После освобождения процессора в момент t19 начнется обслуживание процессором третьей заявки потока X2, а затем с момента -- монитором. По завершении этого обслуживания () можно будет вычислить третье значение времени реакции по потоку X2:
С момента времени t19 принтер начнет обслуживание второй заявки потока X1 и завершит его к моменту , после чего определяется второе значение времени реакции по потоку X1:
Указанные процедуры выполняются до истечения времени моделирования. В результате получается некоторое количество (выборка) случайных значений времен реакции {u1} и {u2} по первому и второму потокам. По этим значениям могут быть определены эмпирические функции распределения и вычислены количественные вероятностные характеристики времен реакции. В процессе моделирования можно суммировать продолжительности занятости каждого устройства обслуживанием всех потоков. Например, на рис. 1 занятость процессора 1 выделена заштрихованными ступеньками. Если результаты суммирования разделить на время моделирования, то получатся коэффициенты загрузки устройств.
Одновременно появляется возможность определения таких характеристик системы, как время ожидания заявок в очереди, число заявок, обслуженных системой, средняя и максимальная длина очереди заявок к каждому из устройств, требуемая емкость памяти и некоторые другие характеристики.
Имитационное моделирование дает возможность учесть надежностные характеристики ВС. В частности, если известны времена наработки на отказ и восстановления всех входящих в систему устройств, определяются моменты возникновения отказов устройств в период моделирования и моменты восстановления. Если в моменты возникновения отказа устройство занято обслуживанием заявки, то может приниматься разное решение в зависимости от типа устройства и режима его работы: заявка снимается и больше не обслуживается (выбывает из системы) или заявка помещается в очередь, а после восстановления устройства дообслуживается или поступает на повторное обслуживание.
2. Обобщенные алгоритмы имитационного моделирования
Алгоритм моделирования по принципу особых состояний. В изложенном выше примере моделирование проводилось по принципу особых состояний (событий). В качестве особых событий выделены поступление заявки в систему, освобождение элемента после обслуживания заявки, завершение моделирования. В общем случае в системе могут быть выделены события и других типов, например возникновение отказа устройства в процессе обслуживания заявки и завершение восстановления устройства после отказа.
Рис. 2. Алгоритм моделирования по принципу особых состояний
Процесс имитации функционирования системы развивался во времени с использованием управляющих последовательностей, определяемых по функциям распределения вероятностей исходных данных путем проведения случайных испытаний. В качестве управляющих последовательностей использовались в примере последовательности значений периодов следования заявок по каждому i-му потоку {} и длительностей обслуживания заявок i-го потока k-м устройством {Tik}. Моменты наступления будущих событий определялись по простым рекуррентным соотношениям. Эта особенность дает возможность построить простой циклический алгоритм моделирования, который сводится к следующим действиям:
1) определяется событие с минимальным временем -- наиболее раннее событие;
2) модельному времени присваивается значение времени наступления наиболее раннего события;
3) определяется тип события;
4) в зависимости от типа события предпринимаются действия, направленные на загрузку устройств и продвижение заявок в соответствии с алгоритмами их обработки, и вычисляются моменты наступления будущих событий; эти действия называют реакцией модели на события;
5) перечисленные действия повторяются до истечения времени моделирования.
В процессе моделирования производится измерение и статистическая обработка значений выходных характеристик. Обобщенная схема алгоритма моделирования по принципу особых состояний (принцип ) изображена на рис. 2. Вначале производится инициализация моделирующей программы -- подготавливаются массивы, вводятся и размещаются в оперативной памяти входные данные, настраиваются датчики случайных чисел. Затем генерируются первые заявки по каждому потоку -- определяются моменты их поступления в систему и конкретизируются другие параметры.
Остальные операции выполняются в цикле. Определяется момент наступления наиболее раннего события и до этого момента смещается модельное время. После определения типа события реализуется соответствующая реакция на событие. В процессе этих действий могут возникать те или иные события в будущем, что фиксируется в массиве событий. Реакция на определенное событие, кроме всего прочего, приводит, как правило, к исключению его из массива событий. Кончается каждая реакция возвратом к определению события с минимальным временем.
Такой цикл повторяется до достижения конца моделирования, после чего завершается обработка статистики и выводятся результаты. На этом заканчивается модельный эксперимент.
В системе-оригинале могут протекать одновременно несколько процессов. Это приводит к тому, что в один и тот же момент времени в системе может возникнуть несколько особых событий. При моделировании на однопроцессорной ВС эти ситуации разрешаются таким образом: последовательно в установленном порядке реализуются реакции на все одновременно возникшие ситуации без продвижения модельного времени. Это называется псевдопараллельной имитацией нескольких процессов.
Рис. 3. Алгоритм моделирования по принципу временных приращений
Алгоритм моделирования по принципу . Укрупненная схема моделирующего алгоритма, который реализует принцип постоянного приращения модельного времени (принцип ), представлена на рис. 3. Как и в предыдущем алгоритме, вначале инициализируется программа, в частности, вводятся значения zi(t0), i= 1, ...,n, которые характеризуют состояние системы в n-мерном фазовом пространстве состояний в начальный момент времени t0. Модельное время устанавливается t = t0 = 0.
Основные операции, с помощью которых имитируется функционирование системы, выполняются в цикле. Функционирование системы отслеживается по последовательной смене состояний Zi (t). Для этого модельному времени дается некоторое приращение . Затем по вектору текущих состояний определяются новые состояния zi (t + ), которые становятся текущими. Для определения новых состояний по текущим в формализованном описании системы должны существовать необходимые математические зависимости. Такой цикл продолжается до тех пор, пока текущее модельное время меньше заданного времени моделирования Тm.
По ходу имитации измеряются, фиксируются и обрабатываются требуемые выходные характеристики. При t завершается обработка измерений и выводятся результаты моделирования.
При моделировании стохастических систем вместо новых состояний вычисляются распределения вероятностей для возможных состояний. Конкретные значения вектора текущего состояния определяются по результатам случайных испытаний. В результате проведения имитационного эксперимента получается одна из возможных реализации случайного многомерного процесса в заданном интервале времени (to, Tт).
Моделирующий алгоритм, основанный на принципе , применим для более широкого круга систем, чем алгоритм, построенный по принципу особых состояний. Однако при его реализации возникают проблемы с определением величины . Для моделирования ВС на системном уровне в основном применяется принцип особых состояний.
Контрольные вопросы
Общее определение имитационного моделирования.
Имитация функционирования ВС.
Алгоритм моделирование по принципу особых состояний.
Алгоритм моделирования по принципу временных приращений.
Литература
1. Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.
2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.
3. Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.
4. Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.
Лекция 13. МЕТОДЫ ИССЛЕДОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ (2 часа)
План
1. Методы определения характеристик вычислительных систем
2. Метод повторных экспериментов
3. Методы генерации случайных величин и последовательностей
1. Методы определения характеристик вычислительных систем
Измеряемые характеристики ВС. При имитационном моделировании можно измерять значения любых характеристик, интересующих исследователя. Обычно по результатам измерений вычисляют характеристики всей системы, каждого потока и устройства.
Для всей ВС производится подсчет поступивших в систему заявок, полностью обслуженных и покинувших систему заявок без обслуживания по тем или иным причинам. Соотношения этих величин характеризуют производительность ВС при определенной рабочей нагрузке.
По каждому потоку заявок могут вычисляться времена реакции и ожидания, количества обслуженных и потерянных заявок. По каждому устройству зачастую определяются время загрузки при обслуживании одной заявки и число обслуженных устройствам заявок, время простоя устройства в результате отказов и количество отказов, возникших в процессе моделирования, длины очередей и занимаемые емкости памяти.
При статистическом моделировании большая часть характеристик -- это случайные величины. По каждой такой характеристике у определяется N значений, по которым строится гистограмма относительных частот, вычисляются математическое ожидание, дисперсия и моменты более высокого порядка, определяются средние по времени и максимальные значения. Коэффициенты загрузки устройств вычисляются по формуле
(1)
где -- коэффициент загрузки k-го устройства; -- среднее время обслуживания одной заявки k-м устройством; Nok-- количество обслуженных устройством заявок за время моделирования Тт
Определение условий удовлетворения стохастических ограничений при имитационном моделировании производится путем простого подсчета количеств измерений, вышедших и не вышедших за допустимые пределы.
Расчет математического ожидания и дисперсии выходной характеристики. В случае анализа стационарного эргодического процесса функционирования системы вычисление математического ожидания и дисперсии характеристики у производится усреднением не по времени, а по множеству N значений, измеренных по одной реализации процесса достаточной продолжительности. В целях экономии основной памяти ВС, на которой проводится моделирование, математическое ожидание и дисперсия вычисляются в ходе моделирования путем наращивания итогов при появлении очередного измерения случайной характеристики по рекуррентным формулам. Математическое ожидание случайной величины у для ее n-го измерения уn:
(2)
где mn-1 -- математическое ожидание, вычисленное по предыдущим п -- 1 измерениям.
Дисперсия для n-го измерения:
(3)
где -- дисперсия, вычисленная по предыдущим п -- 1 измерениям. Вначале дисперсия принимается равной нулю.
При большом количестве измерений эти оценки являются состоятельными и несмещенными.
Расчет среднего по времени значения выходной характеристики. В процессе моделирования постоянно ведется подсчет длины очереди к каждому устройству и занимаемой емкости накопителей. При этом отслеживается максимальное значение и вычисляется среднее по времени значение. Например, средняя длина очереди вычисляется по формуле
(4)
Рис. 1. Временная диаграмма изменения длины очереди
где i -- номер очередного изменения состояния очереди (занесения заявки в очередь или исключения из очереди) (рис. 1); N--количество изменений состояния очереди; i; -- интервал времени от (i-1)-го до 1-го изменения состояния; li -- число заявок в очереди в интервале
По аналогичной формуле вычисляется средняя по времени используемая емкость накопителя:
(5)
где qi -- емкость накопителя, занятая в интервале времени между двумя последовательными, обращениями к накопителю.
Формулы (4) и (5) приводят к виду, удобному для вычисления путем наращивания итогов.
Построение гистограммы. Основное достоинство имитационного моделирования заключается в том, что по любой выходной характеристике может быть построена гистограмма относительных частот -- эмпирическая плотность распределения вероятностей, вне зависимости от сочетаний распределений параметров системы и внешних воздействий. При исследовании стационарной системы гистограмма строится по следующей методике.
Перед началом моделирования задаются предположительные границы изменения интересующей выходной характеристики y, т. е. нижний yH и верхний yB пределы, и указывается число интервалов гистограммы Ng. По этим данным вычисляется интервал
Затем в процессе моделирования по мере появления измерений характеристики у, определяется число попаданий этой случайной величины в i-й интервал гистограммы Ri; и подсчитывается общее число измерений N. По полученным данным вычисляется относительная частота по каждому интервалу:
Этих данных достаточно для построения гистограммы относительных частот: на оси абсцисс откладываются пределы изменения анализируемой характеристики у; весь диапазон изменения подразделяется на заданное число интервалов; над каждым t-м интервалом проводится отрезок, параллельный оси абсцисс, на расстоянии, равном Gi от оси абсцисс (рис. 2).
Отметим, что площадь гистограммы относительных частот равна единице, так же, как интеграл от плотности вероятности в пределах от минус до плюс бесконечности равен единице. Площадь гистограммы равняется сумме площадей прямоугольников, построенных на каждом i-ом интервале:
Рис. 2. Гистограмма относительных частот
поскольку общее число измерений характеристики у равно сумме чисел попаданий в каждый из интервалов:
При необходимости выдвигается гипотеза о том, что полученное эмпирическое распределение согласуется с некоторым теоретическим распределением, имеющим аналитическое выражение для функции или плотности распределения. Эта гипотеза проверяется по тому или другому критерию. Например, при использовании критерия хи-квадрат в качестве меры расхождения используется выражение
(6)
где pi -- определенная из выбранного теоретического распределения вероятность попадания случайной величины в i-й интервал.
Из теоремы Пирсона следует, что для любой функции распределения F(у) случайной величины у при N распределение величины имеет вид
(7)
где z -- значение случайной величины k = Ng --(r +1) -- число степеней свободы распределения хи-квадрат; r -- количество параметров теоретического закона распределения; Г (k/2) -- гамма-функция.
Функция распределения хи-квадрат табулирована по вычисленному значению и числу степеней свободы с помощью таблиц определяется вероятность (7). Если она превышает заданный уровень значимости С, то выдвинутая гипотеза принимается.
2. Метод повторных экспериментов
Характеристики нестационарных процессов. Для системы, процесс функционирования которой отличается от стационарного эргодического, нельзя вычислять вероятностные характеристики по одной реализации процесса, поскольку оценки могут получиться смещенными или несостоятельными. Следует ожидать, что если на ВС поступает поток заявок, интенсивность которого изменяется во времени, как это показано, например, на рис. 3. выходные характеристики такой системы относятся к нестационарным случайным функциям (процессам).
Известно, что в основе всех формальных методов лежит представление случайного процесса с помощью ансамбля реализации и описание его посредством характеристик, получаемых усреднением по ансамблю. Предположим, что случайный процесс Y(t) задан ансамблем реализации , а интересующая исследователя вероятностная характеристика в определяется предельным соотношением
(8)
где -- оператор преобразования, лежащий в основе определения характеристики -- количество реализации, по которым производится усреднение.
При усреднении по ограниченной совокупности реализации прямые измерения значений вероятностной характеристики в могут быть выполнены в соответствии с формулой
(9)
Полной вероятностной характеристикой случайного процесса может служить многомерная функция распределения вероятности мгновенных значений процесса. Случайный процесс Y(t) считается исчерпывающе описанным в вероятностном смысле на интервале , если задана его Nr- мерная функция распределения:
(10)
которая соответствует любому сочетанию моментов времени tr на интервале (О, Т) при произвольном Nr, в том числе при . Исходя из этих предпосылок, при исследовании стохастических систем необходимо получать для каждой выходной характеристики совокупности Ni реализации, причем по каждой реализации следует измерять значения no Nr сечениям (отсчетам), как это показано на рис. 3. Таким способом могут быть получены вероятностные оценки выходных характеристик, если они являются нестационарными или стационарными неэргодическими процессами.
Рис. 3. Реализации нестационарного случайного процесса
Алгоритм повторных экспериментов. При имитационном моделировании нестационарного режима функционирования ВС требуется получить ni реализации случайных процессов по всем выходным характеристикам. С этой целью необходимо проводить ni имитационных экспериментов в интересующей исследователя области определения случайных процессов (О, Т).
Изменение характера сочетаний случайных событий в каждом последующем эксперименте может быть достигнуто заменой начальных значений датчиков случайных чисел, используемых в процессе моделирования, в частности, для генерации управляющих последовательностей. Это можно реализовать, например, так: при каждом последующем эксперименте в качестве начальных значений датчиков случайных чисел используют последние значения предыдущего эксперимента.
Исследование систем с нестационарным режимом путем имитационного моделирования с применением метода повторных экспериментов сводится к следующему. Проводится Ni имитационных экспериментов. При каждом последующем эксперименте параметры системы и нагрузки устанавливаются на исходные значения и в процессе каждого эксперимента остаются неизменными или изменяются по одним и тем же зависимостям. Датчики случайных чисел устанавливаются в начальное состояние только один раз -- перед моделированием и до конца моделирования вырабатывают последовательности случайных чисел.
Рис. 4. Алгоритм моделирования по методу повторных экспериментов
Период моделирования Тm по каждому эксперименту разделяется на Nr сечений. Интервал времени моделирования между двумя соседними сечениями будем называть прогоном. В каждом эксперименте для фиксированных моментов времени определяются численные значения выходных характеристик.
По каждому i-му сечению для всех выходных характеристик может определяться эмпирическая многомерная функция или плотность распределения, оцениваться математическое ожидание my(tr), корреляционная функция или дисперсия Dy (tr) по всей совокупности Ni реализации.
Для обеспечения статистической достоверности результатов обычно требуется проведение нескольких сотен или тысяч экспериментов с измерением и обработкой вектора выходных характеристик по нескольким десяткам сечений. Очевидно, что выполнение этой работы «вручную» не представляется возможным в приемлемые сроки. Это означает, что на ВС должно быть возложено не только проведение имитации, но и реализация метода повторных экспериментов.
Машинный алгоритм повторных экспериментов представлен на рис. 4. В первом блоке выполняется ввод данных о моделируемой системе и нагрузке, а также производится инициализация программы. Отдельно выделен блок настройки датчиков случайных чисел, чтобы подчеркнуть, что датчикам задаются начальные значения до основных циклов моделирования. В дальнейшем датчики вырабатывают неповторяющиеся последовательности случайных чисел. Затем вводятся и размещаются в соответствующих массивах и переменных исходные данные. В частности, задаются количества прогонов Nr, экспериментов Ni и период моделирования Тm.
В следующем блоке выполняется имитационное моделирование процесса функционирования так, как это описано в п. 2, по тому или другому алгоритму. В ходе имитации изменяются значения тех переменных параметров, которые заданы как функции времени, и постоянно отслеживается достижение конца прогона, т. е. событие, когда текущее модельное время станет равным tr. При выполнении этого условия определяются, вычисляются и запоминаются статистические данные по r-му сечению, после чего имитация продолжается.
Если выполнено Nr прогонов, т. е. завершен очередной эксперимент, формируется номер следующего эксперимента и управление передается блоку подготовки исходных данных. После проведения Ni экспериментов завершается обработка и вывод результатов моделирования.
Расчет характеристик по методу повторных экспериментов. При анализе систем с нестационарным процессом функционирования путем имитационного моделирования с использованием метода повторных экспериментов для каждой выходной характеристики, которая является случайным процессом, зачастую оценивается математическое ожидание, корреляционная функция или дисперсия, а также могут быть построены по каждому сечению гистограммы, чем определяется многомерная плотность распределения вероятностей.
Математическое ожидание случайного процесса Y (t) -- это неслучайная функция ту(t), которая при каждом значении аргумента tr представляет собой математическое ожидание соответствующего сечения случайной функции:
Корреляционная функция случайного процесса -- это тоже неслучайная функция двух аргументов Ку(t, t'), которая при каждой паре значений аргументов t,t' равна корреляционному моменту соответствующих сечений случайной функции:
При равенстве t=t' корреляционная функция превращается в дисперсию случайной функции:
В соответствии с формулой (9) Nr-мерная плотность распределения вероятностей оценивается по формуле:
(11)
где значения функции равны 1 при и равны 0, если хотя бы одно из этих неравенств для i-й реализации не выполняется.
В результате вычисления по формуле (11) получается многомерная плотность распределения вероятностей, подобная той, которая изображена на рис. Важно отметить, что для проверки выполнения стохастических ограничительных условий нет необходимости вычислять плотность распределения по формуле (11), а достаточно подсчитать общее количество Ny и количество Np значений измерения случайной величины, попадающих между ограничивающими пределами, по всей совокупности экспериментов, а затем определить вероятность выполнения ограничительного условия:
Py=NP/Ny (12)
При моделировании вычисления результатов производятся в конце каждого прогона путем наращивания итогов. В частности, количественные вероятностные значения таких выходных характеристик, как длины очередей к каждому устройству, времена реакции по каждому потоку заявок и времена загрузки каждого устройства, определяются по r-му сечению для i-го эксперимента по следующим формулам. Оценка математического ожидания длины очереди к устройству:
(13)
где Li-1 -- математическое ожидание длины очереди за предыдущие (i-1) экспериментов; li -- длина очереди по r-му сечению для i-го эксперимента.
Дисперсия длины очереди
где D[Li-1] -- дисперсия длины очереди за предыдущие (i -- 1) экспериментов; в первом эксперименте дисперсия принимается равной нулю.
По временам реакции и загрузки при достаточно большом количестве сечений, когда процесс можно считать стационарным на протяжении одного прогона, текущие значения математических ожиданий и дисперсии вычисляются по формулам (2) и (3) соответственно. Тогда в r-м сечении i-го эксперимента оценка математического ожидания времени загрузки каждого устройства при обслуживании одной заявки:
где Vi-1 -- математическое ожидание времени загрузки за предыдущие (i-- 1) экспериментов; Nz(i-1) -- число загрузок устройства на r-м прогоне по предыдущим (i -- 1) экспериментам; -- математическое ожидание времени загрузки на r-м прогоне в i-м эксперименте; nzi -- число загрузок устройства на r-м прогоне в i-м эксперименте.
Дисперсия времени загрузки каждого устройства на r-м прогоне
где D [Vi-1] -- дисперсия, вычисленная по предыдущим (i -- 1) экспериментам; di --дисперсия, вычисленная в i-м эксперименте.
Коэффициенты загрузки устройств вычисляются по формуле (1).
Оценки математического ожидания и дисперсии времени реакции Ui по каждому потоку в r-м сечении i-го эксперимента выполняются по формулам, аналогичным (15) и (16). Для экономии места в памяти моделирующей ВС обновленные статистические характеристики по r-му сечению записываются на место прежних, вычисленных в (i -- 1) эксперименте.
3. Методы генерации случайных величин и последовательностей
Датчики равномерно распределенных случайных чисел. При статистическом моделировании стохастических систем возникает необходимость в определении случайных событий, величин и последовательностей по заданным статистическим характеристикам. В основе их определения лежит использование последовательности чисел, равномерно распределенных в интервале (0,1). Программы ВС, формирующие такие последовательности, называют датчиками или генераторами случайных чисел.
Для получения последовательности равномерно распределенных случайных чисел с помощью ВС часто используется мультипликативный способ. Случайные числа получаются из рекуррентного соотношения
(17)
где А, С -- константы; М -- достаточно большое положительное целое число.
При соответствующем выборе констант и задании некоторого начального значения эта формула позволяет получать последовательность целых чисел, равномерно распределенных в интервале (0, М -- 1). Последовательность имеет период повторения, равный М. Поэтому точнее называть числа псевдослучайными. Случайные числа, равномерно распределенные в интервале (0,1), находятся масштабным преобразованием полученных целых чисел.
Моделирование случайных событий и дискретных величин. Для моделирования случайного события X, наступающего с вероятностью Р, берется значение случайного числа, равномерно распределенного на интервале (0,1), и сравнивается с Р. Если Р, то считается, что произошло событие X.
Предположим, что дискретная случайная величина Y может принимать значения y1, …, yn вероятностями р1, ..., рп.. При этом
.
Тогда берется значение случайного числа, распределенного равномерно на интервале (0, 1), и определяется такое k, принадлежащее совокупности (1, n), при котором удовлетворяется неравенство
Тогда случайная величина Y принимает значение уk..
Моделирование случайных непрерывных величин. Пусть непрерывная случайная величина Y имеет произвольный закон распределения. Предположим, что она задается эмпирической плотностью распределения f* (у) -- гистограммой (рис. 5, а). Из гистограммы определяется эмпирическая функция распределения F* (у) -- дискретная кумулятивная функция (рис. 5, б) для середин интервалов группирования случайной величины в пределах (ymin, y max).
Для определения одного конкретного значения случайной величины Y берется значение б случайного числа, равномерно распределенного на интервале (0, 1). Затем находится такое k, при котором
Рис. 5. Графики для определения значения случайного числа по дискретной и интегральной функции распределения
Тогда искомое случайное число равно yk (рис. 5, б). Это же правило применимо и при задании случайной непрерывной величины интегральной функцией распределения F (у), как показано на рис. 5, в. Оно вытекает из теоремы: если случайная величина Y имеет плотность распределения F (у), то ее распределение
(18)
является равномерным на интервале (0, 1).
Для некоторых законов распределения (экспоненциальный, Эрланга) имеются простые аналитические зависимости у = Ф (). Например, пусть требуется получить конкретное значение случайного числа Y с экспоненциальным законом распределения. Подставим в формулу (18) а и плотность распределения:
После интегрирования получается
Разрешая это уравнение относительно уk,, имеем
Учитывая, что если случайная величина подчинена равномерному закону распределения в интервале (0, 1), то случайная величина также имеет равномерный закон распределения в интервале (0, 1), последнее соотношение можно заменить следующим:
(19)
Процедура определения конкретного значения случайного числа с заданным законом распределения называется случайным испытанием или «бросанием жребия».
Моделирование случайных процессов сводится на практике к определению последовательностей случайных величин. Исходными данными являются функции распределения, определенные в требуемые моменты времени, и последовательность случайных чисел подчиняющаяся равномерному закону распределения в интервале (0, 1). Конкретные значения случайных процессов в нужные моменты времени находят по изложенным выше правилам.
В большом числе публикаций, рассматриваются вопросы алгоритмизации, программирования и исследования качества датчиков случайных чисел.
В процессе статистического моделирования существует необходимость в частом обращении к датчикам случайных чисел. С их помощью формируются конкретные значения случайных параметров каждой заявки, параметров обслуживания заявки каждым устройством; определяются пути продвижения заявки по тому или иному маршруту при вероятностной дисциплине маршрутизации и т. д. Имитационное моделирование систем по принципу особых состояний проводится с постоянным использованием датчиков случайных чисел для формирования всех управляющих последовательностей.
Контрольные вопросы
Измеряемые характеристики ВС.
Основные формулы для расчета выходных характеристик ВС.
Методика построения гистограммы и ее использование для исследования ВС.
Основная идея метода повторных экспериментов.
Что понимается под датчиком случайных величин?
Какие методы (алгоритмы, программы) генерации последовательностей случайных величин вы знаете?
Примеры использования датчиков случайных чисел.
Литература
1. Альянах И.Н. Моделирование вычислительных систем, Л.: Машиностроение, 1988 г. - 223 стр.
2. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука, 1980 г. - 208 стр.
3. Зобов Б.И., Сурков А.В. Основы моделирования вычислительных систем. М.: МЛТИ, 1982 г. -32 стр.
4. Масков А.И. моделирование вычислительных систем. Пермь: ПГУ, 1982 г. - 95 стр.
Лекция 14. МОДЕЛИ ЛИНЕЙНОГО БУЛЕВА ПРОГРАММИРОВАНИЯ (2 часа)
План
1. Модели линейной дискретной оптимизации с булевыми переменными
2. Преобразование задачи с дискретными переменными к задаче с булевыми переменными
3. Преобразование задачи линейного булева программирования к задаче нелинейного булева программирования
1. Модели линейной дискретной оптимизации с булевыми переменными
Задача оптимизации линейной целевой функции с булевыми переменными и линейными ограничениями является одной из самых распространенных моделей дискретного программирования. Комбинаторные задачи с булевыми переменными, принимающими значения 0 или 1, встречаются при решении многих практических проблем из экономики, проектирования, управления и других областей.
Задача оптимизации (минимизации или максимизации) линейной целевой функции с булевыми переменными и линейными ограничениями в общем виде описывается с помощью одной из следующих моделей линейного булева программирования:
I. Модель А - для задачи минимизации
(1)
(2)
II. Модель В - для задачи максимизации
(3)
(4)
т.е. требуется минимизировать или максимизировать линейную целевую функцию q(x) по булевым переменным xj{0,1} при выполнении условия, задаваемого системой линейных неравенств вида (2) или (4).
Проблема отыскания решения задачи (1), (2) или (3), (4) может в принципе решаться с применением метода полного перебора, суть которого заключается в переборе всех булевых векторов заданной длины, проверке для каждого вектора выполнения линейных ограничений, вычислении значений целевой функции для допустимых векторов и выборе из них минимального или максимального значения целевой функции. Однако решение, полученное методом полного перебора, связано с большим объемом вычислений, который неосуществим при больших размерностях задачи даже на сверхпроизводительных ЭВМ. Так как каждая из n компонент независимо от других может принимать два значения 0 или 1, поэтому общее число булевых векторов длины n равно 2n.
Это величина и характеризует сложность алгоритма полного перебора. В связи с тем, что для большинства задач дискретной оптимизации полный перебор неосуществим, были разработаны различные методы неявного перебора, которые обеспечивают нахождение точного решения без пересмотра всех булевых векторов. Такими являются различные варианты метода отсечений, метода ветвей и границ, метода динамического программирования. Но опыт применения этих методов при решении реальных задач с достаточно большим числом переменных показал, что многие задачи линейного программирования с булевыми переменными еще являются нерешаемыми на ЭВМ из-за нехватки машинного времени. Следовательно, с ростом размера задачи n она становится "труднорешаемой", т.е. практически неразрешимой.
Подобные документы
Имитационное моделирование как один из наиболее широко используемых методов при решении задач анализа и синтеза сложных систем. Особенности имитационного моделирования систем массового обслуживания. Анализ структурной схемы системы передачи пакетов.
курсовая работа [1,2 M], добавлен 28.05.2013Язык GPSS как один из наиболее эффективных и распространенных языков моделирования сложных дискретных систем. Транзакт - элемент системы массового обслуживания. Решение задач на основе моделирования с применением языка GPSS, создание имитационной модели.
курсовая работа [54,7 K], добавлен 25.11.2010Программные средства имитационного моделирования систем массового обслуживания. Программная среда Matlab, ее структура и основные компоненты, функциональные особенности, а также назначение. Разработка подсистем моделирования. Инструкция пользователя.
дипломная работа [3,3 M], добавлен 10.07.2017Определение функциональных характеристик систем массового обслуживания (СМО) на основе имитационного моделирования; синтез СМО с заданными характеристиками. Разработка программы на языке SIMNET II; расчет процесса работы СМО; подбор требуемого параметра.
лабораторная работа [623,8 K], добавлен 11.03.2011Характеристика электрических систем в установившихся режимах. Классификация кибернетических систем. Развитие методов моделирования сложных систем и оптимизация на электронных вычислительных машинах моделей в алгоритмическом и программном аспекте.
реферат [27,3 K], добавлен 18.01.2015Основные сведение о системе моделирования GPSS и блоки, используемые при моделировании одноканальных и многоканальных систем массового обслуживания. Разработка модели работы ремонтного подразделения в течение суток с использованием программы GPSS World.
курсовая работа [36,4 K], добавлен 11.02.2015Структурно-информационный анализ методов моделирования динамических систем. Математическое моделирование. Численные методы решения систем дифференциальных уравнений. Разработка структуры програмного комплекса для анализа динамики механических систем.
дипломная работа [1,1 M], добавлен 14.05.2010Математическое описание имитационной модели. Описание блок-схемы алгоритма. Анализ полученных результатов имитационного моделирования. Сопоставление полученных результатов для разработанных моделей. Математическое описание аналитического моделирования.
курсовая работа [306,5 K], добавлен 25.03.2015Концептуальная модель процесса обслуживания покупателей в магазине. Описание системы моделирования GPSS. Разработка моделирующей программы на специализированном языке имитационного моделирования в среде AnyLogic. Результаты вычислительных экспериментов.
курсовая работа [906,9 K], добавлен 12.07.2012Моделирование как основная функция вычислительных систем. Разработка концептуальной модели для системы массового обслуживания и ее формализация. Аналитический расчет и алгоритмизация модели, построение блок-диаграмм. Разработка и кодирование программы.
курсовая работа [164,8 K], добавлен 18.12.2011
