63459 (597593), страница 5

Файл №597593 63459 (Моделирование систем массового обслуживания) 5 страница63459 (597593) страница 52016-07-30СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)




2

3

n

k

(k+1)


Разметим граф, т.е. проставим у стрелок интенсивности соответствующих потоков событий. Пусть система находится в состоянии S1. Как только закончится обслуживание заявки, занимающей этот канал, система переходит в состояние S0, интенсивность перехода . Если занято 2 канала, а не один, то интенсивность перехода составит 2.

Предельные вероятности состояний p0 и pn характеризую установившийся режим работы системы массового обслуживания при t .

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

Зная все вероятности состояний p0 , … , pn , можно найти характеристики СМО:

  • вероятность отказа – вероятность того, что все n каналов заняты

  • относительная пропускная способность – вероятность того, что заявка будет принята к обслуживанию

  • среднее число заявок, обслуженных в единицу времени

Полученные соотношения могут рассматриваться как базисная модель оценки характеристик производительности системы. Входящий в эту модель параметр = 1 / tОБРАБОТКИ, является усредненной характеристикой пользователя. Параметр является функцией технических характеристик компьютера и решаемых задач.

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

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

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

Идея метода: вместо того, чтобы описывать случайное явление с помощью аналитической зависимости производится «розыгрыш», т.е. происходит моделирование случайного явления с помощью некоторой процедуры, дающей случайный результат. Произведя такой розыгрыш n раз, получаем статистический материал, т.е. множество реализаций случайного явления, которое потом можно обработать обычными методами математической статистики. Метод Монте-Карло предложил Фон-Нейман в 1948 году, как метод численного решения некоторых математических задач.

Суть метода:

      1. Вводим в некотором единичном квадрате любую поверхность S.

      2. Любым получаем 2 числа xi, yi, подчиняющиеся равномерному закону распределения случайной величины на интервале [0, 1].

      3. Полагаем, что одно число определяет координату x, второе – координату y

      4. Анализируем принадлежность точки (x, y) фигуре. Если принадлежит, то увеличиваем значение счетчика на 1.

      5. Повторяем n раз процедуру генерации 2х случайных чисел с заданным законом распределения и проверку принадлежности точки поверхности S.

      6. Определяем площадь фигуры как количество попавших точек, к количеству сгенерированных.

Фон-Нейман доказал, что погрешность .

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

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

Способы получения последовательностей случайных чисел

На практике используются 3 основных способа генерации случайных чисел:

  1. аппаратный (физический)

  2. табличный (файловый)

  3. алгоритмический (программный)

Аппаратный способ.

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

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

Простейшие алгоритмы генерации последовательности псевдослучайных чисел

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

Если n пробегает значения натурального ряда числе, то поведение yn выглядит весьма хаотично.

К. Якоби доказал, что при рациональном коэффициенте a множество y конечно, а при иррациональном – бесконечно и всюду плотно в интервале [0, 1].

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

  1. 1946 год, Фон Нейман.

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

  1. Лемер.

. Для подборов коэффициентов k, c, m были потрачены десятки лет. Подбор почти иррациональных чисел ничего не дает.

  1. Разумнее ввести вычисления с целыми числами.

при 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, что дает вполне относительно хорошее приближение к нормальному распределению.

Немарковские случайные процессы, сводящиеся к марковским

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

  1. Метод разложения случайного процесса на фазы (метод псевдосостояний)

  2. Метод вложенных цепей Маркова

Метод псевдосостояний

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

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

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

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

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

Характеристики

Тип файла
Документ
Размер
3,72 Mb
Тип материала
Учебное заведение
Неизвестно

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее