автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Исследование управляемых конечных марковских цепей с неполной информацией и его приложение к расчету показателей надежности сложных систем

На правах рукописи

Карманов Анатолий Вячеславович

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

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

информации»

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА - 2006

Работа выполнена соискателем в инициативном порядке.

Научный консультант, доктор физико-математических наук

Малиновский В.К. - МИАН им. В.А.Стеклова

Официальные оппоненты:

Доктор физико-математических наук, профессор

Доктор физико-математических наук, старший научный сотрудник

Доктор физико-математических наук, профессор

Каштанов В.А.

Пресман Э.Л. Рыков В.В.

Ведущая организация:

Институт Систем Энергетики имени Л.А.Мелентьева СО РАН

Защита состоится «.//» в '

диссертационного совета Д 2 У2.133.01 при Московск

. часов на заседании диссертационного совета Д 2Й. 133.01 при Московском государственном институте электроники и математики по адресу: 109028, Москва, Большой Трехсвятительский переулок 3/12, МГИЭМ.

С диссертацией можно ознакомиться в библиотеке МГИЭМ. Автореферат разослан «_»_2006 г.

Ученый' секретарь Диссертационного Совета

—-----кл'.н., доцент Бузников С.Е.

¿ж^

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

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

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

Поскольку УКМЦ с неполной информацией является обобщением классической управляемой конечной марковской цепи, то целесообразно

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

[ a, J, { : ieJ}, (М*): ЫИъ iej }], (I)

где а = [atаа] — стохастический вектор, называемый начальным распределением, J « (1„.,,п) - множество состояний, ЧЛ\ ■ {I, .,m(i)} — конечное множество управлений в состоянии i, hj(i) = [pi(f).4i(^)l. PiCO = IpfcjCOf'tPuW)]* вектор переходных вероятностей из состояния i при управлении ¿gUu величина дохода в состоянии i при управлении являющаяся ограниченной величиной, i = 1,...,п. У правление УКМЦ в дискретном времени к, к« 0,1,2,.., осуществляется в соответствии с (марковской) стратегией, имеющей вид:

B-i*0',...,*®,...], (2)

где 4<k) = - . . , ], ¿¡и= [л^', if^dj]- стохастический вектор-

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

, B(i4j)], или рандомизированное управление в состоянии i, i =l,n, к множество событий на множестве управлений

(элементарных исходов) И\. При этом множество S всех стратегий вида (2) называется множеством (марковских) стратегий и имеет вид:

S-{[*(,,...,*(k),...]: *lkieP, k=I^}, (3)

(к) . (к) (к), „ „ „ „ (к) „ „ где * ]€/% Р = PtM>) * • . .X 4, e/'j.mf,), /\т®*

множество всех ш (1)-мерных стохастических векторов-строк, i=l,n.

По исходным данным (1) при фиксированной стратегии s, где seS, на пространстве траекторий {Т, Zt(T)], где

Т = {Г, = [(i„ А).... ,(ik Л+i), -..]: ike J, 4+i e Щ, k=0^}- множество траекторий, B(T) - множество событий на множестве Т, можно задать:

-51) вероятностную меру Р„,5, обладающую свойством

2) последовательность случайных величии т|(з) » {пьк= йм}, являющуюся марковской цепью относительно меры Р^» где

1ь 'г еТ (5)

При этом условная вероятность, называемая переходной вероятностью из состояния 1 в состояние 3 при стратегии б на (к+1)-ом шаге, определяется в соответствии с выражением (4) по формуле:

Рц(*!к+,))-Р.Лчкч^ / Чк-1) = чГ1)Ри(0 + .. -+^т+соРу(тО», (6)

где *|к+1'> -рандомизированное управление в состоянии 1 на (к+1)-ом шаге, являющееся соответствующей компонентой стратегии б, 1 ] к=0^со, В начальный момент (к = 0 ) марковская цепь ц(з) имеет начальное распределение а, т.е. Рд,^(т)о=11) = а1> где 1 =1,п ;

3) последовательность q(s) = { Ч(к)(8)« ^ = } векторов дохода, где

ЛиЛ^У.

Ч:(*Г+1)) "*и+1)Ч1(0 +• • •+ЧтО))ЧКт(!)), I =й, к=0/» (7)

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

Пусть = (п(8), q(s)) - конечная марковская цепь с доходом (КМЦД), соответствующая стратегии я , где эеБ , п(3)" {ль к=«0^о} - марковская

цепь, определенная выражением (5) , я(з) ~ {ч(4(к+1)), к } ,

/ (к+1\ г ^ (к+1К у (к+|К,т „ . ... „

) ~ [Я1<>1 ). • - ..ЧпС*,, )] - вектор дохода за (к-Н)-ый шаг

, . - (к+1к цепи т](з), т- знак транспонирования, ) - величина, определяемая

выражением (7), 1 =» Хп, и пусть 3 - множество всевозможных КМЦД с числом состояний равным п. Тогда УКМЦ с конечным множеством управлений представляет собой совокупность, имеющую вид:

[Б.Н.^Ь (8)

где —> Н , т.е. § является отображением множества стратегий Б

в множество всех КМЦД Е ; при этом £ (э) = и 5 (к)е Е .

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

с«, {Р<к+п(Ю.к»0^}, {Ч(к+1><5), к=0^>], (9)

где а - начальное распределение, Р<к+П(з) & (рц(*-к+1>)) - матрица переходных вероятностей на Ыш шаге, имеющая порядок п и элементы которой определяются выражением (6), = п-мерный

вектор дохода за к-ый шаг, ¡-ая компонента которого определяется выражением (7), ¡=£п ;

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

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

Ф(8)= Цш (з),к)или Ф(э)= Лтк-' 0(л^(8),к), (10)

где к) - я -¿Пр">) чг("Чз). {11)

».I

то цель управления УКМЦ состоит в максимизации этого дохода, т.е. в определении такой оптимальной стратегии з*, для которой выполняется соотношение: Ф(а') = аир { Ф(з): } (12)

УКМЦ, задаваемая совокупностью (1), исследуется в многочисленных работах и основным результатом здесь является следующее утверждение: существует непустое множество оптимальных стратегий, независящих от начального распределения я, и это множество содержит стационарную вырожденную в точке и стратегию (простую стратегию) s(u), где s(u) = №), • •, ¿(и),...] е S, и = (и......и„), Uj «= 44,, i -Гп, ¿(и) = [1>,(и1),...^л(ил)]е Р,

ij(ui) - стохастический вектор, вырожденный в точке Ui, т.е. (U|) ~ 1, если t =* Ui, и (u() « 0, если t* и,, где uie%, i = Этот результат * имеет важное прикладное значение, т.к. позволяет осуществлять поиск оптимальной стратегии s* на конечном множестве стационарных вырожденных стратегий.

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

НО = [{Pi.i(j?),..., рUi). ) ]. (13)

определяющего стохастические свойства УКМЦ и входящего в совокупность (1) точно неизвестно, а известна лишь некоторая область его значений Д(0, где t= I,..., m(i), i =l,n .

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

1. Вектор hi(£) определяется обработкой статистических данных, поэтому достаточно точно бывает известна лишь некоторая область его значений Ц(£), гдеt= I,...,m(i),i = l,n ;

2. Вектор hj(-f) определяется расчетным путем, однако исходные данные для такого расчета известны с некоторой ошибкой. При этом также возникает область £>,((■)> которой принадлежит вектор

Область Ц(£) является характеристикой неполной информации в значении вектора где , 1 =17п, и входит в совокупность исходных данных, которой задается новый объект - УКМЦ с неполной информацией. Эта совокупность записывается аналогично совокупности (1) и имеет вид : [ а, Д, {%: ¡еД}, : Ы и» ¡е ] }] (14)

Понятно, что в случае, если , 1 являются

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

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

Так как определение множества 5(8), где веБ, требует дополнительных формальных построений, которые целесообразно опустить при первом и во многом качественном знакомстве с УКМЦ с неполной информацией, то здесь оно не приводится, а приводится в разделе 2 настоящего автореферата. Однако чтобы оценить элементный состав множества £(з) отметим, что даже для наиболее простого случая, когда 8 является стационарной вырожденной (простой) стратегией, множество #(з) может содержать в качестве элементов как однородные, так и

неоднородные марковские цепи с доходом, которые задаются совокупностями вида (9).

Теперь сформируем два функционала для УКМЦ с неполной информацией: Ф i(s)= inf{ Пт к):$ e?{s) },

Ф ,(s) = inf {Jim k-' QtoS, к): % € 9{s) } (15)

где Q(e,£, к) - средний аддитивный доход за к шагов марковской цепи \ с доходом, определяемый в соответствии с выражением (11),

Таким образом, <t>i(s) является гарантированным средним доходом в единицу дискретного времени, получаемым на УКМЦ с неполной информацией при фиксированной стратегии s, где seS.

Цель управления УКМЦ с неполной информацией сохраняется той же, что и в случае УКМЦ с полной информацией, и состоит в максимизации гарантированного среднего дохода <t>i(s) , т.е. в определении такой оптимальной стратегии s*, если она существует, или такой е -оптимальной стратегии Зе. если s" не существует, для которых выполняются соотношения : * Ф ](з*)= sup { <J>i(s): seS }, (16) sup { 0>i(s):seS } - <j>i(se) £ E, (17) где с - некоторое положительное число.

1.2. Цель работы

До настоящего времени УКМЦ с неполной информацией и функционалом (15) в полном объеме не исследовалась, хотя ее частные случаи рассматривались в работах В.А.Капгганова, Е.Ю.Барзиловича, Н.Гирлиха, В. Фогеля и др. В работах Э.Л.Пресмана и И.М.Сонина применяется адаптивных подход к решению задачи оптимального управления конечной марковской цепью по неполным данным с более широким множеством стратегий, чем множество марковских стратегий, в предположении, что переходные вероятности цепи зависят от дискретного времени только в

снлу зависимости от времени компонент стратегий. В этом случае функционал вида (15), естественно, не используется, а оптимальной в общем случае является не марковская стратегия.

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

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

Методы исследования

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

1.4, Научная новизна

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

1.5, Теоретическая м практическая ценность

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

В качестве приложения исследований приводятся алгоритмы решения ряда задач оптимального управления дискретными марковскими объектами с неполной информацией (см. [12] на стр. 33 автореферата). Разработаны также алгоритмы: 1) расчета верхней и нижней оценок стационарных показателей надежности сложных систем для случая, когда характеристики надежности элементов имеют интервальную оценку (см. [14, 15, 17} на стр.33 автореферата); 2) оценки финальных вероятностей при агрегировании марковской цепи (см. [18] на стр. 33 автореферата).

