Разностный метод в конфликтно управляемых системах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи УДК 518.9

ТРОЕВА Марианна Степановна РАЗНОСТНЫЙ МЕТОД В КОНФЛИКТНО УПРАВЛЯЕМЫХ СИСТЕМАХ

01.01.09 - математическая кибернетика

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

Санкт-Петербург 1994

Работа выполнена на кафедре математической статистики, теории надежности и массового обслуживания Санкт-Петербургского государственного университета.

Научный руководитель: доктор физико-математических наук, профессор О.А.МАЛАФЕЕВ.

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

доктор физико-математических наук, профессор В.Ф.ДЕМЬЯНОВ,

кандидат физико-математических наук, доцент Г.Г.ТКАЧЕНКО.

Ведущая организация: НИИ информатики и автоматизации Российской Академии Наук (С.-Петербург).

К-063.57.16 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 190004, Санкт-Петербург, В.О., 10 линия, д. 33, аудитория 88.

С диссертацией можно ознакомиться в научной библиотеке имени А.М.Горького Санкт-Петербургского государственного университета (Университетская наб.,.7/9).

Защита диссертации

1994 г.

на заседании специализированного совета

Автореферат разослан Ученый секретарь

специализированного совета

д.ф.-м.н.

В.Ф.Горьковой

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Предметом исследования теории дифференциальных игр является математические модели конфликтно управляемых динамических процессов. Целый ряд практически важных реальных процессов, возникавших в природе и во многих областях человеческой деятельности, могут быть смоделированы дифференциальными играми. В настоящее время наиболее полно исследованы антагонистические дифференциальные игры с полной информацией. Фундаментальные результаты в этой области связаны с работами научных вкол Л.С.Понтрягияа и Н.Н.Красовского, а также с работами Санкт-Петербургских и Киевских математиков.

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

Основной цель» работы является разработка численного метода для приближенного ревения дифференциальных антагонистических игр с предписанной продолжительностью, с непрерывной терминальной функцией выигрыша, основанного на конечно-разностном методе ревения уравнения Гаиильтона-Якоби (Беллмана-Ай-зекса), соответствувяего этой игре; разработка конечно-разностного метода для приближенного ревения дифференциальной антагонистической игры, динамика которой описывается краевой задачей для уравнения теплопроводности, характеризующей некоторые

динамические процессы теплообмена; создание комплекта программ дда реализации построенных методов на ЭВМ.

Научная новизна. В диссертации вводится новое понятие слабого реаения уравнения Гамильтона-Якоби (Беллмана-Лйзекса) для дифференциальной антагонистической игры с предписанной продолжительность« и непрерывной терминальной функцией выигрыша; доказывается существование и единственность слабого реаения и совпадение его с функцией значения игры; построен конечно- разностный метод для приближенного реаения таких игр; разработан конечно-разностный метод для реаения задачи нахождения оптимального технологического режима управления динамическим процессом теплообмена, моделируемой дифференциальной антагонистической игрой, динамика которой описывается краевой задачей для уравнения теплопроводности; доказывается теорема о гладкой устойчивости ситуаций равновесия в матричных играх, полученные результаты применяется для построения численных методов ревения дифференциальных антагонистических игр; составлен комплехт программ для реализации построенных методов ка ЗВЦ; реаены конкретные примеры дифференциальных актагонистичеких игр.

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

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

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

Апробация работы. Результаты диссертации докладывались на Ш Школе "Математические проблемы экологии" (г. Чита,.1990 г.), на Ш Всесоюзной яколе "Понтрягинсхие чтения. Оптимальное управление. Геометрия и анализ" (г. Кемерово, 1898 г.), на 10 Якутской республиканской научно-практической конференции молодых ученых и специалистов, на научных семинарах факультета прикладной математики-процессов управления Санкт-Петербургского госуниверситета.

Публикации. Основные результаты диссертации опубликованы в работах /1-7/.

Структура и обьем работы. Диссертация состоит из введения, трех глав и списка литературы. Объем составляет 100 страниц мавинописного текста. Библиография содержит 92 названий.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении обоснована актуальность темы диссертационной работы, сформулирована ее цель, приводится краткий обзор основных направлений развития теории дифференциальных антагонистических игр, а такхе краткое содерхание работы.

Глава 1. Слабое решение уравнения Гамильтона-Якоби

для дифференциальной антагонистической игры В данной главе приводится формализация дифференциальной антагонистической игры, строится разностная схема для уравнения Гамильтона-Якоби, вводится понятие слабого реаения для этого уравнения, доказывается его существование, единствен-

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

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

Динамика игры Г(хо,т) описывается системой дифференциальных уравнений

х ' f(x,u,v), х(0) - хо, (!)

