Автоматика и телемеханика, № 10, 2009
РЛСЯ 89.75.Fb
© 2009 г. М.А. МАТАЛЫЦКИЙ, д-р физ.-мат. наук (Гродненский государственный университет, Беларусь)
О НЕКОТОРЫХ РЕЗУЛЬТАТАХ АНАЛИЗА И ОПТИМИЗАЦИИ МАРКОВСКИХ СЕТЕЙ С ДОХОДАМИ И ИХ ПРИМЕНЕНИИ
Рассматриваются методы нахождения ожидаемых доходов в системах марковских сетей массового обслуживания с доходами произвольной топологии. Приводятся примеры применения таких сетей в качестве математических моделей различных объектов.
1. Введение
Известно, что функционирование любой марковской сети массового обслуживания (МО) описывается с помощью цепей Маркова с непрерывным временем. С описанием и некоторыми результатами по исследованию в стационарном и переходном режимах различных экспоненциальных сетей: с дисциплинами обслуживания FIFO в системах, с ограниченными очередями и блокировками, с приоритетными заявками, с ограниченным временем ожидания в очередях, с ненадежными системами массового обслуживания (СМО), с резервными линиями обслуживания заявок в СМО, с отрицательными заявками, с обходами систем обслуживания заявками и т.д. можно познакомиться в [1-4]. Такие сети имеют различные практические применения в качестве математических моделей в компьютерной технике, производстве и других постоянно расширяющихся областях [5, 6].
В работе Р. Ховарда [7] было введено понятие цепей Маркова с доходами, являющимися константами, и предложено использовать для анализа таких цепей с небольшим числом состояний метод преобразований Лапласа и метод одномерных ^-преобразований. Это понятие легло в основу определения марковских сетей МО с доходами, которые впервые были введены в рассмотрение в [8-11]. Обычно рассматриваются замкнутые сети с большим числом состояний, при исследовании которых возникает проблема размерности [11-20], либо открытые сети со счетным числом состояний [10, 19-26]. Вначале были исследованы замкнутые и открытые сети с центральной СМО в двух случаях: а) доходы от переходов между состояниями сети зависят от состояний и времени [13, 14, 16]; б) доходы являются случайными величинами (СВ) с заданными моментами первого и второго порядков [19, 20]. В [21-30] эти результаты распространялись на случай сетей произвольной топологии. При этом предполагалось, что в случае а) СМО сети являются однолинейными, а в случае б) - многолинейными.
Рассмотрим открытую экспоненциальную сеть МО с однотипными заявками, состоящую из п СМО: Si, 5*2,..., Sn. Под состоянием сети понимается вектор
(1) k(t) = (k,t) = (k1,k2 ,...,kn,t) ,
4 Автоматика и телемеханика, № 10
97
где кг - число заявок в системе в момент времени £ € [0,+оо), I = 1 ,п. Для унификации обозначений введем систему 5о (внешнюю среду), из которой в сеть поступает простейший поток заявок с интенсивностью Л. Интенсивность обслуживания заявок в г-й СМО /¿¿(А^) зависит от числа заявок в ней, г = 1, п. Пусть роу -
п
вероятность поступления заявки из системы 5о в систему Sj, ^ рoj = 1; р^- - веро-
¿=1
п
ятность перехода заявки в СМО Sj после ее обслуживания в СМО S¿, ^ р^ = 1,
__3=0
г = 1 ,п. Заявка при переходе из СМО в СМО Sj приносит ей некоторый доход, а доход СМО Si уменьшается на эту величину, I, ] = 0,п. В принципе, результаты могут быть распространены и на случай, когда уходящая из СМО заявка также приносит ей некоторый доход. Требуется найти ожидаемые (средние) доходы СМО сети за время 4 при условии, что будет известно состояние сети в начальный момент времени.
2. Методы анализа марковских сетей с доходами в случае а)
Пусть г.(к, 4) - полный ожидаемый доход, который получает система Sj за время 4, если в начальный момент времени сеть находится в состоянии (к, 0); г. (к) - доход системы Sj в единицу времени, когда сеть находится в состоянии к; I. - п-вектор с нулевыми компонентами, за исключением компоненты с номером г, которая равна 1; го. (к + I. ,4) - доход системы Sj, когда сеть совершает переход из состояния (к, 4) в состояние (к + I.,4 + Д4) за время А4; —Д.о (к — I.,4) - доход этой системы, если сеть совершает переход из состояния (к, 4) в состояние (к — I.,4 + Д4); г^- (к + I. — Ij ,4) - доход системы Sj (расход или убыток системы Sj), когда сеть изменяет свое состояние из (к, £) на (к + — £ + А£) за время АЬ, I,] = 1 ,п.
Пусть сеть находится в состоянии (к, 4). В течение интервала времени Д4 сеть может остаться в состоянии к или перейти в состояния: (к — I.), (к + I.), (к + I. — ^), I,] = 1 ,п. Возможные переходы между состояниями сети, их вероятности и доходы системы Sj от таких переходов представлены в таблице. Например, если сеть остается в состоянии (к, 4 + Д4), то ожидаемый доход системы Sj составит г.(к)Д4 плюс ожидаемый доход г. (к, 4), который эта система получит за оставшиеся 4 единиц
Таблица
Возможные переходы между состояниями сети Вероятности переходов Доходы системы от переходов между состояниями
(к, г) ->■ (м +Дг) п 3=1 + о(Дг) п(к)А1 + у{(к,1)
(к, г) ->■ (к + 1з,1 + Дг), ] Ф г \pojAt + o(Дí) п(к)Аг + Уг(к + 1э,г)
(к, í) ->■ (к - + Ы), ] Ф г + о(Д^) п(к)А1 + у{(к-
{к,г) + + с, в ф г /ís(fes)гí(fes)pscДí + о(Д^) гДАОДг + гД/с + Д-Д^)
(к,г) ->■ (к + 1г,г + дг) \poiAt + о(Дг) г0г(А; + /4,<) + ?Д/с +Дг)
(к,г) ->■ (к-1г,г + Аг) ^г{кг)и(кг)ргоАг + о(Д2) —Ию(к — Д + гД/г — Д
у,5(к5)и(к5)рцАЬ + о(АЬ)
зфг + о(Д^)
времени; вероятность такого события равна 1 —
Л + £ рз (кз )и(кз) 3=1
Аг + о(Аг), где
и(х) ^ ^ р' X < о' Аналогично, если сеть переходит из состояния (к, г) в состояние
(к + 1г — ,г + Аг), ] ф г, с вероятностью рз (кз)и(кзАг + о(Аг), то сеть приносит системе !Зг доход в размере г^ (к + 1г — 1з ,г) плюс ожидаемый доход сети за оставшееся время, если бы начальным состоянием сети было состояние (к + 1г — 1з).
Тогда, используя формулу полной вероятности для условного математического ожидания, для ожидаемого дохода системы Si можно получить систему разностных уравнений, которая при Аг ^ 0 сводится к системе разностно-дифференциальных уравнений (РДУ):
(2)
¿VI (к, г)
сЙ
Л + Щ Рз (кз )и(кз
3=1
»(к,г)
У^ [Лроз VI (к + 1з ,г) + Рз (кз )и(кз )р^0 VI (к — ,г)]
з=1
У^ [рз (кз)и(кз)р^-иг(к + 1г — ,г) + рг (кг)и(кг)рц-иг(к — 1г + ,г)]
з=1, з=г
У^ [рз (кз )и(кз )рзг Ггз (к + 1г — 1з ,г) — рг (кг )и(кг )ргз Гц (к — 1г + ,г)]
з=1, о=г
У^ [рз (кз )и(кз )рзг Ггз (к + 1г — 1з ,г) — рг (кг )и(кг )ргз Ггз (к — 1г + 1з ,г)]
д'=1,
з=г
у^ рз (кз )рзс г0г (к + 1С — 1з ,г) + Лрог Гог (к + 1г ,г) —
с:ё = 1: с,з=г
— рг (кг )и(кг )рго Кго (к — 1г ,г) + Гг (к).
Число уравнений в этой системе равно числу состояний сети.
Для замкнутых сетей в случае а) система уравнений (2), в свою очередь, пред-ставима в виде системы конечного числа линейных неоднородных обыкновенных дифференциальных уравнений (ОДУ) с постоянными коэффициентами, которая в матричной форме может быть записана в виде
(3)
(М,
ф Яг(г)+ АВг(г),
где П^(г) ф (гиг(1,г)^г(2,г),...'гиг(1,г)) - искомый вектор доходов системы Sг, I - число состояний сети. Решение системы (3) можно найти, используя прямой
метод Бг (г) ф еА1Ог (0) + / еА(4~т^г (т)вт или метод преобразований Лапласа, того
да Бг (г) ф Ж (г) * Qг (г) + Н (г)Пг(0), где Ж (г), Н (г) - обратные преобразования Лапласа соответственно матриц —(в! — А)^1 и (в! — А)^1, * - операция свертки:
Ж (г) * Qг(г) ф / Ж (и^г (г — и) ¿и. Можно доказать [14], что для общего ожидаемого
о
4* 99
дохода сети Б (г) = ^ В() справедливо выражение Б (г) = дг + в + а (г), где д -так
i=l
называемый вектор прибылей, О - вектор весов состояний, а(г) -^ 3$, 3$ - нулевой вектор-столбец. Однако не следует забывать, что число состояний замкнутой сети МО равно I = СП_К_1, где К - число заявок, обслуживающихся в сети; I является довольно большим при относительно небольших п и К, т.е. число уравнений в системе (3) будет также достаточно большим. Опыт показал, что такими методами удобно находить ожидаемые доходы для систем сетей с относительно небольшим пространством состояний (I < 100); прямой метод позволяет вычислять доход для сетей большей размерности по сравнению с методом преобразований Лапласа. Для нахождения ожидаемых доходов можно также применить численные методы [12].
Для открытых сетей, когда число уравнений в системе (2) бесконечно, вычислять ожидаемые доходы в системах сети, в которой доходы от переходов между состояниями не зависят от времени, можно, используя метод ^-преобразований. Введем ^-преобразование для ожидаемого дохода системы Si:
^ ^ ^ ^ п
&(г,г)=^ ]Г ...^^(кък2,...,кп ,г)г* • ... • гП- = ]Т ^ (к,г)Ц ^,
кг=0к2=0 кп=0 1=1
г=1 ,п
где г <Е {(-21, Z2, ■ ■ ■, гп)/\ги\ <1, к = 1, п}. Обозначим в системе (2) через а^к) сумму:
(4) ^ (к) = ^2 [Рз (кз )и(кз г^з (к + ^ - Iз) ~ № (^)и(к)рцГц (к - ^ + )]
3=1
+ + Ь) - рг(Ь)и(кг)рмНм(к - /¿) + п(к), 1 = 1, п.
Будем предполагать, что рг(кг) = ргкг, г = 1,гг, т.е. интенсивности обслуживания заявок в системах линейно зависят от их числа. В этом случае рг(кг)и(кг) = ргкг, г = 1, гг. Тогда система (2) примет вид:
^ (к, г)
сЙ
А + Рз кз
г(к,Ь)
з=1
У^ [Ар$зVi(к + 1з, г) + РзкзРз$Vi(к - ,г)]
з=1
У^ [Рзкзр^Vi(к + ^ - 1з, г) + РiкiРiзVi(к - ^ + , г)]
з=1, з'^
У^ Рз кз РscVi (к + 1С - 18 ,г) + щ (к).
с,з = 1, с,з=
Теорема 1 [25]. Функция <рг(г,г) удовлетворяет соотношению ду.(г,г)
дг
-Ау.(г,г)
Е
з=1
Ароз
П (г, г) - <р\з} (г, г)
+ Рз гз
гг
' /' /1'¡1
гз
д[&(г,г) - ^(г,г)
(^•о^ - 1)--Ь^о^ДМ)
уг(г,г) - (г,г)
дгз
д{п(г, г) - <р?} (г, г)
гз
- > ^зРзс —
с,з , гс
с,з=1, с,s=i
то п
- Е (к)П-
дгi
д (фс(г, г) - ср1с}(г,г)
дг
Ус (г, г) - у^с}(г,г)
А
7 ,
йг=0,
г=1, п
1=1
Г .-> оо оо оо оо
где (г,г) = 52 ... Е Е ... Е Vi(к1,...,кз_1,0,кз+1 ,...кп,г) х
„ к1 к^ х г11 ■ ... ■ гЛ_Л г
к1 =0 к,-1 =0 к,+ 1 =0 кп=$
то
'з'_1 гз+1 ' ... ' гп
Е «¿(М)к=0 П V. з =
к1= о,
1=1,п,
1=1, 1=з
Рассмотрим последнюю сумму в (5). Предположим, что доходы г^(к), Го.(к), До (к) не зависят от состояний сети к, т.е. г.з (к) = г^, Гог(к) = Го. , К.о (к) = До .
1 то , п к \г=1 1-гг) гз Л 1
то п
Поскольку 52 П гк1 = П
"г 11 1 Г и ^ пз и ^г —
йг=о,г=1 г=1 1 —^г ггг=о, 1=1
1=1,п 1=1,п
топ кз
г] гз
дгз
1~гз Д 1
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.