1.6. Апробация работы и публикации.

Основой диссертации является опубликованная в центральном издании «Физико-математическая литература» монография «Исследование управляемых конечных марковских цепей с неполной информацией »(М.: Наука, 2002,173 е.). Решение ряда задач управления марковскими объектами с неполной информации приводятся в главе 9 монографин [12].

Прикладные работы, связанные с проведенными исследованиями, опубликованы в периодических научных издательствах, поименованных в перечне ВАК РФ.

Основные результаты диссертации, включая приложения, докладывались и обсуждались на международном научном семинаре им. Ю.Н.Руденко «Методические вопросы исследования надежности больших систем энергетики»,1 ИСЭМ СО РАН (под рук. член-корр. Воропая Н.И.), на научных семинарах в ВЦ АН СССР (под рук. академика Моисеева

Н.Н.) , МПИЭМ (под рук. Д.Т.К. Афанасьева В.Н., д.т.н. Носова В.Р., д.ф,-м.н. Колмановского Б.В.) , ЦЭМИ РАН (под рук. д.ф.-м.и. Пресмана Э.Л., к.ф.-м.н. Аркнна В.И.), на кафедре «Прикладная математика» РГУНГ им. И.М.Губкина (завкафедрой д.т.н., проф.Сухарев М.Г.). Список докладов приводится на стр. 30- 31 автореферата.

2.0бъсм, структура и краткое содержание работы

Объем диссертации - 249 стр. Она состоит из введения, 9 глав и заключения.

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

В первой главе даются определения УКМЦ как с полной, так и с неполной информацией. При этом УКМЦ с полной информацией определяется совокупностью (8) : [Б, 3, £ ] , где Э - множество (марковских) стратегий, Н - множество всех конечных марковских цепей с доходом (множество всех КМЦД ) с число состояний равным п, £: в -> 2 - отображение множества стратегий 5 в множество всех КМЦД 2, определенное выражением £ (я) = (п(з), ч (э)). Такое определение УКМЦ с полной информацией не является традиционным, однако оно в явном виде указывает на то, что при полной информации каждой стратегии 8, гдеэеЗ, соответствует лишь одна КМЦД ^ (з), где £ (в)е 2.

Определяется УКМЦ с неполной информацией !К, задаваемая совокупностью исходных данных (14), а также один частный случай этой цепи Эти УКМЦ представляют собой следующие совокупности:

И>[3,<*Г(3),5], (18)

где с#(Е) - множество всех подмножеств множества 3, -

известные отображение множества Э в множество о?(2); при этом

5](8)ее£(Е), и эеЯ . Формальный вид отображений

& и приводится (после введения необходимых обозначений) в разделе 2 автореферата.

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

элементом множества

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

Во второй главе рассматриваются основные свойства множества 5„ всех однородных КМЦЦ с числом состояний равным п, которое представляется в виде : 30 = {£о(а. 11) : , ЬеН" }, где Ь) -

однородная КМЦЦ, задаваемая парой (а, Ь), а - начальное распределение, - множество всех п-мерных стохастических векторов-строк, Н"™

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

[-Ро. РоЬ Ро>0, Ь = [Ь(.....Ь„]бН",К1»[Ьи элементЬ

определяет матрицу переходных вероятностей Р(Ь) и вектор-столбец дохода Р(Ь) = ( Ьц), 1 , ] =Пп , я(Ь) = ......Ь„_п+|]т, -

соответствующая компонента элемента Ь. Эта глава состоит из четырех параграфах.

В первом параграфе определяются стационарные характеристики однородной КМЦЦ Ь), которыми являются:

а. Вектор финального дохода г(Ь) =* ЛГ(Ь)-д(Ь), где - матрица финальных вероятностей и ¿Г(Ь) 13 1!т к'1-[Б 4- Р(Ь) + . . . + Рк"'(Ь)],

Б - единичная матрица порядка п ;

б. Вектора «весов» \у,.(11) = (-1)к+|-[В?00- - г(Ь)], к

где В|(11) = (Е - Р(Ь) + Л(Ь))"' - матрица, обратная к фундаментальной матрице (Е - Р(Ь) + 7Г(Ь)) однородной КМЦД ^.(а.Ь).

Во втором параграфе вводятся классы эквивалентности в множестве основанные на представлении множества состояний каждой однородной КМЦЦ в виде суммы следующих

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

В третьем параграфе излагаются методы расчета стационарных характеристик однородной КМЦД.

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

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

В третьей главе вводится ¿-частичная упорядоченность в множестве Нп, основанная на сравнении стационарных характеристик г(Ь), лу^Ь), к -V» однородных КМЦЦ ¡;0(а, Ь), Ье Нл, где £ *= V», и устанавливаются ее основные свойства.

Пусть h и t являются некоторыми элементами из множества Н", тогда

t _

/-частичная упорядоченность, обозначаемая =s , где ( = j,«, определяется следующим образом : 1

1. h=$t тогда и только тогда, когда выполняется неравенство

i<h) * КО, (19)

1

где неравенство векторов понимается как покомпонентное. При этом h-<t

-, когда r(h) < r(t), где строгое неравенство векторов понимается как неравенство (19), в котором хотя бы для одной компоненты неравенство строгое; е

2. h=st тогда и только тогда, когда выполняется хотя бы одно следующих двух соотношений:

¿-1

h -е t , (20)

r(h)= КО, wk(h) =■ wk(t),k = 1,t-2, WM(h)5wM(t), (21)

/

где £ = 2, 3,.... При этом h-<t -, когда выполняется соотношение (20) или соотношение (21), в котором последнее неравенство является строгим.

Одним из основных свойств ¿-частичных упорядоченностей в множестве Нп ,£ = 1,2,..., является следующее: в множествен8 имеется конечное число различных ¿-частичных упорядоченностей, при этом различными могут являться упорядоченности, для которых ¿ = l.n+2.

В четвертой главе определяется t- минимальный элемент в множестве D относительно ¿-частичной упорядоченности в множестве М", а в его отсутствие - ({, е)-минимальный элемент ((- максимальный и ^-максимальный элементы в множестве D), где ¿е{1,... ,n+2}, е>0, DcH",

D ■= Дх... x I>n . Uiс:H, i = йп . Выявляются условия существования, основные свойства и методы вычисления этих элементов в зависимости от свойств множеств Dt, i = Пп .

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

1. Для любого £- минимального (I- максимального) элемента h(l) из множестваD, где ¿е{1,..., п+2}, справедливо выражение:

r(t), V teD, (r(h(i))&r(t). V teD ), (22)

где r(0 - вектор финального дохода однородной КМЦД ^(а, ■);

2. В случаях, когда Pj, i = l,n являются конечными множествами или линейными многогранниками в множестве D существует ¿-минимальный {¿- максимальный) элемент, который можно отыскать некоторой итерационной процедурой за конечное число итераций, ..,, п+2};

3. В случае, когда Dt„ i =■ являются замкнутыми множествами показывается, что для любого е > 0 существует такое множество Tt = Tej х... хТм, где Tj,|-линейный многогранник, обладающий свойством

DicTtjc:H, i = £n, для которого выполняются следующие системы неравенств

где

Г|(1) = mf{r,(h) : heD}, п(2) = sup{ri(h) : heD}, i = Гп , ri(h) - ¡-ая компонента вектора r(h) финального дохода, ^ — соответственно £- минимальный и I- максимальный элементы в множестве Т, ¿е{1,... ,п+2},

В пятой главе вводится £- частичная упорядоченность в множестве о?(Н"), согласованная с ¿-частичной упорядоченностью в множестве Н",

где I = 1,п+2, - множество всевозможных подмножеств множества

Н", и устанавливаются ее некоторые свойства. Этот раздел состоит из трех параграфов.

В первом параграфе дается определение I- частичной упорядоченности в множестве и приводятся утверждения, устанавливающие

ее основные свойства. Вводятся также понятия ¿-максимального и ¿-минимального элементов в подмножестве А(&Г) = {Б(н) : иеН] множества «з£(Нп) и выявляются некоторые их свойства.

Пусть 0| и 02 являются элементами множества т.е.

Б^ с: Н", к = 1,2 , и пусть в этих множествах соответственно

являются ¿-минимальными элементами (по отношению к ¿-частичной упорядоченности в множестве Нп ), тогда ¿- частичная упорядочен-

I

ность в множестве определяется следующим образом : Ю^Ог,

I

тогда и только тогда, когда выполняется соотношение ¿) =г ¿), I

где <= - символ ¿- частичной упорядоченности в множестве <з£(Нв) , * __

- символ ¿-частичной упорядоченности в множестве Н", ¿=1,п+2. Элемент Э(ае(,)) (0(ар>)) из множества А(И) - {О(и) : и&14) называется ¿- максимальным (¿- минимальным) элементом в А(И), если справедли-

< г

во выражение: С(м) <= П(®(1>), V п<еМ (0(сер)) <= Э(м), V иеИ )

Из введенных определений непосредственно следует, что:,

<

1. Соотношение <?= Т>г, с учетом выражения (22), влечет выполнение системы неравенств:

