Построение и исследование имитационных моделей

Построение и исследование имитационных моделей

Введение

При решении поставленной задачи необходимо выбрать реальную систему массового обслуживания, которая является аналогом моделируемой системы. Учитывая заданные входные параметры (требования поступают в среднем с интервалом 10 секунд, обрабатываются в среднем 25 секунд; дисциплина обслуживания - FIFO, количество обслуживающих устройств - 5), можно взять в качестве аналога производственную систему, где имеется 5 устройств, с помощью которых определённым образом обрабатываются детали, например, обтачиваются. С помощью конвейера детали продвигаются к устройствам; если имеется свободное устройство, то с помощью него немедленно начинается обработка детали, а если все устройства заняты - деталь продвигается в специальный накопитель, в котором может поместиться не более 32 деталей. Если накопитель при поступлении очередной детали заполнен - она откладывается и поступает на обработку позже (со следующей партией). Также аналогом может быть сервер базы данных, к которому идут запросы, не имеющие приоритетов (но среднее время обслуживания, указанное в техническом задании, не соответствует скорости работы современных компьютеров, поэтому мы не рассматриваем такую систему в данной работе).

1. Выбор входных распределений. Построение генераторов случайных чисел

.1      Выбор входных распределений

При выборе входных распределений следует обратить внимание на свойства потоков событий, которым соответствуют поступление требований в систему и обработка этих требований. Рассмотрим простейший поток событий. Он обладает одновременно следующими свойствами:

·        стационарность (вероятность появления определённого числа событий в некотором интервале не зависит от начала отсчёта, а зависит только от ширины интервала);

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

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

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

генератор интерфейс пользовательский программа

1.2    Построение генераторов случайных чисел

Генерация случайных величин, распределённых по экспоненциальному закону, производится в два этапа:

)        генерация стандартной равномерно распределённой псевдослучайной последовательности псевдослучайных чисел;

)        преобразование полученной последовательности в экспоненциально распределённую.

Для создания стандартной равномерно распределённой последовательности используется мультипликативный линейный конгруэнтный генератор (ЛКГ), описываемый формулой:

,

где . 1

Мультипликативный ЛКГ имеет максимальный период (m-1), когда выполняются следующие условия:

·        m является простым числом;

·        a является первообразным корнем по модулю m, т.е. наименьшее целое число l, для которого a^l-1 делится на m, есть l = m-1.

В данной работе при построении ЛКГ взяты следующие параметры:

·        m = 2³¹-1 = 2 147 483 647;

·        a = 630 360 016.

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

Для получения экспоненциального распределения используется следующая формула:

x= - b ln g,

где x - значение экспоненциально распределённой случайной величины, b - математическое ожидание, g - значение равномерно распределённой случайной величины.

1.3   
Оценка входных распределений

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

,

где n - количество чисел в последовательности.

Получены следующие оценки математического ожидания:

·        для времени поступления требований:  = 10.1320;

·        для времени обработки требований:  = 24.9472.

Видно, что полученные оценки мало отличаются от средних значений (µ_A = 10 с, µ_S = 25 с), являющихся входными параметрами.

Оценка дисперсии производится по формуле:

,

где n - количество чисел в последовательности,  - оценка математического ожидания.

Получены следующие оценки дисперсии:

·        для времени поступления требований:  = 98.3608;

·        для времени обработки требований:  = 617.9198.

Для оценки корреляции необходимо сначала вычислить ковариацию по формуле:

,

где n - количество чисел в последовательности,  - оценка математического ожидания.

Формула для оценки корреляционной функции:

где  - ковариация,  - оценка дисперсии.

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

Рисунок 2.2 - График корреляционной функции для времени обработки

По графикам видно, что корреляция для времени поступления составляет менее 0.05, для времени обработки - менее 0.07.

1.4    Оценка результатов

Для оценки результатов используем три метода:

·        метод гистограмм;

·        метод доверительных интервалов;

·        метод c².

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

Гистограмма для времени поступления

Гистограмма для времени обработки

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

График функции распределения вероятностей для времени обработки

График зависимости следующего значения от предыдущего для времени поступления

График зависимости следующего значения от предыдущего для времени обработки

Доверительный интервал для математического ожидания случайных величин определяется формулой:

,

где  = 0,95 - доверительная вероятность,  - математическое ожидание (здесь мы рассматриваем его оценку), б = 1 - в = 0.05 - уровень значимости, U_{1 - б/2} - квантиль порядка 1 - б/2 (для доверительной вероятности  = 0,95 U_{1 - б/2} = 1,96),  - среднеквадратическое отклонение.

Для математического ожидания времени поступления и времени обработки получены следующие доверительные интервалы:

·        9.6371 <  < 10.9516;

·        23.6729 <  < 26.9516.

Оценки математического ожидания, полученные ранее (10.1320 для времени поступления и 24.9472 для времени обработки), входят в доверительные интервалы. Это говорит о неопровержимости экспоненциального распределения для последовательностей, которые мы рассматриваем.

