Тынянский Н.Т., Жуковский В.И. Дифференциальные игры с ненулевой суммой (кооперативный вариант)

Подождите немного. Документ загружается.

Р^Т^Сг + рСь Р

(Г) = С

Сами оптимальные стратегии угроз имеют вид

Й (t) = -RT

B[P

(t)

х>

(*), Й (')=-- /?-"^Р

ХУ

(*),

где л:

(*), ^о<^<-

-~Р

ег

ение

системы

.х

= (А

—

B.R-^P,-1 B

R^B

) x, x (*

) = x

§ 4. Лексикографически оптимальное решение

В.

п. 4.1 доказано, что лексикографически оптимальное ре-

шение является одновременно оптимальным по Парето. Подход

к ранжировке критериев рассмотрен в п. 4.2, необходимые

условия — в п. 4.3.

4.1.

Определение. Предположим, что компоненты «вектора

I={I

...,

} (И) образуют иерархическую систему, т. е. чем

•важнее максимизация компоненты I, тем меньший индекс ей

присваивается. Таким образом, все функции выигрыша, обра-

зующие векторный критерий, строго упорядочены: при сравне-

нии двух наборов управляющих воздействий в первую очередь

используется первая функция .выигрыша 1\ и лучшей считается

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

значение Д больше; если значения Д на обоих наборах одина-

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

больше значения второй функции выигрыша /

и т. д. Если

значения всех функций выигрыша для рассматриваемых двух

наборов совпадут, то эти наборы считаются эквивалентными.

Пусть

—множество всех наборов управляющих воздейст

вий в игре (10)-

(11).

Лексикографически оптимальное решение

для (10)- (И) можно определить [124] с помощью следующих

рекуррентных соотношений: набор управляющих воздействий

Щ называется лексикографически оптимальным для игры (10)—

(11),

если а

1]е%

, где Щ

={иЩ, t

<t<T \u{-\eUj-u

Jj («!•])-= max /, <«!-!)> у-=1,2,

...,N;

<U$

= % «Г =

<¥&.

Задачи, связанные с лексикографически оптимальным реше-

нием, встречаются как в математической экономике, так и в

исследовании операций.

Важной особенностью такого решения является следующий

хорошо известный [122, 86] факт: лексикографически опти-

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

(10) —

(11)

является оптимальным по Парето.

Доказательство приведенного утверждения [68]: пусть

[t] —лексикографически оптимальный набор для игры (10) —

(11),

тогда для любого набора w[.]{in}~2/ либо найдется индекс

;{in}l,...,JV такой, что I

[-])>I

(u[-]), либо /,г("

[-])-

—

{

(и[-])

для iBcex t=

2,...,

N. Это в свою очередь озна-

чает, в силу определения Ь) (стр. 16), что набор u

[t] оптима-

лен по Парето для игры (10)

—

(11).

Изложенный подход к решению задачи векторной оптими-

зации впервые, по-видимому, был высказан Нельсоном оз 1964 г.

[308].

Глубоким исследованиям задач лексикографической оп-

тимизации в случае статических (не дифференциальных) игр

посвящена монография В. В. Подиновского и В. М. Гаврилова

[124].

Этот же вопрос для динамических систем рассматривал-

ся в статье [207] и в монографии Р. Габасова и Ф. Кирилловой

[25].

Частный случай линейной системы с двумя квадратич-

ными функциями выигрыша разобран ов статье

[237];

линейная

система с двумя функциями выигрыша, аддитивными по х и и,

исследована в

[207].

Далее мы остановимся лишь на двух во-

просах: задача ранжировки критериев (Валтс [356]) и необ-

ходимые условия существования типа принципа максимума

(В.

М. Гаврилов [124, гл. IV]).

4.2.

Ранжировка критериев. В практических задачах может

отсутствовать четкая ранжировка критериев, т. е. нет строгой

упорядоченности критериев по важности. В этом случае Валтс

