Исследование управляемых конечных марковских цепей с неполной информацией и его приложение к расчету показателей надежности сложных систем Карманов Анатолий Вячеславович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Карманов Анатолий Вячеславович. Исследование управляемых конечных марковских цепей с неполной информацией и его приложение к расчету показателей надежности сложных систем : дис. ... д-ра физ.-мат. наук : 05.13.01 Москва, 2005 249 с. РГБ ОД, 71:07-1/15

Содержание к диссертации

Стр.
Основные обозначения 5

Введение 5

1. Управляемые конечные марковские цепи (УКМЦ)

УКМЦ с полной информацией. Цель и основные результаты исследования 27
УКМЦ с неполной информацией. Цель и основные результаты исследования 42

2. Свойства множества однородных конечных марковских цепей
с доходом

Стационарные характеристики 50
Отношения эквивалентности 54
Методы расчета стационарных характеристик 63
Свойства стационарных характеристик 69

3. Частичные упорядоченности в множестве Н^п

Определение і -частичной упорядоченности 71
Свойства частичных упорядоченностей 72

3.3 Доказательство основных теорем 78

4. Минимальные и максимальные элементы в подмножествах
множества Н^п и их свойства

Определение минимальных и максимальных элементов. Условия их существования 94
Случай 1 ЮЗ
Случай 2 108
Случай 3 114
Случай 4 129
Случай 5 142

5. Частичные упорядоченности в множестве jr(Hⁿ)

Определение ^-частичной упорядоченности. Максимальный и минимальный элементы 151
Теоремы существования минимального и максимального элементов

в множестве A(U) 155

5.3. Некоторые свойства частичной упорядоченности 167

6. 1-частичная упорядоченность в множестве f} и ее свойства

Определение 1-частичной упорядоченности. Минимальные и максимальные элементы в подмножествах множества 177
Условия существования минимальных и максимальных элементов

в замкнутом множестве 180

6.3. Теоремы существования (1, є )-минимального и (1, є )-максималь-

ного элементов 188

7. 1-частичная упорядоченность в множестве я{р)

Определение 1-частичной упорядоченности и ее свойства 198
Теоремы существования 1-минимального и 1-максимального элементов в множествах Д , и J,^ 202
Теоремы существования 1-минимального и 1-максимального элементов в множествах S „ и .q 206

8. Основные свойства управляемых конечных марковских цепей

Основные свойства УКМЦ с полной информацией 215
Основные свойства УКМЦ с неполной информацией 219

9. Алгоритм решения задачи оптимального управления сложной
системой с неполной информацией о надежности элементов

Алгоритмы решения вспомогательных задач 228
Алгоритм решения основной задачи 234
Обоснование алгоритмов 234

10. Заключение 245

11. Литература 245

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

УКМЦ - управляемая конечная марковская цепь.
КМЦД - конечная марковская цепь с доходом и ресурсом.
R¹ - множество всех действительных чисел.
{хє А : В(х)} - совокупность всех элементов х из множества А, для которых выполняется условие В(х).
е#(') - множество всех подмножеств множества ().
[х, у] - замкнутый интервал, где xgR¹ , yeR¹.

J= (1,.. ., n} - конечное множество состояний. Любой элемент из множества J называется состоянием и обозначается через і, где i=l,n , п-натуральное число.
Р\_А- {{а\,..., а_а): а\ +... +а_а= 1, а;>0, і=ІТп} - множество всех

n-мерных стохастических векторов - строк.

а - начальное распределение, aeP\_fi.
Н = /\пХ[-Ро, р₀]х[а₀, pj, где 0<а_о<(З_о.

П.Н^п=Нх...хН - прямое произведение п экземпляров множества Н.

12. h = (hi,... ,h_n) - любой элемент из множества Н^п, где hi=(hji,..
Ди, h_i>n+i,h_u+2)GH, і=й . При этом (h_u,..., Ъ^)еР\^ п_і)П+іє[-(3₀, р₀],

Ьу,+2Є[(Хо, Ро].

P(h) = (h;j) - стохастическая матрица порядка ^соответствующая элементу h, где i=l,n , j=l,n .
qi(h) = [h^+i,..., Ivh]⁷ - вектор - столбец дохода, соответствующий элементу h, где т - знак транспонирования.

q₂(h) = [hj^+2,. . . ,^+2^- вектор - столбец ресурса, соответствующий элементу h.
^„(а, h) - однородная конечная марковская цепь с доходом и ресурсом (однородная КМЦЦ), задаваемая начальным распределением а, матрицей переходных вероятностей P(h), векторами дохода и ресурса соответственно qi(h) и q₂(h).
S₀ = {о(а, h) : aeP\_fl , 1ієН^п} - множество всех однородных

КМЦЦ с числом состояний равным n .

= {(h⁽¹⁾,..., h⁰⁰,...); Ь^єН", к=ї^}.
= (11^,...,11^,...) - любой элемент из множества о.

(Р^(к)()?)}" - последовательность стохастических матриц, соответствующая элементу Ь , где P^(k)(l»=P(h^(k)), к=1,оо .
{q⁽,^k) ()?)}" - последовательность векторов дохода, соответствующая элементу )> , где q[^k)()» = qi(h^(k)), k=l,oo .
{q⁽₂^k) (>)}" - последовательность векторов ресурса, соответствущая элементу Ь,где qf(l»=q2(h^(k)), k=V» .
,{а, Ь)- конечная марковская цепь с доходом и ресурсом (КМЦЦ),

задаваемая начальным распределением а , последовательностью матриц переходных вероятностей {P^(k)()}", последовательностями векторов дохода и

ресурса соответственно {q⁽,^k)(&)}", {q^O»}"-

