Компьютерное моделирование

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

Системный подход при составлении математических моделей (рис. 1.1) начинается с формулировки главной цели моделирования (главной цели функционирования системы). Затем на основе исходных данных формулируются требования, которым должна удовлетворять математическая модель. На основе этих требований из модели вычленяются ее отдельные элементы и описываются уравнениями. Как правило, элементы модели представляют собой реальные элементы реального объекта.

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

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

Рис. 2.3. Схематическое изображение системного подхода (Ц - главная цель; Д - исходные данные; Т - требования к модели; Э - элементы модели; М - математическая модель; О.С. - обратная связь (1-й контур); К.В. - критерий выбора (2-й контур обратной связи).

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

1. Саморегуляция - возможность проверки математической модели на соответствие исходной цели (обеспечивается первым контуром ОС).

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

2.2.2 Основные понятия математического моделирования экономических систем

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

Процесс решения экономических задач осуществляется в несколько этапов:

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

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

На заключительном этапе производится эксплуатация модели и получение результатов.

Таким образом, решение задачи включает следующие этапы:

1. Содержательная постановка задачи.

2. Системный анализ.

3. Системный синтез (математическая постановка задачи)

4. Разработка или выбор программного обеспечения.

5. Решение задачи.

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

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

2.2.3 Методы аналитического, имитационного и натурного моделирования

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

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

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

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

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

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

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

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

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

Контрольные вопросы

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

Что такое модель?

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

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

Сформулируйте основные этапы построения модели при системном подходе.

Назовите функции моделей.

Каковы этапы процесса решения экономических задач?

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

Тема 3. Процессы массового обслуживания в моделировании продуктов питания из растительного сырья

3.1 Метод Монте-Карло

3.1.1 Вводные замечания

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

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

Термин "метод Монте-Карло" (предложенный Дж. Фон Нейманом и С. М. Уламу в 1940-х) относится к моделированию процессов с использованием генератора случайных чисел. Термин Монте-Карло (город, широко известный своими казино) произошел от того факта, что "число шансов" (методы моделирования Монте-Карло) было использовано с целью нахождения интегралов от сложных уравнений при разработке первых ядерных бомб (интегралы квантовой механики). С помощью формирования больших выборок случайных чисел из, например, нескольких распределений, интегралы этих (сложных) распределений могут быть аппроксимированы из (сгенерированных) данных.

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

Отечественные работы по методу Монте-Карло появились в 1955-1956 гг. За два десятилетия накопилась обширная библиография по методу Монте-Карло, которая насчитывает более 2000 названий. При этом даже беглый просмотр названий работ позволяет сделать вывод о применимости методы Монте-Карло для решения прикладных задач из большого числа областей науки и техники.

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

Метод Монте-Карло оказал и продолжает оказывать существенное влияние на развитие метода вычислительной математики (например, развитие методов численного интегрирования) и при решении многих задач успешно сочетается с другими вычислительными методами и дополняет их. Его применение оправдано в первую очередь в тех задачах, которые допускают теоретико-вероятностное описание. Это объясняется как естественностью получения ответа с некоторой заданной вероятностью в задачах с вероятным содержанием, так и существенным упрощением процедуры решения. Трудность решения той или иной задачи на ЭВМ определятся в значительной мере трудностью переложения ее на «язык» машины. Создание языков автоматического программирования существенно упростило один из этапов этой работы. Наиболее сложными этапами поэтому в настоящее время являются: математическое описание исследуемого явления, необходимые упрощения задачи, выбор подходящего численного метода, исследование его погрешности и запись алгоритма. В тех случаях, когда имеется теоретико-вероятностное описание задачи, использование метода Монте-Карло может существенно упростить упомянутые промежуточные этапы. Впрочем, как будет следовать из дальнейшего, во многих случаях полезно и для задач строго детерминированных строить вероятностную модель (рандомизовать исходную задачу) с тем, чтобы далее использовать метод Монте-Карло.

3.1.2 Общая схема метода Монте-Карло

Предположим, что нам требуется вычислить некоторую неизвестную величину m, и мы хотим сделать это, рассматривая случайную величину такую, что ее математическое ожидание М, = m. Пусть при этом дисперсия данной случайной величины D = b.

Рассмотрим N случайных независимых величин,,…, распределения которых совпадают с распределением рассматриваемой случайной величины о. Согласно центральной предельной теореме теории вероятностей, распределение суммы =о1+ о2+…+оN будет приблизительно нормальным со средним, равным м= Nm, и дисперсией у2 = Nb2. Согласно «правилу трех сигма», каковы бы ни были m и s,

Р{м - Зу< сN< м+ Зу} = 0.997,

т. е.

Последнее соотношение можно переписать в виде



Полученная формула дает метод расчета т и оценку погрешности этого метода.

Сущность применения метода Монте-Карло заключается в определении результатов на основании статистики, получаемой к моменту принятия некоторого решения.

Например. Пусть Е1 и Е2 -- две единственно возможные реализации некоторого случайного процесса, причем p1 - вероятность исхода Е1, а р2 = 1 - p1 -- вероятность исхода Е2. Чтобы определить, какое из двух событий, e1 или Е2, имеет место в данном случае, возьмем в интервале между 0 и 1 случайное число и, равномерно распределенное в интервале (0, 1), и произведем испытание. Исход Е1 будет иметь место, если , а исход Е2 -- в противном случае.

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

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

гк+1 = F(гk),

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

Использование равномерно распределенных случайных чисел составляет основу моделирования с помощью метода Монте-Карло. Можно сказать, что если некоторая случайная величина была определена с помощью метода Монте-Карло, то для ее вычисления использовалась последовательность равномерно распределенных случайных чисел.

Равномерно распределенные случайные числа заключены в интервале от 0 до 1 и выбираются случайным образом в соответствии с функцией распределения

F(x) = Рr{Х< х} = х, .

При этом распределении одинаково правдоподобно по явление любых значений случайной величины в интервале (0, 1). Здесь Рг{Х< х} -- вероятность того, что случайная величина X примет значение меньше х.

Основным методом получения случайных чисел является их генерация по модулю. Пусть m, a, с, х0 -- целые числа, такие, что m > х0 и а, с, х0 > 0. Псевдослучайное число хi из последовательности {хi} получается с помощью рекуррентного соотношения

xi = а * xi-1 + с (mod m).

Стохастические характеристики генерируемых чисел решающим образом зависят от выбора m, а и с. Их неудачный выбор приводит к ошибочным результатам при моделировании методом Монте-Карло.

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

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

Существует быстрый тест, с помощью которого необходимо проверять каждый генератор. Качество генератора случайных чисел можно продемонстрировать, заполняя полностью d-мерную решетку (например, двух- или трехмерную). Хороший генератор должен заполнить все пространство гиперкуба.

Другой приближенный способ проверки равномерности распределения N случайных чисел хi состоит в вычислении их математического ожидания и дисперсии. Согласно этому критерию, для равномерного распределения должны выполняться условия

и

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

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

В начале программы целой переменной X присваивается некоторое значение Х0. Затем случайные числа генерируются по правилу

X = (аХ + с) mod m. (1)

Выбор параметров следует осуществлять, пользуясь следующими основными принципами.

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

2.Число m должно быть большим, например, 230 (поскольку именно это число определяет период генерируемой псевдослучайной последовательности).

3.Если m -- степень двойки, выбирают а таким, чтобы amod8 = 5. Если m -- степень десяти, выбирают а таким, чтобы amod10 = 21. Такой выбор гарантирует, что генератор случайных чисел будет вырабатывать все m возможных значений, прежде чем они начнут повторяться.

4.Множитель а предпочтительнее выбирать лежащим между 0.01m и 0.99m, и его двоичные или десятичные цифры не должны иметь простую регулярную структуру. Множитель должен пройти спектральный критерий и, желательно, еще несколько критериев.

5.Если a -- хороший множитель, значение с не существен но, за исключением того, что с не должно иметь общего множителя с m, если m -- размер компьютерного слова. Можно, например, выбрать с = 1 или с = а.

6. Можно генерировать не больше m/1000 случайных чисел. После этого должна использоваться новая схема, например, новый множитель а.

Перечисленные правила, главным образом, относятся к машинному языку программирования. Для языка программирования высокого уровня, например С++, часто используют другой вариант (1): выбирается простое число m, близкое к наибольшему легко вычисляемому целому числу, значение а полагается равным первообразному корню из m, а с берется равным нулю. Например, можно принять a = 48271 и т = 231 - 1.

3.1.3 Пример расчета системы массового обслуживания методом Монте-Карло

Рассмотрим простейшую систему массового обслуживания (СМО), которая состоит из n линий (иначе называемых каналами или пунктами обслуживания). В случайные моменты времени в систему поступают заявки. Каждая заявка поступает на линию № 1. Если в момент поступления за явки Тк эта линия свободна, заявка обслуживается время t3 (время занятости линии). Если линия занята, заявка мгновенно передается на линию № 2 и т. д. Если все n линий в данный момент заняты, то система выдает отказ.

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

Для подобных систем практически единственным методом расчета является метод Монте-Карло.

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

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

=-ln (2)

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

Каждой линии ставится в соответствие ячейка ЭВМ, в которую записывается момент освобождения линии. Пусть в момент времени Т1, который мы примем за начало чета, все линии свободны. За время окончания расчета примем Ткон = Т 1+ Т.

Первая заявка поступает на линию № 1 и тут же обслуживается, поскольку линия свободна. Следовательно, в течение времени t3 эта линия будет занята. Поэтому заменяем t1 на новое значение:

t1 Т1 + t3

и добавляем 1 к счетчику выполненных заявок. Затем переходим к рассмотрению следующей заявки. Для этого генерируем значение , равномерно распределенное на [0, 1], и по формуле (2) вычисляем очередное значение = 2. Вычисляем момент поступления второй заявки:

T2=T1+2.

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

t1T2.

Если это условие выполнено, линия свободна и приступает к обслуживанию второй заявки. Заменяем t1 на Т2 + t3, добавляем 1 к счетчику выполненных заявок и переходим к рассмотрению следующей заявки.

Если линия занята, то проверяем, свободна ли вторая линия, и т. д. Если в какой-то момент времени заняты все линии, добавляем 1 в счетчик отказов и переходим к выполнению следующей заявки.

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

Tk>Tкон.

Если это условие выполнено, опыт заканчивается.

Такой опыт повторяется N раз, и результаты всех опытов усредняются.

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

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

3.1.4 Генерация последовательности случайных чисел

Существует три способа генерации случайных чисел:

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

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

Программный (алгоритмический) - случайные числа формируются с помощью специальных программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ. Этот способ наиболее распространен.

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

Непрерывная случайная величина имеет равномерное распределение в интервале (a,b), если ее функции плотности и распределения соответственно примут вид

Для получения случайных чисел на ЭВМ используются алгоритмы, поэтому такие последовательности, являющиеся по сути детерминированными, называются псевдослучайными. ЭВМ оперирует n-разрядными числами, поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала (0,1) используют дискретную последовательность 2n случайных чисел того же интервала - закон распределения такой дискретной последовательности называется квазиравномерны распределением.

Требования к идеальному генератору случайных чисел:

Последовательность должна состоять из квазиравномерно распределенных чисел.

Числа должны быть независимыми.

Последовательности случайных чисел должны быть воспроизводимыми.

Последовательности должны иметь неповторяющиеся числа.

Последовательности должны получаться с минимальными затратами вычислительных ресурсов.

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

xi+1=Ф(xi),

представляющие собой реккурентные соотношения первого порядка.

Например. x0 = 0,2152 , (x0)2=0,04631104 , x1 = 0,6311 , (x1)2=0,39828721, x2=0,8287 и т.д.

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

x0 = 0,4500 , (x0)2=0,20250000, x1 = 0,2500 , (x1)2=0,06250000, x2=0,2500 и т.д.

Широкое применение получили конгруэнтные процедуры генерации псевдослучайных последовательностей.

Два целых числа и конгруэнтны (сравнимы) по модулю m, где m - целое число, тогда и только тогда, когда существует такое целое число k, что -=km.

19844 (mod 10), 50088 (mod 103).

Большинство конгруэнтных процедур генерации случайных чисел основаны на следующей формуле:



где - неотрицательные целые числа.

По целым числам последовательности {Xi} можно построить последовательность {xi}={Xi/M} рациональных чисел из единичного интервала (0,1).

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

Методы улучшения качества последовательностей случайных чисел:

Использование рекуррентных формул порядка r:

Но применение этого способа приводит к увеличению затрат вычислительных ресурсов на получение чисел.

Метод возмущений:

.

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

1. Необходимо реализовать случайное событие А, наступающее с заданной вероятностью p. Определим А как событие, состоящее в том, что выбранное значение xi равномерно распределенной на интервале (0,1) случайной величины удовлетворяет неравенству:

xi =<p.

Тогда вероятность события А будет Противоположное событие состоит в том, что xi >p, его вероятность равна 1-р.

2. Рассмотрим группу событий. Пусть А1, А2 ,..., Аs - полная группа событий, наступающих с вероятностями p1, p2 ,..., ps соответственно. Определим событие Аm как событие, состоящее в том, что выбранное значение xi случайной величины удовлетворяет неравенству

,

где

Процедура моделирования испытаний в этом случае состоит в последовательном сравнении случайных чисел xi со значениями lr. Если условие выполняется, исходом испытания оказывается событие Аm .

3. Рассмотрим независимые события А и В с вероятностями наступления рА и рВ. Возможными исходами совместных испытаний в этом случае будут события АВ, с вероятностями рАрВ, (1-рА)рВ, рА(1-рВ), (1-рА)(1-рВ). Для моделирования совместных испытаний можно использовать два варианта процедуры:

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

Определение одного из исходов АВ, по жребию с соответствующими вероятностями, т.е. процедура, рассмотренная в п.2.

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

4. События А и В являются зависимыми и наступают с вероятностями pА и pВ . Обозначим через pА(В) условную вероятность наступления события В при условии, что событие А произошло.

Контрольные вопросы

Как можно определить метод Монте-Карло?

Практическое значение метода Монте-Карло.

Общая схема метода Монте-Карло.

Пример расчета системы массового обслуживания методом Монте-Карло.

Способы генерации случайных чисел.

Каковы требования к идеальному генератору случайных чисел?

Методы улучшения качества последовательностей случайных чисел.

3.2 Основные понятия теории массового обслуживания

3.2.1 Основные понятия теории массового обслуживания

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

Элементами системы являются ее составные части, имеющие самостоятельную характеристику надежности.

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

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

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

По определению, система массового обслуживания состоит из следующих элементов:

Входящего потока требований.

Каналов обслуживания.

Очереди требований, ожидающих обслуживания.

Выходящего потока требований.

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

Рис. 3.1 Основные элементы системы массового обслуживания

Все СМО принято делить на три типа - системы с отказами (потерями), системы с ожиданием и смешанные системы

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

К числу обслуживающих систем можно, например, отнести АТС, городской транспорт, учреждения бытового обслуживания и т.д.

Под требованием понимается запрос на выполнение какого-либо вида обслуживания. (Заявка на перевозку пассажиров, материальных средств и т.п. служит требованием на их обслуживание.)

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

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

Удовлетворение требования составляет процесс обслуживания. Например, доставка пассажиров является процессом обслуживания.

Обслуживаемая система, в свою очередь, делится на обслуженную и необслуженную системы.

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

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

Потоки объектов обслуживания делятся на входящие и выходящие.

Совокупность объектов, поступающих в обслуживающую систему, принято считать входящим потоком объектов обслуживания.

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

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

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

В практике пассажирских перевозок в обслуживающую систему, как правило, объекты поступают из ограниченного источника. К примеру, конечным источником поступления объектов обслуживания являются пассажиры.

В системах массового обслуживания с отказами не имеет значения, из какого источника поступают объекты на обслуживание.

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

3.2.2 Классификация систем массового обслуживания

Системы массового обслуживания делятся на типы или классы по ряду признаков. На рис. 2 показана краткая классификация СМО. Рассмотрим ее.



Рис. 3.2. Классификация систем массового обслуживания

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

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

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

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

СМО с очередью подразделяются на разные виды в зависимости от того, как организована очередь - ограничена она или не ограничена. Ограничения могут быть по длине очереди или по времени ожидания.

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

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

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

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

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

3.2.3 Потоки событий

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

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

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

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

Будем изображать поток событий последовательностью точек на оси времени как показано на рис. 3. Пользуясь таким изображением, не надо забывать, что положение каждой точки на оси абсцисс случайно.

Рис. 3.3

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

На практике наиболее распространены случайные потоки событий, для которых момент наступления событий и промежутки времени между ними случайны.

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

- последовательностью моментов времени поступления заявок;

- последовательностью промежутков времени между заявками;

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

На данной лекции мы рассмотрим потоки событий, обладающие некоторыми особо простыми свойствами. Для этого введем ряд определений.

1. Поток событий называется стационарным, если вероятность попадания того или иного числа событий на участок времени длиной t зависит только от длины участка и не зависит от того, где именно на оси времени расположен этот участок.

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

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

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

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

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

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

Ординарность потока означает, что события в потоке приходят поодиночке, а не парами, тройками и т.д.

Ординарным называется поток заявок, для которого выполняется условие:



где Рk(t, t+) - вероятность появления двух и более заявок за промежуток времени (t, t+).

Ординарность потока отражает практическую невозможность поступления более одной заявки в любой момент времени t.

Если в неординарном потоке события происходят только парами, только тройками и т.д., то можно его рассматривать как ординарный поток пар, поток троек событий и т.д. Несколько сложнее обстоит дело, если число событий, образующих "пакет" (группу одновременно приходящих событий) случайно. Тогда приходится наряду с потоком пакетов рассматривать случайную величину Х - число событий в пакете, и математическая модель потока становится более сложной. Такой поток представляет собой не только последовательность моментов появления пакетов, но и последовательность случайных величин - чисел событий в каждом пакете, где x1, x2,..., xi,... - значения, принятые случайной величиной Х в первом, втором и т.д. пакетах. Пример неординарного потока событий со случайным числом событий в пакете - поток многопакетных сообщений, передаваемых в сетях передачи данных с коммутацией пакетов.

3.2.4 Простейший поток и его свойства

Рассмотрим поток событий, обладающий тремя свойствами: стационарностью, отсутствием последействия, ординарностью. Такой поток называется простейшим или стационарным пуассоновским потоком. Название «простейший» связано с тем, что математическое описание событий, связанных с простейшими потоками, оказывается наиболее простым. Отметим, что самый простой, на первый взгляд, регулярный поток со строго постоянными интервалами между событиями отнюдь не является «простейшим» в вышеназванном смысле слова: он обладает ярко выраженным последействием, так как моменты появления событий связаны между собой жесткой функциональной зависимостью. Именно из-за этого после действия анализ процессов, связанных с регулярными потоками, оказывается, как правило, труднее, а не легче по сравнению с простейшими.

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

Если поток событий не имеет последствия, ординарен, но не стационарен, он называется нестационарным пуассоновским потоком.

В таком потоке интенсивность = (t), (среднее число событий в единицу времени) зависит от времени.

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

Контрольные вопросы

Что понимается под системой массового обслуживания?

Каковы основные элементы системы массового обслуживания?

Что составляет процесс обслуживания?

Что такое требование (заявка)?

Что называется потоком событий?

Что такое задержка?

Какими тремя условиями определяется простейший поток?



Тема 4. Типовые системы компьютерного моделирования

4.1 Инструментальные средства компьютерного моделирования

4.1.1 Модельное время

Одной из наиболее важных задач при создании модели является реализация двух функций:

1) корректировка временной координаты состояния системы ("продвижение" времени, организация "часов");

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

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

Модельное время - это виртуальное время, в котором автоматически упорядочиваются все события, причем не обязательно пропорционально реальному времени, в котором развивается моделируемый процесс. Например:

реальное время развития процесса - 3 года;

модель процесса, охватывающая эти 3 года, выполняется на компьютере за 1 с,

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

...