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

Размещено на http://www.allbest.ru/

38

Размещено на http://www.allbest.ru/

Введение

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

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

Термин «модель» широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений.

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

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

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

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

1. Имитационное моделирование как метод исследования систем большой сложности

Имитационное моделирование основано на воспроизведении с помощью ЭВМ развернутого во времени процесса функционирования системы с учетом взаимодействия с внешней средой. Основой всякой имитационной модели (ИМ) является:

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

· выбор информативных (интегративных) характеристик объекта, способов их получения и анализа;

· построение модели воздействия внешней среды на систему в виде совокупности имитационных моделей внешних воздействующих факторов;

· выбор способа исследования имитационной модели в соответствии с методами планирования имитационных экспериментов (ИЭ).

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

На рисунке 1 - показана структура имитационной модели. Блок имитации внешних воздействий (БИВВ) формирует реализации случайных или детерминированных процессов, имитирующих воздействия внешней среды на объект. Блок обработки результатов (БОР) предназначен для получения информативных характеристик исследуемого объекта. Необходимая для этого информация поступает из блока математической модели объекта (БМО). Блок управления (БУИМ) реализует способ исследования имитационной модели, основное его назначение - автоматизация процесса проведения ИЭ.



Рисунок 1. Структура имитационной модели

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

К достоинствам метода имитационного моделирования могут быть отнесены:

· проведение ИЭ над ММ системы, для которой натурный эксперимент не осуществим по этическим соображениям или эксперимент связан с опасностью для жизни, или он дорог, или из-за того, что эксперимент нельзя провести с прошлым;

· решение задач, аналитические методы для которых неприменимы, например, в случае непрерывно - дискретных факторов, случайных воздействий, нелинейных характеристик элементов системы и т.п.;

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

· сокращение сроков и поиск проектных решений, которые являются оптимальными по некоторым критериям оценка эффективности;

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

1.1 Случайные события и их имитация

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

· Имитация случайного события;

· Имитация сложного события;

· Имитация сложного события, состоящего из зависимых событий;

· Имитация событий, составляющих полную группу.

1.1.1 Имитация случайного события

Пусть некоторое событие А происходит с вероятностью P_A. Требуется воспроизвести факт наступления события А. Поставим в соответствие событию А событие В, состоящее в том, что х меньше либо равно P_A, где х здесь и в дальнейшем - случайное число (СЧ) с равномерным на интервале (0,1) законом распределения. Вычислим вероятность события В:

Таким образом, события А и В являются равновероятными. Отсюда следует процедура имитации факта появления события А. Она сводится к проверке неравенства х_{Аменьше, либо равно}Р, а алгоритм заключается в следующем:

1. С помощью датчика случайных чисел (СЧ) получают СЧ х;

2. Проверяют выполнение неравенства х меньше, либо равно P_A;

3. Если оно выполняется, то событие А - произошло, если нет-то произошло .

1.1.2 Имитация сложного события

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

В зависимости от исхода проверки неравенств делается вывод какой из вариантов:

имеет место.

1.1.3 Имитация сложного события, состоящего из зависимых событий

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

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

В качестве исходных данных задаются P_A, P_B и условная вероятность P_B/A, вероятность может быть вычислена по формуле полной вероятности:

, где , отсюда легко выразить .

1.1.4 Имитация событий, составляющих полную группу

Пусть событие А_i (i=1, n) составляют полную группу, тогда их вероятности Р_i, таковы что:

Имитация факта появления одного из событий А_i (i=1, n) сводится к проверке следующих неравенств:

где ,

Выполнение неравенства K эквивалентно выполнению события А_К. Описанный алгоритм называют иногда алгоритмом «розыгрыша по жребию». Его можно интерпретировать как установление номера К отрезка длинной Р_К, на который пало СЧ х, при условии разбиения отрезка единичной длины на отрезки с длинами P1, P2,… Pn (рисунок 2):

Рисунок 2. Отрезок выполнения неравенства K

1.2 Имитация непрерывных случайных величин

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

1. метода обратной функции;

2. предельных теорем теории вероятности;

3. приближенных методов;

4. метода Неймана (режекции);

5. алгоритма получения значения нормально распределенной случайной величины;

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

1.2.1 Метод обратной функции

Пусть непрерывная случайная величина (СВН) ? задана своим законом распределения:

где - плотность распределения вероятностей, а - функция распределения вероятностей. Доказано, что случайная величина

распределена равномерно на интервале (0,1).

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

которое эквивалентно уравнению:

где y - значение случайной величины ?, а x - значение CB ?.

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

1.2.2 Метод Неймана (режекции)

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

Метод Неймана состоит в следующем:

1. С помощью датчика случайных чисел получают пару чисел, распределенных равномерно на (0,1).x1 и x2.

2. Путем преобразований (по методу обратной функции получают два числа x*1 и x*2, равномерно распределенных соответственно на интервалах (a, b) и (o, w), то есть (рисунок 3):

и

где



Рисунок 3. График преобразований сгенерированных чисел

3. Из точек с координатами выбирают те, которые попали «под колокол» функции f_h (y), то есть те точки, для которых .

4. Если выполнено условие 3, то искомое значение y полагают равным .

1.2.3 Алгоритм получения значения нормально распределенной случайной величины

Нормальное распределение является наиболее часто встречающимся. Функция плотности распределения вероятностей для него имеет вид:

где m - мат. ожидание, а ?² - дисперсия.

Согласно центральной предельной теореме теории вероятностей СВ

распределена асимптотически нормально, если ? распределены одинаково.

Для практического получения значений ? в качестве и ? выбирают равномерно распределенные СВ. При этом наиболее часто используют преобразование:

где x_i - равномерно распределенные на (0,1) случайные числа. При к=12 формула приобретает вид наиболее удобной для расчетов, но она дает достаточно точные результаты уже для к=3,4. Формула верна для центрированной (m=0) и нормированной (?=1) случайной величины.

Для получения y*, распределенного нормально с произвольными m и ?, пользуются дополнительно преобразованием:

1.2.4 Алгоритм получения случайной величины, распределенной по Пуассону

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

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



Здесь np=а, где а - параметр закона Пуассона.

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

1. Положить р меньше, либо равно 0,1 (так как события являются редкими).

2. Вычислить число испытаний n=а/р.

3. Значение х - случайного числа с равномерным на интервале (0,1) законом распределения сравнить с р, если х меньше, либо равно р, то к счетчику событий добавляется 1.

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

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

1.3 Алгоритмы получения значений систем случайных величин (случайных векторов)

Алгоритмы получения значений систем случайных величин (случайных векторов) разделяются на несколько основных методов:

1. Метод аналитических преобразований;

2. Метод разложения по координатным случайным величинам;

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

1.3.1 Метод аналитических преобразований

Пусть системы непрерывных случайных величин (СНСВ) (?₁, ?₂, …, ?_n) задана условными законами распределения СВ ?_i (i=1, n). По теореме умножения плотностей распределения, совместная функция плотности распределения вероятностей равна:

f(z₁, z₂,…, z_n)=f₁(z₁) f₂(z₂|z₁) f₃(z₃|z₁z₂)… f_n(z_n| z₁, z₂,…, z_n-1).

Для системы двух случайных величин (?₁,?₂), алгоритм получения вектора ее значений сводится к следующему:

Вычисление частной функции плотности для ?₁:

Получение значения в соответствии с f₁(z₁) согласно любому методу;

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

Получение - значения ?₂ любым известным методом в соответствии с найденным законом ее распределения.

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

1.3.2 Метод разложения по координатным случайным величинам

Пусть СНСВ задана в рамках теории корреляций: математическими ожиданиями компонент (m₁, m₂,…, m_n) и матрицей корреляционных моментов:

Теоремой доказано, что h_i можно получить с помощью их разложеия по координатам СВ x_i :

…………………………

,

где ?_i - некоррелированные, центрированные, нормированные нормально распределенные СВ.

Коэффициенты с_ij могут быть достаточно просто получены решением системы уравнений:

,

Алгоритм получения значений СНСВ сводится к следующему:

1) Решение системы нелинейных уравнений;

2) Получение n значений y_i нормировнных, центрированных СВ, распределенных нормально.

3) Вычисление z_i, i=(1, n) значений СВ, образующих СНСВ.

1.3.3 Алгоритм получения значений системы дискретных случайных величин

Дискретный двумерный вектор CDCB задается двумерным законом распределения, т.е.:

а) матрицей вероятностей , где P_ij - вероятность совместного появления i-ого и j-ого значений соответственной первой и второй компоненты, причем:

б) двумя векторами возможных значений первой и второй компоненты {A_i}, {B_i}, .

Получение значений двумерной дискретной системы случайных величин (СДСВ) может осуществляться по следующему алгоритму:

1) Вычисляют суммы:

, , ;

2) Если х - равномерно распределенное случайное число из интервала (0,1) такое, что , то считают, что ?₁ компонента двумерной СДСВ получила к-ое значение.

3) Выбирают к-ую строку вычисляют .

4) Если вновь полученное с помощью датчика случайных чисел х такое, что вторая компонента СДСВ получила S-е значение.

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

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

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

СП считается заданным, если задана функция дисперсии d(t), математического ожидания m(t) и корреляционная функция k(t_i, t_j). Эти функции являются неслучайными, их определяют путем обработки опытных данных методами математической статистики.

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

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

Пусть F(t₁), F(t₂),…, F(t_n) - реализация СП на конечном интервале Т времени, тогда в соответствии с методом:

F(t₁)=m(t₁) + x_1?1(t₁),

F(t₂)=m(t₁) + x_1?1(t1) + x_2?2(t₂),

F(t_n)=m(t₁) + x_1?1(t₁) + x_2?2(t₂) +… + x_n?n(t_n).

Здесь х₁, х₂,…, х_n - значения случайных, некоррелированных, центрированных СВ ? о заданным законом распределения; ?_i(t_k) - координатные функции, обладающие свойствами:

а) ?_i(t_j)=0 при i>j; б) ?_i(t_i)=1.

Координатные функции и дисперсии D_i величин ? можно вычислить в соответствии с рекуррентными уравнениями:

,

, .

1.4.2 Имитация стационарных СП

Для стационарных СП справедливы соотношения m(t)=m; d(t)=?²; k(t_i, t_j)=k(?), где ?=t_i-t_j. Один из методов имитации стационарных СП заключается в вычислении F(t_i) по формулам:

F(t₁)=m+c₁x₁+c₂x₂+… +c_nx_n,

F(t₂)=m+c₁x₂+c₂x₃+… +c_nx_n+1,

F(t_n)=m+c₁x_n+c₂x_n+1+… +c_nx_2n-1.

Здесь х_i - реализации некоррелированных случайных величин ?, для которых M[?]=0, D[?]=?², закон их распределения задан. Коэффициенты c_j () вычисляют решением уравнений

K(t_k-t₁)=(c₁c_k + c₂c_k+1 +… + c_n+k-1c_n)?+2, ().

1.4.3 Имитация стационарных нормальных СП

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

В их основу положены линейные преобразования стационарной последовательность F(t_k) независимых нормальных случайных чисел (белый шум) в последовательность F(t_k), k=1, 2,…; t_k-t_k-1=?t=const, коррелированную по заданному закону. При этом оператор линейного преобразования записывается либо в виде формулы скользящего суммирования с некоторым весом а_i:

либо как рекуррентное уравнение вида:

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

1.5 Обработка результатов моделирования

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

1.5.1 Оценка вероятности

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

1.5.2 Гистограммы

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

1.5.3 Оценка математического ожидания

Оценку математического ожидания получают как среднее арифметическое значение СВ:

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

1.5.4 Оценка дисперсии

Оценку дисперсии можно вычислять по формуле:

Однако это связано с непроизводительным использованием памяти ЭВМ. Поэтому лучше воспользоваться формулой:

1.5.5 Оценка характеристик случайного процесса

Для вычисления оценки характеристик СП производят статистическую обработку по N реализациямит СП. Для этого интервал задания СП разбивают на части с?t=const. Матожидания и дисперсии для каждого t_k=k?t можно вычислить по формулам, приведенным выше. Оценку корреляционной функции - по формуле:

Здесь t_k=k?t, t_j=j?t

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

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

Первые задачи теории систем массового обслуживания (ТСМО) были рассмотрены сотрудником Копенгагенской телефонной компании, датским ученым А.К. Эрлангом (1878-1929 г.) в период между 1908 и 1922 гг. Эти задачи были вызваны к жизни стремлением упорядочить работу телефонной сети и разработать методы, позволяющие заранее повысить качество обслуживания потребителей в зависимости от числа используемых устройств. Оказалось, что ситуации, возникающие на телефонных станциях, являются типичными не только для телефонной связи. Работа аэродромов, морских и речных портов, магазинов, терминальных классов, электронных вычислительных комплексов, радиолокационных станций и т.д. может быть описана в рамках ТСМО.