S= {,{а, Ь): яє?^, !>є} - множество всех КМЦЦ с числом состояний равным n.
% ={l,...,m(i)} - конечное множество управлений в состоянии і.

[U\, в{Щ] - пространство управлений, где йв(Щ - множество событий, определенное на множестве %.
Р[ - множество всех вероятностных мер на пространстве

2&.P=P_lx...xp_n,

29. S = {|>⁽¹⁾, . . . , *^(к), . . . ] : №еР, к=1,оо}- множество (марковских)

стратегий, где *^(к) = [о/^к\..., ^], ^^к)еР_ь i=u .

s = [*⁽¹⁾,. . ., J,. . . ] - любой элемент из множества S, именуемый стратегией и представляющий собой последовательность вероятностных мер на пространствах управлений [%,#(%)]> і=ї^п .
ці і : U\ -»H - борелевское отображение множества % в множество Н, i=u .
>(s) - элемент множества $, соответствующий стратегии s, где

seS, Ъ{*)=^%^{\ , *%*>),. .. ], hk)U^(k))> ,hi^k4^^k))]eHⁿ,

к=ІЯ hi«U^w)eH, те^к))= Vi(l)*5^} ++ Vi(m(i))C). ⁱ⁼^

[S, S, ] - управляемая конечная марковская цепь (УКМЦ) с полной информацией, где f: S -> S - отображение множества стратегий S в множество всех КМЦЦ И, задаваемое соотношением (s) = %{а, (s)), seS.
iDj(wi) - характеристика неполной информации в состоянии і, соот -ветствующая управлению щ, где !Д(иі)с Н, i=l,n, щ= 1,..,m(i).
(s) = {[п⁽¹⁾(>⁽¹⁾),..., hk> (j)^^k) , hi» фє

j-i

є 2)i(j), і⁼ In , k = I,» } - нестационарная характеристика неполной ин-

формации , соответствующая стратегии s, где se S, * = [*{^fc),...,^¹⁰] -соответствующая компонента стратегии s, 11^(/^) = [h{^k)(y,^k)),...,h⁽_n^k)(^⁽_n^k))] є єН^п, к=ІЯ

36. i(s) = {[h⁽¹⁾(*⁽¹⁾), ..., h%^{k)),...]et)(s): [ для любого k = 1^ выпол-

m(i)

няется равенство h[^k)(>,^(k)) = ^ Q^^k) , hi(j)ei(j), і = l,n ] } - стационарная

j=i

характеристика неполной информации, соответствующая стратегии s.