предложил [3561 следующий подход для выявления иерархии

критериев. Пусть в дифференциальной игре

(10)

—(11) найдены

/V наборов управляющих воздействий u^[t], i = \, . .'.,JV,

такие, что /-(«(-){•]) = max/i(.#[•])• Предполагаем, что каждый

из указанных максимумов достигается на единственном (для

него) наборе

#<-)[.*].

Найдем N

выигрышей //--=/-(и

(у)

[-])

(i,

/—-1,

.. .,/V) и составим матрицу

[/{]Г*

Поскольку эта ма-

трица конечна, то ее анализ позволяет в некоторых случаях

выбирать главный критерий.

Пример. Для игры:

= х

, х

=и, x

(0) = x

(Q) = x

(\) =

JCI(1)

= 20,

|и(^)|<1;

= mlns\iji\u(t)\, I

=min

\ tt

(t)dt, I

= minsup

(t)\;

«(•)

t «(•) i «(•) t

матрица

Г80 6400 40

[Ii]

i= 90 4982, 432,01

L90 5400 30 .

Оценка элементов этой матрицы показывает, что при увеличе-

нии пиковой амплитуды управления с 80 до 90 (т. е. на 12,5%)

выигрыш от снижения энергетических затрат на управление

составит 15,4% и одновременно снизится пиковая амплитуда

скорости x

(t) на 25%. Отсюда вытекает иерархия оптимизации,

связанная с предпочтением критерия 1

Однако указанный подход может быть практически полезным,

когда матрица [ij]?, указывает на явное преимущество какого-

.либо критерия и когда имеет место высокая чувствительность

критериев к изменению управления.

4.3.

Необходимые условия. Будем предполагать, что в

(10) —

(11) N^n, функции Ф,г = 0, f=f(x, и) и

= Fi(x, и) непрерыв-

но дифференцируемы; набор программных управлений u(t)&

{in}l/

—

компакту в R

, to^t^T и функции u(t) кусочно непре-

рывны. Множество u(t) обозначим через

°U.

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

(10)

— (11)

к виду:

x^=f(x,u),

x{t

) = x

= F(x,u),

y(t

)

y£R

; 1Ли\-\) =

У1

{Т),

J-----1,

...,JV.

Необходимые условия существования лексикографически опти-

мального набора программных управлений u

(t) далее формули-

руются 11241 уже для приведенной игры; решение первой

лодсистемы (х=/(х, и), x(t

) = x

) при

{t)

обозначим

{t),

<ct*cT,

а решение второй подсистемы при x =

(t),

^-_гг

(0-через

*у),

<t<T.

Непосредственное применение принципа максимума Л. С. Понт-

рягина дает необходимое условие оптимальности и

(t) по пер-

вому критерию Уг{Т):

Если к

(/)и соответствующее ему решение х

^),

*ct<cT,

оптимальны по критерию

У\(Т),

то существует ненулевая

вектор-функция

ф(-)

{ф<->(*),

(^)}е^"

,^о<^<Г, удовлет-

воряющая уравнениям

() B=

agl