inf{ rj(h): h eD|} s inf {n(h): h eDj.i-'in, (23) где mfinOOsheDO-iiC^O), inf { ri(h): h eD2} = /)), r,(->- ьая компонента вектора финального дохода !<■), i = ITn ;

2. Основное свойство ¿-максимального элемента D(ae[l>) в множестве А(М) = {D(k) : иеЩ се/ЦН?) , где D(«)e of (Н"), жеИ, устанавливается выражением:

inf (ri(h): ЬеО(м) } s mf {r;(h): heD<®(,>) } , V не<М, (24) где rj(-) - i-ая компонент вектора г(-) финального дохода, i = l,n ,/=1,п+2.

Во втором параграфе приводится доказательство существования ¿-максимального (/- минимального) элемента D(ae<!>) (D(®0))) в множестве А{Щ где A(U)<z.<d(et), A(iO ={D(w): иаЩ, D(u)=Di(ut)x . dd(u„),

DiiuJcH и Di(wj)- характеристика неполной информации, введенная в выражении (14), «¡-¡-ая компонента элемента и, И *= % х — х i/0, i/j °

т

{I.....m(i)}» i" Ца» a^'eii, j"=l,2, £ ^(.п+г. При этом излагается итерационная процедура нахождения элементов Е>(«{|)) которая сущес твенно использует наличие в каждом множестве D(h), u<zti (п+2)-мини

t

мального ((п+2 ^максимального) элемента по упорядоченности =s вН".

При этом отметим одно важное обстоятельство, являющееся следствием выражения (24). Для любого начального распределения а, где ae.Pijt, элемент <аз(1) является решением следующей экстремальной задачи:

Ф'(аэ(|,)с* sup {q>(u) : ueU), (25)

где ф(и) = inf { a-r(h) : heD(u) }, r(h) - вектор финального дохода однородной КМЦД h).

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

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

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

числом состояний равным п имеет вид: Н = { £>) : аеР1п , Ч?е£> } ,

где £) - КМЦЦ, задаваемая парой (а, 1»; а - начальное распределение;

. е Н", к ; элемент определяет как

последовательность матриц переходных состояний этой цепи { Р^ф) = Рф***), к =],»}, так и последовательность доходов

{ ч^'С?) = чЛ к , Р(ь№)) = ОЛ 1 , ] , ч.сь^Ъ -

= Ьу00 - соответствующая компонента элемента Ь(к).

Эта глава состоит из трех параграфов,

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

ти с частичной упорядоченностью в множестве Н°, где 1,а+2.

Введем обозначения; фн>)(1» = Шп Ь), фв,1Й>) = Пш ф1(к, 1», (26)

к-«« к-**

где 1 =* ^п , Шп(-), Вт0-соответственно нижний и верхний'предел последовательности (•)> Ь = [Ь(,). • • • »Ь<к),.. .]е£>, Ь^еН" , кейУ, ф|(к,!» - ¡-ая компонента вектора ф(к, ф(к, У?) = к'^фкф),

Фкф) = ^ ]~{ Р01) Д>) • д(л) (?>) - вектор среднего дохода за к шагов, •м-1 н

получаемого на марковской цели £>), Р*0)(1» - единичная матрица порядка п, Р^ф) = РФ**), к - 1/й , Р(Ь<к)) - стохастическая матрица, соответствующая элементу ^еН", Ь№)- к-ая компонента элемента Ь, 4<т'1(^)= Ч(Ь<Щ>) - вектор дохода, соответствующий элементу Ь(га*еН",

Тогда 1-частичная упорядоченность в множестве £ определяется следующим образом: пусть £>1 и Ьг - два произвольно выбранных элемента

из множества £), тогда £>|-<£>1 в том и только в том случае, когда выполняется система неравенств: I4""? (27)

где )>,е£>, Ъ2е-Ь, Ф«(-) - [фн,1(->..... <Р*.в(0]\ =* [фм(')-----ФмХ-)]т.

При этом Ьг в том и только в том случае, когда в системе

неравенств (27) хотя бы одно неравенство строгое; £>|>; 1>2 - , когда

в системе (27) присутствуют только равенства.

Соотношение между 1-частичной упорядоченностью в множестве £> и

¿-частичной упорядоченностью в множестве Н" устанавливается следующим утверждением. Пусть н ^ - два стационарных элемента

из множества £>, порожденных соответственно элементами Ь и I из множества Н", т.е. )>| = [Н,.. ,Ь,,.], £>1 = [1,. ..]. Тогда соотношение ?ч**«(>2 выполняется при следующих условиях:

1) когда выполняется соотношение ьД^ где I ■= 1,п+2;

2) тогда и только тогда, когда выполняется соотношение .

В этом параграфе даются также определения 1 - минимального ( 1 -мак-

симального) и (1, е)- минимального ((1, е)- для максимального) элементов в множестве £>cf>, где е>0. При этом:

1. 1-минимальным называется такой элемент Ь\ в множестве £> с f>, для которого выполняется при любом ЬгбО, система неравенств:

2) „„

Ws-.Jfp.ib,), 1 '

где <p a(-). Ф и(*) - вектора, определенные в выражении (27);

2. (1, е>минимальный элемент в множестве 35 называется такой элемент

(>е,для которого выполняются неравенства:

Фифе)- ФиФие.Ф.Фе)- Ф,(0)5е, где -[Фн,,(0),..., Фн.рСО)] \ ф,(1)) = [ф|,|СО),...,ф1у1(0)],

Фн.)(0)- infi^iO» : i>e»} ,4>„,i(0) = inf {ф».й>): *><=»}, i-U, e>0.

Во втором параграфе доказываются условия существования 1-минимального (1-максимального) и (1, с)- минимального ((1, б)- максимального) элементов в замкнутом множестве О, где Ю = D х ,.. xDx..,, 0 =

D1 х .., х Dn, Di - любое замкнутое подмножество множества Н, i = i^n. Указываются также основные свойства этих элементов.

При этом, одно та основных свойств (1, е)-миннмального элемента

в замкнутом множестве О, утверждает, что в множестве существует

элемент |>Е = [he,-, he,...], для которого справедливо выражение

Фи(!>е)-Ф(,(1>б) = г(Ьб), (29)

где he - любой (1, е)- минимальный элемент в множестве о, r(he) — финальный доход однородной КМЦЦ £o(a,he).

В третьем параграфе приводятся теоремы существования (1,е)-ми-

нимального и (1,е)- максимального элементов в множестве О = 0х ...

м.хВх ..., гдеО = ц х ... х и„, П) - любое подмножество множества Н, 1" 1,п, и указываются основные свойства этих элементов.

Приведем одно из основных свойств (1,е>- минимального элемента Ъъ

в множестве О, утверждающее, что в множестве О существует элемент

!>б , для которого справедливо выражение :

Ф.ФО-'Ф&а)» I Ф«0>8)-г(11Е) е, (30)

где е >0, Ье- любой {1 — минимальный элемент в замыкании множества Б, г(Ъ ^ ) - вектор финального дохода однородной К МИД Ье), I. I - любая норма в п-мерном векторном пространстве. В седьмой главе вводится 1- частичная упорядоченность в множестве ), согласованная с 1-частичной упорядоченностью в множестве &,

где 6ЕН"х,,,хН'х,,.) ) - множество всевозможных подмно-

жеств множества £, £ = 1,п+2. Устанавливаются основные свойства введенной частичной упорядоченности. Эта глава состоит из трех параграфов.

В первом параграфе дается определение 1-частичной упорядоченности в множестве о?ф ) и приводится ее соотношение с £- частичной упорядоченностью в множестве с^СН"), Даются также определения ¡-максимального и 1- минимального элементов в подмножестве %с.сДф ).

Пусть »1 и Ог - некоторые произвольно выбранные элементы из множества «?{£>), т.е. О^с^Э, к = 1,2,. Тогда 1 - частичную упорядоченность в множестве <??(£>) определяется следующим образом: ЗЭ^ 2>г, в том и только в том случае, если выполняются неравенства:

<PwCO])S (p»(B2), фв(»,)5 фв(И2) , (31)

где <= '^символ 1-частичной упорядоченности в множестве ), (p«.¡(Dk) inf { : í? е 25i¡ ) - ¡-ая компонента вектора (рн^О*),

inf ív^iO»: } - i-ая компонента вектора {рБ(35к), i = i,n , k «

1,2,; при этом О, =3>2 , если в (31) присутствуют только равенства.

Укажем на одно важное следствие определения 1 •частичной упорядоченности в множестве aí(p): пусть £ = { ¡0(s): seS } некоторое подмножество множества ¿l{f> ), в котором существует максимальный элемент £>( Sj), т.е. элемент, для которого справедливо выражение

1

£>(s) <= t)(s,), V S€S,

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

[ 9„(0(s))í ф„(Х>(з,)), ф8СD(s))s 9.(0(3,)) ], V seS, (32)

где фн )(33(-)) = inf {фи,(ф): !?«£>{■) } - i-ая компонента вектора ф,,(!)(•)),

Ф^ОО) " üif{<fcKW : Ь е ЗЗ(-) } - i-ая компонента вектора фв(0(-))> ¡" l.n ■

Во втором параграфе приводятся теоремы существования 1-максимального и 1-минимального элементов в множествах Si = Í Ъ№ seS} и 2;|>0 = »,(>(«)) : иеЩ, связанных непосредственно

с УКМЦ с неполной информацией = [S, e/f(E), где . S - множество стратегий, £>i(s)c 0 , ?¡(s) » í>) : аеЛ,п, í>e£i(s)}, 5») - КМЦЦ, задаваемая парой (а, !» (см. определение множества S

всех КМЦЦ, введенное при изложении материала шестой главы), s («)- стационарная стратегия, вырожденная в точке w, U= U\ х ... х ЧАп -

множество управлений, % = {1.....ш(0}, \ = Гп . Множество £1(5)

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

£1(3) = {[Ь<п(4(1)).....Ь(к)(4Л>)>...]е^ : [ для любого к = выполняется

равенство Ы^С*^1) Ш»?? ,11Й)еД<Ш= 1.....шО),!»^ ]},

где Ь|к>(*)к*)-¡-ая компонента элемента ^(¡Л*), = -

к-ая компонента стратегии з, 1-ая компонента а**' , Д()) — характеристика неполной информации в значении вектора Ь[( ]), заданная в совокупности (14), ]ъИ\, I = 1,а-