[S, с5#(Е), j] - УКМЦ с неполной информацией и стационарной характеристикой неполной информации, где S - множество стратегий, с4(Е) --множество всех подмножеств множества S, #i: S-*c#(E) - отображение, определяемое выражением : #i(s) = {Ца, 1» : аеРі_д, ei(s)}.
[S, с#(Е), &2І - УКМЦ с неполной информацией и нестационарной характеристикой неполной информации , где 2 : S -» сДЕ) - отображение, определяемое выражением: ^(s)⁼ {Ца, >) : аєР\_А, >g(s)}.

Введение к работе

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

Хотя первые публикации по управляемым конечным марковским цепям (УКМЦ) появились в конце пятидесятых начале шестидесятых годов [2-8] , исследования в этой области интенсивно продолжаются и в настоящее время [12-16, 24-28, 32-68], что с одной стороны определяется плодотворностью теории УКМЦ, а с другой стороны показывает, что не все запросы практики удовлетворяются ею полностью.

Действительно, в приложениях часто возникает ситуация, когда непосредственное использование полученных в теории УКМЦ результатов становится некорректным, что указывает на существование иных, хотя и близких к УКМЦ , но в должной мере не изученных математических объектов. Для описания одного из таких объектов, названного УКМЦ с неполной информацией, подробней остановимся на ситуации, в которой он возникает.

Прежде всего, укажем некоторые особенности определения и способа задания УКМЦ с конечным множеством управлений. Для наглядности эти особенности выявим на примере некоторого технического объекта, управляемого диспетчером и обладающего следующими свойствами :

1. Объект характеризуется наблюдаемыми и регистрируемыми в дискретные моменты времени tk параметрами, где к=1,оо. Множество значений этих параметров является конечным множеством, независящим от к. Это

множество представляется в виде : J = {1,..., п}, - и называется множеством состояний объекта, где пєо/V ;

2. Если в момент времени t_k4 объект находится в состоянии і, то дис
петчер должен с вероятностью * [J выбрать одно управляющее воздействие
из конечного множества % допустимых управляющих воздействий в

СОСТОЯНИИ І И ПрИМеНИТЬ ЄГО К Объекту, ГДЄ к = 1,00 , % = {1,...,т(і)}, І = 1,П.

Управляющее воздействие примененное к объекту, влияет на его дальнейшее поведение следующим образом: состояние объекта в следующий момент времени t_k будет j с вероятностью рц(), где j =l,n . Для вероятностей &$,

Рц() выполняются соотношения:

^>о, *{?+... + *„, =1, О)

р#)>0, М0 ⁺ -⁺Ри(0 = 1. (2)

где і = Tin , j = ЇГп , е % . При этом стохастический вектор д[^к) = [$,. , ^_{і) ]

именуется рандомизированным управлением в состоянии і, а стохастический вектор рі( ) = [рі_;і(^ ),..., рі_А( )] - вектором переходных вероятностей в состоянии і, соответствующим управляющему воздействию і, где ІЄІІі .

В начальный момент времени to объект находится в состоянии і с

її

вероятностью а\, где а\ > О, і =l,n , д; ⁼ ¹- Вектор а = [а\ , . . . , а_а]

называется начальным распределением;

3. Если в момент времени tk-i объект находился в состоянии і и было
применено управление , то на интервале времени [t_k_i, t_k], именуемом по
традиции [5] к -ым шагом, объект приносит доход равный qi() , где і =
= йі, ^єї/;,к=1,оо. При этом для дохода выполняется соотношение :

-p₀<_qi(0<(3o, (3)

где р_о>0.

Соотношения (3 ) указывают на то, что доход является ограниченной величиной.

Объект, обладающий свойствами 1-3, представляет собой управляемый марковский объект. Укажем следующие пять его основных особенностей :

1. Управление объектом осуществляется диспетчером в дискретные
моменты времени tk-ь где к = 1,оо, в соответствии с правилом s , называемым
(марковской) стратегией и имеющим вид : s = [*⁽¹⁾,..., *^(к),.. . ], (4)

где 4^(к) = [,4,^(к),..., ^^к)], *[^к) - рандомизированное управление в состоянии і,

применяемое в момент времени tk_i (или на к-ом шаге), к = 1,оо, і =i,n . При этом множество S всех стратегий вида (4), называемое множеством (марковских) стратегий, имеет вид :

S = {[^...,^,...]:^k=W, (5)

где *^(k) = U^(k\ ,*.^№)]e^ P = P_lMnx.. .хЛмп), *i^WePirf>, *W

множество всех m (і)-мерньіх стохастических векторов, i=l,n.

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

2. Минимальным набором исходных данных, которым можно задать рас
сматриваемый марковский объект, является следующая совокупность :

[a,J,{%:i₆J},{hi(^): *_е%Ы}], (6)

где h^) = [_Pi>1(^..,p_u(^q^)];

3. При фиксированной стратегии s, где seS, наблюдение за процессом
смены состояний и управлений объекта в моменты времени tk, k=0,oo дает
траекторию г, которая имеет вид:

r=[(io^i),(ii,4),...,(i_k,4₊i),...], (7)

где (ik , 4+i) - пара, состоящая соответственно из состояния i_k, в котором пребывает объект в момент времени tk, и управляющего воздействия 4+i, примененного диспетчером к объекту в этом состоянии. При этом для любого к, где к=0,оо, справедливо выражение: і_к є J, 4+1 є Ц_к. Вероятность

траектории г определяется, в соответствии с определением стратегии s и исходными данными, изложенными в свойстве 2 объекта, по формуле:

^{р», и -ч. <:«, р»!,, («х... х}^»a_w^._P^g_M⁽⁴₊₁⁾^х...⁽⁸⁾

Таким образом, формируется вероятностное пространство траекторий:

(R,.^(R),P_a,_s), (9)

R - множество всевозможных траекторий г, имеющих вид (7), $(R) -

множество событий на множестве траекторий , P_as - вероятностная мера, заданная на множестве $(R) и обладающая свойством (8);

4. При фиксированной стратегии s, где seS, математической моделью процесса смены состояний объекта в дискретном времени tk , где к =0,», является конечная марковская цепь t](s) . Эта цепь представляет собой последовательность случайных величин щ, к =0,а>, определенных на вероятностном пространстве траекторий (9) выражением :

Лк(г)= іь к=0Я (10)

где reR . При этом следующая условная вероятность, называемая переходной вероятностью из состояния і в состояние j при стратегии s на (к+1)-ом шаге, определяется в соответствии с выражением (8) по формуле :

=,S⁺¹⁾ PuO) + .+ Pij(m(i)), (И)

где ^^к+1)- рандомизированное управление, применяемое в состоянии і в момент времени tk (на (к+1)-ом шаге) и являющееся соответствующей компонентой стратегии s, i = l,n,j=l,n,k=0,oo.

В момент времени to марковская цепь rj(s) имеет начальное распределение а, т.е. Ра,Б(ло=і) = Яі, гдеі ⁼ ^:й;

5. Пусть при фиксированной стратегии s, где se S, управляемый марков
ский объект в момент tk находится в состоянии і, тогда за (к +1)-ый шаг он
приносит доход, который в соответствии со свойством 3 определяется по
формуле : фГ¹⁾) = 4Г Ф(0 + +«) 4>(т(і)), (12)

