6. СИСТЕМЫ С НЕЯВНО ОПРЕДЕЛЕННЫМ ВРЕМЕНЕМ ОКОНЧАНИЯ ПРОЦЕССА

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

Итак, пусть управляемая система А является детерминированной системой, характеризуемой уравнением состояния вида

где принадлежит множеству — финальное множество. Как и прежде, считается заданной функцией, осуществляющей отображение из , где — область изменения . Отметим, что если является поглощающим состоянием, т. е. состоянием из множества Т, то можно записать для всех

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

A в момент находится в состоянии то расплывчатое ограничение на задается расплывчатым множеством в условным по Функция принадлежности этого множества будет обозначатся как

Пусть — начальное состояние , где — дополнение Т до X. Каждому такому начальному состоянию будет соответствовать решение определяемое формулой

в которой последовательные состояния могут быть выражены в виде функций от в результате последовательного применения уравнения состояния (34). Итак,

Обметим, что так же, как и в уравнении (26), множества С в (35) следует рассматривать как расплывчатые множества в декартовом произведении пространств . Кроме того, нужно отметить, что соотношением определяется однозначно для каждого причем считается, что пусто, если не существует конечной последовательности входных сигналов — переводящей систему из начального состояния в состояние из Т. В этом случае мы будем говорить, что Т недостижимо из начального состояния.

Из (35) несложно получить более простое неявное уравнение, которому удовлетворяет . Действительно, вследствие инвариантности по времени Системы А и независимости от времени цели и ограничений из (35) вытекает

для . В частности,

и, следовательно, (37) можно записать как

или, используя (34), в виде

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

где время окончания также является функцией от и определяется с помощью уравнения состояния и дополнительного условия при .

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

Поскольку определяются по с помощью (42) и уравнения состояния (34), то функцию принадлежности для можно записать как . Аналогично можно представить как как . В этих обозначениях (41) приобретает более компактный вид:

что по существу является системой уравнений (по одному для каждого значения ) относительно . Эта система уравнений определяет как функцию от Для каждой стратегии причем считается, что если при стратегии процесс не заканчивается,

т. е. не существует конечного числа такого, что . Кроме того, считается, что для состояний из Т.

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

Для решения задачи удобно представить стратегию в виде вектора стратегии

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

Имея в виду систему уравнений (43), введем n-мерный вектор

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

которое означает, что стратегия не хуже стратегии в том и только в том случае, если

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

Существует ли оптимальная стратегия для рассматриваемой задачи? Ответ на этот вопрос является положительным. Это утверждение может быть строго доказано [12], однако для наших целей достаточно считать его следствием принципа «чередования» [13] — весьма общего принципа, справедливость которого в каждом конкретном случае может быть непосредственно доказана.

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

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

Пользуясь соотношением (43), нетрудно получить функциональное уравнение, которому удовлетворяет вектор достижения цели, соответствующий оптимальной стратегии. Пусть

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

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

максимум от обеих частей равенства (43), получим

Данное выражение и является искомым функциональным уравнением относительно . Уравнение (49), отличаясь в деталях, имеет тот же общий вид, что и функциональные уравнения, возникающие в теории марковских процессов принятия решений [17]. Однако его решение может быть получено значительно проще вследствие дистрибутивности операций .

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

Воспользовавшись дистрибутивностью и приводя подобные члены, можно представить уравнение (50) в гораздо более простой форме — в виде системы уравнений относительно компонент

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

в уравнении (51) являются , в то время как — заданные константы.

Чтобы облегчить поиск решений уравнений (51), полезно упростить обозначения, введя новые неизвестные . Заменим также символы знаками произведения и суммы. Тогда в матричной записи уравнение (51) примет следующий весьма компактный вид:

где причем если не следует непосредственно за , где — входные сигналы, переводящие и

при этом считается, что для состояний, не входящих в финальное множество Т.

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

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

а поскольку то, следовательно, .

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

достижения цели . Более подробный анализ показывает, что процесс (54) дает решение уравнения (52) не более чем за I итераций. Этот факт является непосредственным следствием следующей леммы.

ЛЕММА. Пусть — квадратная матрица порядка l, состоящая из вещественных элементов. Пусть также степень матрицы В, причем знаки суммы и произведения везде обозначают операции соответственно. Тогда для всех целых

и

где I — матрица тождественного преобразования.

Доказательство. Справедливость леммы становится довольно очевидной, если интерпретировать (56) в рамках теории графов. Именно, пусть обозначает граф с I вершинами, причем представляет «прочность» дуги между вершинами и Пусть через обозначена цепь из дуг в графе

начинающаяся в вершине и оканчивающаяся в вершине . Индекс служит меткой рассматриваемой цепи и изменяется в пределах от 1 до М, где М — число различных цепей длины соединяющих вершины и .

