Реферат: Методические указания ф со пгу 18. 2/05 Министерство образования и науки

Методические указания





Ф СО ПГУ 7.18.2/05
Министерство образования и науки Республики Казахстан

Павлодарский государственный университет им. С. Торайгырова


Кафедра информатики и информационных систем


Опорный конспект лекции


дисциплины Основы компьютерного моделирования


для специальностей 050703 Информационные системы


Павлодар



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





Форма

Ф СО ПГУ 7.18.1/05



УТВЕРЖДАЮ
Декан ФФМиИТ

_________ Тлеукенов С.К.

"___" __________200__г.



^ Составители: доцент Даутова А.З., ст.преподаватель Бельгибаева С.А, преподаватель Оспанова Г.А.

Кафедра «Информатика и информационные системы»

Опорный конспект лекции

по дисциплине «Основы компьютерного моделирования»


для студентов специальностей 050703 Информационные системы,


Рекомендована на заседании кафедры от “__28__”_августа__2008г.

Протокол № __1_
Заведующая кафедрой ___________ Ж.К.Нурбекова

Одобрена методическим советом факультета Физики, математики и информационных технологий “_1_”__сентября____2008г. Протокол №_1__

Председатель МС__________________________ А.З. Даутова
^ Аналитико-имитационный аппарат компьютерного моделирования. Метод Монте-Карло. Случайные числа и принцип их моделирования. Метод усечения. Конгруэнтный метод. Метод суммирования. Анализ последовательности случайных чисел. Критерии качества последовательностей случайных чисел. Метод возмущения.


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

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

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

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

Формы представления модели

инвариантная - запись соотношений модели с помощью традиционного математического языка безотносительно к методу решения уравнений модели;

аналитическая - запись модели в виде результата аналитического решения исходных уравнений модели;

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

схемная (графическая) - представление модели на некотором графическом языке (например, язык графов, эквивалентные схемы, диаграммы и т.п.);

физическая

аналоговая

Наиболее универсальным является математическое описание процессов - математическое моделирование.

В понятие математического моделирования включают и процесс решения задачи на ЭВМ.
Обобщенная математическая модель

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

Элементами обобщенной математической модели являются (рис. 1):

множество входных данных (переменные) X,Y;
X - совокупность варьируемых переменных; Y - независимые переменные (константы);

математический оператор L, определяющий операции над этими данными; под которым понимается полная система математических операций, описывающих численные или логические соотношения между множествами входных и выходных данных (переменные);

множество выходных данных (переменных) G(X,Y); представляет собой совокупность критериальных функций, включающую (при необходимости) целевую функцию.

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

Множество варьируемых параметров (переменных) X образует пространство варьируемых параметров Rx (пространство поиска), которое является метрическим с размерностью n, равной числу варьируемых параметров.

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

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

Это могут быть:

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

Выходные данные рассматриваемой обобщенной модели образуют метрическое пространство критериальных показателей RG.

Требования к математической модели

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

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

Универсальность - определяется в основном числом и составом учитываемых в модели внешних и выходных параметров.

Экономичность модели характеризуется затратами вычислительных ресурсов для ее реализации - затратами машинного времени и памяти.

.
Методы получения моделей

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

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

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

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

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

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

математические методы планирования экспериментов,

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

Использование математических моделей

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

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

изучить свойства исследуемого объекта;

умение отделить главные свойства объекта от второстепенных;

оценить принятые допущения.

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


^ Основные понятия
Модель - способ замещения реального объекта, используемый для его исследования, когда натуральный эксперимент невозможен, дорог, опасен, долговременен.

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



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

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

При стремлении адекватности к 0% - затраты уменьшаются, точность уменьшается, но ущерб увеличивается.

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

То есть существуют два пакета:

используемый в процессе моделирования;

написанный после разработки модели.

Проектирование - процесс создания модели объекта. Моделирование - оценка результата проектирования.

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

^ Имитационное моделирование.



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

V - переменная:

b) Формально-математическая схема:


t:= t + h  f




SП:= SП +VП h f

SВ:= SВ + VВ  h f

f:= not (ed (D - (SП + SВ)))

stop(f)



Где f - флаг, показывающий был пройден к текущему моменту t весь путь или нет.
Геометрический способ:




d) Статистическая постановка задачи:








Модель:

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


Критериальный способ:

Пример:



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

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


^ Регрессионные модели

По степени информированности исследователя об объекте существует деление объектов на три типа “ящиков”.

Черный (ничего об объекте неизвестно).




Серый (известны или выходные, или промежуточные, или входные данные).

Белый (об объекте известно все).

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


Пример:




Исследователь вносит гипотезу о структуре “ящика”.

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

y =A1 x + A0


Определим неизвестные коэффициенты модели A0 и A1.