где i = l,n, k=0,co.

Теперь дадим определение УКМЦ с конечным множеством управлений и укажем особенности этой управляемой цепи.

Пусть (s) = (ti(s), q(s)) - конечная марковская цепь с доходом (КМЦД), соответсвующая стратегии s , где seS , t|(s) = {r|_k, k =0,oo} - марковская цепь, определенная выражением (10), q(s)= {q(V^k+1)), k=0,oo }, q(^^(k+1))= =

[qiW^X > qn(^^<_n^k+1))]^T- вектор дохода за (к+1)-ый шаг цепи r|(s), т- знак

транспонирования, qi(*-^k+1)) - величина, определяемая выражением (12), і = = 1,п, и пусть S - множество всевозможных КМЦД с числом состояний равным n.

Тогда УКМЦ с конечным множеством управлений представляет собой
совокупность, имеющую вид : [ S , S , ], (13)

где : S -> Н , т.е. является отображением множества стратегий S в множество всех КМЦД 5 ; при этом (s) = (ti(s), q(s))H (s)eS .

Теперь укажем две основные особенности УКМЦ, являющиеся следствием ее определения:

а. Каждой фиксированной стратегии s, где seS , ставится в соответствие одна конечная марковская цепь с доходом (s), которая задается следующей совокупностью исходных сведений;

[a, (P^(k+1)($), k=0^}, (q^(k+1)(*), k=0^}], (14)

где а - начальное распределение, Р¹ ^;($) = (рц(*[^к+|))) - матрица переходных вероятностей на к-ом шаге, имеющая порядок п и элементы которой определяются выражением (11), q^(k+1)($ = q( J^^+l)) - n-мерный вектор дохода за k-ый шаг, і-ая компонента которого определяется выражением (12), і =ї~п ;

б. УКМЦ является математической моделью рассматриваемого управляемого марковского объекта и может быть задана совокупностью исходных данных, определяемой выражением (6). Здесь же отметим, что в подавляющем числе работ, например [4-6, 12-16], УКМЦ традиционно задается именно этой совокупностью .

Сформулируем теперь цель управления УКМЦ.

Если каждой фиксированной стратегии s, где sgS, поставить в соответствие значение среднего дохода, получаемого за один шаг марковской цепи (s) и определяемого, например, выражением :

0(s)=I5k-4№u(s),k) (15)

ІС-»оо

где Q(a,5 (s), k) = а П^р(Н)(⁸) Л), (¹⁶)

то цель управления УКМЦ состоит в максимизации этого дохода, т.е. в определении такой оптимальной стратегии s , для которой выполняется соотношение:

(s):seS } (17)

Отметим, что : 1) Ф (s) является функционалом, заданным на множестве стратегий S , т.е. Ф : S -> R¹ , а выражение (17) определяет критерий оптимальности для УКМЦ ; 2) Q(a, (s), к) является средним аддитивным доходом, получаемым на цепи % (s) за интервал времени [to, t_k] (или за к шагов), при стратегии s, где seS ; 3) именно стратегию s необходимо иметь диспетчеру для осуществления эффективного управления,

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

УКМЦ , задаваемая совокупностью (6), исследуется в работах [4,5,8] и основным результатом здесь является следующее утверждение: существует непустое множество оптимальных стратегий, независящих от начального распределения, и это множество содержит стационарную вырожденную в точке и стратегию s(u), где s(u) = [lv.., и_п), щ

є etdi, і = l,n, *(u) = [n)] є P, ^i(ui) - стохастический вектор,

