книги / Прикладная теория систем массового обслуживания.-1

аналогично которой для произвольной марковской цепи можно записать систему уравнений вида

которая называется системой уравнений детального баланса. Эти уравне­ ния необязательно справедливы для любой цени Маркова. Однако для процессов гибели и размножения уравнения детального баланса (4.8) спра­ ведливы. Существуют и другие примеры марковских цепей, для которых система (4.8) справедлива, что сильно упрощает нахождение стационарно­ го распределения вероятностей П(/), которое в этом случае совпадает с ре­ шением <?(/) системы уравнений детального баланса (4.8). Проблема со­ стоит в получении и формулировании конструктивного критерия эквива­ лентности систем (4.6) и (4.8).

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

Определение 1. Вершины / и у графа назовем инцидентными (или связанными), если Ру Pji > 0.

Определение 2. Последовательность различных вершин /1, /2, ..., in называется циклом в графе, если п > 2 и РпаРаа ••• РылтРтн > 0.

Будем рассматривать только неприводимые, апериодические цепи Маркова, для которых система (4.6) определяет стационарные вероятно­ сти, т.е. для всех i вероятности П(/) > 0. Здесь множество вершин графа яв­ ляется эргодическим и для цепи Маркова выполнены условия существова­ ния стационарного режима.

Критерий эквивалентности уравнений глобального и детального балансов цепи Маркова. Так как рассматриваются только такие цепи Мар­ кова, для которых система (4.6) с условием нормировки имеет единствен­ ное положительное решение П(/) > 0, i = 1, 2, ..., совпадающее со стацио­ нарным распределением вероятностей состояний марковской цепи, то име­ ет место следующее утверждение.

Теорема 1. Системы уравнений глобального и детального балансов эквивалентны, когда система (4.8) имеет решение, удовлетворяющее усло­ вию нормировки

£<2(0 = 1-

1=0

1=0 (4.8) удовлетворяет решению системы (4.9).

В силу единственности решения системы (4.6), удовлетворяющего условию нормировки, системы (4.6) и (4.8) эквивалентны.

Следствие. Если система уравнений детального баланса (4.8) имеет решение G(j)J = 0, 1,2,..., удовлетворяющее условию нормировки

LG O ) = l,

то это решение совпадает со стационарным распределением вероятности П(j)J = 0, 1,2, ...,состояний цепи Маркова.

В силу изложенного дается следующая рекомендация. При доказа­ тельстве справедливости уравнений детального баланса для данной цепи Маркова предполагается, что они справедливы, затем делается попытка решить их и найти стационарные вероятности П(j)J = 0, 1,2, ... Имеются две возможности: либо система (4.8) вместе с условием нормировки несо­ вместима, либо распределение С(/), удовлетворяющее (4.8), будет найдено. В последнем случае ясно, что это распределение будет удовлетворять так­ же уравнению глобального баланса (4.9), которое определяет единственное стационарное распределение П(/),у = 0, 1,2,

Можно предложить критерий эквивалентности систем (4.6) и (4.8), исключающий необходимость решения системы (4.8). Предварительно до­ кажем следующее утверждение.

Теорема 2. Для того чтобы стационарное распределение П(/‘) цепи Маркова удовлетворяло системе уравнений детального баланса, необходи­ мо, чтобы выполнялось условие: если для какой-либо пары вершин i и у Ру > 0, то Pji > 0.

Доказательство. Допустим, существует такая пара /,у, что Ру> 0, но Pji = 0. Записав для этих вершин уравнение детального баланса П(/)Л/ = = U(j)Pji, получим, что П(/) = 0, но это противоречит требованию П(/) > 0, / = 0,1,2,

Таким образом, для каждой вершины i существует инцидентная ей вершина j и любая пара таких вершин либо не принадлежит ни одному из циклов (но эти вершины принадлежат разным циклам), либо обе вершины одновременно принадлежат одному из циклов.

Теорема 3. Если две инцидентные вершины / и j графа состояний марковской цепи не принадлежат одновременно одному из циклов, то для этих вершин стационарные вероятности П(/) и П(/) удовлетворяют уравне­ нию детального баланса