2.1 Примеры систем массового обслуживания. Анализ задач ТСМО

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

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

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

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

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

Задача: Обеспечить определенный объем перевозок при минимальных расходах. При этом сократить простои судов при погрузочно-разгрузочных работах.

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

Задача: Обеспечить ускорение обработки сигналов при заданной суммарной длине очереди.

Пример 5. На рисунке 4 изображена структурная схема типичной системы массового обслуживания - ремонтного предприятия (например, по ремонту ПЭВМ). Порядок ее работы ясен из схемы и не требует разъяснений.



Рисунок 4. Структурная схема типичной системы массового обслуживания

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

Характерным для таких задач является:

1) Условия «двойной» случайности:

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

· случайна длительность времени обслуживания.

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

А.К. Эрланг обратил внимание на то, что СМО могут быть разделены на два типа, а именно: на системы с ожиданием и системы с потерями. В первом случае - заявка, поступившая на вход системы «ждет» очереди на выполнение, во втором - она из-за занятости канала обслуживания получает отказ и теряется для СМО.

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

2.2 Математические модели потоков событий

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

1) Регулярный и случайный потоки;

2) Простейший пуассоновский поток и т.д.

2.2.1 Регулярный и случайный потоки

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

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

· все заявки потока с точки зрения обслуживания являются равноправными;

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

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

Функция f(х) плотности распределения вероятности случайной величины Т - интервала времени между событиями имеет при этом вид:



где - дельта функция, М_т - математическое ожидание, причем М_т=Т, дисперсия D_т=0 и интенсивность наступления событий в поток ?=1/M_т=1/T.

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

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

a) Заданием закона распределения моментов появления событий

Здесь - случайные моменты времени появления событий в потоке, t1, t2, tn- их назначение, Р - вероятность;

b) Заданием многомерного закона распределения системы случайных величин Т₁, Т₂,…, Т_n, являющихся длинами интервалов между последовательными событиями:

где z - значения T_i(i=1, n). В этом случае моменты наступления событий могут быть вычислены следующим образом:

t₁=t₀+z1

t₂=t₁+z2

………,

где, t₀ - момент начала потока.

2.2.2 Простейший пуассоновский поток

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

Определение: Поток называется стационарным, если вероятность появления n событий на интервале времени (t, t+T) зависит от его расположения на временной оси t.

Определение: Поток событий называется ординарным, если вероятность появления двух или более событий в течении элементарного интервала времени D t есть величина бесконечно малая по сравнению с вероятностью появления одного события на этом интервале, т.е. при n=2,3,…

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

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

Доказано, что для простейшего потока число n событий попадающих на любой интервал z распределено по закону Пуассона:

Вероятность того, что на интервале времени z не появится ни одного события равна:

тогда вероятность противоположного события по определению: P (T<z)=F(z). Это функция распределения вероятности Т. Отсюда получим, что случайная величина Т распределена по показательному закону:

параметр ? называют плотностью потока. Причем:

2.3 Цепи Маркова

Маркова цепь (Markov Chain) - марковский процесс с дискретным временем, заданный в измеримом пространстве.

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

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

Пример:

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

1) после осуществления доставки в А следующая доставка в 30 случаях осуществляется в А, в 30 случаях - в В и в 40 случаях - в С;

2) после осуществления доставки в В следующая доставка в 40 случаях осуществляется в А, в 40 случаях - в В и в 20 случаях - в С;

3) после осуществления доставки в С следующая доставка в 50 случаях осуществляется в А, в 30 случаях - в В и в 20 случаях - в С.

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

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

Например, р₁₂ = 0.4 - это вероятность того, что после доставки в район В следующая доставка будет производиться в районе А.

Допустим, что каждая доставка с последующим перемещением в следующий район занимает 15 минут. Тогда, в соответствии со статистическими данными, через 15 минут 30% из курьеров, находившихся в А, будут в А, 30% будут в В и 40% - в С. Так как в следующий момент времени каждый из курьеров обязательно будет в одном из округов, то сумма по столбцам равна 1. И поскольку мы имеем дело с вероятностями, каждый элемент матрицы 0<р_ij<1. Наиболее важным обстоятельством, которое позволяет интерпретировать данную модель как цепь Маркова, является то, что местонахождние курьера в момент времени t+1 зависит только от местонахождения в момент времени t.