вырожденный в точке U;, т.е. 4у(ііі) = 1, если] = Ui, *ij(uj) = 0, если] * щ, j =

1,..., m(i), і =l,n. При этом процедура поиска указанной оптимальной стратегии представляет собой итерационный алгоритм Р.Ховарда, сходящийся за конечное число итераций. Этот результат имеет важное прикладное значение, т.к. позволяет осуществить поиск оптимальной стратегии s на конечном множестве стационарных вырожденных стратегий.

Однако использование указанного результата теории УКМЦ становится некорректным в следующей ситуации, часто встречающейся в приложениях при управлении марковским объектом : значение вектора

^ад=[(р_ц^{(п...,рао, ф(')]>.}^сію

определяющего стохастические свойства управляемого марковского объекта и входящего в совокупность (6) точно неизвестно, а известна лишь некоторая

область его значений !%0, где = 1,..., m(i), i = l,n .

Укажем следующие два случая, которые приводят в приложениях к возникновению указанной ситуации :

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

ЭД, где^=1,...,т(і),і=й;

2. Вектор hi(f) зависит от некоторого изменяющегося во времени параметра Vi (t_k), где к = 1,оо, т.е. hj(f) = f(f,Vj (t_k)) . Про этот параметр известно лишь то, что он принимает значения го некоторого множества Уі(^)которое порождает область

0i(/) = {f&Vi(tfc)) : Vi(1k)eV,(0}, (19)

где = 1,..., m(i), і =ЇЯ Область (D[(i) является характеристикой неполной информации в значении

вектора hj(^), где ЫЯ4.\, і =1,п, и входит в совокупность исходных данных, которой задается новый объект - УКМЦ с неполной информацией. Эта совокупность записывается аналогично совокупности (6) и имеет вид :

[в, J, ( : i_eJ}, №(/): ^ i_eJ }] (20)

Понятно, что в случае, если )[(), є% , і =1,п являются

одноэлементными множествами, то совокупность (20) совпадает с совокупностью (6), т.е. УКМЦ с неполной информацией тождественна УКМЦ, которую теперь уместно именовать УКМЦ с полной информацией.

Существенное отличие УКМЦ с полной информацией, задаваемой совокупностью (6), от УКМЦ с неполной информацией, задаваемой совокупностью (20), заключается в следующем : если любой стратегии s, где seS, в УКМЦ с полной информацией соответствует одна марковская цепь с доходом (s), задаваемая совокупностью (14), то в УКМЦ с неполной информацией каждой стратегии s будет соответствовать множество марковских цепей (s), определяемое на основе данных совокупности (20).

Так как определение множества Щ), где sgS, требует дополнительных

формальных построений, которые целесообразно опустить при первом, во

і многом качественном знакомстве с УКМЦ с неполной информацией, то

сейчас - в введении в предмет исследования- это определение не приводится

(оно подробно и во всех нюансах излагается в разделе 1.2). Однако, чтобы оценить элементный состав множества $(s) отметим, что даже для наиболее простого случая, когда s является стационарной вырожденной стратегией, множество 3F(s) может содержать в качестве элементов как однородные, так и неоднородные марковские цепи с доходом, которые задаются совокупностями вида (14).

Теперь сформируем функционал для УКМЦ с неполной информацией.

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

множества (s) , где seS, является процессом блуждания марковского объекта по своим состояниям, то функционал Ф(б), определяемый выражением (15), трансформируется, ориентируясь на «наихудшую» цепь из множества f(s), и записывается в виде:

«4(8)= inf (jEk-'-QteS.k): ^е (s)}, (21)

* где Q(a, , к) - средний аддитивный доход за к шагов марковской цепи с

доходом, определяемый в соответствии с выражением (16).

Таким образом,

Цель управления УКМЦ с неполной информацией сохраняется той же, что и в случае УКМЦ с полной информацией, и состоит в максимизации гарантированного среднего дохода <&i(s) , т.е. в определении такой оптимальной стратегии s*, если она существует, или такой є - оптимальной стратегии s_s, если s не существует, для которых выполняются соотноше -ния:

44(s*) = sup{C»i(s):s6S}, (22)

Фі(зУ *i(ss) < є , (23)

где є - некоторое положительное число.

Несмотря на достаточно простой способ задания совокупностью (20), УКМЦ с неполной информацией является довольно сложным математическим объектом. На это, в частности, указывает следующее обстоятельство : даже при «хорошей» - стационарной вырожденной стратегии s, где seS, множество (s) может содержать в качестве элементов неоднородные марковские цепи, требующие разработки специальных методов их сравнения (частичного упорядочивания).

До настоящего времени УКМЦ с неполной информацией, функционалом (21) и критерием оптимальности (22) в полном объеме не исследовалась, хотя ее частные случаи рассматривались в работах В.А.Каштанова, Е.Ю.Барзило -вича, Н.Гирлиха, В. Фогеля и др. Открытыми оставались вопросы : о существовании оптимальных стратегий, о существовании оптимальных стратегий, независящих от начального распределения, о существовании оптимальных стационарных вырожденных стратегий и т.д.

В настоящей монографии проводится полное описание и исследование УКМЦ с неполной информацией, выявляющее такие экстремальные свойства фундаментальных характеристик марковских цепей с доходами в множествах Щб), seS, которые позволяют как доказать существование оптимальных стационарных вырожденных стратегий, независящих от начального распределения, так и разработать итерационную процедуру их нахождения.

Работа строится по принципу «от простого к сложному» и состоит из 9 разделов и заключения.

В первом разделе даются определения УКМЦ как с полной, так и с
неполной информацией. Указываются цели и основные результаты исследо
вания указанных УКМЦ.
» Во втором разделе рассматриваются основные свойства множества 2 ₀

всех однородных КМЦЦ с числом состояний равным п, которое представля-

ется в виде : Н₀= {ZJa, h): аеР_1д, ЬєН"}, где ₀(а, h) - однородная КМЦД,

задаваемая парой (a, h), а - начальное распределение, P_lfl - множество всех

n-мерных стохастических векторов-строк, Н^п = Н х . . . х Н - прямое произведение п экземпляров множества Н, Н = Л,_п х [-р₀, Ро], Ро> 0, h =

=[h,,..., h_n] єН^п, hj= [hg , ... , hyn+JeH , элемент h определяет матрицу переходных вероятностей P(h) и вектор-столбец дохода qi(h), P(h) = ( hy), i = = l,n , j =l,n , qi(h) = [hi_sn+i,..., Iv-h]⁷, hjj - соответствующая компонента элемента h .

В третьем разделе вводится ^-частичная упорядоченность в множестве Н" основанная на сравнении стационарных характеристик *_t(h), w_k(h), k =

= 1,оо однородных КМЦЦ о(д, h), he Hⁿ, где = 1,<», и устанавливаются ее основные свойства, где «i(h) = Я(п)- qi(h) - вектор финитного дохода, JTQi) -

- матрица финитных вероятностей и JT(h) = limk'^pB + P(h) + ...+ P^k_1(h)],

E - единичная матрица порядка n, w_k(h) = (-l)^k+1-[B₁^k(h) qi(h) - *i(h)], k=I^o - вектора «весов», B^h) = (E - P(h) + TC(h))'¹ - матрица, обратная к

фундаментальной матрице (Е - P(h) + 7T(h)) .

Одно из основных свойств ^-частичной упорядоченности, которое утверждает, что в множестве Н^п существует не более (п+2)-ух различных частичных упорядоченностеи, при этом различными могут являться упорядоченности, для которых -\,п+2.

В четвертом разделе определяются - минимальный, - максимальный и (, є)- минимальный, (, є)- максимальный элементы в множестве >, где

е {1,..., п+2}, є>0, 2)сН^п, и выявляются свойства этих элементов.

Этот раздел состоит из шести подразделов.

В первом подразделе даются определения - минимального, -максималь-ного и (, є)- минимального, (, є)- максимального элементов в множестве 2).

Во втором подразделе рассматривается случай, когда множество (D -

^=<D\x. . . х2)_п таково, что каждое множество !Д, где і = l,n , является

конечным множеством. Показывается, что в этом случае в множестве 2)

существует - минимальный и I- максимальный элементы, где t = l,n+2.

В третьем подразделе рассматривается случай, когда три множества: 2) = >_1Х... х#_п,где !ЦсН, i = u, СоЮ=аЮ_[х... хй>_п,где CfD-_x-

выпуклая оболочка множества Ю_ь і = 1,п , Т = Ті _х. . . х Т_п, где Т\ с Н, і = 1,п , связаны соотношениями : Т>\ с Tj с СЛ)\. Показывается, что в этом