В этом параграфе показывается, что 1-максимальный ( 1-минимальный) элемент^1(3(30'")) (й[(8(ае0))) )вмножестве является 1-макси-

мальным (1-минимальным) элементом в множестве Хь При этом , где j ■■ 1,2, является таким элементом из множества ЧА, для которого 0(зе( 1'), (0(ае( 1 *)) является (- максимальным {(- минимальным) элементом в мно-ожестве А(^0= { 0(н) : иеН), где £ = 1,п + 2, Е>(ы)™ Д(м|)х ... х ц,(м„), Ц(и{) - характеристика неполной информации в значении вектора Ь,(»|), заданная в выражении (14) , и, - ¡-ая компонента управления и,

Отметим, что, в силу выражений (24), (25), (32), элементом ее(|) определяется такая стратегия з(ае(1>), которая для любого начального распределения а , где де^1>п , является решением следующей

экстремальной задачи:

Ф,(з(ф<'>)) = ф(®(,>) =эир { Ф)(з): эев } , (33)

где «>i(s)= inf {lim к) : % e iT,(s) }, (34)

Ф (ae<n) - величина, определяемая выражением (25), Q(a, 5,, к) - средний аддитивный доход за к шагов марковской цепи 5 с доходом, определяемый в соответствии с выражением (11), «lim» в выражении (34) может являться как верхним, так и нижним пределом.

Из соотношений (33) и (34) следует, что простая стратегия sfaä*") является решением исходной задачи управления (15), (16) для УКМЦ с неполной информацией 5Ci.

В третьем параграфе приводятся теоремы существования 1- максимального и 1-минимального элементов в множествах ЗГз №,(з) г seS} и £2,0■= {02(s(u)) : иеН}, связанных непосредственно с

УКМЦ с неполной информацией % = [ S, сА(Е), JT], где )с J), ^s)={ г аеркп, )>е£з(з)}. Множество fi2(s) называется нестацио-

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

»^-{[tfVV-.bW)....]«» :

: Ь!к,(*1Ю) =Sh<k)Qhu ■ Ь® ДО), j= 1..■ -,т(0, i - ü > k - & }, j-t

где h[4(*jk')- i-ая компонента элемента h'^i^i № = - к-ая

компонента стратегии s, ¡-ая компонента , ДО) — характеристика

неполной информации, заданная в совокупности (14), jeiii, i = Ün.

В этом параграфе показывается, что 1- максимальный ( 1-минималь-ный) элемент i»2(s(«(1))) ( f>i(s(as,3))) ) в множестве ЗГад является 1-максимальным (1-минимальным) элементом в множестве STi. При этом aeft) к =1,2, является таким элементом из множества И, для которого D (®т)

( D (ае<1)) ) является I- максимальным (t- минимальным) элементом в множестве а (И) « {о («) : иеН}, где t =• l,n+2, d"(w) - замыкание множества D(ti),

Отметим, что, в силу выражений (24), (25), (29), (32), элементом геш определяется такая простая стратегия s(asm), которая для любого начального распределения а, где деДд,, является решением следующей экстремальной задачи: ®t(s(a(,i))= ф(ае"*) =sup { <Di(s): ssS }, (35) где Ф ,(s)= inf (lim k-' Q(a,£,, k): ? <= iT.(s) }, (36)

<p(ae(1)J • величина, определяемая в соответствии с выражением (25), в котором множество D(m) заменено на 5" (и), Q(a, £ ,k) - средний аддитивный доход за к шагов марковской цепи £, с доходом, определяемый в соответствии с выражением (11), «Иш» в выражении (36) может являться как верхним, так и нижним пределом.

Из соотношений (35) и (36) следует, что простая стратегия s(aa(l)) является решением исходной задачи управления (15), (16) для УКМЦ с непаяной информацией 9С.

В восьмой главе приводятся теоремы, являющиеся следствием теорем главы 7 и устанавливающие основные свойства УКМЦ с неполной информацией. Эти теоремы представляют собой результаты исследования УКМЦ 5Си , которые приводятся в разделе 3 автореферата.

В девятой главе приводятся алгоритмы решения задачи оптимального управления сложной системой с учетом неполной информации о надежностных характеристиках элементов и расчета оценок стационарных показателей надежности таких систем. При этом характеристики неполной информации Ц(1), ЫЧАп ieJ представляют собой линейные многогранники с «интервальной» оценкой переходных вероятностей для УКМЦ.

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

3. Основные результаты работы

3.1 • Результаты исследования УКМЦ <К\ - [$, с

Определим в множествах стратегий 8 и однородных КМЦД Е„ =

: , ЬеН" } (см. с. 13 автореферата) частичные упорядочен-

ности: 1. й а12) тогда и только тогда, когда (з'") (з(2))( где

- частичная упорядоченность в множестве е/1{& ) (см. с.22 автореферата);

I I

2.0 тогда и только тогда, когда Ь«=51, где -

- ¿-частичная упорядоченность в множестве Н", I = 1,2,... (см. с. 15 автореферата).

Тогда для УКМЦ с неполной информацией справедливы следующие утверждения.

1. В множестве стратегий Э существует максимальная Э] и минимальная

стратегии, которые являются стационарными вырожденными стратегиями (простыми стратегиями), порожденными соответственно управлениями м*11 и и®, у=*1,2 ■

2. Для множества £](зи)<= Е, где V = 1,2 , в) и йг-соответственно максимальная и минимальная стратегии в множестве Э, порожденные управлениями и(1) и справедливы следующие утверждения.

2.1. Для любого е > 0 в множестве ?|(8у) существуют е-

максимальная однородная КМЦД 3 н е-минимальная

однородная КМЦД ^ =Чо(а, где , соответственно (1, е) -

максимальный и (1, 8)-минимальный элементы в множестве 0(и(у*) = Д{в1М)х..,х|1)(иМ), V = 1,2 .

2.2. Если множества I = Пп , v = ^ 2 являются конечными

множествами или линейными многогранниками, то в множестве ¿Г,^) существуют максимальная однородная КМЦД ^(й, Ь(|)) и минимальная однородная КМЦД ¡;0(о. Ьи}), где Ь{|), Ь<2) - соответственно максимальный и ¿-минимальный элементы в множестве = С|(и^)х,,. х

^ = I.00 ■ При этом разработан численный итерационный метод, позволяющий отыскать как стратегию зу, так и однородную КМЦД £¿,((3, Ь11)) за конечное число итераций, где v = 1,2, к «1,2; 3. Максимальная стратегия £| является решением исходной экстремальной задачи (15), (16) для рассматриваемого случая.

3.2. Результаты исследовании УКМЦ К= [8, сЙ(Е), Определим в множествах стратегий 5 и всех КМЦД Е= { :

: аеР^, (>е0 } частичные упорядоченности:

1. 80> 5 з(5) тогда и только тогда, когда (з<1) ) с= (з0) ), где -частичная упорядоченность в множестве ) (см. с.22 автореферата);

2. £(«, 1>й>) тогда и только тогда, когда 1>а), где Д-

частичная упорядоченность в множестве 0 (см. с.20 автореферата).

Тогда для УКМЦ с неполной информацией К справедливы следующие утверждения.

1. В множестве стратегий б существует максимальная Б) и минимальная

стратегии, которые являются стационарными вырожденными стратегиями, порожденными соответственно управлениями к(|) и и{2), нме 14, V = = 1,2.

2. Для множества с Е , где V = 1, 2 , 5] и в! - соответственно максимальная и минимальная стратегии в множестве 8, порожденные управлениями ы(|) и и®, справедливы следующие утверждения.

2.1. Для любого е > 0 в множестве существует с-максимальная

е -минимальная КМЦД ^ )• для которых

выполняются соотношения: фвО^Ъ^ФвО^)» к = 1.2 , где ер/-) - вектора, 1-ые компоненты которых определены на стр.19 автореферата, -соответственно е-максимальныйие-минималь-

ный элемент в множестве

2.2. Для случая, когда множества I Vе 1,2, и/"1- 1-ая