Определим прочность . Цепи как прочность самого слабого ее звена, т. е.

Из определения произведения матриц (с заменой суммы и произведения на операции соответственно)

ясно, что элемент матрицы может быть представлен в виде

или, в более компактной форме,

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

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

Таким образом, утверждение леммы эквивалентно следующему:

Если В — матрица порядка и , то прочность самой прочной из всех цепей с длиной соединяющих вершины и равняется прочности самой прочной цепи среди всех цепей с длиной, меньшей или равной соединяющих вершины и .

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

Следовательно, для окончания доказательства достаточно установить справедливость противоположного неравенства .

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

из определения прочности цепи (58) имеем

и, следовательно, супремум от по всем цепям длины не превышает супремума от по цепям длины . Таким образом,

откуда

что вместе с (61) доказывает соотношение (56).

Фиг. 2.

Что касается равенства (57), то заметим, что при (62) справедливо для . Без ограничения имеет место для если для . Последнее условие удовлетворяется при замене В на . Это означает, что показатель I в (56) может быть заменен на при замене В на . В результате получается формула (57).

Возвращаясь к решению уравнения (52), заметим, что итерация имеет вид

Применяя лемму, получим

откуда следует, что процесс (54) дает решение уравнения (52) не более чем за итерации.

Для большей наглядности описанного способа решения уравнения (52) полезно представить переход от (49) к (51) с помощью диаграммы состояний системы А. Предположим для определенности, что система А имеет пять состояний и переходы между состояниями под воздействием различных входных сигналов соответствуют фиг. 2. На этой диаграмме

Фиг. 3.

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

Для рассматриваемой системы функция перехода в новые состояния представлена табл. помощью этой таблицы нетрудно построить матрицу для любой выбранной стратегии. Например, для ось имеем

Система уравнений (51) получается при изменении направления перехода по каждой дуге на обратное (фиг. 3), причем состояния из Т рассматриваются как источники, а состояния и из как приемники (стоки). Пользуясь диаграммой, представленной на фиг. 3, можно сразу написать уравнения системы (51):

Таблица 8 (см. скан)

Применяя систему упрощенных обозначений, в которой операции заменены произведением и суммой, и полагая , можно привести систему уравнений (67) к виду

где

Полагая получаем первое приближение . Последующие итерации дают

Следовательно, есть решение уравнения (68).

Чтобы наглядно представить процесс итераций, предположим, что каждый из источников на фиг. 3 (являющихся поглощающими состояниями на фиг. 2) порождает шарики различных диаметров, причем для источника диаметры шариков меняются в пределах от 0 до . Представим себе далее, что дуга на фиг. 2, соответствующая переходу из состояния при входном сигнале является трубой диаметром которая в обратном направлении, т. е. в направлении, показанном на фиг. 3, может пропускать щарики диаметром не более . Следовательно, диаграмму на фиг. 3 можно интерпретировать как сеть труб указанных диаметров, которые могут пропускать шарики меньшего или такого же диаметра в указанных направлениях. Состояния принадлежащие финальному множеству, играют роль источников шариков диаметров не более соответственно, а остальные состояния являются приемниками. Поскольку поглощающие состояния действуют как источники, описанный метод решения будет называться методом обратного потока.

Предположим теперь, что на переход шарика из одной вершины сети на фиг. 3 в другую затрачивается одна единица времени. Если в момент времени шариков в вершинах нет, то в момент максимальные диаметры шариков в будут соответственно равны , где — первая итерация, получаемая с помощью уравнения (68). В момент максимальные диаметры шариков будут задаваться величиной , а в момент величиной . Так как для перехода любого шарика из порождающего его источника в любую вершину сети требуется не более трех единиц времени; то при новых итерациях не будет происходить дальнейшего увеличения размеров шариков в каждом источнике. Таким образом, величина определяет максимальный диаметр шариков

в каждом стоке и, следовательно, является искомым решением (68).

Переходя к иллюстрации уравнений (43) и принципа чередования, рассмотрим вектор стратегии . Для этого вектора система (43) принимает вид

В этом случае состояния принадлежат . Замечая, что сразу находим искомое решение:

Результаты, полученные с помощью аналогичных вычислений для других возможных стратегий, приведены в табл. 9.

Таблица 9 (см. скан)

Для проверки принципа чередорания возьмем и Применение правила (47) дает Отметим, что и . Согласно данным табл. 9, оптимальной стратегией будет , что совпадает с результатом итераций.

Описанный в настоящем разделе подход к решению задач с неявно определенным временем окончания

может быть распространен на более общие процессы принятия решений в расплывчатых условиях. В частности, метод решения функционального уравнения (49) может быть легко обобщен на случай расплывчатых систем в расплывчатых условиях. Кроме того, по аналогии с разд. 4 уравнения (43) и (49) можно обобщить на случай стохастических систем с конечным числом состояний.