случае, если в одном из множеств Ю, Т, СЛ) существует (п+2)-

минимальньш ((п+2)- максимальный) элемент, то в каждом из этих множеств также существует I- минимальный (- максимальный) элемент, где = 1,п+2. При этом - минимальный (- максимальньгй) элемент в множестве 2) является - минимальным (- максимальным) элементом в множествах Т и СаЮ, а - минимальный { - максимальный) элемент в множестве Т является

- минимальным - максимальным) элементом в множестве СЛ).

В третьем подразделе показывается также, что если множество Т таково, что каждое множество Ті является конечным множеством, либо линейным многогранником, то в множестве Т существует (п+2)- минимальный ((п+2)- максимальный) элемент.

В четвертом подразделе рассматривается случай, когда множество Ю = = Ю\х . . . х 1)_п, где >; с Н, і = 1,п , имеет некоторый специальный вид. Показывается, что в этом случае в множестве Т> существует I-минимальный и I- максимальный элементы, где t = l,n+2.

В пятом подразделе рассматривается случай, когда Ю - Ю\ _х . . . х (D_n

является замкнутым множеством, в котором существует элемент h, обладающий свойством : множество J состояний однородной КМЦЦ ,₀(а, h) образует один класс возвратных сообщающихся состояний. При этом показывается, что в множестве Ю имеется 1- минимальный (1- максимальный) элемент С,, для которого выполняется соотношение: «i,i(Q =.. = *i,_n(Q > ^гД^е«ід(0 - і- ая компонента вектора «i(Q, і = l,n. Показывается также, что в том случае, когда в множестве (D отсутствуют элементы, для которых соответствующие однородные КМЦЦ имеют невозвратные состояния, в этом множестве *D имеется - минимальный (- максимальный) элемент, где ^ = 1,п+2.

В шестом подразделе рассматривается случай, когда (D = (Di _х. .. х 2)_п» где Ю\ сН, і = 1,п , является замкнутым множеством. Показывается, что для

любого є > 0 существует такое множество Т_є = Т_Є;і _х. . . х Т_Е>П , где Т_6;; -линейный многогранник, обладающий свойством: (D_t с T₈₎j с Н, і = l,n , для

которого выполняются следующие системы неравенств:

Гі(1)-_Чі(С⁽¹⁾)<є, і = й, _Чі(С⁽²⁾)-Гі(2)<є, і=й,

где 1,(1) = inf{_4i(h) : he>}, r_;(2) = sup{*_u(h) : he0}, і = l,n , _4i(h) - і-ая

компонента вектора *i(h) финитного дохода, С}¹\ ⁽²⁾ - соответственно 1-минимальныйи 1-максимальный элемент в множестве Т_є.

В пятом разделе вводится - частичная упорядоченность в множестве с#(Н^п), согласованная с ^-частичной упорядоченностью в множестве Hⁿ, где

= 1,п+2, с^(Н^п) - множество всевозможных подмножеств множества Н^п, и

устанавливаются ее некоторые свойства.

Этот раздел состоит из трех подразделов.

В первом подразделе дается определение - частичной упорядоченности в множестве с^(Н^п) и приводятся утверждения, устанавливающие ее основные

свойства. Вводятся также понятия - максимального и - минимального элементов в подмножествах множества cf (Н^п) и выявляются некоторые их

свойства.

Во втором подразделе приводится доказательство существования ^-максимального {- минимального) элемента >(аэ) в множестве А(їі), где А(ЭДсс^(Н^п), h(U)= Щи):и&Щ, Ф(и) = Фі(щ)х...х>_п(и_а), Щи^сН,

Ui-i-ая компонента элемента и, U = U\ х ... х U_n, % = {1,..., m(i)}, i = l,n, аеєї/.

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

В шестом разделе дается определение и указываются свойства 1-частичной упорядоченности в множестве & , являющемся основной ха-

рактеристикой множества S всех конечных марковских цепей с доходом (всех КМЦД), где Ь = Н^п х . . . х Н" х . . . . Множество S всех КМЦЦ с

числом состояний равным п представляется в виде :

Е = {^а,Ь):аеР_1п, >є }, (24)

где Ца, ЬУ КМЦД, задаваемая парой {а, Ъ);а- начальное распределение; >= = (h^(l),. .., h^,.. )є, h^(k) є Hⁿ, k=l,oo ; элемент fy определяет как последовательность матриц переходных состояний этой цепи { Р^(к)( Ь)⁼ Р( h^(k)), к= = 1,оо}, так и последовательность доходов (q^(k)(^»)= qi(h^(k)), k=l,oo}, ?(hⁱ⁾) = (by⁰⁰), і =й , J = U , qi(h^(k)) = [h ^,.... h_u+1«]^T, Ьу^м - соответствующая компонента элемента h^(k).

Устанавливаются основные свойства 1-частичной упорядоченности в множестве и указывается ее соотношение с ^-частичной упорядоченностью

в множестве Н^п, где i = l,n+2.

Этот раздел состоит из трех подразделов.

В первом подразделе дается определение 1- частичной упорядоченности в множестве > и указывается соотношение этой упорядоченности с

I- частичной упорядоченностью в множестве Н^п, где і = 1,П+2.

Во втором подразделе доказываются условия существования 1-минимального (1-максимального) и (1, є)- минимального ((1, є)- максимального) элементов в замкнутом множестве >,где> = (Рх...х)х..., 2) = ^ х .

.. х (D_a, Ю\- любое замкнутое подмножество множества Н, і = п. Указываются также основные свойства упомянутых элементов.

В третьем подразделе приводятся теоремы существования (1, є)-минимального и (1, є)- максимального элементов в множестве > = fDx . . . х

Юх . . . , где Ю = >! х . . . х Ю_п, _X- любое подмножество множества Н, і = 1,п, и указываются основные свойства этих элементов.

В седьмом разделе вводится 1- частичная упорядоченность в множестве сДф ), согласованная с 1-частичной упорядоченностью в множестве >, где

Ь ⁼ Н^п х . . . х Н^п х . . . , сДф ) - множество всевозможных подмножеств

множества t>, - 1,п+2. Устанавливаются основные свойства введенной

частичной упорядоченности.

Этот раздел состоит из трех подразделов.

В первом подразделе дается определение 1-частичной упорядоченности в множестве сф) и приводится ее соотношение с - частичной упорядоченностью в множестве о#(Н^п). Даются также определения 1- максимального и 1- минимального элементов в подмножестве %<^сАф).

Во втором подразделе приводятся теоремы существования 1-максимального и 1-минимального элементов в множествах 2л = { >i(s): sgS} и2л,о⁼

={i(s(tt)): u&U], связанных непосредственно с УКМЦ с неполной информа

цией К\ = [S, с#(Е), #i], где S - множество стратегий, i(s)c & , #i(s) =

={(я, Ь) ' аеР_іл, !>ei(s)}, Qa, Ь) - КМЦЦ, задаваемая парой {а, Ь) (см .

выражение (24)), s (и)- стационарная стратегия, вырожденная в точке и, М = =М\ х ... х % - множество управлений, %= (1,..., m(i)}, і = l,n . Множество i(s) называется стационарной характеристикой неполной

информации, определяется на основе совокупности исходных данных (20) и имеет следующий вид :

i(s) = {[h⁽¹\P),..., h%%..]^>: [ для любого к = 1,» выпол-

m(i)

няется равенство h[^k)(^,^(lc)) ⁼X^hi (І)*і? ' ^пі(І)^є^іС)> і = l,n ]},

где h[^k)(<»i^(k)) - і-ая компонента элемента h*^*⁵), J = [>j^k),...,.*⁽_n^k)] - к-ая

компонента стратегии s, ^^(1с)- і-ая компонента /^k) , 2),(j) - характеристика

