Методи побудови інваріантних множин у лінійних різницевих іграх утримання

Описано конструктивні методи побудови мінімальних та максимальних інваріантних множин у дискретному випадку. У диференціальній грі утримання розглянуто задачу знаходження інваріантних множин із застосуванням повного вимітання в новій постановці. Мета гравця-переслідувача — із будьякої точки одержано...

Full description

Saved in:

Bibliographic Details
Date:	2007
Main Authors:	Остапенко, В.В., Терещенко, І.М.
Format:	Article
Language:	Ukrainian
Published:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2007
Subjects:	Методи оптимізації, оптимальне управління і теорія ігор
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/14083
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Методи побудови інваріантних множин у лінійних різницевих іграх утримання / В.В. Остапенко, І.М. Терещенко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 72-84. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-14083
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-140832025-02-23T17:49:12Z Методи побудови інваріантних множин у лінійних різницевих іграх утримання Methods for building in invariant sets in linear differential games of deduction Методы построения инвариантных множеств в линейных разностных играх удержания Остапенко, В.В. Терещенко, І.М. Методи оптимізації, оптимальне управління і теорія ігор Описано конструктивні методи побудови мінімальних та максимальних інваріантних множин у дискретному випадку. У диференціальній грі утримання розглянуто задачу знаходження інваріантних множин із застосуванням повного вимітання в новій постановці. Мета гравця-переслідувача — із будьякої точки одержаної множини утримати в ній траєкторію динамічної системи. Мета гравцявтікача — протилежна. Наведено приклад, на якому показана важливість різних умов повного вимітання, накладених на керування гравців. The constructive methods for building minimal and maximal invariant sets in the discrete case are described. The aim of the chasing player is to keep the trajectory of dynamic system in this set from any point within the acquired set. The aim of the escaping player is contrary. The given example shows the importance of different conditions of «a complete sweeping», superimposing on the players’ control. Описаны конструктивные методы построения минимальных и максимальных инвариантных множеств в дискретном случае. В дифференциальной игре удержания рассмотрена задача нахождения инвариантных множеств с применением полного выметания в новой постановке. Цель догоняющего игрока — из любой точки полученного множества удержать траекторию динамической системы в этом множестве. Цель убегающего игрока — противоположная. Приведен пример, в котором показана важность разных условий полного выметания, которые накладываются на управления игроков. 2007 Article Методи побудови інваріантних множин у лінійних різницевих іграх утримання / В.В. Остапенко, І.М. Терещенко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 72-84. — Бібліогр.: 5 назв. — укр. 1681–6048 https://nasplib.isofts.kiev.ua/handle/123456789/14083 517.977 uk application/pdf Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор
spellingShingle	Методи оптимізації, оптимальне управління і теорія ігор Методи оптимізації, оптимальне управління і теорія ігор Остапенко, В.В. Терещенко, І.М. Методи побудови інваріантних множин у лінійних різницевих іграх утримання
description	Описано конструктивні методи побудови мінімальних та максимальних інваріантних множин у дискретному випадку. У диференціальній грі утримання розглянуто задачу знаходження інваріантних множин із застосуванням повного вимітання в новій постановці. Мета гравця-переслідувача — із будьякої точки одержаної множини утримати в ній траєкторію динамічної системи. Мета гравцявтікача — протилежна. Наведено приклад, на якому показана важливість різних умов повного вимітання, накладених на керування гравців.
format	Article
author	Остапенко, В.В. Терещенко, І.М.
author_facet	Остапенко, В.В. Терещенко, І.М.
author_sort	Остапенко, В.В.
title	Методи побудови інваріантних множин у лінійних різницевих іграх утримання
title_short	Методи побудови інваріантних множин у лінійних різницевих іграх утримання
title_full	Методи побудови інваріантних множин у лінійних різницевих іграх утримання
title_fullStr	Методи побудови інваріантних множин у лінійних різницевих іграх утримання
title_full_unstemmed	Методи побудови інваріантних множин у лінійних різницевих іграх утримання
title_sort	методи побудови інваріантних множин у лінійних різницевих іграх утримання
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2007
topic_facet	Методи оптимізації, оптимальне управління і теорія ігор
url	https://nasplib.isofts.kiev.ua/handle/123456789/14083
citation_txt	Методи побудови інваріантних множин у лінійних різницевих іграх утримання / В.В. Остапенко, І.М. Терещенко // Систем. дослідж. та інформ. технології. — 2007. — № 4. — С. 72-84. — Бібліогр.: 5 назв. — укр.
work_keys_str_mv	AT ostapenkovv metodipobudoviínvaríantnihmnožinulíníjnihríznicevihígrahutrimannâ AT tereŝenkoím metodipobudoviínvaríantnihmnožinulíníjnihríznicevihígrahutrimannâ AT ostapenkovv methodsforbuildingininvariantsetsinlineardifferentialgamesofdeduction AT tereŝenkoím methodsforbuildingininvariantsetsinlineardifferentialgamesofdeduction AT ostapenkovv metodypostroeniâinvariantnyhmnožestvvlinejnyhraznostnyhigrahuderžaniâ AT tereŝenkoím metodypostroeniâinvariantnyhmnožestvvlinejnyhraznostnyhigrahuderžaniâ
first_indexed	2025-11-24T04:34:28Z
last_indexed	2025-11-24T04:34:28Z
_version_	1849644934278152192
fulltext	 В.В. Остапенко, І.М. Терещенко, 2007 72 ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 TIДC МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР УДК 517.977 МЕТОДИ ПОБУДОВИ ІНВАРІАНТНИХ МНОЖИН У ЛІНІЙНИХ РІЗНИЦЕВИХ ІГРАХ УТРИМАННЯ В.В. ОСТАПЕНКО, І.М. ТЕРЕЩЕНКО Описано конструктивні методи побудови мінімальних та максимальних інва- ріантних множин у дискретному випадку. У диференціальній грі утримання розглянуто задачу знаходження інваріантних множин із застосуванням повно- го вимітання в новій постановці. Мета гравця-переслідувача — із будь-якої точки одержаної множини утримати в ній траєкторію динамічної системи. Мета гравця-втікача — протилежна. Наведено приклад, на якому показана важливість різних умов повного вимітання, накладених на керування гравців. ВСТУП У роботах [1, 2] розглядалися лінійні різницеві системи з перешкодою. Було введено поняття інваріантної множини, тобто такої, починаючи з кожної точки якої траєкторія залишається у цій множині. У роботах [3, 4] досліджується ігрова постановка цієї задачі, де беруть участь гравець-переслідувач та гравець-утікач, що керує перешкодою. У цій статті узагальнено результати робіт [3, 4] та проведено порів- няльний аналіз розроблених методів. ПОСТАНОВКА ЗАДАЧІ Розглянемо гру з динамікою kkkk vuAxx +−=+1 , 0≥k , (1) де A — матриця розмірності nn × ; Uuk ∈ , Vvk ∈ , U , V — опуклі компа- кти. Параметрами ku та kv розпоряджаються гравці P (переслідувач) і E (утікач) відповідно. Причому гравець P на k -му кроці вибирає ku , знаючи kx і kv , тобто ( )kkkk vxuu ,= , а гравець E вибирає kv , знаючи kx , тобто ( )kkk xvv = . Мета гравця P — утримати траєкторію kx , 1≥k , рівняння (1) на множині M . Причому початкова позиція Mx ∈0 . Мета гравця E — протилежна. Множина M припускається опуклою та компактною. Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 73 Означення 1. Множину nEM ⊂ будемо називаюти інваріантною множиною рівняння (1), якщо для будь-якої точки Mx ∈0 та будь-яких ке- рувань Vvk ∈ існують керування ( )kkkk vxuu ,= такі, що Mxk ∈ , 1≥k . Отже, знаходження інваріантної множини можна вважати розв’язком поставленої задачі. КРИТЕРІЙ ІНВАРІАНТНОСТІ Перепишемо рівняння (1) у вигляді kkkk vAxux +=++1 , 0≥k . (2) З (2) випливає: умова інваріантності означає, що для будь-яких Mxk ∈ і Vvk ∈ існують Mxk ∈+1 і Uuk ∈ такі, що kkkk vAxux +=++1 , 0≥k . Таким чином, інваріантність M еквівалентна включенню VAMUM +⊃+ . (3) Нижче шукані інваріантні множини будуть описані у вигляді деяких нескінченних рядів. Опишемо їх. Нехай n k EN ⊂ , 0≥k , послідовність компактних множин. Під N будемо розуміти множину ∑ ∞ = =++++= 0 10 k kk NNNNN  , (4) яка є об’єднанням рядів ∑ ∞ = = 0k kxx , (5) де kk Nx ∈ , Nx∈ . Припустимо, що ряди виду (5) збігаються і множина N цих рядів обмежена. Користуючись теоремою Тіхонова [5], можна показати, що з компактності kN випливає компактність N . Відмітимо також: якщо kN — опуклі множини, то N — опукла. Як ряд (4) розглянемо  +++++= KAKAAKKN k2 , (6) де nEK ⊂ — компактна множина; A — nn × -матриця, яку розглянуто у рівнянні (1). Припустимо, що для будь-якого власного числа λ матриці A викону- ється 1<≤ qλ , де q — фіксоване число. Відомо, що в цьому випадку існує константа 0≥C така, що kk CqA ≤ . Оскільки K — обмежена, то існує константа 0>R така, що Rxk ≤ для будь-якого Kxk ∈ . Кожний елемент В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 74 Nx∈ можна представити у вигляді ряду ∑ ∞ = = 0k k k xAx , де Kxk ∈ . Оскільки k k k k k CRqxAxA ≤≤ , то CR q x − ≤ 1 1 . Тому множина N із (6) компак- тна. Означення 2. Нехай BA, — непорожні множини з nR . Під геомет- ричною різницею множин A і B розуміють множину { +∈=− aAaBA :* }AB ⊂+ . Означення 3. Множина B повністю вимітає множину A , якщо вико- нується рівність ( ) ABBA =+* . ПОБУДОВА МІНІМАЛЬНОЇ ІНВАРІАНТНОЇ МНОЖИНИ Припустимо, що матриця A задовольняє наведеним вище умовам. Теорема 1. Нехай множина U повністю вимітає множину V . Тоді сис- тема (1) має мінімальну інваріантну множину ( )∑ ∞ = = 0 * min k k UVAM . (7) Доведення. Нехай M — довільна інваріантна множина рівняння (1). Покажемо, що включення (3) еквівалентне включенню ( )UVAMM +⊃ . (8) Від обох частин включення (3) віднімемо геометрично множину U . Тоді ( ) ( ) ( )( ) ( )UVAMUUUVAMUVAMUUMM **** +=++⊃+⊃+= . Отже, одержуємо (8). Нехай тепер виконується (8). Тоді з умови повно- го вимітання одержуємо ( ) VAMUUVAMUM +=++⊃+ * , тобто отримуємо включення (3). З (8) маємо ( ) ( ) ( ) ⊃++⊃+⊃ UVUVAMAUVAMM *2 ( ) ( )UVUVAMA kk *1 +++⊃ −  . Оскільки множина M обмежена, то послідовність множин MAk пря- мує до нуля у метриці Хаусдорфа. Звідси та із замкненості M отримуємо ( ) MUVAM k k ⊂= ∑ ∞ =0 min . Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 75 Покажемо, що minM інваріантна множина. Для цього перевіримо включення (8), яке еквівалентне (3). Дійсно, ( ) ( ) ( ) ( ) min 0 * 0 *** min MUVAUVAAUVUVAM k k k k ==+=+ ∑∑ ∞ = ∞ = . Теорему доведено. Одержимо інше, ніж у формулі (7), представлення множини minM . Теорема 2. Нехай множина U повністю вимітає множину * 0         ∑ ∞ =k kVA         ∑ ∞ =1 * k kUA . Тоді система (1) має мінімальну інваріантну множину                 = ∑∑ ∞ = ∞ = 0 * 0 min k k k k UAVAM . Доведення. Нехай M — довільна інваріантна множина рівняння (1). Скористаємося формулою (3). Домножимо обидві частини включення на A та додамо V . Звідси ( ) ( ) VUAMAVVAMA ++⊂++ , AUUMUVAMVAUAMVAMMA ++⊂++=++⊂++2 . Застосувавши ( )1+k раз формулу (3), одержимо UAUMVVAMA kkk +++⊂++++ 1 . Оскільки множина M обмежена, то MAk 1+ прямує до нуля у метриці Хаусдорфа. Тоді отримуємо ∑ ∑ ∞ = ∞ = +⊂ 0 0k k kk UAMVA . Звідси MUAVAM k k k k ⊂                = ∑∑ ∞ = ∞ = 0 * 0 min . Покажемо тепер інваріантність minM . Перевіримо виконання включен- ня (3). Маємо VUAVAVUAVAAVAM k k k k k k k k +                =+                        =+ ∑∑∑∑ ∞ = ∞ = ∞ = ∞ = 1 * 10 * 0 min . Враховуючи той факт, що ( ) MNNM ⊂+* , де M , N — опуклі підм- ножини в nE (із геометричних властивостей), отримуємо ∑∑∑∑ ∞ = ∞ = ∞ = ∞ = ⊂+                111 * 1 k k k k k k k k VAUAUAVA . В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 76 Отже, для нашого випадку маємо ∑∑∑∑∑ ∞ = ∞ = ∞ = ∞ = ∞ = =+⊂++                0111 * 1 k k k k k k k k k k VAVVAVUAUAVA . Віднімемо геометрично від обох частин включення ∑ ∞ =1k kUA .                 ⊂         +        +                ∑∑∑∑∑∑ ∞ = ∞ = ∞ = ∞ = ∞ = ∞ = 1 * 01 * 11 * 1 k k k k k k k k k k k k UAVAUAUAVUAVA ,                 ⊂+                ∑∑∑∑ ∞ = ∞ = ∞ = ∞ = 1 * 01 * 1 k k k k k k k k UAVAVUAVA . Враховуючи умову теореми, що множина U повністю вимітає множи- ну                 ∑∑ ∞ = ∞ = 1 * 0 k k k k UAVA , одержуємо =+                         =                ∑∑∑∑ ∞ = ∞ = ∞ = ∞ = UUUAVAUAVA k k k k k k k k * 1 * 01 * 0 UMUUAVA k k k k +=+                = ∑∑ ∞ = ∞ = min 0 * 0 . Теорему доведено. Узагальнимо результат теореми 1. Нехай minM — мінімальна інварі- антна множина рівняння (1) та множина U повністю вимітає множину V . Використовуючи ту властивість геометричної різниці, що ( ) MNNM =+ * , де M , N — опуклі підмножини в nE , отримуємо ( ) ( ) ( )∑∑∑ ∞ +== ∞ = =+== 1 * 0 * 0 * min nk k n k k k k UVAUVAUVAM ( ) ( ) =        ++= ∑∑ ∑∑ ∞ += ∞ += ∞ +== 1 * 1 1 * 0 * nk k nk nk kk n k k UAUAUVAUVA ( ) =                += ∑∑∑ ∞ += ∞ +== 1 * 10 * nk k nk k n k k UAVAUVA ( ) ( )=+        += ∑∑∑ ∑ ∞ +=== = 1 * 0 * 0 0 * nk k n k k n k n k kk UVAUAUAUVA ( )=+                = ∑∑∑ ∞ +=== 1 * 0 * 0 nk k n k k n k k UVAUAVA Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 77 ( ) min 0 * 00 * 0 0 * MUAVAUAUAUVA k k k k k k k k kk =                =        += ∑∑∑∑ ∑ ∞ = ∞ = ∞ = ∞ = ∞ = . Отже, довели такий результат. Наслідок 1. Нехай множина U повністю вимітає множину V . Тоді си- стема (1) має мінімальну інваріантну множину, яка може бути виражена од- нією з еквівалентних формул: а) ( )∑ ∞ = = 0 * min k k UVAM ; б)                 = ∑∑ ∞ = ∞ = 0 * 0 min k k k k UAVAM ; в) ( )                 += ∑∑∑ ∞ += ∞ +== 1 * 10 * min nk k nk k n k k UAVAUVAM ; г) ( )∑∑∑ ∞ +=== +                = 1 * 0 * 0 min nk k n k k n k k UVAUAVAM . ПОБУДОВА МАКСИМАЛЬНОЇ ІНВАРІАНТНОЇ МНОЖИНИ Змінимо обмеження на матрицю A та опишемо в цьому випадку макси- мальну інваріантну множину. Вважаємо, що матриця A невироджена і існує таке 1>p , що для будь-якого власного числа λ матриці A викону- ється p≥λ . Теорема 3. Нехай множина V повністю вимітає множину U . Тоді сис- тема (1) має максимальну інваріантну множину ( )∑ ∞ = −= 1 * max k k VUAM . Доведення. Нехай M — довільна інваріантна множина рівняння (1). Так само, як і у теоремі 1, можна показати, що включення (3) еквівалентне включенню ( ) AMVUM ⊃+ * або ( ) MVUAMA ⊃+ −− 11 . (9) Із (9) випливає, що ( ) ( ) ( )⊂++⊂+⊂ −−−−− VUAVUAMAVUAMAM 21211 ( ) ( )VUAVUAMA kk *1 −−− +++⊂  . Оскільки M — обмежена, то MA k− прямує до нуля у метриці Хаус- дорфа і, отже, В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 78 ( )∑ ∞ = −=⊂ 1 max k k VUAMM . Покажемо тепер інваріантність maxM , використовуючи формулу (9). Отримуємо ( ) ( ) ( ) max 1 2 1 max 1 MVUAVUAVUAMA k k =+=+ − ∞ = −−− ∑ , що й доводить теорему. Одержимо інше представлення множини maxM . Теорема 4. Нехай виконується співвідношення UAVAUAVAUA k k k k k k k k 1 2 22 * 1 − ∞ = − ∞ = − ∞ = − ∞ = − +                =                ∑∑∑∑ . Тоді система (1) має максимальну інваріантну множину                 = ∑∑ ∞ = − ∞ = − 1 * 1 max k k k k VAUAM . Доведення. Нехай M — довільна інваріантна множина рівняння (1). Перепишемо включення (3) у вигляді UAMAVAM 111 −−− +⊂+ . (10) Домножимо обидві частини включення на 1−A та додамо UA 1− . Звідси ( ) ( ) UAUAMAAUAVAMA 1111111 −−−−−−− ++⊂++ , UAUAMAVAUAMA 122211 −−−−−− ++⊂++ . З іншого боку, UAUAMAVAUAMAVAVAM 21221121 −−−−−−−− ++⊂++⊂++ . Застосувавши формулу (10) k раз, одержимо UAUAMAVAVAM kkk )1(1)1()1(1 +−−+−+−− +++⊂+++  . Оскільки множина M обмежена, то MA k )1( +− прямує до нуля у мет- риці Хаусдорфа. Звідси отримуємо ∑∑ ∞ = − ∞ = − ⊂+ 11 k k k k UAVAM . Тоді                 =⊂ ∑∑ ∞ = − ∞ = − 1 * 1 max k k k k VAUAMM . Тепер покажемо інваріантність множини maxM . Перевіримо включення (10). Застосувавши цей вираз, маємо Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 79 VAVAUAVAM k k k k 1 1 * 1 1 − ∞ = − ∞ = −− +                =+ ∑∑ . Використовуючи властивість геометричної різниці ( ) MNNM ⊂+* , де M , N — опуклі підмножини в nE , отримуємо ∑∑∑∑ ∞ = − ∞ = − ∞ = − ∞ = − ⊂+                111 * 1 k k k k k k k k UAVAVAUA . Отже, для нашого випадку маємо ∑∑∑∑ ∞ = − ∞ = −− ∞ = − ∞ = − ⊂++                12 1 1 * 1 k k k k k k k k UAVAVAVAUA . Віднімемо геометрично від обох частин включення ∑ ∞ = − 2 1 k VA . Звідси отримуємо такий результат: ⊂         +        +                ∑∑∑∑ ∞ = − ∞ = −− ∞ = − ∞ = − 2 * 2 1 1 * 1 k k k k k k k k VAVAVAVAUA                 ⊂ ∑∑ ∞ = − ∞ = − 2 * 1 k k k k VAUA . Враховуючи умову теореми про співвідношення, одержуємо =                ⊂+                ∑∑∑∑ ∞ = − ∞ = −− ∞ = − ∞ = − 2 * 1 1 1 * 1 k k k k k k k k VAUAVAVAUA =+                         =+                = − ∞ = − ∞ = −−− ∞ = − ∞ = − ∑∑∑∑ UAVAUAAUAVAUA k k k k k k k k 1 1 * 1 11 2 * 2 UAMA 1 max 1 −− += . Теорему доведено. Узагальнимо результати теореми 3. Припустимо, що maxM — мак- симальна інваріантна множина рівняння (1) та множина V повністю ви- мітає множину U . Використавши властивість геометричної різниці ( ) MNNM =+ * , де M , N — опуклі підмножини в nE , отримуємо ( ) ( ) ( )=+== ∑∑∑ ∞ += − = − ∞ = − 1 * 1 * 1 * max nk k n k k k k VUAVUAVUAM ( ) ( ) =        ++= ∑∑ ∑∑ ∞ += − ∞ += ∞ += −− = − 1 * 1 1 * 1 * nk k nk nk kk n k k VAVAVUAVUA ( ) =                += ∑∑∑ ∞ += − ∞ += − = − 1 * 11 * nk k nk k n k k VAUAVUA В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 80 ( ) ( )=+        += ∑∑∑ ∑ ∞ += − = − = = −− 1 * 1 * 1 1 * nk k n k k n k n k kk VUAVAVAVUA ( )=+                = ∑∑∑ ∞ += − = − = − 1 * 1 * 1 nk k n k k n k k VUAVAUA ( ) max 1 * 11 * 1 1 * MVAUAVAVAVUA k k k k k k k k kk =                =        += ∑∑∑∑ ∑ ∞ = − ∞ = − ∞ = − ∞ = ∞ = −− . Отже, доведено такий результат. Наслідок 2. Нехай множина V повністю вимітає множину U . Тоді си- стема (1) має максимальну інваріантну множину, яка може бути виражена однією з еквівалентних формул: а) ( )∑ ∞ = −= 1 * max k k VUAM ; б)                 = ∑∑ ∞ = − ∞ = − 1 * 1 max k k k k VAUAM ; в) ( )                 += ∑∑∑ ∞ += − ∞ += − = − 1 * 11 * max nk k nk k n k k VAUAVUAM ; г) ( )∑∑∑ ∞ += − = − = − +                = 1 * 1 * 1 max nk k n k k n k k VUAVAUAM . Приклад. У теоремах 1 та 2 за різних умов вимітання будуються різні мінімальні інваріантні множини. Причому в загальному випадку множина із теореми 2 ширше за множину із теореми 1. Тому, якщо виконується умова теореми 1, то мінімальна інваріантна множина визначається за формулою (7), і нема необхідності застосовувати теорему 2. Побудуємо приклад, де взято такі множини (рис. 1 та 2), що не викону- ється умова теореми 1, проте справедлива теорема 2. x2 1 x1 1 –1 –1 Рис. 1. Множина P x2 1 x1 1 –1 –1 Рис. 2. Множина Q Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 81 Позначимо ( ){ }2 ,1 ,1 :, 21 =≤== ixxxxP i , ( ){ }1 :, 2121 ≤+== xxxxxQ . Покладемо             − = 2 1 2 1 2 1 2 1 A . Тоді       − =− 1 1 111A . Множина P є квадратом, Q — «ромбом», який є зменшеним квадра- том P , що повернули на 4 π . Матриця A є матрицею повороту на 4 π , що зменшує довжину вектора в 2 рази. Далі ( ){ }=∈== − PxAxxxAP 1 21 : , ( ){ }=≤+≤−== 1 ,1 : , 212121 xxxxxxx ( ){ } Qxxxxx =≤+== 1 : , 2121 . Аналогічно знаходимо ( ){ }=∈== − QxAxxxAQ 1 21 : , ( ){ }=≤++−== 1 : , 212121 xxxxxxx ( ) Pixxxx i 2 12 ,1 , 2 1 : , 21 =       =≤== . Розглянемо гру з матрицею A та множинами PV = , QU = . Очевидно, що { }0** == QPUV , проте U не вимітає повністю V . Отже, умова теоре- ми 1 не виконується. Дослідимо умову теореми 2. Із зроблених позначень випливає ∑ ∞ = =++++= 0 32 k k VAVAAVVVA   ++++++++= QPQPQPQP kk 2 1 2 1 4 1 4 1 2 1 2 1 . Множини P та Q — компактні, ряди чисел, що стоять у якості коефі- цієнтів перед множинами P та Q , збігаються абсолютно. Знайдемо, чому дорівнює ∑ ∞ =0k kVA . { } +       =≤=+=≤==∑ ∞ = 2 ,1 , 2 1 :),( 2 ,1 ,1 :),( 2 1 2121 0 ixxxxixxxxP ii k k В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 82 Pixxxx ki 22 ,1 , 2 1 :),( 21 =+       =≤=+  , { } +       ≤+=+≤+==∑ ∞ = 2 1 :),( 1 :),( 2 1 21212121 0 xxxxxxxxxxQ k k Qxxxxx k 2 2 1 :),( 2121 =+       ≤+=+  , ( )QPQPVA k k k k k k +=+= ∑∑∑ ∞ = ∞ = ∞ = 2 2 1 2 1 000 . Покажемо процес побудови множини PAk (рис. 3). Аналогічно обчислимо ∑ ∞ =1k kUA . ∑ ∞ = ++++=+++= 1 32 4 1 4 1 2 1 2 1 k k QPQPUAUAAUUA +       =≤==+++ 2 ,1 , 2 1 :),( 2 1 2 1 21 ixxxxQP ikk   +       ≤=++       =≤=+ kii xxxxixxxx 2 1 :),( 2 ,1 , 4 1 :),( 2121  +       ≤+=+       ≤+=+ 4 1 :),( 2 1 :),( 21212121 xxxxxxxxxx Рис. 3. Множина AkP x2 1 x1 1 –1 –1 A3P A2P AP P Методи побудови інваріантних множин у лінійних різницевих іграх утримання Системні дослідження та інформаційні технології, 2007, № 4 83 { }+=≤==+       ≤+=+ 2 ,1 ,1 :),( 2 1 :),( 212121 ixxxxxxxxx ik  { } QPxxxxx +=≤+=+ 1 :),( 2121 . Звідси ( ) ( ) QPQPQPUAVA k k k k +=++=                ∑∑ ∞ = ∞ = * 1 * 0 2 . Таким чином отримуємо ( )( ) QPQQQP +=++ * , тобто множина                 ∑∑ ∞ = ∞ = 1 * 0 k k k k UAVA повністю вимітається множиною QU = . Отже, умова теореми 2 виконується і у випадку ( ) VPQQPUAVAM k k k k ==+=                = ∑∑ ∞ = ∞ = * 0 * 0 min . Далі розглянемо, як будується множина QP + (рис. 4). Звернемо увагу на те, що у розглянутому випадку формула (7) дала б множину, яка складалася б із одного нуля, що є невірним ( PM =min ). Це говорить про важливість умов вимітання, які використовуються в теоремах 1 та 2. Рис. 4. Множина QP + x2 2 x1 2 –2 –2 P Q P+Q –1 1 1 1 В.В. Остапенко, І.М. Терещенко ISSN 1681–6048 System Research & Information Technologies, 2007, № 4 84 ВИСНОВКИ Запропоновано два різних підходи до побудови інваріантних множин у лі- нійних різницевих іграх утримання. У залежності від власних чисел матриці A , що описує динаміку систе- ми, побудовано мінімальну або максимальну інваріантну множину. Наведено приклад відмінності різних підходів до побудови інваріант- них множин. Подальші дослідження можуть бути спрямовані на розгляд даних задач при невиконанні умови повного вимітання. ЛІТЕРАТУРА 1. Кунцевич В.М., Пшеничный Б.М. Минимальные инвариантные множества динамических систем с аддитивными ограниченными возмущениями // Кибернетика и системный анализ. — 1996. — №1. — С. 74–81. 2. Кунцевич В.М. Управление в условиях неопределенности: гарантированные ре- зультаты в задачах управления и идентификации. — Киев: Наук. думка, 2006. — 264 с. 3. Остапенко В.В., Амиргалиева С.Н., Остапенко Е.В. Выпуклый анализ и диф- ференциальные игры. — Алматы: Fылым, 2005. — 392 с. 4. Амиргалиева С.Н., Остапенко В.В., Терещенко И.Н. Инвариантные множества в дискретной игре удержания // Кибернетика и системный анализ. — 2005. — №2. — С. 150–154. 5. Келли Дж.Л. Общая топология. — М.: Наука, 1981. — 431 с. Надійшла 20.06.2006 МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ УПРАВЛІННЯ І ТЕОРІЯ ІГОР Методи побудови інваріантних множин У лінійних різницевих іграх утримання В.В. Остапенко, І.М. Терещенко ВСТУП Постановка задачі Критерій інваріантності Побудова мінімальної інваріантної множини Побудова максимальної інваріантної множини ВИСНОВКИ Рис. 1. Множина Рис. 2. Множина Рис. 3. Множина AkP Рис. 4. Множина

Методи побудови інваріантних множин у лінійних різницевих іграх утримання

Institution

Similar Items