(у!

компонента управления ик , являются замкнутыми множествами справед-вы следующие утверждения.

2.2.1. Для любого е > 0 в множестве существуют е-

макснмапьная однородная КМЦЦ ^ = V» ^} и е-минимальная однородная КМЦДЪ,г-Ь^),где Ь^-соответственно (1,е)-шкси-мальный и (1, 8)- минимальный элементы в множестве Б(и(1')} «

2.2.2. Если множества Ц(м^), 1 = С" , V = 1, 2 являются конечными множествами или линейными многогранниками, то в множестве ^(8») существуют I- максимальная однородная КМЦД

Ь(|)) и £' минимальная однородная КМЦД ^¡(а, Ь(2)), где Ь(|), Ь{2) -

соответственно £- максимальный и £- минимальный элементы в множестве E(z/Vl) = Д, . х Ц,(н£^)( £ = . При этом разработан численный итерационный метод, позволяющий отыскать как стратегию , так и однородную КМЦД £0(а, h'*') за конечное число итераций, где v ™ 1,2 , к » 1,2,

3. Максимальная стратегия Si является решением исходной экстремальной задачи (15), (16).

Результаты работы докладывались на следующих конференциях и семинарах:

1.Карманов A.B. Определение оптимального правила выбора периода профилактического обслуживания объектов магистрального нефтепровода при неполной информации об их надежностных характеристиках, доклад на Четвертой Всесоюзная Межвузовская научно-техническая конференция по надежности систем и средств управления, Ленинград, ЛЭТИ, сентябрь, 1975.

2.Карманов A3. Определение изменения средней производительности магистрального нефтепровода при неполной информации о его надежностных характеристиках, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Красный Курган, СЭИ СО АН СССР, октябрь, 1987.

3. Карманов A.B. Задача оптимизации характеристик надежности технологического оборудования магистрального нефтепровода, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика ГО.Н,Руденко, Цимлянск, СЭИ СО АН СССР, май, Î988.

4. Жуков В.М., Карманов A3. Математическая модель определения нормативных показателей надежности для морских нефтегазовых месторождений, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Киев, СЭИ СО АН СССР, октябрь, 1988.

5.Жуков BAI., Карманов A.B., Ливанов ЮЗ. Математическая модель управления сложной системой с учетом надежности ее элементов, доклад на семинаре «Системный анализ» под рук. академика H.H. Моисеева, Москва, ВЦ АН СССР, февраль,1988.

6. Карманов A.B. Задача динамической оптимизации развития межпромысловой сети газопроводов в условиях Северо-Западной Сибири, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н.Руденко, Сыктывкар, СЭИ СО АН СССР, июнь, 1989.

7. Карманов A.B. «Методические вопросы применения теории управляемых конечных марковских цепей в задачах надежности больших систем энергетики», доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Иваново, СЭИ СО АН СССР, сентябрь, 1989.

8. Жуков В.М., Карманов A.B. Оценка степени риска эксплуатации магистральных газопроводов, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Уфа, СЭИ СО АН СССР, июнь, 1990.

9. Жуков ВЛ1, Карманов A.B. Особенности анализа надежности систем добычи и обустройства нефтяных и газовых месторождений с учетом процесса возникновения аварий, доклад на Всесоюзном научном семинаре по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Иркутск, СЭИ СО АН СССР, май, 1991.

10. Карманов A.B. Управляемые конечные марковские цепи с неполной информацией и их приложения, доклад на семинаре «Управление и устойчивость» под рук. д.т.н. Афанасьева В,Н., д.т.н. Носова В.Р., д.ф.-м.н. Колмановского Б.В., Москва, МГИЭМ, март, 2000.

11. Карманов A.B. Результаты исследования управляемых конечные марковские цепи с неполной информацией, доклад на семинаре «Математические методы в экономике» под рук. д.ф.-м.н. Пресмана ЭЛ., к.ф.-м.н. Аркина В .И. и Сонина И.М., Москва, ЦЭМИ РАН, ноябрь, 2002.

12. Карманов A.B. Оценка финитных вероятностей на основе агреги рования марковской цепи, доклад на семинаре «Управление и устойчивость» под рук. д.т.н. Афанасьева В.Н., д.т.п, Носова В.Р., д.ф.-м.н. Колмановского Б.В., Москва, МГИЭМ, апрель, 2004.

13. Карманов A.B. Метод оценки стационарных' характеристик надежности сложных систем на основе агрегирования марковской цепи, доклад на международном научном семинаре им. Ю.Н.Руденко «Методические вопросы исследования надежности больших систем энергетики» под рук. член-корр, Воропая Н.И, г.Псков, ППИ, ИСЭМ СО РАН, З-б июля, 2005.

14. Карманов A.B. Исследование марковских цепей с неполной инфор-

мацией и его приложение к расчету показателей надежности сложных систем, доклад на международном научном семинаре им. Ю.Н.Руденко «Методические вопросы исследования надежности больших систем энергетики», под рук. член-корр. Вороная Н.И г.Псков, ППИ, ИСЭМ СО РАН, 3-6 июля, 2005.

Список работ, опубликованных по теме диссертации:

1. Жуков В.М., Карманов A.B. Одна стратегия рационального обслуживания сложной системы, состоящей из «п» последовательно соединенных блоков. М. ВИНИТИ, р.ж. Математика, 1974, X® 7, рефЛа 7В 766,7с.

2. Жуков В.М., Карманов A.B., Фридман В.Г. О решении одной экстремальной задачи. М. ВИНИТИ, р.ж. Математика, 1975, реф. 1113541,16с.

3. Жуков В.М., Карманов A.B. Исследование и выбор рациональной стратегия обслуживания сложной технической системы в нефтехимической промышленности. Баку, Нефть и Газ, Известия ВУЗов, 1975, №7, е.78-84.

4. Карманов A.B. Численный метод определения коэффициента готовности сложной технической системы, М., Нефть и Газ, 1976,4с.

5. Карманов A.B. Расчет рациональной стратегии обслуживания с временем восстановления специального вида, М., Недра, сб. «Системы и средства управления нефтяной промышленностью», вып. 131,1977,5с.

6. Жуков В.М., Карманов A.B., Ливанов ГСШ. и др. Модели обслуживания в АСУ ТП трубопроводного транспорта. М., Автоматизация и телемеханизация нефтяной промышленности, 1980,65 с.

7. Жуков В.М., Карманов A.B., Ливанов Ю.В. Индикаторный метод решения экстремальных задач и его приложения, М. ВЦ АН СССР, 1984, деп. в ВИНИТИ N 8133-84,40 с. (печ, по решению Ученого Совета ВЦ АН СССР от 15.11.84 г.)

8. Жуков В.М., Карманов A.B., Ливанов Ю.В. Учет надежности оборудования при автоматизированном проектировании генеральных схем обустройства нефтяных месторождений, М., Автоматизация и телемеханизация нефтяной промышленности, 1986,40 с.

9. Жуков 6Ж, Карманов А.В, Ливанов ЮЗ. Автоматизация оператиа ного планирования поставок и транспортирования нефти в системе магист ральных нефтепроводов отрасли. М., Автоматизация и телемеханизация нефтяной промышленности, 1986,38 с.

10. Жуков В.М., Карманов A.B., Ливанов Ю.В. Управляемые конечные марковские цепи с неполной информацией и их приложения, М. ВЦ АН СССР, 1988, деп. в ВИНИТИ № 4623-В88деп., 227с. (печ. по решению Ученого Совета ВЦ АН СССР от 08.04.1988г.)

11 .Жуков В.М., Карманов A.B. Математическая модель определения

нормативных показателей надежности для морских нефтегазовых месторождений, труды Всесоюзного научного семинара по проблеме «Методические вопросы исследования надежности больших систем энергетики» под рук. академика Ю.Н. Руденко, Киев, СЭИ СО АН, УМК ВО, 1989, с.61-63.

12. Карманов A.B., Жуков В.М. Управляемые конечные марковские цепи с неполной информацией (минимаксный подход), М. МГИЭМ, 2000,219с.

13. Карманов A.B. Исследование управляемых конечных марковских цепей с неполной информацией, М. Наука, 2002,173с.

14. Карманов A.B. Метод расчета стационарных показателей надежное-та объектов нефтеснабжения в условиях неполной информации об исходных данных. М.: Автоматизация, телемеханизация и связь в нефтяной промышленности, Ка 12,2004,

15. Карманов A.B., Карманова Л.А. Алгоритм решения задачи оптималь ного управления сложной системой с неполной информацией о надежности элементов. М.: Автоматизация, телемеханизация и связь в нефтяной промышленности, № 5,2005.

16. Карманов A.B. О возможности «зацикливания» вычислительной процедуры при определении стационарных характеристик надежности. М. ¡Автоматизация, телемеханизация и связь в нефтяной промышленности, >6 6,2005.

17. Карманов A.B. Метод определения «весов» в процедуре расчета стационарных характеристик надежности сложных систем нефтеснабжения с неполной информацией. М.: Автоматизация, телемеханизация и связь в нефтяной промышленности, 2005, № 9,

18. Карманов A.B., Карманова Л.А. Метод оценки финитных вероятностей на основе агрегирования марковской цепи. М.: Автоматика и Телеме-механика, 2005, Ка 10,

Подписано к печати" 30 * 1/ 2005 г. Отпечатано в типографии МИЭМ, Москва, ул. М. Пионерская, 12 Заказ Ыв ¿33 . Объем 2,0 пл. Тираж 400 экз.

Основные обозначения.

Введение

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

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

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

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

2.1. Стационарные характеристики.

2.2. Отношения эквивалентности.

2.3. Методы расчета стационарных характеристик.

2.4. Свойства стационарных характеристик.

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

3.1. Определение £ -частичной упорядоченности.

3.2. Свойства частичных упорядоченностей.

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

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

4.1. Определение минимальных и максимальных элементов. Условия их существования.

4.2. Случай 1.

4.3. Случай 2.

4.4. Случай 3.

4.5. Случай 4.

4.6. Случай 5.

5. Частичные упорядоченности в множестве ^(Нп) 5.1. Определение ¿-частичной упорядоченности. Максимальный и минимальный элементы.

5.2. Теоремы существования минимального и максимального элементов в множестве А(#)

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

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

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

6.2. Условия существования минимальных и максимальных элементов в замкнутом множестве.

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

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

7.1. Определение 1-частичной упорядоченности и ее свойства.

7.2. Теоремы существования 1-минимального и 1-максимального элементов в множествах и

7.3. Теоремы существования 1-минимального и 1-максимального элементов в множествах ^ и Ji^q.

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

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

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

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

9.1. Алгоритмы решения вспомогательных задач.

9.2. Алгоритм решения основной задачи.

9.3. Обоснование алгоритмов.

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

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

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

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

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

2. Если в момент времени ^ объект находится в состоянии то диспетчер должен с вероятностью ^ выбрать одно управляющее воздействие £ из конечного множества % допустимых управляющих воздействий в состоянии I и применить его к объекту, где к = 1,оо, % = {1,.,т(Т)}, {= 1,п. Управляющее воздействие примененное к объекту, влияет на его дальнейшее поведение следующим образом: состояние объекта в следующий момент времени ^ будет } с вероятностью ), где ] =1,п . Для вероятностей ¿^Л

Рц(£) выполняются соотношения: + *£,«> =1. 0) рц(£)>о, + + = и (2) где \ = , При этом стохастический вектор ¿[к) = [¿[V, ■ ,¿иш] именуется рандомизированным управлением в состоянии а стохастический вектор р[(£ ) = ),., р^О?)] - вектором переходных вероятностей в состоянии {, соответствующим управляющему воздействию £ , где £е(!Л\ . В начальный момент времени ^ объект находится в состоянии 1 с п вероятностью а\, где ах > 0, { =1,п , £а, = 1- Вектор а = [щ ап] ы называется начальным распределением;

3. Если в момент времени ^ объект находился в состоянии { и было применено управление £, то на интервале времени [^-1, именуемом по традиции [5] к -ым шагом, объект приносит доход равный ) , где 1 = = 17п , , к=1,оо. При этом для дохода выполняется соотношение :

-р0<Я1(0<Ро, (3) где ро>0.

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

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

1. Управление объектом осуществляется диспетчером в дискретные моменты времени где к = 1,оо, в соответствии с правилом 8 , называемым (марковской) стратегией и имеющим вид : б = [¿(1), . . . , ¿(1с),. . ], (4) где ¿(к) = [¿,(1с),., ¿[к) - рандомизированное управление в состоянии применяемое в момент времени (или на к-ом шаге), к = 1,<», I =1,п . При этом множество Б всех стратегий вида (4), называемое множеством (марковских) стратегий, имеет вид :

8 = (5) где = Р = Р1М1}х.х?1Ма), ^ еР^ф, Л,ш®множество всех т ©-мерных стохастических векторов, 1=1,п.

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

2. Минимальным набором исходных данных, которым можно задать рассматриваемый марковский объект, является следующая совокупность : яД {(6) где Ь^) = [ри(Д.,ри(4я^)];

3. При фиксированной стратегии в, где БеЭ, наблюдение за процессом смены состояний и управлений объекта в моменты времени к=0,оо дает траекторию г, которая имеет вид: г=[&,Ш1ь4),.Д1к,4+1),.], (7) где (¡к, 4+1) - пара, состоящая соответственно из состояния ¿к, в котором пребывает объект в момент времени ^, и управляющего воздействия 4+1, примененного диспетчером к объекту в этом состоянии. При этом для любого к, где к=0,оо, справедливо выражение: 4+1 £ . Вероятность траектории г определяется, в соответствии с определением стратегии в и исходными данными, изложенными в свойстве 2 объекта, по формуле: ■ • ч^ргиад* ■ • • да

Таким образом, формируется вероятностное пространство траекторий: к,.ад,ра>5), (9)

Я - множество всевозможных траекторий г, имеющих вид (7), йв(К) множество событий на множестве траекторий , Раз - вероятностная мера, заданная на множестве и обладающая свойством (8);

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

Лк(г)= ¡к, к=0Я (10) где ГбЯ . При этом следующая условная вероятность, называемая переходной вероятностью из состояния { в состояние ] при стратегии 8 на (к+1)-ом шаге, определяется в соответствии с выражением (8) по формуле :

Р ФГ]) =Ра>5(Лк+1 = ]/Лк=1) =