где х е ¡Г, te to, т] ; uî«cîp, v е v с r4 - управлявши параметры игроков р и б соответственно; v к v - компактные множества в евклидовых пространствах if к кя соответственно. Вектор-функция £ в правой части (1) непрерывна на rf" х и * V, удовлетворяет условии Липшица по х с постоянной Kf, удовлетворяет неравенству \ftx,u,v)i < в. Кроме того, предполагается, что множество {£(x,u,v)\ u е V, v е. V} выпукло.

Допустишм управлением игрока Р (б) называется измеримая на отрезке to,г] вектор-функция и - и<t) (v * v(t)), удовлетворяющая условиям uft; с u (vit) e v) при любых t e to,x). Система дифференциальных уравнений (t) при любой паре допустимых управлений uit) и vit) и любом начальном условии *о имеет единственное решение, продолжимое на отрезок времени (о.г].

Состояние информации в игре следующее. В каждый момент времени t игрокам рис известна позиция игры x(t), момент t-o - начала и Т - окончания игры и динамика игры. В момент окончания игры игрок £ (максимизирующий) получает от игрока р (минимизирующего) выигрыш равный н(х(Т)), где х 1т) - конечная позиция игры. Функция н : R4 r' равномерно непрерывна, ограничена и удовлетворяет условию Липница,

Пол стратегией игрока Р (£) поьимается пара » - ia,-Ka 1

t

