63459 (597593), страница 5
Текст из файла (страница 5)
2
3
n
k
(k+1)
Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода . Если занято 2 канала, а не один, то интенсивность перехода составит 2.
Предельные вероятности состояний p0 и pn характеризую установившийся режим работы системы массового обслуживания при t .
- среднее число заявок, приходящих в систему за среднее время обслуживания одной заявки.
Зная все вероятности состояний p0 , … , pn , можно найти характеристики СМО:
-
вероятность отказа – вероятность того, что все n каналов заняты
-
относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию
-
среднее число заявок, обслуженных в единицу времени
Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр = 1 / tОБРАБОТКИ, является усредненной характеристикой пользователя. Параметр является функцией технических характеристик компьютера и решаемых задач.
Эта связь может быть установлена с помощью соотношений, называемых интерфейсной моделью. Если время ввода/вывода информации по каждой задачи мало по сравнению со временем решения задачи, то логично принять, что время решения равно 1 / и равно отношению среднего числа операций, выполненных процессором при решении одной задачи к среднему быстродействию процессора.
На практике далеко не все случайные процессы являются Марковскими или близкими к ним. В СМО поток заявок не всегда Пуассоновский, ещё реже наблюдается показательное или близкое к нему распределение времени обслуживания.
Для произвольных потоков сообщений, переводящих систему из одного состояния в другое, аналитическое решение получено только для отдельных частных случаев. Когда построение аналитической модели по той или иной причине трудно осуществимо, применяется другой метод моделирования – метод статистических испытаний (Монте-Карло). Широкое распространение метода связано с возможностью его реализации на компьютере.
Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.
Суть метода:
-
Вводим в некотором единичном квадрате любую поверхность S.
-
Любым получаем 2 числа xi, yi, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].
-
Полагаем, что одно число определяет координату x, второе – координату y
-
Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.
-
Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.
-
Определяем площадь фигуры как количество попавших точек, к количеству сгенерированных.
Фон-Нейман доказал, что погрешность .
Преимущества метода статистических испытаний в его универсальности, обуславливающей возможность всестороннего статистического исследования объекта, однако, для реализации этой возможности нужны довольно полные статистические сведения о параметрах элементов.
К недостаткам относится большой объем требуемых вычислений, равный количеству обращений к модели. Поэтому вопрос выбора величины n имеет важнейшее значение. Уменьшая n – повышаем экономичность расчетов, но одновременно ухудшаем их точность.
Способы получения последовательностей случайных чисел
На практике используются 3 основных способа генерации случайных чисел:
-
аппаратный (физический)
-
табличный (файловый)
-
алгоритмический (программный)
Аппаратный способ.
Случайные числа вырабатываются специальной электронной приставкой (генератором случайных чисел). Реализация этого способа не требует дополнительных вычислительных операций по выбору случайных чисел. Необходимо только оперативное обращение к ВУ.
В качестве физического эффекта, лежащего в основе генератора, чаще всего используют шуму в электронных приборах.
Простейшие алгоритмы генерации последовательности псевдослучайных чисел
Одним из первых способов получения является выделение значения дробной части у многочлена первой степени:
Если n пробегает значения натурального ряда числе, то поведение yn выглядит весьма хаотично.
К. Якоби доказал, что при рациональном коэффициенте a множество y конечно, а при иррациональном – бесконечно и всюду плотно в интервале [0, 1].
Критерий равномерности распределения любой функции: свойство эргамичности – среднее по реализациям псевдослучайное число равно среднему по всему их множеству с вероятностью 1.
-
1946 год, Фон Нейман.
Каждое последующее случайное число образуется возведением в квадрат предыдущего и отбрасывание цифр с обоих концов. Способ оказался ненадежным.
-
Лемер.
. Для подборов коэффициентов k, c, m были потрачены десятки лет. Подбор почти иррациональных чисел ничего не дает.
-
Разумнее ввести вычисления с целыми числами.
при c = 0 и m = 2n наибольший период достигается при k=3+8i или k=5+8i и при нечетном начальном числе.
Для имитации равномерного распределения на [a, b] используется обратное преобразование функции плотности вероятности.
где R – равномерно распределенное псевдослучайное число на [0, 1].
В основе построения программы генерации случайной числа с законом распределения, отличным от равномерного, лежит метод преобразования последовательности случайных чисел с равномерным законом распределения в последовательность случайных чисел с заданным законом распределения.
Метод основан на том, что случайная величина x принимает значения, равные корню уравнения
, имеет плотность распределения f(x). R – случайная величина, равномерно распределенная на [0, 1].
Значение случайной величины, распределенной по показательному закону может быть вычислено из данного уравнения следующим образом:
Распределение Пуассона относится к числу дискретных (переменная может принимать лишь целочисленные значения, включая 0, с математическим ожиданием и дисперсией > 0). Для генерации Пуассоновских переменных можно использовать метод точек, в основе которого лежит генерируемое случайное значение Ri , равномерно распределенное на [0, 1], до тех пор, пока не станет справедливым
При получении случайной величины, функция распределения которой не позволяет найти решение уравнения
в явной форме, можно произвести кусочно-линейную аппроксимацию, а затем вычислить приближенное значение корня. Кроме того, при получении случайной величины часто используют те или иные свойства распределений.
Воспользуемся этим методом, чтобы сгенерировать случайную величину с законом распределения Эрланга. Распределение Эрланга характеризуется параметрами и k.
При вычислении случайно величины воспользуемся тем, что поток Эрланга может быть получен путем прорешивания потока Пуассона k раз. Поэтому, достаточно получить k значений случайной величины распределенной по показательному закону и усреднить их.
Нормальное распределение случайной величины может быть получено как сумма большого числа случайных величин, распределенных по одному и тому же закону распределения с одними и теми же параметрами.
Случайная величина X имеющая нормальное распределение с математическим ожиданием MX и среднеквадратичным отклонением X может быть получена по следующей формуле:
Для сокращения вычислений на практике принимаю N=12, что дает вполне относительно хорошее приближение к нормальному распределению.
Немарковские случайные процессы, сводящиеся к марковским
Реальные процессы часто обладают последствием и поэтому не являются марковскими. Иногда при исследовании таких процессов удается воспользоваться методами, разработанными для марковских процессов. Наиболее распространены два способа:
-
Метод разложения случайного процесса на фазы (метод псевдосостояний)
-
Метод вложенных цепей Маркова
Метод псевдосостояний
Суть метода состоит в том, что состояния системы, потоки переходов из которых являются немарковскими, заменяются эквивалентной группой фиктивных состояний, потоки переходов из которых являются марковскими.
Условие статистической эквивалентности реального состояния и соответствующих ему фиктивных состояний в каждом конкретном случае выбирается по-разному. В качестве одного из критериев эквивалентности можно принять следующее условие:
, где i экв() – эквивалентная интенсивность перехода в i-той группе переходов, заменяемой реальный переход обладающей интенсивностью i().
За счет расширения числа состояний системы, некоторые процессы удается точно свести к марковским. Созданная таким образом новая система по своим характеристикам статистически эквивалентна или близка реальной системе, но она должна быть обязательно подвергнута обычному исследованию на адекватность, с помощью хорошо проработанного математического аппарата с использованием уравнений Колмогорова.
К числу процессов, которые введением фиктивных состояний можно точно свести к марковским, относятся процессы, происходящие в системе под воздействием потока Эрланга.