Линейная одномерная модель:




y =A0 + A1 x


Ei = Yi - A0 - A1 Xi, i = 1,n , где n - число снятых экспериментально точек.

=> min

Ei - ошибка между теоретическим значением функции (A0 + A1 x) и экспериментальным Y у точки i. Ошибки всех точек (i от 1 до n) следует сложить. Чтобы положительные ошибки не компенсировали в сумме отрицательные, каждую из ошибок возводят в квадрат и складывают их значения в суммарную уже одного знака. Данный метод поэтому называется Методом наименьших квадратов.

Таким образом, F - суммарная ошибка. F является функцией двух переменных A0 и A1так как меняя эти величины можно влиять на величину ошибки. Естественно, что суммарную ошибку следует минимизировать за счет подбора коэффициентов A0 и A1, то есть они являются переменными для данного метода. Функция F является функцией двух переменных. Для нахождения минимума функции F по ее переменным найдем производные по неизвестным A0 и A1 и приравняем их нулю.



Получим систему из двух уравнений с двумя неизвестным A0 и A1:



Надо найти коэффициенты A0 и A1, для этого решаем систему методом Крамера, построив предварительно определитель следующего вида:



Проверка.

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





Найдем значение “sigma” по формуле:



Если в интервал (YЭ -  YТ  YЭ +) попадает 67% точек и более, то выдвинутая нами гипотеза принимается. В противном случае, выбирают более сложную гипотезу или проверяют исходные данные. Если требуется большая уверенность в результате, то используют дополнительное условие: в интервал (YЭ - 2 YТ  YЭ +) должны попасть 95% экспериментальных точек.

^ Обобщенная математическая модель
Математическая модель описывает зависимость между исходными данными и искомыми величинами.

Элементами обобщенной математической модели являются (рис. 1):

множество входных данных (переменные) X,Y;
X - совокупность варьируемых переменных; Y - независимые переменные (константы);

математический оператор L, определяющий операции над этими данными; под которым понимается полная система математических операций, описывающих численные или логические соотношения между множествами входных и выходных данных (переменные);

множество выходных данных (переменных) G(X,Y); представляет собой совокупность критериальных функций, включающую (при необходимости) целевую функцию.



Рис. 1.


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

Множество варьируемых параметров (переменных) X образует пространство варьируемых параметров Rx (пространство поиска), которое является метрическим с размерностью n, равной числу варьируемых параметров.

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

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

Это могут быть:

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

Выходные данные рассматриваемой обобщенной модели образуют метрическое пространство критериальных показателей RG.

 Схема использования математической модели в системе автоматизированного проектирования показана на рис.2.
 
 



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

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

изучить свойства исследуемого объекта;

умение отделить главные свойства объекта от второстепенных;

оценить принятые допущения.

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


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

Рассматривание задачи в условиях неопределённости.

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

В случаях, когда аналитические модели не приемлемы, строят статистические модели. Рассматривают метод статистического моделирования.

Статистические модели можно назвать имитационными. Они моделируют случайный процесс при помощи ПК.

Метод Монте-Карло является методом статистического моделирования.

^ Метод Монте-Карло - это численный метод решения задач при помощи моделирования случайных величин.

Происхождение метода Монте-Карло

Датой рождения метода Монте-Карло принято считать 1948г. создателями метода считают математиков Дж. Неймана и С. Улама.

Теоретическая основа метода была известна давно. Однако до появления ЭВМ этот метод не мог найти широкого применения.

Само название метода происходит от названия города Монте-Карло в княжестве Монако, знаменитого своими игорными домами. Дело в том, что одним из простейших механических приборов для получения случайных величин является рулетка. Возникает вопрос: помогает ли метод Монте-Карло выигрывать в рулетку? Нет не помогает. И даже не занимается этим.

^ Идея метода

Идея метода чрезвычайно проста и состоит в следующем.

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

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

Пример

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

Р(k >= 1) = P(1)+P(2)+P(3) = 1-P(k < 1)

P(0) = 1/2*1/2*1/2 = 1/8

P(k >= 1) = 1-1/8 = 7/8

^ Эту задачу можно решить розыгрышем - статистическим моделированием. Вместо 3 выстрелов будем бросать 3 монеты, считая, что герб - попадание, решка - промах. Опыт считается удачным, если на одной из монет выпадет герб. Проведем множество опытов, подсчитаем общее количество удач и разделим на число - N (количество проведённых опытов). Таким образом, они получили частоту события, а она при большом числе опытов близка к вероятности.

Метод Монте-Карло применяется: при моделировании случайных процессов, где присутствует множество случайных факторов.

^ Получение случайных величин

Таблица случайных чисел.

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