Теперь зададим простой вопрос: если курьер стартует из С, какова вероятность того, что осуществив две доставки, он будет в В, т.е. как можно достичь В в 2 шага? Итак, существует несколько путей з С в В за 2 шага:

1) сначала из С в С и потом из С в В;

2) С->B и B->B;

3) С->A и A->B.

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

P = P(CA)*P(AB) + P(CB)*P(BB) + P(CC)*P(CB)

Подставляя числовые значения:

P = 0.5*0.3 + 0.3*0.4 + 0.2*0.3 = 0.33

Полученный результат говорит о том, что если курьер начал работу из С, то в 33 случаях из 100 он будет в В через две доставки.

Ясно, что вычисления просты, но если Вам необходимо определить вероятность через 5 или 15 доставок - это может занять довольно много времени.

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

Тогда элемент (2, 3) - это вероятность перехода из С в В за 2 шага, которая была получена выше другим способом. Заметим, что элементы в матрице P² также находятся в пределах от 0 до 1, и сумма по столбцам равна 1.

Т.е. если Вам необходимо определить вероятности перехода из С в В за 3 шага:

1 способ. p(CA)*P(AB) + p(CB)*P(BB) + p(CC)*P(CB) = 0.37*0.3 + 0.33*0.4 + 0.3*0.3 = 0.333, где p(CA) - вероятность перехода из С в А за 2 шага (т.е. это элемент (1, 3) матрицы P²).

2 способ. Вычислить матрицу P³:

Матрица переходных вероятностей в 7 степени будет выглядеть следующим образом:

Легко заметить, что элементы каждой строки стремятся к некоторым числам. Это говорит о том, что после достаточно большого количества доставок уж не имеет значение в каком округе курьер начал работу. Т.е. в конце недели приблизительно 38,9% будут в А, 33,3% будут в В и 27,8% будут в С. Подобная сходимость гарантировано имеет место, если все элементы матрицы переходных вероятностей принадлежат интервалу (0, 1).

2.4 Имитационное моделирование систем массового обслуживания

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

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

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

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

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

2.4.1 Виды имитационного моделирования

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

2) Дискретно-событийное моделирование - подход к моделированию, предлагающий абстрагироваться от непрерывной природы событий и рассматривать только основные события моделируемой системы, такие как: «ожидание», «обработка заказа», «движение с грузом», «разгрузка» и другие. Дискретно-событийное моделирование наиболее развито и имеет огромную сферу приложений - от логистики и систем массового обслуживания до транспортных и производственных систем. Этот вид моделирования наиболее подходит для моделирования производственных процессов. Основан Джеффри Гордоном в 1960-х годах.

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

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

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

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

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

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

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

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

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

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

Заключение

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

Моделирование всегда имеет целевую направленность. Цели и методы моделирования могут быть разнообразными. Различают вербальное, геометрическое (предметное), физическое и информационное моделирование.

Вербальное моделирование - это моделирование на основе использования разговорного языка.

Геометрическое моделирование осуществляется на макетах или объектных моделях. Эти модели передают пространственные формы объекта, пропорции и т.п.

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

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

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

Список использованной литературы

1. Дьяконов В.П. Вейвлеты. От теории к практике. - М.: СОЛОН-Р, 2002. - 448 с.

2. Корн Г., Корн Е. Справочник по математике для научных работников и инженеров. - М.: Наука, 1984.

3. Френкель А.А., Адамова Е.В. Корреляционный и регрессионный анализ в экономических приложениях: Учебное пособие / МЕСИ - М:, 1987 г.

4. Мхитарян В.С., Трошин Л.И., Адамова Е.В., Шевченко К.К., Бамбаева Н.Я. Теория вероятностей и математическая статистика / Московский международный институт эконометрики, информатики, финансов и права. - М., 2002 г.

5. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. - М., ЮНИТИ-ДАНА, 2001 г.

6. «Многомерный статистический анализ на ЭBM с использованием пакета Microsoft Excel»/ М., 1997.

Размещено на Allbest.ru