Моделирование СМО ОКМ ДМ экономическая информатика визуальные среды - 4GL Теория и практика обработки информации

Моделирование систем массового обслуживания и метод Монте-Карло

До сих пор мы рассматривали системы, для которых удавалось описать результаты обследования в аналитическом виде. Однако, многие реальные системы (многофазные, c оригинальными приоритетами, с признаками нестационарности, c непуассоновскими входными потоками, с непоказательным распределением длительности обслуживания и т.д.) не поддаются такому решению.

Cуть математического моделирования системы заключается в следующем.

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

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

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

Пусть R - случайные числа с равномерным законом распределения в [0,1] и X - создаваемые случайные числа с плотностью распределения p(X). Между ними можно установить соотношение [39]

Так для показательного распределения p(X)=lexp(-lx) для X>0 легко установить, что X= -ln(1-R)/l. Для равномерного распределения в [a,b] c очевидностью X=a+(b-a)R. Получение дискретных случайных чисел сводится к поиску наименьшего значения X, при котором

Если взятие интеграла и представление X через R составит затруднение, можно воспользоваться методом Неймана. Здесь при неограниченности области значений X усекаем ее до некоторого интервала [a,b]; например для нормального распределения концы интервала берем отстоящими от среднего на 3-4 стандартных отклонения. Затем генерируется пара случайных чисел R₁ и R₂; если то берем X=a+(b-a)R₂ и в противном случае берем следующую пару случайных чисел.

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

Вопрос о числе N отдельных реализаций системы решается на основе закона больших чисел [30] и вывода о том, что погрешность оценок имеет порядок

Cуществуют многочисленные примеры успешного моделирования вполне реальных СМО (см. библиографию [37]).

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

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

НОВОСТИ ФОРУМА

Рыцари теории эфира