Монтируется диск (рулетка). Диск вращается и резко останавливается, и выбирается та цифра, на которую указывает неподвижная стрелка.



Ряд цифр 20389320...

Составляется таблица случайных чисел, выбирается определённое их количество (400).

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

^ Генераторы случайных чисел

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

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



0,а1,а2,...аm, где каждая из величин ai имитирует случайную величину с распределением:



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

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


^ Моделирование случайных событий. Моделирование простых событий. Моделирование полной группы событий. Моделирование сложных событий.


Моделирование задач управления.

Постановка задачи.

План

Математическая модель.

Методы исследования.

Анализ результатов.

Прогнозирования развития системы.

Исследования системы управления на имитационной

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

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

рациональное использование сырья и материалов;

задачи оптимизации раскроя;

оптимизации производственной программы предприятий;

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

на составление оптимального плана перевозок, работы транспорта;

управления производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

Так, по оценкам американских экспертов, около ^ 75% от общего числа применяемых оптимизационных методов приходится на ЛП. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач ЛП и их многочисленных модификаций.
^ Пример задачи ЛП
Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет чистый доход в 2,5 руб., один бычок - 5 тыс. руб.
^ Постановка задачи
1. В качестве показателя эффективности целесообразно взять доход за операцию (годовой чистый доход с земли в рублях).

2. В качестве управляемых переменных задачи следует взять:

x1 - количество откармливаемых бычков в год;

x2 - количество выращиваемых партий быстрорастущих новогодних елей по 1000 шт. каждая в год.

3. Целевая функция:

W=5000 x1 + 2500 x2 

где

5000- чистый доход от одного бычка, руб.;

2500 - чистый доход от одной партии деревьев (1000 шт. по 2,5 руб.).

4. Ограничения:

4.1. По использованию земли, га:

4 x1 + 1,5 x2 <=24.

4.2. По бюджету, руб.:

1200 x1 + 150 x2<= 6000.

4.3. По трудовым ресурсам, ч:

20 x1 + 20 x2 <= 200.

4.4. Обязательства по контракту, шт.:

x1 >= 2.

4.5. Областные ограничения:

x1 >= 0, x2 >= 0.
^ Графическое решение задачи линейного программирования
Задачи ЛП с двумя переменными поддаются решению графическим способом. Продемонстрируем данный способ на примере 1 "Оптимизация размещения побочного производства лесничества":

5000 x1 + 2500 x2 max,

4 x1 + 1,5 x2 <= 24;

1200 x1 + 150 x2 <= 6000;

20 x1 + 20 x2 <= 200;

x1 >= 2;

x1 >= 0; x2 >= 0.

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

4 x1 + 1,5 x2 = 24;

1200 x1 + 150 x2 = 6000;

20 x1 + 20 x2 = 200;

x1 = 2; x2 = 0,

и
заштриховываем область, в точках которой выполняются все ограничения. Каждая такая точка называется допустимым решением, а множество всех допустимых решений называется допустимой областью. Очевидно, что решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области, которое, в свою очередь, называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, максимизирующее функцию 5000 x1 + 2500 x2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП. В нашем случае, для нахождения оптимального решения достаточно через любую из вершин допустимой области провести прямую целевой функции и, вслед за этим, путем параллельного переноса полученной прямой найти такие вершины, в которых происходит только касание с допустимой областью.


Максимальный доход в размере 34 тыс. руб. лесничество может извлечь придерживаясь следующей стратегии - выращивая 3,6 бычка и 6,4 партии новогодних елей. Однако окончательное решение должно быть представлено в целочисленной форме. Как правило, на практике полученные результаты округляют до ближайших целых, что может привести к достаточно грубым ошибкам. В разбираемом примере округление даст x1=3 и x2=6, что приводит к доходу в 30 тыс. руб. Однако достаточно удаленная от оптимального решения стратегия x1=4 и x2=5 приводит к более оптимистичному результату в 32,5 тыс. руб. Более того, как будет показано далее, еще более далекая точка x1=3 и x2=7 приводит к аналогичному результату. Поэтому расчеты необходимо продолжить с использованием методов целочисленного программирования, которые нами будут обсуждаться ниже.


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



^ Моделирование непрерывных случайных величин. Классификация методов моделирования непрерывных случайных величин. Метод обратной функции. Метод исключения Дж.Неймана. Метод предельных теорем. Метод композиций. Моделирование специальных непрерывных распределений.


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

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

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

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

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

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

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

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

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

1) с неограниченным временем ожидания (с ожиданием),

2) с отказами;

3) смешанного типа.

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

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

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

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

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

Изучение СМО начинается с анализа входящего потока требований.

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

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

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

[pic]

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

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

Простейший поток обладает такими важными свойствами:

1)Свойством стационарности, которое выражает неизменность

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

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

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

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