неполной информации в значении вектора hi(j), заданная в совокупности (20),

je%,i = u-

В этом подразделе показывается, что 1- максимальный (1- минимальный)

элемент i(s(«)) в множестве 21,о является 1- максимальным (1-минималь-ным) элементом в множестве Зл- При этом ж является таким элементом из множества U, для которого 2)() является - максимальным (- минималь-

ным) элементом в множестве А(ї/) = {>(«) : иєЩ, где i? = l,n + 2, 2)(w) = =2^(^) х ... х 2)_п(и_п), і(«і) - характеристика неполной информации в значении вектора hi(ui), заданная в выражении (20), щ - і-ая компонента управления и, и_х = 1,..., m(i), i = Vn.

В третьем подразделе приводятся теоремы существования 1-максимального, 1-минимального элементов в множествах 2л⁼ {(^s): s%x_fi-

{&(s(u)) :ueVd}, связанных непосредственно с УКМЦ с неполной информа щей К₂ = [ S, tff(S), $], где (s))c , fc(s) = {(а, Є>): ає/%, &є$(з)}. Множество (s) называется нестационарной характеристикой неполной информации, определяется на основе совокупности исходных данных (20) и имеет следующий вид : >(s) = {[h⁽¹⁾(»⁽¹⁾),..., h%^{\..]ef> :

m(i)

h[^k)U^(k)!^K))=Zh«(j)^ ,hi^WG)e Щ),і = 1,п,к= !,« }

где h[^k)0,^(k))- і-ая компонента элемента h⁽ у )> * ⁼ [*i^k) >-»*п^Ю]^_ k-ая компонента стратегии s, ^^(k) - і-ая компонента *^(k), i);(j) - характеристика неполной информации, заданная в совокупности (20), je% , і = 1,п.

В этом параграфе показывается, что 1- максимальный ( 1-минимальный) элемент >₂(s(ae⁽¹⁾)) ( ₂(s(a2⁽²⁾)) ) в множестве 2л_>0 является 1-максимальным (1-минимальным) элементом в множестве 5^2- При этом аэ

является таким элементом из множества Ъ1, для которого D (аэ) является - максимальным (- минимальным) элементом в множестве А{Щ ={о(и):ие⁽М}, где і = 1,п + 2, D {и) - замыкание множества І)(и).

В восьмой главе доказываются теоремы, устанавливающие аналитические соотношения, из которых следуют основные свойства УКМЦ как с полной, так и неполной информацией. Именно эти теоремы представляют собой основные результаты исследования указанных УКМЦ, которые приводятся в разделе 1 настоящей работы.

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

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

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