Доказательство этого утверждения очевидно, так как пара стрелок (UJ) и (/, /) в данном случае образует сечение исходного графа, т.е. удале­ ние этих стрелок из графа разбивает его на два несвязанных графа, поэто­ му имеет место равенство (4.10).

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

Пусть граф состояний цепи Маркова содержит один единственный цикл, т.е. для всех вершин (1, 2, 3, ..., л) графа состояний цепи выполнено равенство

РпР* ••• РпЛпРпХ > 0

и не существует меньшего набора вершин, образующего цикл в этом графе состояний. Докажем утверждение.

Теорема 4. Для того чтобы стационарное распределение вероятно­ стей П(/),у = 1 ,2 ,..., л рассматриваемой цепи Маркова удовлетворяло сис­ теме уравнений детального баланса, необходимо и достаточно выполнение равенства

Необходимость. Так как стационарное распределение П(j),j = 1, 2,

..., л,удовлетворяет системе уравнений детального баланса:

откуда (7(л) = (7(1) (Р\2Ргъ ... Рп-\ЖРпп-\РпЛп-г - />2i). Полученное выражение подставим в (4.13), тогда

л-1

0(1)П(Рм+,/Р*+и)Р„, = G(1)P,„,

к=1

откуда будем иметь равенство

л-1

G(\)(P\2Pll ... РпАпРпХ ~ Р[пРпп-\Рл-1л-2 .*• Pl\V^iPk+\k = 0, к=\

которое в силу (4.11) выполняется для G(l) Ф0.

Таким образом, (4.14) определяет нетривиальное решение системы уравнений детального баланса (4.12), (4.13). Если выбрать G(l) * 0 таким образом, чтобы выполнялось условие нормировки

£<?(*)=1, к=1

то решение (4.14) определит некоторое вероятностное распределение G{k), к = 1,2, ..., п, которое удовлетворяет системе уравнений глобального ба­ ланса и в силу единственности его решения определяет стационарное рас­ пределение исходной цепи Маркова.

Наконец рассмотрим граф состояний марковской цепи, вершины ко­ торого образуют несколько циклов.

Теорема 5. Стационарное распределение вероятностей П(/) состоя­ ний цепи Маркова удовлетворяет системе уравнений детального баланса

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

Достаточность. Покажем, что если для каждого цикла вершин гра­ фа выполнено равенство (4.15), то система уравнений детального баланса непротиворечива.

Выделим в графе состояний цепи Маркова какой-либо цикл (/ь /2,

Пусть вершины im,n < т,рассмотренного цикла принадлежат дру­ гому циклу:

Значения G(i„), G ( /„ + i) ,G{im) вычисляются по равенству (4.16), ос­ тальные значения GQi) определим рекуррентно, используя уравнения де­ тального баланса.

G(Jm*l) G{im)Pt„jm+\/P,m+]imi

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

G(in)Pinjr - G(Jr)PjH = 0.

Подставляя в него решение (4.18) для G(Jr) и (4.16) для G(in\ полу­ чим равенство

которое в силу (4.15) для цикла (4.17) выполняется при G(i\) Ф0. Аналогично определяются остальные значения G(j) для всех вершин

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

Величина G(ii) определяется условием нормировки. Условия (4.15) не обязательно проверять для всех циклов, достаточно их проверить лишь для циклов, минимальных в некотором смысле.

Определение 3. Будем считать, что цикл А включается в цикл В, если все вершины цикла А принадлежат циклу В.

Определение 4. Минимальным назовем цикл, не включающий ника­ кого другого цикла, кроме себя самого.

Определение 5. Циклы будем считать пересекающимися, если они имеют одну или несколько пар инцидентных вершин.

Теорема 6. Если условие (4.15) выполнено для двух пересекающихся циклов, то оно выполнено и для объединяющего их цикла.

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

2. Переходные вероятности для к-го цикла обозначим Ру, здесь к = 1 или 2, тогда условие (4.15) запишется в виде

Перемножив эти равенства, получим

А так как вершины 1 и 2 принадлежат тому и другому циклам одно­ временно, то

Оно совпадает с условием (4.15) для цикла, включающего вершины 2, З1, /и1, 1, л2, ..., 3 , 2 и объединяющего оба исходных цикла.

Следствие. Если условие (4.15) выполнено для всех минимальных циклов графа, то оно выполнено для любого цикла графа состояний цепи Маркова.

Для цепи Маркова, представленной в подразделе 4.2, выполняется условие теоремы 6. Применяя теорему и используя нормировочное усло­ вие, получим

авероятность отказа найдем в соответствии с формулой (4.3).

Взаключение отметим следующее:

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

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

2. Использование критерия эквивалентности глобального и детально­ го балансов цепей Маркова позволяет изменить размерность задачи и вы­ полнять вычисления на ЭВМ средней мощности, используя рекуррент­ ность вычислений. Кроме этого, имеется возможность:

-производить расчеты для любых значений п\

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

табл. 4.1.

5. ПОСТРОЕНИЕ ИМИТАЦИОННОЙ МОДЕЛИ

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

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

Исходные данные:

G - количество каналов измерительного преобразователя (АЦП).

\j - интенсивность поступления заявок на измерение (для одного ка­

нала);

N - число нейронов в АЦП;

£?min, Qmax - диапазон распределения запросов на число нейронов за­ явки входного неоднородного потока;

р - интенсивность обслуживания заявки одним нейроном. Дисциплина обслуживания заявки - система с отказами. Для опреде­

ленности будем считать, что интенсивности поступления и обслуживания заявки распределены по пуассоновскому закону. Запросы на число прибо­ ров распределены равномерно в диапазоне Qmin- 0 max.

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

Пусть г, принадлежит совокупности случайных величин {г,}, равно­ мерно распределенных в интервале (0, 1), {*,} - совокупность случайных величин с известной плотностью распределения. Для пуассоновского рас­ пределения примем

r= J/(x)dx = jA.e-Xjrcbc. -00 о

Осуществив интегрирование, получим

г, = 1 - е"^'

Решая это уравнение относительно имеем

Случайное число г, распределено равномерно в интервале (0, 1), сле­ довательно, (1 - г,) также случайная величина, принадлежащая интервалу (0,1). Поэтому г, и (1 - г,) распределены одинаково. Отсюда

1, */= ^ н е ­

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

Таким образом, интервал времени между заявками определяется следующим образом:

где RND, - равномерно распределенная случайная величина в диапазоне (0,1), генерируемая ЭВМ.

Закон распределения вероятности числа требуемых приборов равно­ мерный в диапазоне (g mjn, бтах)- Поэтому число запрашиваемых нейронов

(т) определяется как

где ROUND - функция округления числа до ближайшего целого.

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

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

к

где - число заявок, получивших отказ за реализацию; К - объем реа­ лизации.

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

Имитационное моделирование включает в себя следующие этапы:

1. Построение входного потока заявок. Заявка генерируется на каж­ дом цикле, поэтому время появления заявки с учетом (5.1) определяется как

G

где Xz = - суммарная интенсивность входного потока; /мод. - модель- 1=1

ное время.

2.Обслуживание заявок. Для каждой заявки, стоящей на обслужива­ нии, проверяется, не истекло ли время ее обслуживания. Если время истек­ ло, то заявка поступает на выход системы и занятые ею приборы освобож­ даются.

3.Генерацию новой заявки. Разыгрывается число приборов, запра­

шиваемых заявкой согласно (5.2). Если число свободных приборов больше или равно т, то заявка принимается на обслуживание и согласно (5.2) оп­ ределяется время обслуживания. Если свободных приборов меньше, чем необходимо для обслуживания заявки (/я), то она теряется (получает от­ каз). Блок-схема алгоритма имитационного моделирования представлена на рис. 5.1.

Описание блок-схемы приведено ниже:

1.Определяются начальные данные. Задаются следующие парамет­ ры: G - число источников заявок в системе, X - интенсивность входного потока заявок на измерение одного канала, р - интенсивность обслужива­ ния одного нейрона, п - начальное количество обслуживающих нейронов в системе, N - число реализаций.

2.Устанавливаются параметры системы для очередного цикла моде­

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

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

Создан некий тип переменных: type

tSRec =record

end;

Здесь поле tosv хранит время окончания обслуживания текущей за­ явки, а поле пп - число затребованных заявкой нейронов, поля prev и next указывают соответственно на предыдущую и последующую заявки.