ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 4, с. 99-108
СИСТЕМНЫЙ АНАЛИЗ ^^^^^^^^ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ
УДК 681.5
АНАЛИЗ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ МЕТОДАМИ ТЕОРИИ СИСТЕМ СО СЛУЧАЙНОЙ СКАЧКООБРАЗНОЙ СТРУКТУРОЙ*
© 2013 г. В. А. Бухалёв, А. А. Скрынников, А. Ю. Федотов
Москва, ВУНЦВВС "ВВА им. проф. Н.Е. Жуковского и Ю.А. Гагарина" Поступила в редакцию 17.02.12 г., после доработки 20.11.12 г.
Рассматривается задача определения вероятностных характеристик системы массового обслуживания, динамика которой описывается немарковской цепью с конечным числом состояний. Находятся точное и приближенное решения, основанные на теории систем со случайной скачкообразной структурой. При этом система массового обслуживания описывается динамической системой с условно-марковской случайной структурой. С использованием предложенного подхода получено приближенное решение прикладной задачи вероятностного анализа восстановления авиационной техники в ходе боевых действий.
БО1: 10.7868/80002338813030049
Введение. Теория массового обслуживания (ТМО) [1—5] широко используется в задачах исследования надежности, эффективности и проблем эксплуатации во многих областях техники, экономики, социологии, медицины и т.д. Практические задачи ТМО связаны с исследованием многократно повторяющихся однородных операций, подвергающихся воздействию случайных факторов (например, транспортные перевозки, информационные сообщения, обслуживание клиентов, конвейерное производство, элементы военных операций и пр.). Математические модели, используемые в ТМО, принадлежат главным образом к классу марковских систем с конечным числом состояний или, реже, к классу систем, приводимых к марковским различными способами.
Методы ТМО, применяемые для анализа марковских систем с конечным числом состояний, достаточно эффективны и несложны. Однако при расширении класса систем, используемых в математических моделях, т.е. немарковских стационарных процессов, а тем более немарковских нестационарных процессов, сложность методов анализа возрастает, а их точность уменьшается [1—5]. Между тем необходимость в рассмотрении более широких классов систем существует вполне объективно. Достаточно сказать, что в имитационных математических моделях практически нет искусственных ограничений математического характера. Все ограничения носят естественный характер, обусловленный причинно-следственными связями, которые формализованы в модели.
Главное принципиальное ограничение, существующее в марковской системе с конечным числом состояний, заключается в следующем. Основным параметром в такой системе является матрица вероятностей переходов (для дискретной во времени формы представления) или матрица интенсивностей перехода (для непрерывной формы) из одного состояния в другое. Эти вероятности в общем случае зависят от времени, что характеризует влияние на них некоторых детерминированных воздействий, не зависящих от состояний системы. В имитационных моделях, как и в реальных явлениях, переходы из одного состояния в другое в общем случае зависят от случайных воздействий, которые в свою очередь могут зависеть от состояний системы. Если анализ исследуемого объекта путем только имитационного моделирования по каким-либо причинам неприемлем, то в качестве альтернативного подхода можно применить теорию систем со случайной скачкообразной структурой (ССС) [6—17].
Состояние дискретной системы ССС в каждый момент времени к = 0, 1, 2, ... характеризуется вектором [Хк, Бк], где Хк — ях-мерный вектор фазовых координат, принадлежащий непрерывному или счетному множеству; Бк — скалярный индекс состояния структуры, принадлежащий конеч-
* Работа выполнена при финансовой поддержке РФФИ (грант № 13-08-01191А).
99
7*
ному множеству; при этом Хк и — случайные процессы, связанные между собой стохастически или функционально.
Вектор состояния системы — марковский процесс, однако его компоненты Хк и 8к являются условно-марковскими (обе вместе или хотя бы одна из них), т.е. немарковскими. Это означает, что состояние одной из компонент в дискретный момент времени к + 1 зависит не только от ее состояния в предыдущий момент времени к, но и от состояния другой компоненты в момент к.
По сравнению с системами, рассматриваемыми в ТМО, класс моделей, анализируемых методами теории ССС, является более широким, а алгоритмы анализа представляют собой рекуррентные формулы (или дифференциальные уравнения), хорошо реализуемые на современных ЭВМ.
1. Постановка задачи. Дискретная динамическая система ССС описывается стохастическим рекуррентным уравнением
Хк+1 = Фк($к+1, Хк, $к, "к), (1.1)
где Е к — вектор возмущений, т.е. последовательность векторных случайных величин, независимых при разных к, с известной функцией распределения Фк(2,к), которая служит общим описанием как для непрерывных распределений, например гауссовского, так и для дискретных, например распределения Бернулли; фк (•) — вектор известных детерминированных функций своих аргументов.
Объединенный вектор [Хк, Бк] называется вектором состояния системы. Индекс структуры 8к — условно-марковская цепь с конечным числом состояний, заданная условными вероятностями переходов из состояния зк в состояние зк+1 при фиксированном значении хк:
ук(зк+1!хк, я к) = Р [^к+1 = Зк+11Хк = хк, ^к = Як]> Зк = 1> пз • (1-2)
В (1.1), (1.2) большими буквами Хк, Бк, Ек обозначены случайные величины, а соответствующими им малыми буквами хк, зк, 2, к — детерминированные переменные; = означает равенство по определению; Р [•] — символ вероятности.
Известно начальное распределение вероятности вектора состояния — у0(х0, 50). Требуется найти текущее распределение ук(хк, зк), плотность вероятности фазовых координат /к(хк), вероятности состояний структуры рк ($к) и другие вероятностные характеристики, зависящие от них.
2. Точное решение. Используя формулу полной вероятности и формулу умножения вероятностей [18], запишем равенство
У к+1(Хк+1, ^+1) = X I8 к (Хк+1!^к+1, Хк, Sk )Ук (^Хк, Sk )у к (Хк, Мхь (2.1)
где бк(Хк+1!^к+1, Хк, зк) — плотность вероятности перехода из хк в Хк+1 при фиксированных зк+1, 5к; символом |() йХк обозначен кратный определенный интеграл по всему евклидовому пространству 1№п изменения вектора хк.
В (2.1) дк (эк+1|Хк, sk) задана (см. (1.2)), а б к(Хк+1|^к+1, Хк, sk) можно найти из (1.1). Для этого определим условную характеристическую функцию вектора Хк+1 при фиксированных зк+1, хк, зк [9, 19, 20]:
0к-и(юкк+1, Хк, Sk) = Ы[ехр[ттXк+1>!^к+1, Хк, Зк] =
= |ехр{/юТХк+1> е к (Хк+К+1, Хк, Зк) йХк+1,
где Т — символ транспонирования; М — математическое ожидание (МО). Отсюда с учетом (1.1) следует
0к+1(ю I Зк+1, Хк, Зк) = |ехр{/ютФк(эк+1, Хк, Зк,%к)> ^Фк(%к), (2.2)
где |() йФк(,к) — кратный интеграл Стилтьеса [18].
Плотность вероятности sk(xk+1|sk+1, xk, sk) связана с 0k+1(®+1, xk, sk) обратным преобразованием Фурье
еk(Xk+1ISk+1, Xk, Sk) = (2n)~"x Jek+1(®|sk+1, xb Sk) expHro^k+Jd®. (2-3)
Подставив (2.2) в (2.3), получаем
sk (xk+1|sk+1, xk, Sk) =
n TT T (2.4)
= (2n) x JJ exp{/w [9k(Sk+1, Xk, sb £k) - xk+1]} dm dФk(^).
Так как (2n) Jexp {/ют[9k(•) - xk+1]} dю = 5[9k(•) - xk+1], где 8(9k(•) - xk+1] — многомерная дельта-функция Дирака:
x /ч 1 fa xk+1 = Ф k() [0, xk+1 * фk("), то формулу (2.4) можно записать также в виде
sk(xk+1 | Sk+1, xk, Sk) = Js[9k(Sk+1, xk, Sk, %k) - xk+1] dOk(2,k), (2.5)
и в приложениях пользоваться формулами (2.4) либо (2.5) в зависимости от конкретного вида функций 9k(-) и (2, k). Например, при гладких, монотонных функциях расчеты удобнее выполнять по формуле (2.5), а при разрывных функциях — по формуле (2.4).
Уравнение (2.1) — функциональное рекуррентное уравнение, решаемое численно на ЭВМ. Найдя уk(xk, Sk), можно отыскать и другие вероятностные характеристики Xk и Sk, например: вероятность состояния структуры Sk:
Pk (Sk) = Jy k fe Sk) dxk;
плотность вероятности фазовых координат Sk:
fk(xk) = X Yk(xk, Sk);
Sk
наиболее вероятное значение состояния структуры:
Sk = arg max Pk (Sk);
Sk = 1, nS
безусловное МО вектора Xk:
xk = Jxkfk (xk) dxk ;
безусловную корреляционную матрицу (КМ) вектора Xk:
Rk = J(xk - x!)(xk - xt ffk (xk) dxk;
условную плотность вероятности Xk при фиксированном sk:
fk (xk\Sk) = Pkl(Sk)Yk(xk, Sk);
условное МО вектора Xk при фиксированном sk:
xk(Sk) = Jxkfk (xk\Sk) dxk;
условную КМ вектора Xk при фиксированном sk: Rk(Sk) = J[xk - x(Sk)][xk - x(Sk)]Tfk (xk|Sk) dxk.
3. Приближенное решение. Необходимость в точном решении не всегда существует, потому что математическая модель (1.1), (1.2) и исходные данные, как правило, неточно описывают реаль-
ное исследуемое явление. Приближенное, но более простое решение может быть получено следующим образом.
Используя связь вероятностных характеристик Хк, Бк с распределением вероятности ук(Хк, Зк), на основании (2.1) запишем следующие уравнения:
Хк+1 =
рк+1(зк+1) - |ук+1(Хк+1, Зк+1) Лхк = X ^Чк (зк+1|Хк, 3 к) У к (Хк, 3 к) Лхк к (Хк+1! Зк+1, Хк, Зк) Лхк+1,
откуда на основании очевидных формул
У к (Хк, ¡к) = /к (Хккк )Рк (¡к ),
к(Хк+1|зк+1, Хк, ¡к) Лхк+1 = 1 следует
РкЖ-и) = XРк(¡к)\чк(¡к-иХк, Зк) /к (Хккк) ЛХк. (31)
¡к
Найдем условное МО хк+1($к+1): Хк+1(Зк+1) = |Хк+1/к+1(Хк+1кк+1) Лхк+1 = = рк-+1(Зк+1) |Хк+1У к+1(Хк+1, як+1) Лхк+1 =
= Рк+1(Зк+1)Х \Чк (Зк+1Х, Зк) У к (Хк, Зк) ЛХк |Хк+18 к (Хк+1кк+1, Хк, Як) ЛХк+1 = (3.2)
Зк
= рк-+1(Зк+1)Х Рк(Зк) (Зк+1|Хк, як) /к (Хк\як) Лхк |Хк+18к(Хк+1|Зк+1, Хк, як) ЛХк+1•
Аналогично для Як+1($к+1) имеем
+1(Зк+1) = |[Хк+1 - Хк+1(Зк+1)][хк+1 - Хк+1(Зк+1)] /к+1(Хк+1|Зк+1) Лхк+1 = = ; Г У, Рк(Зк) I ук (Зк+1\Хк, Зк) /к (Хк\Зк) Лхк Х
(3.3)
Рк+1(Зк+1) 1
Х |Хк0+1(Зк+1)хк+1(Зк+1) 8 к (Хк+1\Я к+1, Хк, як ) Лхк+1,
где хк+1(Зк+1) = Хк+1 - Хк+1(Зк+1).
Безусловные МО и КМ вычисляются по формулам
хк = X Хк (Зк) Рк (Зк),
Л* = (Зк) + хк(Зк)х!(Зк)]Рк(Зк) - Х1(Х1)Т•
Плотность вероятности перехода ек(хк+1\Зк+1, хк, Зк) определяется из (2.4) или (2.5).
Выражения (3.1)—(3.4) превращаются в замкнутую систему уравнений относительно Р($к), хк и Як, если неизвестную плотность вероятности /к (хк\Зк) аппроксимировать известной функц
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.