close

Вход

Забыли?

вход по аккаунту

?

К поиску равновесных управлений в дифференциальной игре m лиц.

код для вставкиСкачать
2000
ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ
МАТЕМАТИКА
Є 12 (463)
УДК 517.977
О.О. ВАСИЛЬЕВА, О.В. ВАСИЛЬЕВ
К ПОИСКУ РАВНОВЕСНЫХ УПРАВЛЕНИЙ
В ДИФФЕРЕНЦИАЛЬНОЙ ИГРЕ
m
ЛИЦ
1. Постановка задачи
Пусть на заданном отрезке времени T = [t0 ; t1 ] каждый i-й участник дифференциальной
игры выбирает свое управление ui = ui (t), ui (t) 2 E ri , i = 1; 2; : : : ; m, из класса измеримых
функций, стесненных прямыми ограничениями ui (t) 2 Ui , где Ui E ri | компакт. Пусть также
выбранный набор допустимых управлений
u(t) = (u1 (t); : : : ; um(t)); u(t) 2 U;
m
X
U = U1 U2 Um E r ; r = ri;
i=1
характеризует ситуацию в игре. При сложившейся ситуации состояние x = x(t; u), x(t; u)2E n ,
процесса игры определяется задачей Коши для системы обыкновенных дифференциальных
уравнений
x_ = f (x; u; t); x(t0 ) = x0 ; t 2 T:
(1.1)
Функционал
Z
Ji (u) = Ji (u1; : : : ; um) = 'i (x(t1 )) + Fi (x; u; t)dt; i = 1; 2; : : : ; m;
(1.2)
T
где 'i , Fi | скалярные функции своих переменных, характеризует выигрыш i-го игрока. Каждый из игроков выбором своего допустимого управления стремится максимизировать свой
функционал выигрыша. Под концом или решением игры будем понимать такой набор допустимых управлений u = u (t) и ему соответствующее состояние x = x(t; u ), при которых
Ji (u ) = u max
Ji (u1 ; : : : ; ui;1 ; ui ; ui+1 ; : : : ; um ); i = 1; 2; : : : ; m:
(1.3)
(t)2U
u
i
= u (t),
i
Набор управлений
удовлетворяющих условиям (1.3), по аналогии с конечномерной
ситуацией ([1]; [2], c. 81) будем называть равновесными управлениями. Наша задача состоит в
построении метода поиска равновесных управлений.
Заметим, что
m
X
J (u) = Ji (u)
(1.4)
i=1
обычно называют ценой игры. Если J (u) = 0, u 2 U , то такая игра называется игрой с нулевой
суммой. При m = 2 игра с нулевой суммой называется антагонистической. Алгоритм решения
антагонистической игры предложен в [3]. Здесь будем рассматривать игру m лиц с переменной
суммой.
Работа выполнена при поддержке Российского фонда фундаментальных исследований и федеральной
целевой программы \Интеграция".
9
2. Метод решения
Предварительно в наборе управлений u = (u1 ; : : : ; um ) формально выделим управление ui ,
которое соответствует функционалу выигрыша Ji (u), и введем обозначение
u = (ui ; vi ); vi = (u1 ; : : : ; ui;1 ; ui+1 ; : : : ; um ):
Теперь в системе дифференциальных уравнений (1.1) определим m задач оптимального управления
ui (t; vi ) : Ji (ui (vi ); vi ) = u max
Ji (ui ; vi ); i = 1; 2; : : : ; m:
(2.1)
(t)2U
i
i
Предположим, что оптимальные управления ui = ui (t; vi ) в задачах (2.1) существуют для любых vi = vi (t), vi (t) 2 Ui , i = 1; 2; : : : ; i ; 1; i + 1; : : : ; m. Для нахождения этих управлений можно
использовать итерационные процессы принципа максимума ([4], c. 114), хотя с их помощью отыскиваются локально-оптимальные управления. Естественно, что при этом на параметры системы
(1.1) и функционалов (1.2) надо наложить известные условия, при которых справедлив принцип максимума Л.С. Понтрягина. Напомним эти условия. Вектор-функция f (x; u; t) и скалярные
функции 'i (x), Fi (x; u; t), i = 1; 2; : : : ; m, непрерывны по своим переменным вместе с частными
производными по x. Кроме того, вектор-функция f (x; u; t) удовлетворяет неравенству Липшица
по x с одной константой для всех u(t) 2 U , t 2 T .
Если предположить, что система (1.1) линейна по состоянию
x_ = A(t)x + b(u; t); x(t0 ) = x0 ;
подинтегральные функции Fi в функционалах (1.2) имеют вид
Fi (x; u; t) = Fi (x; t) + Fi (u; t); i = 1; 2; : : : ; m;
а функции 'i (x), Fi (x; t), i = 1; 2; : : : ; m, вогнуты по x для каждого t 2 T , то любое локальнооптимальное управление ui будет оптимальным.
(1)
(2)
(1)
Замечание. С использованием задач (2.1) равновесные управления (1.3) можно определять
как решения системы операторных уравнений ui (t) = ui (t; vi ); i = 1; 2; : : : ; m, где равенство
понимается почти всюду на T .
Кажущаяся простота такого подхода редко приводит к результату даже для конечномерной
ситуации ([1]; [2], c. 84). Поэтому предложим другой метод.
На основе возможности решения задач (2.1) сформируем функционалы
m
X
J (u) = Ji (ui (vi ); vi );
(2.2)
i=1
m
X
(u) = J (u) ; J (u) =
i=1
(Ji (ui (vi ); vi ) ; Ji (ui ; vi ));
(2.3)
где каждое слагаемое в функционале (2.3) неотрицательно.
Теорема. (u) 0, u(t) 2 U . Если (u ) = 0, то u | набор равновесных управлений. Если
u | набор равновесных управлений, то (u ) = 0.
Результат теоремы следует из определения (1.3), задач (2.1), замечания и вида функционалов
(2.2), (2.3).
Таким образом, поиск равновесных управлений сводится к еще одной задаче оптимального
управления. Именно, к задаче минимизации неотрицательного функционала
u : (u ) = umin
(u) = 0;
(2.4)
(t)2U
10
определенного на системе дифференциальных уравнений (1.1) и системах
x_ i = f (xi ; (ui (vi ); vi ); t); xi (t0) = x0 ;
(2.5)
xi (t) = x(t; (ui (vi ); vi ); t); i = 1; 2; : : : ; m:
К сожалению, для решения задачи (2.4), (2.5) не всегда можно использовать методы, с помощью
которых решались задачи (2.1). Это связано с возможными разрывами непрерывности функций
ui (vi ) и нарушением непрерывности правых частей системы и интегральной части функционала
по состоянию и управлениям. Для того чтобы использовать те же методы, с помощью которых
решались задачи (2.1), введем аппроксимирующий функционал
u (z ) = J u (z ) ; J (z ); z (t) 2 U;
(2.6)
m
P
где J u (z ) = J1 (u1 ; z2 ; : : : ; zm ) + + Jm (z1 ; : : : ; zm;1 ; um ) = Ji (ui ; pi ), ui = ui (t; vi ), pi =
i=1
(z1 ; : : : ; zi;1 ; zi+1 ; : : : ; zm ), i = 1; 2; : : : ; m.
Лемма. Функционал u (z ), z (t) 2 U , определенный на решениях системы (1:1) и систем
(2:5) при фиксированных ui , i = 1; 2; : : : ; m, удовлетворяет тем же условиям, которым удовлетворяют функционалы Ji (u), определенные на решениях системы (1:1). Кроме того,
u (u) = (u); u(t) 2 U; u (z ) (z ); z (t) 2 U:
Действительно,
m
X
u (z ) = Ji (ui ; pi ) ; J (z ) i=1
zmax
J (z ; p ) + + zmax
Jm (zm ; pm) ; J (z) = J (z ) ; J (z ) = (z ):
2U
m 2Um
1
1
1
1
1
Первые два положения леммы очевидны.
Таким образом, функционал u (z ), z (t)2U , аппроксимирует снизу функционал (z ), z (t)2U ,
а при z = u значения этих функционалов совпадают.
Очевидно
Утверждение. Если функциональное множество U = fu = u(t) : u(t) 2 U; t 2 T; (u) = 0g
равновесных управлений не пусто, и для каждой функции u = u(t), u(t) 2 U , t 2 T , не пусто
множество Z (u) = fz = z (t) : z (t) 2 U; t 2 T; u (z ) = 0g, то u Z (u).
Приведенные положения служат основанием для построения алгоритма поиска равновесных
управлений.
3. Алгоритм. Примеры
Алгоритм.
Шаг 0. Задаем u0 (t) 2 U , u0 = (u0i ; vi0 ), i = 1; 2; : : : ; m, k = 0. Решаем задачи оптимального управления (2.1). Находим допустимые управления uki = ui (t; vik ) и соответствующие им
состояния xki = x(t; uki ; vik ), i = 1; 2; : : : ; m. В обозначении решения x = x(t; u) задачи Коши (1.1)
xk1 = x(t; uk1 ; uk2 ; : : : ; ukm ); : : : ; xkm = x(t; uk1 ; : : : ; ukm;1 ; ukm ).
Шаг 1. Вычисляем значение функционала (uk ) по формулам (1.2), (1.4), (2.2), (2.3). Если
(uk ) > 0, то переход на шаг 2. Если (uk ) = 0, то uk = u , u = (u1 ; : : : ; um ) | равновесное
управление. Решение задачи окончено.
Шаг 2. По формуле (2.6) при u = uk , z = u формируем аппроксимирующий функционал
k (u) = uk (u); k (uk ) = (uk ) > 0:
11
Заметим, что функционал k (u) имеет вид
Z
m X
k
k (u) =
'i (xi (t1)) ; 'i (x(t1 )) + (Fi (xi ; ui ; vi ; t) ; Fi (x; u; t))dt ;
T
i=1
(3.1)
и этот функционал определен на решениях x = x(t; u) системы (1.1) и решениях xki = xi (t; uki ; vi )
систем
x_ = f (x; uki ; vi ; t); x(t0 ) = x0 ; i = 1; 2; : : : ; m:
Условия на параметры этой задачи те же, что и для задач (2.1). Поэтому, отправляясь от
uk : k (uk ) > 0, задачу минимизации функционала (3.1) можно решать методами решения
задач (2.1). Заметим только, что нас интересует не минимум этого функционала, а его нулевое
значение
uk+1 : k (uk+1 ) = 0:
Шаг 3. Полагаем uk+1 = uk , k = k + 1 и переходим на шаг 0.
В заключение приведем иллюстративные примеры.
Пример 1.
u = (u ; u ); ju (t)j 1; ju (t)j 1; t 2 T = [t ; t ];
x_ = A(t)x + B (t)u (t) + B (t)u (t) + b(t); x(t ) = x ;
(3.2)
Ji (u) = hci ; x(t ; u)i; i = 1; 2:
Здесь u (t) 2 E r1 , u (t) 2 E r2 , x(t; u) 2 E n , ci 2 E n , i = 1; 2, x(t; u) | решение задачи Коши (3.2)
при выбранных допустимых u = u (t), u = u (t), h; i | символ скалярного произведения в E n .
1
2
1
1
2
1
2
0
2
1
0
0
1
1
2
1
1
2
2
Для решения задач (2.1) используем принцип максимума Л.С. Понтрягина, который является
необходимым и достаточным условием глобально-оптимального управления. Пусть = (t; ci ) :
_ = ;A(t) , (t1 ) = ci , i = 1; 2. Тогда из условий максимума функции
H ( (t; ci ); x; u1 ; u2 ; t) = h (t; ci ); A(t)x + B1 (t)u1 + B2(t)u2 + b(t)i; i = 1; 2;
по управлениям u1 и u2
u1(t; u2 ) = u1 (t) = sign B1(t)0 (t; c1 );
(3.3)
u2(t; u1 ) = u2 (t) = sign B2(t)0 (t; c2 ):
Здесь штрих означает транспонирование матрицы. Теперь построим неотрицательный функционал (u) (формулы (2.2), (2.3)):
(u) = hc1 ; x(t1 ; u1 ; u2 ) ; x(t1 ; u)i + hc2 ; x(t1 ; u1 ; u2 ) ; x(t1 ; u)i = hc1 ; x1 (t1 ; u)i + hc1 ; x2 (t1 ; u)i;
где
x_ 1 = B1(t)[u1 (t) ; u1 (t)]; x1 (t0) = 0;
x_ 2 = B2(t)[u2 (t) ; u2 (t)]; x2 (t0) = 0:
Очевидно, u : (u ) = 0 достигается при u1 (t) = u1 (t), u2 (t) = u2 (t). Таким образом, равновесные
управления в рассмотренной задаче находятся сразу по формулам (3.3).
Пример 2.
u = (u ; u ); u (t) 2 U ; u (t) 2 U ; t 2 T = [t ; t ];
x_ = A(t)x + b(u; t); x(t ) = x ;
Ji (u) = hci ; x(t; u)i; i = 1; 2:
1
2
1
1
2
2
0
12
0
0
1
Здесь равновесные управления u = (u1 ; u2 ) удовлетворяют условиям
h (t; c1 ); b(u ; t)i = umax
h (t; c1 ); b(u1 ; u2 ; t)i;
1 2U1
h (t; c2 ); b(u ; t)i = umax
h (t; c2 ); b(u1 ; u2; t)i:
2 2U2
(3.4)
В каждом t 2 T условия (3.4) определяют точку Нэша [1], [2] в конечномерном пространстве. Для
нахождения этих точек можно использовать конечномерный алгоритм поиска точек равновесия
[5]. Для обеспечения существования точек Нэша и, следовательно, существования равновесных
управлений нужно предположить выпуклость и компактность Ui , i = 1; 2, вогнутость функции
h (t; c1 ); b(u1 ; u2 ; t)i по u1 для всех u2 (t) 2 U2 и вогнутость функции h (t; c2 ); b(u1 ; u2 ; t)i по u2
для всех u1 (t) 2 U1 в каждом t 2 T [2].
Пример 3.
x_ = x + u (t) ; 2u (t); x(0) = 0; t 2 [0; 1];
ju (t)j 1; ju (t)j 1; u = (u ; u );
J (u) = x(1); J (u) = ;x (1);
_ = ; ; (1) = 1; (1) = ;2x(1);
(t) = e e;t > 0; t 2 [0; 1]; u (t; u ) = sign (t);
u (t; u ) = u (t) = 1;
(t) = ;2x(1)e e;t ;
u (t; u ) = ; sign (t) = sign x(1);
(u) = x(1; u ; u ) ; x(1; u ; u ) ; x (1; u ; u ) + x (1; u ; u ) 0;
x(t; u ; u ) : x_ = x + u ; 2u ;
x(0) = 0;
x(t; u ; u ) : x_ = x + 1 ; 2u ;
x(0) = 0;
x(t; u ; u ) : x_ = x + u ; 2 sign x(1); x(0) = 0:
1
2
1
2
1
1
2
2
2
1
2
1
1
1
2
2
1
1
2
2
1
1
2
2
1
2
1
2
1
2
1
2
2
1
1
2
2
1
2
2
2
1
Заметим, что правая часть последнего уравнения не удовлетворяет тем условиям, при которых справедлив принцип максимума Л.С. Понтрягина. Поэтому для решения задачи (2.4)
нельзя использовать те методы, с помощью которых решались задачи (2.1).
Для решения поставленной задачи используем вышеизложенный алгоритм. Пусть u01 0,
0
u2 0, u0 = (u01 ; u02) = 0. Тогда x(t; u0) = 0, J1 (u0) = J2 (u0 ) = 0. Решаем задачи (2.1):
u01(t) = 1; x(1; u01 ; u02 ) = e ; 1;
u02(t) : J2 (u01; u2 ) = ;x2 (1) ! max; ju2 j 1;
x_ = x ; 2u2 ; x(0) = 0:
Очевидно, u02 (t) = 0, x(1; u01 ; u02 ) = 0, (u0 ) = e ; 1 > 0. По формуле (2.6) при u = u0 ; z = u
построим аппроксимирующий функционал
0 (u) = x2 (1) ; x1 (1) ; x23 (1) + x21 (1);
(3.5)
x_ = x + u (t) ; 2u (t); x (0) = 0;
x_ = x + 1 ; 2u (t);
x (0) = 0;
x_ = x + u (t);
x (0) = 0:
1
1
2
2
3
3
1
2
2
1
2
1
(3.6)
3
Задача минимизации функционала (3.5), определенного на решениях системы (3.6), по условиям на ее параметры эквивалентна задачам (2.1). Поэтому при \спуске" 0 (u), 0 (u0 ) > 0, до
его нулевого значения можно применять методы решения задачи (2.1). Для задачи (3.5), (3.6)
13
нетрудно увидеть, что 0 (u1 ) = 0 при u11 (t) = 1, u12 (t) = 0, u1 = (u11 ; u12 ). Теперь опять решаем
задачи (2.1):
u11 (t) = 1;
u12(t) : J2 (u11; u2 ) = ;x2 (1) ! max; ju2 j 1;
x_ = x + 1 ; 2u2 ; x(0) = x0 :
Очевидно, u12 (t) = 0;5. Далее, x(1; u11 ; u12 ) = e ; 1, x(1; u1 ; u12 ) = e ; 1, x(1; u11 ; u12 ) = 0. Отсюда
(u1 ) = (e ; 1)2 > 0. Опять строим аппроксимирующий функционал
1 (u) = x2 (1) ; x1 (1) ; x23 (1) + x21 (1);
x_ 1 = x1 + u1 ; 2u2 ; x1(0) = 0;
x_ 2 = x2 + 1 ; 2u2 ; x2(0) = 0;
x_ 3 = x2 + u1 ; 1; x3(0) = 0:
Очевидно, 1 (u2 ) = 0 при u2 = (u21 ; u22 ), u21 (t) = 1, u22 (t) = 0;5. При u2 = u2 (t) решения u21 (t),
u22 (t) задач (2.1) имеют вид u21 (t) = 1, u22 (t) = 0;5. Тогда (u2 ) = 0 и, следовательно, u1 (t) = 1,
u2 (t) = 0;5 | равновесные управления, J1 (u ) = J2 (u ) = 0. Цена игры J (u ) = 0, хотя цена J (u)
при допустимых u = (u1 ; u2 ) | переменная величина.
Литература
1. Nash J.F. Equilibrium points in N -person games // Proc. Nat. Acad. Sci. { 1950. { V. 36. { P. 48{49.
2. Беленький В.З., Волконский В.А., Иванов С.А. и др. Итеративные методы в теории игр и
программировании. { М.: Наука, 1974. { 239 с.
3. Vasilieva O.O., Vasiliev O.V. Inverse problems and equilibrium strategies in theory of optimal control
// Manuskripte Presently at University of Zurich Institute Operations Research. { 1997. { 30 p.
4. Vasiliev O.V. Optimization methods. { Atlanta: Word Federation Publishing Company, 1996. {
267 p.
5. Vasilieva O.O., Vasiliev O.V. On a method of equilibrium situations search in game of N -partners //
Пленарные докл. 11-й Международн. Байкальской школы-семинара \Методы оптимизации
и их приложения". { Иркутск, 1998. { C. 32{35.
Университет де Валле (Колумбия)
Иркутский государственный университет
Поступила
27.07.1999
14
Документ
Категория
Без категории
Просмотров
3
Размер файла
164 Кб
Теги
лиц, игре, дифференциальной, равновесной, управления, поиск
1/--страниц
Пожаловаться на содержимое документа