ГрцСО + .-.+^РУНО). (П) где рандомизированное управление, применяемое в состоянии [ в момент времени ^ (на (к+1)-ом шаге) и являющееся соответствующей компонентой стратегии 8, 1 = 1,п, ] =1,п, к=0,<».

В момент времени ^ марковская цепь г| (в) имеет начальное распределение а, т.е. Ра,3(ло= 0 = где1 = :й;

5. Пусть при фиксированной стратегии в, где Бе8, управляемый марковский объект в момент ^ находится в состоянии 1, тогда за (к +1)-ый шаг он приносит доход, который в соответствии со свойством 3 определяется по формуле : Я.ОГ") = 4.(0 + ■ • •+*£?> *(т(0), (12) где 1=1,п, к=0,со.

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

Пусть = (т| (б), q(s)) - конечная марковская цепь с доходом (КМЦЦ), соответсвующая стратегии в , где Бе Б , = {ль к =0,оо} - марковская цепь, определенная выражением (10), q(s) = ^(¿(к+1)), к=0,оо }, q(í^(k+1)) = =

Я1(>1к+1))> • ■ Ч„(>Г)]Т- вектор дохода за (к+1)-ый шаг цепи л (в), т- знак транспонирования, - величина, определяемая выражением (12), 1 = 1,11, и пусть 2 - множество всевозможных КМЦЦ с числом состояний равным п.

Тогда УКМЦ с конечным множеством управлений представляет собой совокупность, имеющую вид : [ Б , 2 , % ], (13) где £ : Б -» 2 , т.е. £ является отображением множества стратегий Б в множество всех КМЦЦ 2 ; при этом £ (э) = (л (в), я(в)) и £ (Б)е 2 .

Теперь укажем две основные особенности УКМЦ, являющиеся следствием ее определения: а. Каждой фиксированной стратегии э, где эеБ , ставится в соответствие одна конечная марковская цепь с доходом £ (в), которая задается следующей совокупностью исходных сведений; а, {Р(к+1)(& к=0^}, {Ч(к+1)(*), к=0^}], (14) где а - начальное распределение, Р(к+1)($) = (ру(<>[к+1))) - матрица переходных вероятностей на к-ом шаге, имеющая порядок п и элементы которой определяются выражением (11), = /к+1)) - п-мерный вектор дохода за к-ый шаг, 1-ая компонента которого определяется выражением (12), [ = 1,п ; б. УКМЦ является математической моделью рассматриваемого управляемого марковского объекта и может быть задана совокупностью исходных данных, определяемой выражением (6). Здесь же отметим, что в подавляющем числе работ, например [4-6, 12-16], УКМЦ традиционно задается именно этой совокупностью .

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

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

Ф(з)=1Йк-ЧКа,§ (з), к) (15) к—>оо к т где 0(а,Ш, к) = а • £Пр(Н)00 • Я(т\*), (16) т=1 ;=1 то цель управления УКМЦ состоит в максимизации этого дохода, т.е. в определении такой оптимальной стратегии в* , для которой выполняется соотношение: ф(б*) = вир { ф(б) : б^б } (17)

Отметим, что : 1) ф (б) является функционалом, заданным на множестве стратегий Б , т.е. ф : Б -> Я1 , а выражение (17) определяет критерий оптимальности для УКМЦ ; 2) 0(а, (б), к) является средним аддитивным доходом, получаемым на цепи (б) за интервал времени , 1к] (или за к шагов), при стратегии б, где беэ ; 3) именно стратегию б* необходимо иметь диспетчеру для осуществления эффективного управления, позволяющего получить максимальный средний доход в единицу дискретного времени (на один шаг) от длительной эксплуатации марковского объекта.

УКМЦ , задаваемая совокупностью (6), исследуется в работах [4,5,8] и основным результатом здесь является следующее утверждение: существует непустое множество оптимальных стратегий, независящих от начального распределения, и это множество содержит стационарную вырожденную в точке и стратегию з(и), где з(и) = [¿(и),. . ., ¿(и), . . . ] е Б, и = (и!,., ип), и; ее?/;, I =1,п, ¿(и) = [.^(и,),., ¿п(ип)] е Р, ¿¡(и;) - стохастический вектор, вырожденный в точке иь т.е. ¿у(ц) = 1, если] = иь ^(и,) = 0, если] * ^, ] = 1,., ш(0, i =1,п. При этом процедура поиска указанной оптимальной стратегии представляет собой итерационный алгоритм Р.Ховарда, сходящийся за конечное число итераций. Этот результат имеет важное прикладное значение, т.к. позволяет осуществить поиск оптимальной стратегии в* на конечном множестве стационарных вырожденных стратегий.

Однако использование указанного результата теории УКМЦ становится некорректным в следующей ситуации, часто встречающейся в приложениях при управлении марковским объектом : значение вектора ад = [(рц(А-,Рип <*(*)],. (18) определяющего стохастические свойства управляемого марковского объекта и входящего в совокупность (6) точно неизвестно, а известна лишь некоторая область его значений (0[(£), где £ = 1,., т(Г), 1 = 1,п .

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

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

2. Вектор зависит от некоторого изменяющегося во времени параметра VI (Х), где к = 1,оо, т.е. ^(Т) = ^)) . Про этот параметр известно лишь то, что он принимает значения го некоторого множества У^)которое порождает область v, (19) где £= 1,., т(0,1 = 1*1. Область !Д(0 является характеристикой неполной информации в значении вектора где , I =1,п, и входит в совокупность исходных данных, которой задается новый объект - УКМЦ с неполной информацией. Эта совокупность записывается аналогично совокупности (6) и имеет вид :

Ы}, (20)

Понятно, что в случае, если (0[(£), I е% , [ =1,п являются одноэлементными множествами, то совокупность (20) совпадает с совокупностью (6), т.е. УКМЦ с неполной информацией тождественна УКМЦ, которую теперь уместно именовать УКМЦ с полной информацией.

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

Так как определение множества где эеБ, требует дополнительных формальных построений, которые целесообразно опустить при первом, во я многом качественном знакомстве с УКМЦ с неполной информацией, то сейчас - в введении в предмет исследования- это определение не приводится оно подробно и во всех нюансах излагается в разделе 1.2). Однако, чтобы оценить элементный состав множества £(б) отметим, что даже для наиболее простого случая, когда б является стационарной вырожденной стратегией, множество ^(з) может содержать в качестве элементов как однородные, так и неоднородные марковские цепи с доходом, которые задаются совокупностями вида (14).

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

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

Ф1(8)=м{П^к-1-д(а,^,к): ад}, (21) где 0,(а, £, к) - средний аддитивный доход за к шагов марковской цепи £ с доходом, определяемый в соответствии с выражением (16).

Таким образом, Ф^) является гарантированным средним доходом в единицу дискретного времени, получаемого от длительной эксплуатации марковского объекта при управлении, осуществляемом диспетчером в соответствии со стратегией б, где Бе8.

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

Ф^^ир* Ф^вбБ}, (22) и ф 1(8V* 1(8б) < В , (23) где е - некоторое положительное число.

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

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

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

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

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

Во втором разделе рассматриваются основные свойства множества 2 0 всех однородных КМЦД с числом состояний равным п, которое представляется в виде : Н0= И): аеР1д, 11еНп}, где 11) - однородная КМЦЦ, задаваемая парой (а, Ъ), а - начальное распределение, РКп - множество всех п-мерных стохастических векторов-строк, Нп = Н х . . . х Н - прямое произведение п экземпляров множества Н, Н = х [-р0, Ро], Ро> 0, Ь =

11,,., 11п] еНп, 11;= , . , Ь^+^еН , элемент 11 определяет матрицу переходных вероятностей Р(Ь) и вектор-столбец дохода я^), Р(Ъ) = (11у), 1 = = 1,п , } = 1,п , ql(h) = [11^+1,., Ь^н]7, 11у - соответствующая компонента элемента 11.

В третьем разделе вводится ^-частичная упорядоченность в множестве Н" основанная на сравнении стационарных характеристик «1(11), \ук(Ъ), к = 1,оо однородных КМЦЦ 11), 1ге Нп, где £ = 1,<», и устанавливаются ее основные свойства, где «[(11) = 7С{И)- ql(ll) - вектор финитного дохода, Л(Ъ)

- матрица финитных вероятностей и Л(Ъ) = Ншк"1-^ + Р(Ь) + . . . + Ры(11)],

Е - единичная матрица порядка п, \Ук(11) = (-1)к+1-[В^(Ь) • ql(h) - «1(11)], к=1^оо - вектора «весов», В ¡(И) = (Е - Р(Ь) + Л(\\))'1 - матрица, обратная к фундаментальной матрице (Е - Р(Ь) + Я(Ь)) .

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

В четвертом разделе определяются £- минимальный, £- максимальный и (£, е)- минимальный, {£, е)- максимальный элементы в множестве 2), где е {1,., п+2}, е>0, Юа Н", и выявляются свойства этих элементов.

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

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

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

