5.2.4 Основная теорема о мультипликативности сети

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

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

Теорема. Если для узлов s типа для узлов s типа и для узлов s типов 2 и то существует предельное (стационарное) распределение вероятностей состояний процесса с плотностью распределения вероятностей

где:

для узлов s типа при

и

для узлов s типа 1

для узлов s типов 2 или 3

Доказательство. Нетрудно видеть, что марковский процесс является неприводимым, регулярным и положительно возвратным по Харрису, так как состояние 0 является для него положительно возвратным атомом. Поэтому для доказательства теоремы достаточно показать, что функция определяемая утверждением теоремы, удовлетворяет системе уравнений для стационарных плотностей распределения вероятностей состояний процесса, которую аналогично дискретному случаю назовем системой уравнений равновесия (СУР).

Для записи СУР введем следующие обозначения. Пусть узел находится в состоянии . Тогда через обозначим скорость обслуживания заявки, находящейся в этом узле, т.е.

а через

интенсивность выхода из состояния z за счет окончания обслуживания заявки в узле. Заметим, что в силу предположения для узлов s типа 0 имеем

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

Так как уравнения будут иметь различный вид для внутренних и граничных состояний множества состояний Z процесса , то разобьем его на два подмножества - внутренних и граничных состояний. К внутренним отнесем такие состояния, для которых для всех тех для которых они определены (т.е. для всех ). Очевидно, что внутреннее состояние - это такое состояние, в котором все заявки, находящиеся в узлах типов 1-3, уже обслуживались какое-то время. Остальные состояния будем называть граничными.

Каждому внутреннему состоянию . поставим в соответствие множество состояний , которые будем называть предшествующими состоянию z. Смысл введения предшествующих состояний заключается в том, что только из них возможен непосредственный переход в состояние z. В свою очередь, все состояния, предшествующие внутреннему состоянию z, разобьем на 4 класса, каждый из которых соответствовать определенному типу перехода в состояние z. Первый класс

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

имеющих вид

где

и

а , могут принимать любые (возможные) значения.

Остальные 3 класса предшествующих состояний не пусты только для сетей МО, в которых есть экспоненциальные узлы. Пусть и состояние z таково, что Предположим также, что

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

где

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

причем каждое состояние имеет вид

где

Множество узлов s, для которых подклассы не пусты, обозначим через

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

причем каждое состояние имеет вид

где

Множество узлов s, для которых не пусты подклассы обозначим через

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

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

Поток, выходящий из состояния z, состоит из двух частей. Во-первых, выход из состояния z осуществляется при поступлении новой заявки в сеть МО (с интенсивностью ). Выходящий из состояния z поток вероятностей, связанный с поступлением новых заявок, равен .

Во-вторых, выход из состояния z происходит и при окончании обслуживания заявки в узле (с интенсивностью ). Общий выходящий из состояния z поток вероятностей, связанный с окончанием обслуживания заявок во всех узлах, равен

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

Кроме того, в состояние z можно попасть в случае поступления заявки в экспоненциальный узел с номером т.е. из состояний классов

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

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

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

Аналогично, в третьем случае суммарный входящий в состояние z поток вероятностей, связанный с переходом заявок из неэкспоненциального узла в экспоненциальный, равен

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

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

Теперь мы можем выписать СУР для внутренних состояний z. Эта система имеет вид

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

Следующая далее лемма 1 выявляет определенные соотношения во внутренних точках z для функции задаваемой формулами (5.2-5.6) и показывает, что каждое из выражений, заключенных в квадратных скобках, равно нулю, и, следовательно, функция действительно удовлетворяет СУР (5.7) во всех внутренних точках

Лемма 1. Функция задаваемая формулами (5.2-5.6) для всех внутренних состояний z сети удовлетворяет соотношениям 1.

2. Для любого узла s типов 1-3 () и любого

3. Для любого узла

4. Для любого узла

5. Для любого узла

Доказательство леммы 1 осуществляется непосредственной проверкой справедливости соответствующих соотношений для функций, определяемых формулами (5.2-5.6).

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

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

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

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

Перейдем теперь к граничным состояниям. При этом достаточно ограничиться такими граничными состояниями z, у которых только для одной пары .

Пусть z - граничное состояние, т.е. состояние, у которого для некоторого . Каждое такое состояние отнесем к одному из 3 типов по следующему принципу.

Пусть . Тогда состояние z отнесем к первому типу граничных состояний. Очевидно, что попадание в граничное состояние z первого типа происходит за счет поступления в сеть МО новой заявки, попадающей на место в (неэкспоненциальный) узел.

Если и то состояние z отнесем ко второму типу граничных состояний. Попадание в граничное состояние z второго типа происходит за счет поступления на место в (неэкспоненциальный) узел заявки, обслуживавшейся ранее в экспоненциальном узле.

Наконец, при и состояние z отнесем к третьему типу граничных состояний. Попадание в граничное состояние z третьего типа происходит за счет поступления на место в (неэкспоненциальный) узел заявки, обслуживавшейся ранее в неэкспоненциальном узле.

Так же, как это было сделано ранее для внутреннего состояния, для граничного состояния z определим множество предшествующих состояний.

Для граничного состояния z первого типа множество состоит всего из одного состояния

где

Для граничного состояния z второго типа множество состоит из состояний имеющих вид

где

Для граничного состояния z третьего типа множество состоит из состояний имеющих вид

где

Выпишем уравнения равновесия для граничного состояния z.

Поскольку переход в граничное состояние z первого типа происходит только из состояния причем интенсивность такого перехода равна то уравнение равновесия в этом случае имеет вид

Переход в граничное состояние z второго типа происходит из состояний с интенсивностями откуда получаем уравнение равновесия

Наконец, переход в граничное состояние z третьего типа происходит из состояний с интенсивностями Уравнение равновесия в этом случае имеет вид

Тот факт, что функция определенная формулами (5.2-5.6), в граничных точках z удовлетворяет СУР (5.8-5.10) вытекает из следующей леммы 2, которая аналогично доказательству леммы 1 проверяется непосредственной подстановкой.

Лемма 2. Функция задаваемой формулами (5.2-5.6), для всех граничных состояний z сети удовлетворяет соотношениям.

1. Для граничного состояния z первого типа

2. Для граничного состояния z второго типа

3. Для граничного состояния z третьего типа

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