(

.(O..MO,i'"(0)

^..(D-o, •ft

(T)-l.

такая, что

/-/- {х

{t),

(t),

(1)

(t))

= max tf

(х

(t), и, ^

{l)

(t)),

где Jhf

(x,u,^

{l)

) = [^

{1)

Yf(x,a)^

{

nliF

(x,tt), при этом

«ф$1

(*)

при

<t<T.

Задача оптимизаций процесса по второму критерию запи-

шется в следующем виде:

таху

(Т) при ограничении у

(Т) =

(Г).

Принцип максимума по второму критерию приводит к сле-

дующим необходимым условиям:

Если u

{t) и соответствующее ему решение

(t),

<£<7\

оптимальны по выписанному второму критерию, то существует

ненулевая непрерывная вектор-функция ty

(2)

(£)=-={V (*)» %+i (*)»

tyn+2(t)}> удовлетворяющая системе

(для ij^i+i (t) граничные условия не определены) такая, что для

каждого *'б[*о»

-П

имеет место равенство

(x"(t),

{t), ф

(2)

(0) = тахЯ

(^), и, $

(2)

(t)),

где ЯзСх.и, $

(2)

)-=[V

Y/(^ при

этом ^Slj(t) = Const (у—-1,2).

Продолжая дальше, получим, что задача оптимизации про-

цесса по r-му частному критерию приводится к виду

maxy

(T) при y

(T) = yf(T)

= l, ..

.-r-1).

Необходимые условия оптимальности

(^)

в этом случае пред-

ставлены следующими соотношениями

(х

(t),

(/.),

(

° (/))=гаах Н

{х

(t),

и, ф

(t)),

(х,

и,

(г)

) = [Ч>

]'/

(л,

я)

фЦ/Fy (л, и),

/=-1

Полагая в последних условиях

= 1,2, .. .,JV, получаем сово~

купность необходимых условий лексикографической оптималь

ности набора программных управлений и

^), *

<:£<7\ При

добавлении к этим условиям следующих граничных условий

для фазовых координат

*<*о)-=•*<>. tfCoHO, yi(T) =

y*(T)

= l,...,iV—l)

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

зуются для нахождения лексикографически оптимального набора

программных управлений u

{t). Отметим, что ^i+j(0 = Const

(/=1,.

..,г).

Рассмотрим частный случай игры

(10)

—(11):

A (Or

№(«)!'

(*-)-*о.#(*о)-=о.

ItW = yi(T) (i=l iV),

где элементы

/г X

^-матрицы

Ai(t),

лХ-^-матрицы Л

(0 =

-"•/.-+1

(0 1

= '"•;/-. (ft-вектора a

n+J

(t),

= l,

...,N),

компоненты

я-вектора

<р-

(и) и

JV-вектора

(и)

{ср

я+1

(и),

...,

+N(и)}

непре-

рывны. Необходимые

достаточные условия существования лек-

сико-графически оптимального набора программных управлений;

примут вид (В. В. Подиновский, В. М. Гаврилов [124]).

Для того чтобы и

(£), ^

<£<7\ было лексикографически

оптимальным, необходимо и достаточно, чтобы при каждом

фиксированном t£\t

, T] вектор u

{t) был точкой лексикографи-

ческого максимума на множестве U в смысле векторного кри-

терия Я = {Я

. .., H

}, т. е. и

У)ви

, где £/

(для каждого t}

определяется рекуррентными соотношениями:

Uf=*(u(t)/a{t)&Ji-u Я

;

(/,и(/)) = тахЯ

(/, я

(*))}.

1 ^(06c//Li J

Здесь функции Я

[¥(

)]

+ ф

я+г

, г

==1,

..., N, а функции:

ч-Р

(г)

, (г = 1,..., /V) удовлетворяют системе урав-

нений

^)(t)=-A[W(r)(t)-a

n+r

(t),

W^)(T)

г=1 N.

В [124] получены также необходимые и достаточные усло-

вия существования лексикографически оптимального решения

для многошаговой игры, где система (10) линейна и функции

выигрыша Ii = c/x(T),

i—1,...,

N, d— постоянные векторы

из R

§ 5. Абсолютное кооперативное решение

В п. 5.1. определяется абсолютно кооперативное решение,.

необходимым и достаточным условиям существования которого

посвящен п. 5.2.

5.1.

Определение. Набор управляющих воздействий u

[t]

называется абсолютно кооперативным решением для диффе-

ренциальной игры (10)

—

(И), если

Л(Й*1-1)>Л(Я1-1), >=1,...,л/\

для любых наборов управляющих воздействий w[-]{in}3?/, т. е.

максимумы всех функций выигрыша достигаются на одном и

том же наборе управляющих воздействий u

[t].

Согласно определению, абсолютно кооперативное решение

одновременно является равновесным [151] и оптимальным по

Парето для игры (10) — (И).

Ю.

Б. Гермейер в [32] ввел следующее определение: управ-

ляющее воздействие i-ro игрока Щ

Щ названо абсолютно опти-

мальным, если для любых Uj[t], j¥=i, имеет место

-/•*(•«-/[-],-

N\i[-])^li{u[']). Набор абсолютно оптимальных управляю-

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

обратное, вообще говоря, неверно.

5.2. Необходимые и достаточные условия. Получение необ-

ходимых и достаточных условий существования абсолютно ко-

оперативного решения не вызывает трудностей. Здесь следует

просто N раз повторить соответствующие условия теории опти-

гмального управления. Поэтому авторы больше внимания уде-

ляли геометрическим свойствам такого решения. Впервые,

по-видимому понятие «абсолютно кооперативное» решение было

использовано для дифференциальных игр в работах Бесайла

й Винсента [176, 177]. Ими была рассмотрена дифференциаль-

ная игра:

х = Ах + Ва, I

(u) = c'

x(T), i = l, ..., N,

лричем матрицы Л и В и компоненты n-вектора ci постоянны,

а управляющим воздействием i-ro игрока является i-я компо-

нента вектора и; x£R

, u£R

. Пусть матрица С составлена из

векторов c

, k=l,..., N. Вводится конус G, состоящий из век-

торов типа Са, где компоненты вектора а неотрицательны.

Предполагается, что этот конус лежит по одну сторону от неко-

торой гиперплоскости. Для указанного случая получен ряд

•теорем типа принципа 'максимума в терминах конуса G и ему

сопряженного. Определение абсолютно кооперативного решения

для дифференциальных игр следует из понятия «неулучшаемой

системы», введенной Заде [369] в 1963 г. Впоследствии отсюда

появился термин «оптимальность по Заде», который использо-

ван и в статьях Канинхэм [218, 219]. Далее Геринг и Асанз

посвятили абсолютно кооперативным решениям или «superiori-

ty» цикл статей

{173].

В [234] доказаны необходимые условия существования аб-

солютно кооперативного решения — принцип инфинума (аналог

принципа максимума Л. С. Понтрягина для задач со скаляр-

ным критерием). Причем рассматривается как случай фикси-

рованного правого конца траектории х(Т)=х

\ так и задача со

свободным концом. Кроме того, в [234] выведены и достаточ-

ные условия в терминах векторной функции Беллмана. В каче-

стве приложения доказано, что фильтр Каллмана— Бьюси

•является. решением задачи «superiority», в которой в качестве

конуса неотрицательных элементов- 'берется множество неотри-

цательно определенных матриц. Питер в [314] сформулировал

необходимые и достаточные условия (в терминах функций

Лагранжа), которым удовлетворяет абсолютно кооперативное

решение (в банаховых пространствах).

Интересные результаты, касающиеся «superiority», получе-

ны Винсентом, Лейтмэном [355] и Лэйтмэном, Винсентом и

Токсином [285] и Лантошем

[274].

Пусть в

(10) —

(11) функ-

ции f(t, х, и), (&i{x) непрерывно дифференцируемы и Л =

i-=l,..., N, наборы программных управлений u{t) ограничим

кусочно-непрерывными функциями и u(t)eU некоторому выпук-

лому подмножеству в R

. Введем функции

Ht(t, х, и,

— 'k'.fit, х, и)

•и

.58

Сi

(t) = ^^(t,-v(t),

(t),

(t))

du '

де^(0 —Xj(Q a/(^.*W..-(0) .^(T).= --

"t*"»,x(Q-

решение (10) при a=u

(t). Тогда необходимое условие прини-

мает вид

[3551:

если u

(t)~ абсолютно кооперативное решение

для игры (10) —(И), то для любых достаточно малых

ОЙ

(t) || > 0 и u

(t)

8и

(^)б--

при

•-•

< Т выполнены неравен-

ства ci(zf)6«(^)<0. Достаточное условие сводится [355]

к неравенствам с-(*)8м(*)<0,

г==1,

•••>-

Требование выпук-

лости U можно ослабить до локальной выпуклости или до

-более слабого условия: если и

(ti}$P (t&Vv -Л) замыканию U

и u

(t)~ абсолютно кооперативное решение, то существует

шар В в Д

с центром u

{t^) и радиусом р, такой, что В f]U

выпукло.

Приведенные необходимые условия имеют место и в случае, ес-

ли множество U локально выпукло. Если же множество U не

.обязательно выпукло, u

{i) — абсолютно кооперативное решение

для игры (10)

—

(11) и конус %= 2

i' VuiGR

, ai>0 не со-

держит линейного подпространства, то [285] u

(t) принадле-

жит границе U. Кроме того, тогда существует шар В в ./?"-

•с центром в u

), ^i6[£

> Л- такой, что 2--iC

(^i)8a(<

)<0

для всех ai>0, i=\,

...,N.

Если же конус % содержит

подпространство максимальной размерности 1<^</V, а раз-

мерность £/равна

p~>N~q,

то абсолютно кооперативного

решения не существует

[285].

§ 6. Слабо эффективное решение

В п. 6.1. приведено определение, предложенное В. В. Горо-

ховиком [39]. Необходимым условиям первого и второго по-

рядка посвящен п. 6.2.

6.1.

Определение. Набор управляющих воздействий u

[t]

называется слабо эффективным для игры (10) — (11), если не

существует набора u[t] такого, что Ii(u[-])>Ii(u

[-]),

= 1,,.., р); /,("[•] )-=/jO

[-]) (/-Р + 1,..., N). Функции

выигрыша U, i—l, ..., р, называются показателями предпочте-

ния, а Ij, /=p+l,..., N, — показатели эквивалентности. Слабо

эффективное решение для задач векторной оптимизации введе-

но В. В. Гороховиком [39]. Им же'найдены необходимые усло-

вия первого и второго порядка для таких решений. В [38]

показано, что оптимальное решение в задаче минимизации

«скалярного критерия .качества с ограничениями типа равенств

и неравенств, а также оптимальное решение в задаче миними-

зации скалярного критерия минимаксного типа являются слабо>

эффективными решениями соответствующим образом сформу-

лированных задач векторной оптимизации. Отметим, что в слу-

чае p—N €лабо эффективное решение совпадает с оптимальным

по Слейтеру (§ 7). Оптимальное по Парето решение является

слабо эффективным.

Остановимся теперь на более подробном обсуждении поня-

тия слабой эффективности. Под функцией выигрыша в [38, 39,

40] понимается функционал, заданный на множестве допусти-

мых альтернатив и характеризующий на нем некоторое бинар-

ное отношение. Показатель предпочтения тогда есть функция

выигрыша, характеризующая отношение порядка на множестве

допустимых альтернатив, а показатель эквивалентности

—

функ-

ция выигрыша, характеризующая отношение эквивалентности.

В обычной же постановке задачи векторной оптимизации пред-

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

некоторое конечное число отношений порядка, которые харак-

теризуются только показателями предпочтения

Ii(u),...,

IN (и).

Таким образом, при .использовании понятия слабой эффектив-

ности задача векторной оптимизации рассматривается в более-

общей постановке. Если множество отношений эквивалентности

пусто, то в этом случае понятие слабой эффективности превра-

щается в понятие оптимальности по Слейтеру. Если же оста-

ваться в рамках понятия слабой эффективности, то слабую

эффективность можно рассматривать как обобщение на этот

случай понятия оптимальности по Слейтеру.

6.2. Необходимые условия. Предполагаем, что в (10) функ-

ция / и ее частные производные по х и и до второго порядка

включительно непрерывны по всем аргументам, фиксированы

начальная позиция {t

, хо} и момент T>t

. Скалярное про-

граммное управление u(t), /

{le};/{le}:r, кусочно непрерывно,

u(t)BU

—

открытому множеству (класс скалярных кусочно не-

прерывных функций, определенных тна отрезке [/

, Т] далее

обозначаем £/°), а функция / такова, что каждому управлению

u{t) соответствует единственное решение x(t),

U^t^T,

систе-

мы (10). В (11) функции

Fi =

а Ф,г(#) дважды непрерывно-

дифференцируема. При указанных предположениях приведем

необходимые условия первого и второго порядка для слабой

эффективности u

(t) в игре

(10) —

(11).

Необходимое условие первого порядка [39]: если управление

(t) слабо эффективно для игры

(10) —

(11),

то существует

вектор а-= {сц,..., a

} такой, что

./У

• а

>0(; =

...,-),

2|а.| =

1,'

(

г—1

2«iW

(tt

(-)- б«(-))=0 для всех

6u{t)eW.

(36)

Здесь »•/,(«•(.). »«<•))--$ -••('•--(М'№Т,(0)

Ь[(<)Д| a

-о

H(t, х, и,

№i)

= ¥./(^, х, и), причем х

(£)~решение (10) при

= u

(t)\ функция

ЧГ-

(t)

—

решение системы:

Vtf)'-.

(T) =

d0i{

iT))

(i—1 ЛГ).

Следует отметить, что условие (36) эквивалентно требованию

П|

а//(«,^(О.

.'(О.т,(О)_

<0<<<г>

которое является аналогом условий Эйлера

—

Лагранжа.

Множество всех векторов а, удовлетворяющих (35)—(36)

обозначим через

А(и

Тогда необходимое условие приводится

139] к виду:

если управление и

(t) слабо эффективно для игры (10)

—

11),

то

V d

H(t, х

(t), и

(t),

(t)) ^

, ^ . ^ _

max 2d

ди

г -~->0,

<t<T.

a{in}A(«

)

i--=-l

Это уже условие второго порядка. Если А(и

)= 0, то управ-

ление и

(t) называется экстремалью. Экстремаль является

особой, если max jj

i Г , ——

=0. Приведенные

a(j,4(«

) i=-l

результаты составили и содержание доклада [76] на Всесоюз-

ном симпозиуме по оптимальному управлению и дифференци-

альным играм в 1976 г.

В.

В. Гороховик в [39] получил и необходимые условия

слабой эффективности особых экстремалей. Исследованию за-

дач с особенностями методом кратных максимумов посвящена

статья В. Н. Гурмана и В. А. Дыхта [47].

§ 7. Оптимальность и минимакс по Слейтеру

Необходимые и достаточные условия приведены в п. 7.2,

в п. 7.3 рассматриваются необходимые условия существования

минимакса по Слейтеру.

7.1.

Определение. Набор управляющих воздействий u

[t]

называется оптимальным по Слейтеру для игры (10) —(11),

если не существует -набора управляющих воздействий u[t],

такого, что Li(u[-])>Ii(u

[-]),

г—1,...,

/V.

Согласно определению, оптимальный по Парето набор управ-

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

Слейтеру. В отечественной литературе термин «оптимальность

по Слейтеру» впервые, по-видимому, встречается в статье Гур-

•вица, переведенной на русский язык в

[168].

Решение, не оптимальное по Слейтеру, названо Ю. Б. Гер-

мейером [32] определенно неэффективным. Достаточные усло-

вия оптимальности по Слейтеру получены В. В. Подиновским

[121].

Необходимые и достаточные условия существования

оптимального по Слейтеру решения рассмотрены В. И. Забо-

тиным [67—69]*.

7.2. Необходимые и достаточные условия. Предположим, что»

(10)

—

(11)

функции / и Fi .непрерывны и непрерывно диф-

ференцируемы по х и и, измеримы по t и их частные производ-

ные по х и и ограничены при ограниченных х и и, Ф^--0; набор

программных управлений u(t)GU при почти всех

/б[/

Т];

—

выпуклое тело в R

\ x(to)=x

, х(Т)=х

{Х)

, где х

{1)

—

фиксированы и заданы ограничения вида

q>(x(t),

t)^Q, te[t

Г],

скалярная функция

q>(x,

t) непрерывна по х, t и непрерывно

дифференцируема по х. Необходимые условия формулируются

в следующей теореме.

Теорема [69]. Пусть набор программных управлений

(t)

<z?<7\

оптимален по Слейтеру для игры

(10)

—(11),

a x

(i)>

г-

<^<Г,

—

соответствующее решение (10), x*(T) = xW. Если

аф(

/;^-^0 при <p(je, /)=0 и <р(*

, *о)<0, 90

(1)

> Г)<0„

то существуют абсолютно непрерывная я-вектор-функция ty(t)

и постоянный ./V-вектор а с неотрицательными компонентами,.

причем ty(t) и а не равны одновременно нулю, вектор c£R

и неотрицательная мера d\i(t), сосредоточенная на множестве

& = {te\t

,T]\(p(x

{t)

0},

такие, что

дР

«-

*;f

u4t))

•-}-»+$

acp(

f)l

°-*>(-)•

([

«' ^

*«»

]'t(<)+

«-

»•<•»

u-#w)<0

при почти всех *6[*o» T] и всех

uQ{J.

Достаточные условия получены В. И. Заботиным J69[ в случае-

* Авторы благодарят В. И. Заботина, приславшего подробное изложение

своих и И. A. Корниенко результатов.