В третьем подразделе рассматривается случай, когда три множества: Ю = х2>п,где 2),сН, 1 = й , СоЮ= . . хСо<Па, где а!Двыпуклая оболочка множества Т)х, 1 = 1,п , Т = Т1х. . . хТп,где Т^сН, 1 = 1,п , связаны соотношениями : Т)[ с Т, с Со(1)1. Показывается, что в этом случае, если в одном из множеств Ю, Т, СоЮ существует (п+2)минимальный ((п+2)- максимальный) элемент, то в каждом из этих множеств также существует £- минимальный (£- максимальный) элемент, где £ = 1,п+2. При этом £- минимальный {£- максимальный) элемент в множестве является I- минимальным (£- максимальным) элементом в множествах Т и СоЮ, а I- минимальный {£ - максимальный) элемент в множестве Т является

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

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

В четвертом подразделе рассматривается случай, когда множество (D = = (Dix. . . х (Dn, где 2), с H, i = l,n , имеет некоторый специальный вид. Показывается, что в этом случае в множестве (D существует I-минимальный и i- максимальный элементы, где i = l,n+ 2.

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

В шестом подразделе рассматривается случай, когда (D = (Dix ■ . x(Da, где (D[ с H, i = l,n , является замкнутым множеством. Показывается, что для любого s > 0 существует такое множество Те = Te>i х. . . х , где ТЕ;; -линейный многогранник, обладающий свойством: с Т£;; с H, i = 1,п , для которого выполняются следующие системы неравенств: г;(1)-Ч1(С(1))<е, i = û,

4i(C(2))-ri(2)<s, i=û, где г,(1) = М{*,/11) : Ье£>}, ц(2) = : ЬеЮ}, [ = 1,п , «и(Ь) - 1-ая компонента вектора ^(Ъ) финжного дохода, - соответственно 1минимальныйи 1-максимальный элемент в множестве Т8.

В пятом разделе вводится £- частичная упорядоченность в множестве с^(Нп), согласованная с ¿-частичной упорядоченностью в множестве Нп, где = \,п+2, с/?(Нп) - множество всевозможных подмножеств множества Нп, и устанавливаются ее некоторые свойства. Этот раздел состоит из трех подразделов.

В первом подразделе дается определение £- частичной упорядоченности в множестве с^(Нп) и приводятся утверждения, устанавливающие ее основные свойства. Вводятся также понятия £- максимального и £- минимального элементов в подмножествах множества сА(Ип) и выявляются некоторые их свойства.

Во втором подразделе приводится доказательство существования ¿-максимального (£- минимального) элемента £>(аэ) в множестве А(Щ , где А(г/)с=с^(Нп), РЩ = {Ю{и):и&г[), Ю(и) = Ю1(и1)х . . . хфп(мп), ©¡(«¡)сН, щ-1- ая компонента элемента и, Ы = % х . х % = {\,., т(Т)}, 1 = 1,п, аееЯ/.

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

В шестом разделе дается определение и указываются свойства 1- частичной упорядоченности в множестве Ь , являющемся основной ха рактеристикой множества Е всех конечных марковских цепей с доходом (всех КМЦД), где Ь = Нп х . . . х Нп х . . . . Множество Е всех КМЦД с числом состояний равным п представляется в виде :

Е = {$(а,Ъ):аеР1>п, }, (24) где £,(а,£>)- КМЦД, задаваемая парой (а, начальное распределение; £>= = (И(1),. ., . )е£>, И® е Нп, к=1,оо ; элемент Ь определяет как последовательность матриц переходных состояний этой цепи { Р(к)( Ь)= Р( Ь(к)), к= = 1,оо}, так и последовательность доходов { = <11(Ь(к)), к=1,оо} , Рф00) = {=й ,j = и , Ч1(Ь(к}) = [И 1гЕ+1®,. 11и+1(«]т, Ь,/к) - соответствующая компонента элемента Ь(к).

Устанавливаются основные свойства 1-частичной упорядоченности в множестве £> и указывается ее соотношение с ^-частичной упорядоченностью в множестве Нп, где I = 1,п+2.

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

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

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

Во втором подразделе доказываются условия существования 1-мини -мального (1-максимального) и (1, в)-минимального ((1, в)-максимального) элементов в замкнутом множестве £>, где £> = £)х.х£)х., Ф — х . х - любое замкнутое подмножество множества Н, I = 1,п. Указываются также основные свойства упомянутых элементов.

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

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

В седьмом разделе вводится 1- частичная упорядоченность в множестве сАф ), согласованная с 1-частичной упорядоченностью в множестве •£>, где = Нп х . . . х Нп х . . . , сЛф ) - множество всевозможных подмножеств множества £ , I = 1,п + 2. Устанавливаются основные свойства введенной частичной упорядоченности.

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

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

Во втором подразделе приводятся теоремы существования ¡-максимального и 1-минимального элементов в множествах 2л = { Ф^): зеБ} и Х1>0= и&М}, связанных непосредственно с УКМЦ с неполной информа цией К{ = [Б, сДЕ), где Б - множество стратегий, ф^с £), ^(б) = а, Ь): аеРца, Ь^^)}, Ца, Ь) - КМЦЦ, задаваемая парой {а, Ь) (см . выражение (24)), б (м)-стационарная стратегия, вырожденная в точке и, и = х . х ип - множество управлений, {1,., ш(1)}, {= 1,п . Множество ^(б) называется стационарной характеристикой неполной информации, определяется на основе совокупности исходных данных (20) и имеет следующий вид : i(s)= {[Ь(1)(,(1)), .Д00^),.^ : [ для любого к = 1,оо выполm(i) няется равенство h[k)(>,(lc)) =Xihi О)4!? > hi(í)e^iGX i= l.n ] }, j=i где - i-ая компонента элемента h^i^), = [>|к),.,*(пк)] - к-ая компонента стратегии s, ¿¡(k) - i-ая компонента ¿(k) , íD¡(j) - характеристика неполной информации в значении вектора hi(j), заданная в совокупности (20), }еЦ, i = ü¡.

В этом подразделе показывается, что 1- максимальный (1- минимальный) элемент £>i(s(as)) в множестве 0 является 1- максимальным (¡-минимальным) элементом в множестве !Хь При этом as является таким элементом из множества U, для которого £>(аэ) является £- максимальным (£- минимальным) элементом в множестве А((М) = {D(ú) : иеЩ, где £ = l,n + 2, 'Diu) = =©i(tti) х . х Da(ua), Diu) - характеристика неполной информации в значении вектора h¡(«¿), заданная в выражении (20) , щ - i-ая компонента управления и, щ = 1,., m(i), i = i|ñ.

В третьем подразделе приводятся теоремы существования ¡-максимального, ¡-минимального элементов в множествах %2 = {£>(s):seS}и s(z¿)): ueíí}, связанных непосредственно с УКМЦ с неполной информа щей K2 = [S, <á(Z), Ы где £(s))c t>, £(s) = {£(а, Ь): аí>e©(s)}. Множество £(s) называется нестационарной характеристикой неполной информации, определяется на основе совокупности исходных данных (20) и имеет следующий вид : £(s) = {[h(1)(»(1)),., ¡^(Я),.]^ : j-i где Ь[к) (*,(к))- 1-ая компонента элемента Ь(1%(к)), *(|с) = Ык)] - к-ая компонента стратегии э, ¿¡(к) - ьая компонента *(к), - характеристика неполной информации, заданная в совокупности (20), }е% ,[ =

В этом параграфе показывается, что 1- максимальный ( 1-минимальный) элемент £>2(з(ае(1))) ( £>2(з(а2(2))) ) в множестве Т2>0 является 1-максимальным (1-минимальным) элементом в множестве При этом аэ является таким элементом из множества для которого 5" (ж) является I- максимальным (£- минимальным) элементом в множестве А(Щ = {о (и) : иеЩ, где £ = \,п + 2, б"{и) - замыкание множества "Ь(и).

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

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

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

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

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

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

1) множество состояний системы, представляющее собой декартово произведение множеств состояний составляющих ее элементов;

2) система эксплуатируется в течение длительного времени и ее поведение удовлетворительно описывается управляемым полумарковским процессом;

3) наличие неполной информации о надежностных (вероятностных) характеристиках элементов.

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

1. W. Vogel. An asymptotie Minimax Theorem for the Two-Armed Bandit Problem.-Ann. Math. Stat., 1960, v. 31, p. 444-451.

2. C. Derman. On sequential decisions and Markov chains. Manag. Sci., 9, 1, 1962,16.24.

3. D. Blackwell. Discrete dynamic programming. Ann. Math. Statist. 33,1962, 719-726.

4. O.B. Висков, A.H. Ширяев. Об управлениях, приводящих к оптимальным стационарным режимам. Труды Математич. Ин-та им. В.А. Стеклова АН СССР, 1964, 35-45.

5. Р.Ховард. Динамическое программирование и марковские процессы. М.: Сов. Радио, 1964.

6. Marting Lof A. Optimal control of a continions-time Markov decision chain with periodic transmion probabilities. Operations Pes. 15, 1967,872-881.

7. Fabius J., Zwet D. Some Remarks on the Two-Armed Bandit. Ann. Math. Stat., 1970, v. 41, N 6, p. 1906-1916.

8. Х.Майн, С.Осаки. Марковские процессы принятия решений. М.: Наука, 1977.

9. А.Н. Ширяев. Некоторые новые результаты в теории управляемых случайных процессов. Transacions of 4-th Prague Conference on Information Theory, Statistics, Decision Fuctions, Random Processes. Prague, 1967.

10. Bather. Optimal decision procedures for finite Markov chains. Part III: general convex system. Adv. Appl. Prob, 5, 3 (1973), 541-553.

11. Е.Б. Дынкин, A.A. Юшкевич. Управляемые марковские процессы и их приложения. М.: Наука, 1975.

12. Р.Я. Читашвили. Управляемая конечная цепь Маркова с произвольным множеством решений. Теория вероятностей и ее применения, 1975, 20, № 4, 855-864.

13. Е.А. Файнберг. Об управляемых марковских процессах с конечным числом состояний и компактными множествами управлений. Теория вероятностей и ее применения, 1975, 20, №4, 873-880.

14. Е.А. Файнберг. О конечных управляемых цепях Маркова. Успехи математических наук, 1977, 32, №3,181-182.

15. Е.А. Файнберг. Существование стационарной 8 оптимальной стратегии. Теория вероятностей и ее применения, 1978, 33, № 2, 313-330.

16. Е.А. Файнберг. s оптимальное управление конечной цепью Маркова при среднем критерии. Теория вероятностей и ее применения, 1980, , № 1, 71-82.

17. Чжун Кай-лай. Однородные цепи Маркова. М.: Мир, 1964.

18. Дж. Кемени, Дж. Снелл. Конечные цепи Маркова. М.: Наука, 1970.

19. Е.Г. Белоусов. Введение в выпуклый анализ и целочисленное программирование. М.: Московский университет, 1977.

20. А.Н. Ширяев. Вероятность. М.: Наука, 1980.