Сделаем проверку гипотезы о правильности выбора экспоненциального распределения с помощью метода c². Для этого, как и при использовании метода гистограмм, разделим область выбранного распределения на k интервалов (b₀, b₁), (b₁, b₂), …, (b_k-1, b_k) и подсчитаем количество попаданий в каждый интервал (n_j - количество значений X_i в j-м интервале). Затем вычисляется ожидаемая доля p_j величин X_i, которые попадают в j-й интервал.

Далее нужно вычислить статистику отклонения выборочного распределения от гипотетического по формуле:

Количество интервалов k =20, тогда p_j = 0,05. Если , то гипотеза принимается, если , то гипотеза отвергается. По данным таблицы для k=20 и =0.05 (уровень значимости, = p_j) c² = 30.144.

В результате были получены следующие значения Z:

·        для времени поступления - 12.0800;

·        для времени обработки - 18.1200.

Полученные значения не превышают значения c², следовательно, обе гипотезы принимаются.

2. Логика работы программы

.1 Оценка параметров производится по формулам:

·        коэффициент использования системы:

,

где p_i - суммарное время работы каждого устройства, m - количество устройств, T - общее время моделирования;

·        среднее время ожидания заявки в очереди:

,

где D_i - время ожидания заявки в очереди, n - количество заявок;

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

,

где d - среднее время ожидания заявки в очереди, µ_S - математическое ожидание времени обслуживания требований, полученное в ходе работы программы;

·        среднее по времени число требований в очереди:

,

где q_i - время пребывания требования в очереди, T - общее время моделирования;

·        среднее по времени число требований в системе:

,

где l_i - время пребывания требования в системе, T - общее время моделирования;

·        абсолютная пропускная способность (количество требований в единицу времени):

,

где л = 1/µ_A - интенсивность поступления требований, щ = 1/µ_S - скорость обработки требований;

·        относительная пропускная способность (отношение доли обслуженных требований к общему количеству требований):

,

где л = 1/µ_A - интенсивность поступления требований, щ = 1/µ_S - скорость обработки требований.

2.2 Пользовательский интерфейс

Пользовательский интерфейс модели СМО

Пользовательский интерфейс модели СМО в процессе работы

Графики функций распределения времени поступления и времени обработки

Графики плотности распределения времени поступления и времени обработки

График по времени числа требований в очереди

График по времени числа требований в системе

График среднего по времени числа требований в очереди

График среднего по времени числа требований в системе

График по времени коэффициента использования системы

3. Анализ работы системы

.1 Выбор стратегии и тактики планирования

генератор интерфейс пользовательский программа

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

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

Факторы, влияние которых мы будем учитывать при планировании экспериментов:

·        количество устройств s;

·        среднее время поступления требований µ_A;

·        среднее время обработки требований µ_S.

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

Показатели (отклики), влияние выбранных факторов на которые мы рассматриваем:

·        коэффициент использования системы с;

·        среднее время ожидания заявки в очереди T_q;

·        среднее время пребывания заявки в системе T_s;

·        среднее по времени число требований в очереди N_q;

·        среднее по времени число требований в системе N_s;

·        абсолютная пропускная способность C_a;

·        относительная пропускная способность C_r.

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

.2 Определение необходимого количества экспериментов

Требуется определить необходимое количество экспериментов для факторного плана. Для этого проводятся предварительные прогоны системы с входными параметрами по умолчанию (указанными в техническом задании):

·        количество устройств s = 5;

·        среднее время поступления требований µ_A = 10;

·        среднее время обработки требований µ_S = 25;

·        ёмкость накопителя l = 32.

Количество поступающих требований - 1000; всего проводим 20 прогонов.

Значения выходных параметров вычисляются по формулам:

·        коэффициент использования системы с - по формуле (3.1);

·        среднее время ожидания заявки в очереди T_q - по формуле (3.2);

·        среднее время пребывания заявки в системе T_s - по формуле (3.3);

·        среднее по времени число требований в очереди N_q - по формуле (3.4);

·        среднее по времени число требований в системе N_s - по формуле (3.5);

·        абсолютная пропускная способность C_a - по формуле (3.6);

·        относительная пропускная способность C_r - по формуле (3.7).

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

Вычисление необходимого количества экспериментов производится по формуле:

,

где n_i - количество экспериментов для каждой случайной величины, определяемое с помощью формулы:

,

где у_i² - дисперсия случайной величины (её оценка вычисляется по формуле (2.7)); е_i² - относительная погрешность (5% от оценки математического ожидания случайной величины, вычисляемого по формуле (2.6)); U_1-б/2 - квантиль порядка 1 - б/2, где б = 1 - в - уровень значимости, соответствующий доверительной вероятности в. Здесь мы берём в = 0,95, тогда б = 1 - 0,95 = 0,05; U_1-б/2 - табличное значение, в данном случае равное 1,96.          В таблице 4.1 приведены результаты предварительных 20 прогонов системы и вычисленные значения n_i для каждого из откликов.

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