(9 = (з ,к J), где б (о ) - произвольное конечное разбиение

а

интервала [о,г], к (к ) - отображение, ставяяее в соответс-

i а

твие состоянию информации игрока Р (в) в момент вренени t(6 о( (t е вг) допустимое управление ut(r), г е tt(, tt ^ т i ( v^fr;, г б \tJttJt,».

Функция выигрыяа игрока в в кахдой ситуации Сф,фJ е Ф х 5 определяется следующим образом

K(xo,if,v) . H(x(i,v) (Т)), где x(i(,ip)(t) - траектория, соответствующая ситуации l<t,f) е €ФхФ;ФиФ- множества стратегий игроков р и е.

Таким сбразом, определив множества стратегий игроков f и е и функцию выигцла, мы определили дифференциальную антагонистическую игру s нормальной форме.

Для этой игры строятся две вспомогательные игры с дискриминацией: верхняя Г(х ,т) и нижняя Г (х , т). Известно, что в

о — о

этих играх судествуют ситуации (¡-равновесия.'•* Далее эти две игры аппроксимируются последовательностями многоиаговых игр

_1Г (Г

Г " (х ,т) и Г " (х ,т> с полной информацией, в каждой из ко-

о — о

торых существует значение и седловые точки.

Во втором параграфе строится равномерная сетка в пространстве позиций игры и на отрезке [о,г]:

о , - о х о.. hS h s

Рассматривается задача Коии для уравнения Гамильгона-Яко-

1

Малафеев O.A. Ситуации равновесия в динамических играх// Кибернетика. -1974. № 3. -С. 111-118.

г

Петросян Л.А. Дифференциальные игры преследования. - -П.: Изд-во Ленингр. ун-та, 1977. -224 с.

Си для верхней игпы Г(хо,Т) относительно функции значения VI-) ТГ - «Й» ф [4Ё( <*. и. »>]. (2)

Ъх,Ч\Хт0 - Н1х(Т)>. (3)

Задаче (2)-(3) ставится в соответствие следующая разност-

ная схема на сетке и

-п- I

V

+ Й т!п щах

■С (X1 ,и,у) +..

_л- > - v.

(х'.и.у)

1 - 1,т , ' п - ТТлГ ,

(4)

V. . - Н, . , ;/ € г, :( . 1,т. (5)

* 1.....•'т ■>1.....

Доказывается устойчивость и сходимость построенной схемы, липаицевость сеточных функций - решений разностной схемы (4)--(5). Кроме того, доказывается ограниченность и липвицевость

—о- —с

функции значения v (х , Т) игры Г (х ,т). Эти результаты сфор-

о о

мулировакы в виде лемм.

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

У на все пространство х.

Вводится понятие слабого реаения уравнения Гамильтона--Якоби.

Определение ¡.Слабым решением уравнения Гамильтона-Якоби

(Беллмана-Айзекса) для дифференциальной антагонистической игры Г(хо,т) назовем непрерывное продолхение на все пространство я" предела последовательности ревений разностной схемы.

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

Теорема 1. Пусть / - (lt,- функция, удовлетворяи-яая условиям параграфа 1. Для функции выигрыаа я, удовлетворя-

-JT _1Г

ваей условия Липвица, пусть v 1*0.Т) •> val (Г (хо,т)) - непрерывная функция значения игры Г (хо,Т) с началом в точке хп и продолжительностью г < » , такхе удовлетворяющая условию Липвица в силу леммы 3.

_п _

Пусть V , J е Z, 1 - 1,и - ревение разностной

Jt----/Jm

задачи (4)-(5) на сетке олв. Тогда существует единственное слабое ревение уравнения Гамильтона-Якоби для дифференциальной антагонистической игры Г(хо,Т).

Кроме того, имеет место следующая оценка:

\V (х ,Г - t ) - v" , I < х|0|

1 i " , П Jл » ■ • • » J

1 ж * '

при достаточно малом б на сетке .

Такхе справедлива следующая теорема.

Теорема 2. Если V(') и v(-) - функции значения Г(хо,Т) -верхней и - нижней игр соответственно, и если V(-) =

V(-) mV('), то V(xo,T) я'вляется слабым ревением уравнения Гамильтона-Якоби (Беллмана-Айзекса) для дифференциальной антагонистической игры Г(хо,Т).

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

Глава 2. Гладкая устойчивость ситуаций равновесия в смешанных стратегиях для матричных игр.

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

В параграфе 1 приводятся некоторые вспомогательные сведения иэ дифференциальной топологии и алгебраической геометрии, в частности, параметрическая теорема трансверсальности.

Во втором параграфе рассматривается множество V - V. „ смешанных расширений матричных игр

Гж - < Х,У,Н >,

где х - стандартный замкнутый (т-и-мерный симплекс; г -стандартные замкнутый Гл-.П-меркыЯ симплекс (пространства смешанных стратегий игроков 1 и 2 соответственно).

Функция выигрыша игрока 1 определяется следувшим образом:

т п

Н<х,у) - I £ X V а . хАу,

1-» J•>

где - элементы матрицы а размерности ш х л, задавшей исходную игру; ш и п - числа чистых стратегий I и 2 игроков соответственно. Функция выигрыша игроха 2 равна -н.

Введем во множестве ? - у структуру евклидова пространства размерности га х л, полагая

I Г - Г I - шах \а - а' I.

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

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

Справедлива следувщая теорема.

Теорена 5. Множество у игр пространства множества ситуаций равновесия в которых конечны, есть ннохество второй категории.

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

Глава 3. Теоретико-игровая модель управления динамическим процессом теплообмена.

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

Используя результаты теории динамических игр, протекавших в полных метрических пространствах,3'' показывается существование с-оптимальных стратегий управления динамическим процессом теплообмена. Предлагается численный метод для реаения данной задачи. Глава 3 состоит из четырех параграфов.

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

3

Малафеев O.A. О существовании обобщенного значения игры преследования // Управляемые системы. -1970. N 4-5. -С. 47-55.

Петросян Л.А., Томский Г.В. Динамические игры и их при-лохенил. - Л.: Изя-во Ленингр. ун-та, 1982. -252 с.

к нему тепло тем или иным способом. Математически это воздействие описывается посредством управлявшего параметра w из некоторого множества управлений которым распоряжается технолог. На процесс изменения температурного поля тела также оказывает воздействие состояние v внешней среды, в котором находится тело л. Это управлявший параметр 'природы", он также принадлежит некоторому множеству управлений V. Качество управления процессом теплообмена оценивается некоторым показателем н.

Ставится задача о выборе такой управлявшей функции v -- wtt), t e 10, T] со значениями во множестве управлений которая при лвбых возможных условиях внешней среды - управлявших функциях "природы" гарантировала бы оптимальное значение показателя качества я.

Рассматриваются следувщие критерии качества:

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

2. Выбором управлявшей функции w(c) привести температурное поле материала к заданному состояние за минимальное время при лвбых возможных условиях внешней среды.

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

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

Рассматривается дифференциальная антагонистическая игра V(ао,Т) с предписанной продолжительностью т, с начальной позицией и , протекающая в пространстве с_ - непрерывных функций

° Q

и (ж), определенных на замкнутом ограниченном множестве Я -

- 10,-1,1 X ю.1я].

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

-те-(»£-)♦ ré-<»зг->. >• <е> 118 8

хае(0,Ха), t>o,

" х, " х2€(0,1а), t>0, (7)

1

" *,<a-v>' *, " 1,' 'ае<0,13>. t>0. (8)

1

" *г - О. t>o, (9)

а

исх(,хг,о; - иог*,,хяь *f6(o,ifj. *гб(о,1гь t-o, (It)

где с - с(x,t) - объемная теплоемкость, ж - x{x,t) - коэффициент теплопроводности материала; <<|, «¡а - коэффициенты теплообмена; w и V - управляющие параметры игроков р (технолога) и £ (природы) соответственно; * е », vsv, » и V - компактные множества из евклидовых пространств вр и я4 соответственно.

Кусочно-непрерывная функция w - »ft;, удовлетворяющая условиям v(t) е » при лвбых t с [0,7] называется допустимым управлением игрока р; кусочно-непрерывная функция v - v(t), удовлетворяющая условиям v(t) € V при лвбых t « (О,Г] называется допустимым управлением игрока в.

При любой паре допустимых управлений w(t) и v(t) и любом

начальном условии uQ существует единственное реаение задачи <6)-(11).

Состояние информации игроков риг следующее. В каждый момент времени t игрокам известна позиция игры u(х,t), момент t-o начала и г - окончания игры и динамика игры.

В момент окончания игры игрок е, распоряжающийся выбором

управления v, получает от Р выигрьа равный

■ *

В(и(-)1 - | b(u(x,ti,v(t),v(t),t) at,

о

где и(-) - траектория процесса, соответствующая допустим» управлениям »(•) и v(>) на интервале {р,т); h(u(-),v(t),v(t),t)-- непрерывная, ограниченная яа ограниченных множествах функция, характеризующая затраты энергии. Предполагается, что процесс происходят на интервале [0,7], который выбирается так, что за время до момента 7 траектория процесса достигает множества о фиксированного в задаче заранее.

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

В параграфе 3 вводится s области 0 - * (о,1а) рав-

номерная сетка о с вагон h по л и вагон h по ж , где h -

Л il а а

" • На отрезке времени 10,Т] вводится равномерная сетка

с^с*нагон т.

На сетке 4»Лт - х ет строится локально-одномерная разностная схема для приближенного определения множества достижимости в момент времени t при любой паре допустимых управлений v(t), vft), t « [tj,t^i;, диктуемых кусочно-программными стратегиями игроков р и ж.

Разностная схема, соответствующая задаче (б)-(II), в операторной форме имеет следующий вид:

D* У,* + \ S - . «i-i.a; j -oTvi. (12)

у

»„(*,'*.> > 1-oT»,; * -07, (15)

y!_ yft«-1>'t

где

t •

Методом энергетических неравенств доказана устойчивость и сходимость построенной схеиы.

Справедливы следующие теоремы,

J**sa

Теорема 4. Пусть оператор ол > о^* - положительно оп-

ределенсый, оператор Ал - Ал > cfА^ - самосопряженный положительно определенный и удовлетворяет условию Липшица:

\ < (1*с3ЧАл . J-о,нг-1.

Тогда локально-одномерная разностная схема (12)-(13) абсолютно устойчива и для ее решения выполняется следующая оценка:

/ п /-3-» ' J * В I

if' «», 1 Лг п».

I лг J.о л., >

O.fo t

где J»f - е *

Теорема 5. При Iht -» о, t ■* о ревевке локально-одномерной разностной схемы (12)-(13) сходится к решению исходной задачи (6)-(11) со скоростью Oft+1/il*; и справедлива следующая оценка

t л /—■ a J tots t \

1 « 1 л.,«н, { е /Л- Е к J}.

Аа 1 J-O Л.1 >

где lh|* - h* + ha, Н -const, 1 а в

В параграфе 4 решена задача оптимального нагрева однород-

вого стержня длиной 1. Приводятся исходные данные и результаты численных расчетов.

Основные результаты диссертации опубликованы в работах:

1. Малафеев O.A., Троева М.С. О единственности слабого решения уравнения Гамяльтоиа-Якоби для дифференциальной антагонистической игры U Вести. Ленингр. уи-та. -1987. 14 с. (рук. деп. в ВИНИТИ 26.08.87 г., К 6851-87 Деп.).

2. Троева (Давыдова) U.C. Гладкая устойчивость ситуаций равновесия в смешанных стратегиях для матричных игр // Вестн. Ленингр. ун-та. -1990. 12 с. (рук. деп. а ВИНИТИ 09.08.90 г., И 4548-90 Деп.).

3. Малафеев O.A., Троева (Давыдова) М.С. Разностный метод решения дифференциальных игр П Тезисы докладов Ш Всесовз. ■колы " Понтрягинские чтения. Оптимальное управление. Геометрия и анализ". Кемерово. -1990. -С. 162.

4. Малафеев O.A., Тро«ва (Давыдова) U.C. Численный метод решения задачи оптимального распределения ресурсов // Тезисы докладов И Школы "Математические проблемы экологии". Чита. -1990. -С. 105-106.

5. Троева U.C. Численное решение двумерной сопряженной задачи теплообмена // Тез. докл. Ш респ. конф. молодых ученых и спец. -Якутск, 1980. -С. 28-30.

6. Троева М.С. О численном решении одной задачи теплообмена // Материалы 17 ВСЯК. Математика, НГУ. Новосибирск, 1979. С. 138-144.

7. Малафеев O.A., Троева (Давыдова) М.С. О слабом решении основного уравнения дифференциальной игры и о его аппроксимации // Вопр. цех. и процессов упр.- 1991. N14. - С. 42-57.