21. Д.К. Фадеев, В.Н. Фадеева. Вычислительные методы линейной алгебры. M.-JL: Физматгиз. 1963.

22. А.Н. Колмогоров, С.В. Фомин. Элементы теории функций и функционального анализа. М.: Наука, 1976.

23. Математическая энциклопедия. М.: Сов. энциклопедия, 1977.

24. Е.Ю. Барзилович, В.А. Каштанов. Некоторые математические вопросы теории обслуживания сложных систем. М.: Сов. радио, 1971,

25. Е.Ю. Барзилович, В.А. Каштанов. Организация обслуживания при ограниченной информации о надежности системы. М.: Сов. радио, 1975.

26. В. Джевелл. Управляемые полумарковские процессы. Кибернетический сборник. Новая серия, вып. 4. М.: Мир, 1967,252-268.

27. В.Г.Срагович. Адаптивное управление. М.: Наука, 1981.

28. Э.Л.Пресман, И.М.Сонин. Последовательное управление по неполным данным. М.: Наука, 1982.

29. В.В. Баранов, Н.С. Подцыкин, Н.И. Харыбин. Методы оптимальных решений в управляемых марковских системах с ненаблюдаемыми состояниями. Вестник Харьковского университета, 1987, № 298,49-52.

30. Ю.А. Великий. Условия сходимости распределений моментов достижения для цепей Маркова. Доклады АН СССР, 1988, А, № 6, 10-12.

31. О.Н. Мартыненко. Алгоритм исключения неоптимальных стратегий в управляемых марковских процессах. Автоматика, 1988, № 2, 71-73.

32. Г.Н. Цервадзе. Об агрегировании и укрупнении марковских цепей. Сообщения АН СССР, 1988,129, № 3, 505-508.

33. Т.А. Сарымсаков. Основы теории процессов Маркова. Ташкент: Фан, 1988.

34. В.М. Ядренко. Об одной экстремальной задаче для цепи Маркова, описывающей простейшее случ. блуждание с отражением. Изб. задачи соврем, теории случ. процессов. Киев, 1988,116-119.

35. W. Grassmann. Markov modelling. Winter Simul. Conf. Proc. Arlington, Va, 12-14 Dec, 1983, vol. 1. New York, № 4, 1983,613-619.

36. A. Nazin, A. Poznyak. Stochastic. Contr.: Proc. 2 IF AC Symp., Vilnius, 19-23 May, 1966. Oxforte.a., 1987,365-369.

37. Chrzan Piotr. О pewnym algorithmic rozwiazania zadania optimalizacja niejedno-rodnego okresowego lancncha Markowa. Pr. Nauk. AE Wroclfwin, 1986, № 351, 25-49.

38. Borkar Vivek S. Control of Markov chains with loug run average cost criterion. Sto-chast. Duffer. Syst., Stochast. Contr. Theory and Appl.: Proc. Workshop, June 9-19, 1986. New York e.a., 1988,57-77.

39. Olsder G., Papavassilopoulos G. A Markov chain game with dynamic information. J. Optimiz. Theory and Appl., 1988, 59, № 3, 467-486.

40. Seneta E. Sensitivity to perturbation of the stationary distribution: some refinemens. Linear Algebra and Appl., 1988, 108, 121-126.

41. Schäl M. Estimation and control in Markov decision models. Wiss. Z. Tech. Hochsch., Leipzig, 1988, 12, № 3, 187-192.

42. Rubino G., Sericola B. On weak lumpability in Markov chains. J. Appl. Probab., 1989, 26, № 3, 446-457.

43. Semal P., Courtois P. Stability analysis of large Markov chains. Performance 87: Proc.12 th IFIP WG7. 3 Int. Symp. Comput. Performance Modelling, Meas. and Eval., Brussels, 7-9 Dec., 1987. Amsterdam etc, 1988, 363-382.

44. Filar Jerzy A, Lee Huey Miin. Proc. 24 th IEEE Conf. Decis. and Contr, Fort Lauderdale, Fla, Dec, 11-13, 1985, vol. 2, New York, № 4, 1985, 1106-1112.

45. Kurano Masami. Markov decision processes with a minimum variance criterion. J. Math. Anal, and Appl, 1987, 123, № 2, 572-583.

46. Ohno K. A value iteration method for undiscounted multichain Markov decision processes. Zor : Z. Oper. Res, 1988, 32, № 2, 71-93.

47. Schweitzer P. Solving Markovian decision processes by successeve elimination of va-riables. J. Math. Anal, and Appl, 1988, 130, № 2, 403-419.

48. Borkar Vivek S. Control of Markov chains with loug run average cost criterion: the dynamic programming equations. SIAM J. Contr. and Optim, 1989,27, № 3, 642-657.

49. Жуков B.M, Карманов A.B., Ливанов Ю.В. Управляемые конечные марковские цепи с неполной информацией и их приложения. ВИНИТИ, № 4623 В88 деп, М.: ВЦ АН СССР, 1988 -228 с.

50. Жуков В.М, Карманов A.B., Ливанов Ю.В. Учет надежности оборудования при автоматизированном проектировании генеральных схем обустройства нефтяных месторождений, М, Автоматизация и телемеханизация нефтяной промышленности, 1986, 40 с.

51. Юшкевич A.A. Проверочные теоремы для марковских процессов принятия решений с управляемым детерминированным сносом ., Теория вероятностей и ее применения, 1989, 34, № 3, с.528-551.

52. H.-J. Girlich, A.A. Sokolichin. Schätzen und Steueru in einem Markoffshen Entshei-dungsmodell mit unbekanter Parameterfolge. Wiss. Z. Tech. Hochschule, Leipzig, 1988, 12, №2.

53. Комашко O.B. Устойчивость цепей Маркова, порожденных кусочно-линейными преобразованиями. Киев: Киевский университет, 1990, 17 с. Деп. в ВИНИТИ 3491. Ук. 90.

54. Боровков A.A. Эргодичность и устойчивость многомерных цепей Маркова. Теория вероятностей и ее применения. 1990, 35, № 3, 543-547.

55. Гущин A.A., Екушев А.И. Оценка среднего дохода от программного управления для одного типа управляемых марковских последовательностей. Теория вероятностей и ее применения. 1990, 35, № 3,438-448.

56. Küenle Heinz-Uwe. Maarkov games with complete information and average cost criterion. Trans. 11 th Prague Conf. Int. Theory, Statist. Desis. Funct.: Random Process., Prague, Aug. 27-31,1990, vol. B.

57. Feinberg E. A Markov decision model of a search process. Strateg. Seguet. Search and Select. Real Time : Proc. AMC IMS - SIAM Jt Summer Res. Conf., Amherst, Mass., June 21-27,1990.

58. Schäl M. On the chance tu visit a goal set infinitely of ten Optimization. J. Appl. Probab. 1990.v. 21,№ 4, 585-592.

59. Медницкий В.Г., Авербах Б.А. Стохастическая модель функционирования производственной системы. Экономика и экономические методы. 1991, 27, № 2, 383-391.

60. Mäläncioin Odetta. On the Markov chains with parameter. Sei. Bull. Moch. Eng. Po-lytechn. Inst. Buharest. - 1991 - 53, № 1, 2

61. Tsantas N., Vassilion P. The non homogeneons Markov system in a stochastic environment. J. Appl. Probab. - 1993. - 30, № 2, 285-301.

62. Schäl M. Average optimality in dynamic programming with general state space. Math. Op. Res., 1993, № 18,163-172.

63. Sennot Linn I. The average cost optimality equation and critical number policies. Probab. Eng. and Inf. Sei. 1993. 7, № 1, 47-67.

64. Ferenstein Elzbieta Z. A variation jf the Dynku stopping game. Math. jap. -1993. 38, №2, 271-279.

65. Di Masi G. Stettner L. On adaptive control of a partially observed Markov chain. Appl. Math. 1994. - 22, № 2, 165-180.

66. Guo Xianping. Strong optimality for MDP average model. Acta sei., natur. Univ. norm. Hunanensis. 1996. - 19, № 1, 21-24.

67. Borkar Vivek S. Ergodic control of Markov chains with constraints the general case. SIAM J. Contr. and Optimiz. - 1994. - 34, № 1.

68. Puterman M. Markov Decision Processes. Wiley, New York, 1994.

69. Stettner Lukasz. Ergodic control of Markov processes with mixed observation structure. Diss. math. 1995. - № 341, p. 1-36.

70. Scariano Stephen M. Decisions, decisions,. Math, and Comput. Educ. -1995.-29, № 1, p.83-93.

71. M.Haviv, M.Puterman. Bias optimality in controlled queueing systems. J.Appl.Prob., 1998, V.35, p.136-150.

72. Ибрагимов A.A. О марковской игре «Большой матч». А и Т, 2000, № 11.

73. Ибрагимов A.A. Существование и нахождение оптимальных стратегий в рекур сивных играх. Изв. РАН, Т и СУ, 2001, № 4.

74. Жуков В.М., Карманов A.B. Управляемые конечные марковские цепи с неполной информацией и их приложения (минимаксных подход). М.: МГИЭМ, 2000.

75. Карманов A.B. Исследование управляемых конечных марковских цепей с неполной информацией. М.: Наука, 2002.

76. Карманов A.B. Метод расчета стационарных показателей надежности объектов нефтеснабжения в условиях неполной информации об исходных данных. Автоматизация, телемеханизация и связь в нефтяной промышленности, 2004, № 12.

77. Карманов A.B., Карманова JI.A. Алгоритм решения задачи оптимального управления сложной системой с неполной информацией о надежности элементов. Автоматизация, телемеханизация и связь в нефтяной промышленности, 2005, № 5.

78. Карманов A.B. О возможности «зацикливания» вычислительной процедуры при определении стационарных характеристик надежности. Автоматизация, телемеханизация и связь в нефтяной промышленности, 2005, № 6.

79. Карманов A.B. Метод определения «весов» в процедуре расчета стационарных характеристик надежности сложных систем нефтеснабжения с неполной информацией. Автоматизация, телемеханизация и связь в нефтяной промышленности, 2005, № 9.

80. Карманов A.B., Карманова J1.A. Метод оценки финитных вероятностей на основе агрегирования марковской цепи. Автоматика и Телемеханика, 2005, № 10.

81. Сухарев М.Г, Карасевич A.M. Технологический расчет и обеспечение надежности газо- и нефтепроводов. М.: Нефть и Газ, 2000.