авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |

«Российская академия наук Российская ассоциация математического программирования Институт систем энергетики им. Л.А.Мелентьева СО РАН ...»

-- [ Страница 4 ] --

Ключевые слова: ячейка, частица, экстремальное значение, математическое ожидание.

1. Постановка задачи В N ячеек независимо друг от друга размещаются n частиц в соответствии с полиномиаль ной схемой, в которой каждая частица попадает в ячейку с номером i с вероятностью p i, i = 1,..., N, p1 +... + pN = 1. Обозначим µr = µr (p1,.., pN, n, N ) число ячеек, содержащих ровно r частиц, r = 1,.., n. Требуется найти такие наборы вероятностей p1,..., pN, для которых мате матическое ожидание M µr принимает максимальное значение. Для математического ожидания величины µr справедливо равенство [1, с.111]:

N r pr (1 pi )nr. (1) M µr = C n i i= Заметим, что случай r = 0 был изучен ранее в [1].

2. Эквивалентные задачи Легко показать, что приведенная выше задача размещения эквивалентна следующей задаче слу чайного блуждания: рассматривается движение частицы по целочисленной N -мерной решетке.

Из точки (x1, x2,.., xi,..xN ) может быть сделан шаг в точку (x1, x2,.., xi+1,..xN ) с вероятностью pi, i = 1,..., N, p1 +... + pN = 1. Первый шаг делается из точки (0, 0,.., 0). Пусть P (A) веро ятность того, что частица первые r шагов сделает вдоль одной из координатных осей, а (n r) шагов будут сделаны в других, отличных от этого направлениях. Требуется найти такие наборы вероятностей p1,..., pN, при которых величина P (A) будет максимальной.

3. Вид набора вероятностей (p1,..., pN ) При помощи правила множителей Лагранжа было установлено [3], что функция M µr (p1,.., pN, n, N ) достигает экстремального значения только тогда, когда в наборе (p 1,..., pN ) присутствуют вероятности двух типов: p(1) = x и p(2) = y, тогда M µr = M µr (x, k, n, N ) = Cn [kxr (1 x)nr + (N k)y r (1 y)nr ], r (2) где r = 1, n и выполнено условие kx + (N k)y = 1. Таким образом, задача свелась к нахождению значений x и k, доставляющих экстремум функции M µr при заданных N, n, r. Будем считать, что k K, K = {0, 1,..., [ N ]}, где [u] целая часть числа u.

4. Необходимое условие существования экстремума функции M µr Пусть k, r, n, N - фиксированные величины. Тогда функцию M µr можно считать зависящей толь ко от переменной x. Введем в рассмотрение функцию r (z) = z r (1 z)nr (индекс r в общем случае для дальнейших выводов и рассуждений опустим). Нетрудно показать, что равенство 1 kx (3) (x) = ( ), N k где (x) = z r1 (1 z)nr1 (r nz), является необходимым условием существования экстремума функции M µr (x). Иначе говоря, любая точка x0 [0;

k ], (k = 0) является точкой "подозритель ной"на экстремум функции M µr (x), если для нее выполняется равенство (3), а точка x = N всегда будет "подозрительной"на экстремум.

Возникает закономерный вопрос о разрешимости равенства (3). Был построен пример (при N = 3, n = 7, r = 1, k = 1), показывающий что уравнение (3) в общем случае неразрешимо в радикалах.

5. Поведение функции M µr (x) на границе 1. При функция M µ1 (x) на левой границе изменения аргумента возрастает, а на правой границе - убывает, следовательно, функция M µ1 (x) на границе локального максимума не имеет.

2. При r = n 1 функция M µn1 (x) на левой границе изменения аргумента возрастает, а на правой границе - убывает при k = 1 и возрастает при k = 1, следовательно, функция M µ n1 (x) имеет локальный максимум в точке x = k, при k = 1.

3. При r = n 1, r = 1 функция M µr (x) в точке x = 0 при n r(N k) и в точке x = k при n rk локального максимума не имеет.

6. Экстремум целевой функции в точке x = 1/N Изучив знакопеременность второй производной функции M µr (x) в точке, соответствующей рав новероятному набору вероятностей, т.е. x = N, получим, что при N 1/M или N 1/m равновероятный набор (p1,.., pN ), pi = 1/N не является решением поставленной экстремальной задачи.

Исследование экстремума целевой функции в точке x = 1/N применимо и для локализации корней равенства (3). Допустим, при исследовании функции M µr (x) на границе, выяснилось, что в точке x = 0 (x = 1/k) происходит возрастание (убывание), а точка x = 1/N доставляет локальный минимум целевой функции, следовательно, на интервале x (0, 1/N ) (x (1/N, 1/k)) находится, по меньшей мере, один локальный максимум целевой функции.

В [4] найдены верхняя и нижняя оценки (нижняя для n r(N 1)) для величины max M µr (x, k, n, N ) :

x[0;

1],kK r r M = Cn · N · ( )r (1 )nr, r n n N 1 r N 1 nr r r r + (N 1)( )r (1 )nr ].

M = Cn [(1 r (4) ) (r ) n n n n 7. Некоторые свойства функции (z) Для дальнейшего исследования экстремальной задачи, в частности, для нахождения количества решений равенства (3) перечислим некоторые свойства функции (z), z [0;

1]:

def r 1. нули функции находятся в точках z = 0, z = 1, z0 = n ;

r(n1)(nr) r 2. локальный максимум в точке M = n, локальный минимум в точке n(n1) r(n1)(nr) r ;

m= n+ n(n1) 3. (z) имеет точки перегиба z1, z2, 3, причем z r z1 = n 2 (1 + i 3) v iu + (1 i 3) 3 v + iu, r z2 = n (1 i 3) 3 v iu + (1 + i 3) 3 v + iu, r z3 = n + 3 v iu + 3 v + iu, def r(nr) (r1)(n1)(nr1) def r(n2r)(nr), v = n3 (n1)(n2), i = 1;

где u = n2 (n1)2 (n2) 4. функция (z) выпукла на z (0;

z1 ) (z2 ;

z3 ), вогнута на z (z1 ;

z2 ) (z3 ;

1).

Доказано, что z1, z2, z3 вещественные, причем z1 z2 z3.

def Введем функцию (z) = ( 1kz ) на z [ 1(N k) ;

1 ], k = 0 и изучим некоторые ее свойства.

N k k k 8. Некоторые свойства функции (z) Справедливо следующее Утверждение 1. График функции (x) = ( 1kx ) можно получить из графика функции N k (x) сначала зеркально отражая его относительно прямой x = N, а затем растягивая его относительно той же прямой в N k раз.

k С учетом Утверждения 1 легко указать следующие свойства функции (z). Она на своей области определения имеет def 1(N k) 1 1 r, z = k, z = k (1 n (N k));

1. нули в точках z0 = k def 1 def локальный максимум в M = k N k M, локальный минимум в m = k N k m;

k k 2. def 1 def 1 def (z) имеет точки перегиба z1 = k N k z1, z2 = k N k z2, z3 = k N k z3 ;

k k k 3. 9. Зависимость количества пересечений двух функций от их свойств Для дальнейшего изучения функций (z) и (z) рассмотрим две непрерывные, дифференцируемые на отрезке [a;

b] функции f1 (z) и f2 (z). Рассмотрим некоторые случаи а) Пусть для любого z (a;

b) справедливо f1 (z) 0, f2 (z) 0. Тогда графики функций f1 (z) и f2 (z) имеют не более одной точки пересечения, причем если f1 (a) f2 (a), то точек пересечения нет.

б) Пусть для любого z (a;

b) справедливо f1 (z) 0, f1 (z) 0, f2 (z) 0, f2 (z) 0, тогда графики функций f1 (z) и f2 (z) пересекаются на z (a;

b) не более чем в двух точках.

в) Пусть f1 (a) f2 (a) и для любого z (a;

b) выполняется f1 (z) 0, f1 (z) 0, f2 (z) 0, f2 (z) 0, тогда графики функций f1 (z) и f2 (z) пересекаются на z (a;

b) не более чем в одной точке.

г) Если f1 (z) 0, f1 (z) 0, f2 (z) 0, f2 (z) 0 графики функций f1 (z) и f2 (z) пересека ются на z (a;

b) не более чем в двух точках.

д) Если f1 (a) f2 (a) и f1 (z) 0, f1 (z) 0, f2 (z) 0, f2 (z) 0 графики функций f1 (z) и f2 (z) пересекаются на z (a;

b) не более чем в одной точке.

Заметим, что если графики двух функций f1 (z) и f2 (z) на z (a;

b) пересекаются четное количество раз, либо не пересекаются вообще и f1 (a) f2 (a), тогда f1 (b) f2 (b). Если же графики двух функций f1 (z) и f2 (z) на z (a;

b) пересекаются нечетное количество раз и f1 (a) f2 (a), тогда f1 (b) (b).

10. Исследование количества решений экстремальной задачи Вследствие того, что необходимое условие существования экстремума функции M µ r в общем случае не разрешимо в радикалах, имеет смысл исследовать количество решений равенства (3).

Утверждение 2. Пусть выполняется n 2r, z3 z3, тогда справедливо z0 m z 3 z 3 m z 0.

Автором доказано, что функции (z) и (z) на каждом из (z0 ;

m), (m;

z3 ), (z3 ;

z3 ), (3 ;

m), z (m;

z0 ) подынтервалов отрезка [z0 ;

z0 ] монотонны, обладают постоянной выпуклостью\вогнуто стью.

Теперь перечислим все варианты возможных пересечений графиков функций (z) и (z) на z [z0 ;

z0 ]. В рассуждениях будем использовать результаты, полученные при изучении зави симости количества пересечений двух функций от их свойств, ссылаясь пункты а)–д). Так как на z [z0 ;

m] имеет место (z) 0, (z) 0, (z), (z)0 и (z0 ) (z0 ), то (z) на z [z0 ;

m], согласно 1. более двух точек пересечения графики функций (z) и случаю "г)"иметь не могут;

2. пусть графики функций (z) и (z) на z [z0 ;

m] пересеклись два раза, т.е. четное число раз, т.е. (m) (m). На z [m;

m] согласно случаю "а)"точек пересечения нет, т.е.

(m). На отрезке [m;

z0 ], согласно случаю "в", не более одной точки пересечения.

(m) Итого, на z [z0 ;

z0 ] графики функций (z) и (z) пересекаются не более трех раз;

3. пусть графики функций (z) и (z) на z [z0 ;

m] пересеклись один раз, нечетное число, т.е. (m) (m). Согласно случаю "а"на z [m;

m] не более одной точки пересечения, причем 3.1 если пересечение на z [m;

m] было, то (m) (m). Согласно случаю "в"на отрезке [m;

z0 ] не более одной точки пересечения. Итого, на z [z0 ;

z0 ] графики функций (z) и (z) пересекаются не более трех раз;

3.2 если пересечения на z [m;

m] не было, то (m) (m). Согласно случаю "б"на отрезке [m;

z0 ] не более двух точек пересечения. Итого, на z [z0 ;

z0 ] графики функций (z) и (z) пересекаются не более трех раз;

Т.к. z0 z0, то при z [0;

z0 ) справедливо (z) 0, (z) 0, следовательно, при z [0;

z0 ) (z) не пересекаются. Аналогично при z (0 ;

1].

графики функций (z) и z Следовательно, при z3 z3, n 2r равенство (3) на x [0;

k ] выполняется не более чем в трех точках. Проведя подобное исследование для n 2r, m z3 z3 можно убедиться, что и для этого случая пересечений графиков будет не более трех. Это означает, что при n 2r, m z 3, фиксированном k равенство (3) имеет не более трех решений.

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

11. Исследование вида решения задачи по графикам функций (z), (z) Функция (z) была достаточно полно исследована, что позволяет построить ее график. Далее, учитывая Утверждение 1 можно построить график функции (z). Точки пересечения zi [0;

1] определят точки подозрительные на экстремум, т.к. будут являться решением равенства (3).

Возможны три варианта взаимного расположения графиков в окрестности точки пересечения z i :

1. Левее точки пересечения zi график функции (z) проходит выше графика функции (z), а правее ниже. Иначе говоря, (zi ) (zi ) 0, (zi + ) (zi + ) 0, т.е. в точке zi находится локальный максимум.

2. Левее точки пересечения zi график функции (z) проходит ниже графика функции (z), а правее выше, то в точке zi находится локальный минимум.

3. Точке пересечения zi точка касания графиков функций, то zi точка перегиба.

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

Площадь между кривыми, измеряемая от точки максимума до ближайшей к ней, лежащей справа точки минимума, характеризует величину увеличения значения функции от момента достижения ею локального минимума, поведение функции M µr (x) в "граничных"точках x = 0 и x = 1/k хорошо видно: если в "граничной"точке график функции (z) проходит выше графика функции (z), то в этой точке происходит возрастание функции M µr (x), если ниже, то убывание.

12. Основные выводы Теперь обобщим полученные результаты. Для решения поставленной экстремальной задачи необ ходимо максимизировать функцию (2). Если n = r или n = rN, то решение тривиально, иначе необходимо провести дополнительное исследование.

1. Найти верхнюю оценку величины M µr (x). Для случая n r(N 1) можно найти и нижнюю оценку. Практика показывает, что при больших n она очень близка к точному решению (для n = 23, r = 3, N = 4, k = 1 относительная ошибка составляет 0,001% для решения задачи и 7, 0 · 108 % для значения M µ3 ).

2. Исследовать функцию M µr (x) в точке x = 1/N (ей соответствует равновероятный набор p1 = p2 =.. = pN = 1/N ) и на границе изменения величины x, т.е. в точках x = 0, x = 1/k.

Если в точке x = 1/N функция M µr (x) имеет локальный максимум, то возможно это и есть решение задачи, если же нет, то в зависимости от поведения функции в точках x = 0, x = 1/k можно локализовать искомые точки локального максимума.

3. Учитывая, что необходимое условие существования экстремума в общем случае неразрешимо в радикалах, имеет смысл исследовать количество его решений. Доказано, что при n 2r и m z равенство (3) для каждого k имеет не более трех решений, одно из которых x = 1/N.

4. Исследовать вид решения задачи по графикам функций (z), (z), а именно, определить количество экстремальных точек фукции M µr (x), их характер и примерное местоположение на отрезке [0, 1/k].

Далее, используя результаты проведенного исследования для решения задачи максимизации функции M µr (x), можно применять численные методы. Для достаточно больших n хорошее приближение дает точка x = 1 r Nn при k = 1, соответствующая нижней оценке величины max M µr (x, k, n, N ). В результате будут получены пары величин k и xi, для которых будет x[0;

1],kK справедливо (с допустимой точностью) равенство (3). Необходимо сравнить все соответствую щие им значения M µr (xi ), M µr (0), M µr ( k ) (в случае если имеет место локальный максимум на границе) k K. Те величины k и xi, которые соответствуют наибольшему значению функции M µr (x), определят решение экстремальной задачи: любой набор вероятностей (p 1,..pN ) достав ляет максимум функции M µr (p1,.., pN ), если в нем любые k вероятностей равны xi, а остальные (N k) равны 1kxi.

N k Список литературы [1] Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. – М.: Наука, 1976.

[2] Зубков А.М., Попов Н.Н. Отношение частичного порядка, порожденное распределением чис ла занятых ячеек // Матем. заметки. 1982. Т.32, №1. С. 2–25.

[3] Колокольникова Н.А., Гильманшин Р.Р. Экстремальные задачи в теории случайных разме щений. // Труды XII Байкальской международной конференции "Методы оптимизации и их приложения". 2001. Т.5, С. 71–75.

[4] Гильманшин Р.Р., Колокольникова Н.А. Об одной экстремальной задаче в теории случайных размещений // Колмогоров и современная математика. Тезисы докладов. М.: МГУ, 2003.

С. 627–628.

АСИМПТОТИКА ФОРМ ОБЛАСТЕЙ ДОСТИЖИМОСТИ ЛИНЕЙНЫХ ДИНА МИЧЕСКИХ СИСТЕМ С ИМПУЛЬСНЫМ УПРАВЛЕНИЕМ Е.В. Гончарова, А.И. Овсеевич Институт динамики систем и теории управления СО РАН, Иркутск e-mail: goncha@icc.ru Институт проблем механики РАН, Москва e-mail: ovseev@ipmnet.ru Аннотация. Изучены асимптотические свойства областей достижимости линейных автономных систем с импульсным управлением.

Ключевые слова: Множества достижимости, импульсное управление, линейные динамические системы, формы выпуклых тел.

Введение Статья посвящена исследованию асимптотического поведения множеств достижимости линейных систем с импульсным управлением. Аналогичные вопросы для линейных систем с геометрическими ограничениями на управление изучались в [4, 2]. Применяемый подход открывает определенные преимущества в изучении асимптотической динамики так называемых форм множеств достижимости. Под формой выпуклого множества здесь понимается множество с точностью до обратимого линейного преобразования. Оказывается, что формы множеств достижимости обладают лучшими свойствами по сравнению с самими множествами достижи мости. Во многих случаях при больших временах поведение форм множеств достижимости подобно асимптотическому поведению множеств достижимости систем с устойчивой матрицей.

Как известно, в автономном устойчивом случае множества достижимости имеют предел при T. Здесь сходимость множеств может пониматься в различных эквивалентных смыслах: в смысле метрик Хаусдорфа, Банаха-Мазура или в терминах сходимости опорных функций.

1. Постановка задачи В данной работе мы изучаем линейную автономную систему с импульсным управлением:

x(0) M, (1) dx(t) = Ax(t) dt + B du(t), где x(t) V = Rn, u(t) W = Rm, A, B матрицы соответствующих размерностей. Рассмотрим эту систему на интервале [0, T ] при следующем ограничении на управляющую меру du:

T f (t) du(t) 1 (2) для всех непрерывных вектор-функций f таких, что |f (t)| 1, t [0, T ], или, что эквивалентно, Var[0,T ] u(t) 1. Предположим, что множество начальных состояний M представляет собой цен трально симметричный выпуклый компакт, и для системы (1), (2) выполнено условие Калмана полной управляемости.

Работа выполнена при поддержке РФФИ (проекты 02-01-00201, 05-01-0477) и Программы поддержки научных школ (грант 1627.2003.01).

Множества достижимости D(T ) системы (1), (2) являются центрально симметричными вы пуклыми телами (выпуклыми компактными множествами с непустой внутренностью), определя емыми как T D(T ) = D(T, M ) = {x(T ) : x(T ) = eAT x(0) + eA(T s) B du(s)}, где x(0) M и du удовлетворяет (2).

Цель настоящей работы состоит в исследовании поведения множеств D(T ) при T.

Пусть B есть пространство выпуклых центрально симметричных тел. Определим на B так называемую метрику Банаха-Мазура:

(1, 2 ) = log (t(1, 2 ) t(2, 1 )), где t(1, 2 ) = inf{t 1 : t1 2 }.

Свяжем с каждой точкой (выпуклым телом) B ее форму (shape) Sh, которая по опреде лению есть орбита точки под действием группы GL(V) невырожденных матриц: Sh = {C :

det C = 0}. Пространство B форм выпуклых тел есть множество всех классов эквивалентности на B, где 1 и 2 принадлежат одному классу тогда и только тогда, когда существует невырожден ная матрица C такая, что 1 = C2. На пространстве форм с помощью метрики Банаха-Мазура естественным образом определяется расстояние:

(Sh 1, Sh 2 ) = inf (1, C2 ).

C, det C= Сходимость множеств достижимости D(T ) и их форм Sh D(T ) нами понимается в смысле рассто яния Банаха-Мазура. В частности, будем говорить, что две функции со значениями в B являются асимптотически равными, 1 (T ) 2 (T ), если (1 (T ), 2 (T )) 0 при T. Заметим, что при анализе асимптотического поведения областей достижимости описание выпуклых тел с помощью их опорных функций H () := supx x, оказывается более удобным, чем прямое обращение к определению. Следующий результат [2] устанавливает эквивалентность сходимости выпуклых множеств в смысле данного выше определения и в терминах сходимости их опорных функций.

Лемма 1 Последовательность i в B сходится к B в смысле метрики Банаха-Мазура тогда и только тогда, когда соответствующая последовательность опорных функций H i () = Hi () сходится к опорной функции H () поточечно, и равномерно ограничена на единичной сфере в сопряженном пространстве V.

Отметим также (см. [3]), что опорная функция множества достижимости D(T ) системы (1), (2) имеет вид HD(T ) () = HM (eA T ) + sup B eA t. (3) [0,T ] 2. Асимптотическое поведение форм множеств достижимости Исследуем предельное поведение кривой T Sh D(T ) при T при различных предполо жениях относительно спектра матрицы системы Spec A.

1. Если A устойчивая матрица, т.е. Re Spec A 0, из леммы 1 и (3) сразу следует, что множество достижимости D(T ) имеет предел при T.

2. Пусть A строго неустойчивая (Re Spec A 0). Определим матричный множитель def C(T ) = eAT и рассмотрим множество D(T ) = C(T )D(T ). Легко видеть, что HD(T ) () = HM () + sup B eA s сходится к HD () = HM () + sup B eA s при T равномер [0,T ] [0,] но по на компактном множестве, и, следовательно, Sh D(T ) стремится к Sh D при T.

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

3. Предположим теперь, что матрица A допускает каноническое разложение вида A = A+ A, где Spec A = Spec A+ Spec A, Re Spec A+ 0 и Re Spec A 0 (гиперболический случай). Данное разложение спектра порождает пару взаимно дополнительных проекторов P ± и соответствующее разложение фазового пространства V в прямую сумму двух подпространств V± = P± V. Тогда система (1), (2) эквивалентна следующей:

x+ (0) M+, (4) dx+ (t) = A+ x+ (t) dt + B+ du(t), x (0) M, (5) dx (t) = A x (t) dt + B du(t), Var[0,T ] u(t) 1, (6) где x± = P± x, A± = P± A, B± = P± B, и M± = P± M. Обозначим через D± (T ) = D± (T, M± ) множества достижимости систем (4) и (5) при условии (6).

Прежде чем сформулировать результат об асимптотическом поведении множеств достижи мости, рассмотрим выпуклые множества ± V±. Определим их соединение = + V = V+ V как = {t+ (1 t) : t [0, 1], ± ± }.

Заметим, что опорная функция множества имеет вид H () = max H+ (+ ), H ( ), где = + есть каноническое разложение вектора в V = V+ V, V± = P± V.

Теорема 1 В гиперболическом случае множество достижимости системы (1), (2) удовлетво ряет асимптотическому равенству D(T ) C(T ) (M+ + D ) при T, где D выпуклое тело, не зависящее от T, матричный множитель C(T ) = C+ (T ) C (T ), C+ (T ) = eA+ T, C (T ) = I (единичная матрица).

При этом множество D представляет собой соединение выпуклых тел D+ и D, D± = lim C± (T )D± (T, {0}).

T В частности, формы Sh D(T ) имеют предел Sh(M+ + D+ D ) при T.

Таким образом, предельная форма множества достижимости системы (1), (2) есть соединение предельных форм множеств достижимости систем (4) и (5).

4. Присутствие нейтральной компоненты в каноническом разложении A = A + A0 A, Re Spec A+ 0, Re Spec A0 = 0, Re Spec A 0, существенно осложняет картину. Система (1), (2) может быть представлена в виде:

xi (0) Mi, Var[0,T ] u(t) 1, dxi (t) = Ai xi (t)dt + Bi du(t), где xi Vi = Pi V и Ai = Pi APi, i = +, 0,.

Здесь снова возникает проблема выбора подходящего матричного множителя C(T ), который обеспечивал бы сходимость преобразованных множеств достижимости. В решении этого вопроса будем следовать [2, 4].

Рассмотрим разложение A0 = D+N, где D диагонализуемая, N нильпотентная матрицы, DN = N D. Пусть F (T ) = F (N, T ) матричная функция такая, что F (CN C 1, T ) = CF (N, T )C F (N M, T ) = F (N, T ) F (M, T ), для любой обратимой матрицы C, и 1 0 0 1 T 1....

..

для F (N, T ) = N =.

..

.

T (n1) 0 Более того, F (N, T )N F (N, T )1 = T 1 N и limT F (N, T ) = F есть проектор на ядро ker N.

Тогда искомый матричный множитель, определяющий поведение множеств достижимости систе мы (1), (2) при больших временах, имеет вид C(T ) = C+ (T ) C0 (T ) C (T ), (7) где C+ (T ) = eA+ T, C0 (T ) = F (T )1, и C (T ) = I.

Заметим, что в отличие от гиперболического случая, в общем контексте мы не можем более говорить о сходимости форм Sh D(T ) к единственной предельной форме. В пространстве форм возникает аттрактор A положительной размерности.

тор, порожденный однопараметрической группой операторов {e Dt :

Пусть T GL(V0 ) V0 V0 }. Аттрактор A представляет собой образ тора T при некотором непрерывном отображе нии. Кривая T Sh D(T ) в пространстве форм асимптотически близка к образу T ((T )) прямой геодезической линии (T ) = eDT t на торе T, где t T фиксированный элемент. (Общее обсуждение прямых геодезических содержится в [1]).

Рассмотрим матричную функцию eA0 t = R eit p (t), где p (t) полином с матричны t ми коэффициентами. Заметим, eA0 t F (T ) = F (T ) eit p ( T ) и eA0 t eD T = eD T eA0 t = i(tT ) p (t).

e Дадим теперь явное описание аттрактора A в пространстве форм и отображения : T A.

Пусть t = t( ) T определяется набором углов R/2Z, где 1 {Spec A0 \ {0}}. Введем i в рассмотрение функции ei( t) p (1), eit p (0), ei p ( ).

g+0 (t, t) = F g0 (t) = F g0 (t, ) = F Определим выпуклые тела def def +0 +0 0 0 D = D (t) V+0 = V+ V0, D = D (t) V0 = V V0, D V посредством их опорных функций HD (+, 0 ) = supt0 |B eA+ t + + B g+0 (t, t)0 |, + HD (, 0 ) = supt0 |B eA t + B g0 (t)0 |, = sup [0,1] |B g0 (t, )0 |.

HD (0 ) tT Пусть, наконец, D = D (t) V = V+ V0 V выпуклое тело, определяемое своей опор ной функцией HD () = max HD (+, 0 ), HD (0 ), HD (, 0 ). Заметим, что в последнем +0 0 + выражении только D зависит от t.

Рассмотрим выпуклый компакт M = M(t), M(t) = M+ g0 (t, 1) M0. Заметим, что он зависит только от начальных множеств Mi, i = +, 0, и его опорная функция имеет вид HM () = HM+ (+ ) + HM0 (g0 (t, 1)0 ).

Теперь мы можем сформулировать основной результат:

Теорема 2 Множества достижимости системы (1), (2) удовлетворяют следующему асимп тотическому равенству D(T ) C(T )(t) при T.

Здесь (t) = M(t) + D (t), C(T ) определено в (7), и t = t(T ) элемент тора T, задаваемый последовательностью T mod 2, где 1 {Spec A0 \ {0}}.

i В частности, Sh D(T ) Sh (t), и отображение : T A есть (t) = Sh (t).

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

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

Заметим, что гиперболический случай значительно проще, чем общая ситуация, поскольку тор и аттрактор, возникающие в общем случае, здесь вырождаются в точку. Отметим также, что картина асимптотической динамики форм областей достижимости линейных систем с импульсным управлением оказывается сложнее, чем в изученных ранее случаях автономных и периодических систем с геометрическими ограничениями на управление [4, 2].

Список литературы [1] В.И. Арнольд Математические методы классической механики. М.: Наука, 1989, 472 с.

[2] T.Yu. Figurina, A.I. Ovseevich Asymptotic behavior of attainable sets of linear periodic control systems. J. of Optim. Theory and Appl., vol. 100, No. 2, 1999, pp. 349–364.

[3] E.V. Goncharova, A.I. Ovseevich Asymptotic behavior of attainable sets of a linear impulse control system. Proceedings of the IFAC Workshop on Generalized Solutions in Control Problems (GSCP-2004), Pereslavl-Zalesski, Russia, September, 21–29, 2004. Moscow: Fizmatlit, 2004, pp.

72–76.

[4] A.I. Ovseevich Asymptotic behaviour of attainable and superattainable sets. Proceedings of the Conference on Modeling, Estimation and Filtering of Systems with Uncertainty, Sopron, Hungary, 1990. Birkhaser. Basel, Switzerland, 1991, pp. 324–333.

u ASYMPTOTICS FOR SHAPES OF REACHABLE SETS TO LINEAR DYNAMICAL SYSTEMS WITH IMPULSIVE CONTROL E.V. Goncharova, A.I. Ovseevich Institute of System Dynamics and Control Theory, SB RAS, Irkutsk e-mail: goncha@icc.ru Institute for Problems in Mechanics, RAS, Moscow e-mail: ovseev@ipmnet.ru Abstract. Asymptotic properties of reachable sets to linear time-invariant systems with impulsive control are studied.

Key words: Reachable sets, impulsive control, linear dynamical systems, shapes of convex bodies.

ИССЛЕДОВАНИЕ ДОСТАТОЧНОГО УСЛОВИЯ ЭКСТРЕМУМА В ЛИНЕЙНОЙ ЗАДАЧЕ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В.В. Дикусар, Д.А. Чекарев ВЦРАН, Москва;

МФТИ, Москва e-mail: dikussar@ccas.ru;

chekarev@hotmail.com Аннотация. Рассматривается двухэтапный метод решения задач оптимального управления со смешанными ограничениями. На первом этапе рассматривается дискретно-аппроксимационная задача, на основе решения которой формулируется гипотеза о геометрии оптимальной траек тории, т.е. выделяются промежутки постоянства множества номеров активных ограничений.

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

Предложенный метод эффективно работает при наличии надежного алгоритма решения дискретно-аппроксимационной задачи.

Ключевые слова: задача оптимального управления, смешанные ограничения, задача линейно го программирования, численно-аналитический метод.

Введение Рассмотрим линейную задачу оптимального управления (ОУ) со смешанными ограничениями типа равенства и неравенства.

Минимизировать функционал J(u ) = x (T ) min (1) при следующих ограничениях:

x = x A(t) + U B(t) + a (t), (2) x (T )Q c, (3) x (0) =, b (t), x C1 (t) + u D1 (t) (4) b (t).

x C2 (t) + u D2 (t) (5) Матрицы A(t), B(t), C1 (t), C2 (t), D1 (t) и D2 (t) и векторы a (t), b (t), b (t) имеют кусочно 1 непрерывные компоненты. Соответствующие матрицы и векторы имеют следующие размеры:

A[n n], B[m n], C1 [n r1 ], C2 [n r2 ], D1 [m r1 ], D2 [m r2 ], Q[n q], x [n], u [m], a [n], b [r1 ], b [r2 ], [n], c [q]. Векторы с символом * являются строками, без символа столбцами.

1 Если на правом краю заданы ограничения типа равенства, то каждое из них преобразуется в два исключающих неравенства (3).

Сложность решения данной задачи состоит в наличии условий (4)–(5) (смешанных ограниче ний). Данные условия не позволяют использовать широко известные методы решения задач ОУ, основанные, например, на решении задачи Коши, в силу необходимости априорного определения Работа выполнена при финансовой поддержке РФФИ (код проекта 03-01-00678).

множества номеров (индексов) активных ограничений для каждого момента времени t [0, T ] (ограничение типа неравенства называется активным, если оно обращается в равенство). А раз деление множеств ограничений на активные и неактивные приводит к комбинаторной задаче большой размерности.

В настоящей работе рассматривается двухэтапный метод решения задачи. Первый этап состоит в дискретизации по времени задачи ОУ с использованием схем Эйлера первого или второго порядка точности [1]. В результате получается задача линейного программирования (ЛП) большой размерности. Конкретнее, если выполнялось разбиение отрезка интегрирования на N точек, то число переменных в задаче ЛП есть (n + r) (N + 1). Данный прием широко известен и подробно описан (см, например, [1, 2]). Результат решения задачи ЛП тем точнее может аппроксимировать решение исходной непрерывной задачи, чем больше точек дискрети зации использовалось при разбиении отрезка [0, T ]. Однако размерность получающейся задачи ЛП растет с ростом числа точек дискретизации, а с ростом размерности надежность решения задачи ЛП падает. Решение задачи ЛП дает приближенные значения фазовых переменных и управлений в точках дискретизации. Эти приближенные значения, если они достаточно надежно аппроксимируют точное решение, позволяют сформулировать гипотезу о том, какие ограничения из набора (4) активны в каждый момент времени. Далее отрезок интегрирования [0, T ] разбивается на промежутки, на каждом из которых множество индексов активных огра ничений постоянно. На втором этапе сформулированная гипотеза проверяется на выполнение необходимых (и, если возможно, достаточных) условий экстремума. Рассматриваемый метод будет продуктивным при наличии эффективного алгоритма решения задачи ЛП, возникающей на первом этапе. Следует отметить, что при кажущейся идейной простоте метода решения практическая реализация наталкивается на трудности, возникающие при численном решении задач ЛП большой размерности. В данной работе при решении модельной задачи использовался пакет оптимизационных программ “БАЛАНС-2” [3], позволяющий надежно решать возникающие задачи ЛП.

1. Достаточные условия экстремума Рассмотрим получение достаточных условий экстремума в задаче (1)–(5). При доказатель стве будем опираться на результаты, полученные в [4], где линейные задачи оптимального управления сводятся к задачам ЛП в банаховом пространстве. Приводимые далее результаты слегка изменены без ограничения общности для совместимости с задачей (1)–(5).

Задача А.

Найти управления u (t) L [0, T ], доставляющие максимум линейному функционалу m J(u ) = x (T ) max (6) при следующих ограничениях:

x = x A(t) + U B(t) + a (t), (7) x (T )Q c, (8) x (0) =, x C(t) + u D(t) b (t), u (t) 0. (9) Матрицы A(t), B(t), C(t) и D(t) и векторы a (t), b (t) имеют ограниченные измеримые ком поненты. Соответствующие матрицы и векторы имеют следующие размеры: A[n n], B[m n], C[n r], D[m r], Q[n q], a [n], b [r], [n], c [q]. В данной задаче, в отличие от исходной, отсут ствуют смешанные ограничения типа равенства (5), но присутствуют условия неотрицательности управлений (9);

кроме того, ищется максимум функционала (6), а не минимум. Наряду с задачей А рассматривается сопряженная к ней задача Б.

Задача Б.

Найти управления (t) L1 [0, T ], Rq, доставляющие минимум линейному функционалу r T J() = x(0) c + [b (t) + a (t)x]dt min при следующих ограничениях:

x = A(t)x + C(t), x(t) = + Q, B(t)x + D(t) 0, 0.

Теорема 1 (Тер–Крикоров, [4]).. Пусть для некоторых допустимых управлений u (t) и (t), задач А и Б выполнены условия u [B(t) + D(t)] = 0, (10) i x i = 1, m;

[ C(t) + u D(t) b (t)]j j = 0, (11) x j = 1, r;

[ (T )Q c ]k k = 0, (12) x k = 1, q, причем первые два равенства выполняются почти при всех t. Тогда u (t), x(t) оптимальное решение задачи А, а (t),, x(t) оптимальное решение задачи Б.

Теорема 2. Пусть рассматривается линейная задача ОУ со смешанными ограничениями типа равенства и неравенства (1)–(5). Пусть в любой момент времени можно разрешить все r2 ограничений типа равенства относительно r2 из m управлений (r2 m) (13) ukj = ukj (x, u, t), j = 1, r2.

Далее, пусть при подстановке выраженных таким образом uk в ограничения типа неравенства (4) получаются неравенства относительно n + m r2 переменных (n переменных x и m r переменных u), причем на оставшиеся управления накладываются условия неотрицательности ui 0, j = 1, r2. (14) i = kj Получившаяся таким образом задача подпадает под определение задачи А, следовательно, для нее можно сформулировать задачу Б. Пусть для некоторых допустимых управлений задач А и Б выполнены условия теоремы 1, т.е. получены оптимальные управления и фазовые переменные задачи А. Тогда подстановкой их в выражения (13) можно получить оптимальные управления и фазовые переменные исходной задачи.

Доказательство. Произведем изменение условий задачи таким образом, чтобы она приняла форму задачи А. Для этого будем максимизировать функционал, полученный из (1):

J (u ) = 0 x (T ) max.

Кроме того, выразим часть управлений через фазовые управления и остальные управления из ограничений типа равенства (5);

получим (13). Подставим их в ограничения типа неравенства (4) и в дифференциальные уравнения (2). Проверим выполнение условия (14) для оставшихся управлений. В случае невыполнения условия (14) для управления u i произведем замену ui = u i u i, ui 0, ui 0. (15) В результате получается задача, имеющая форму задачи А;

следовательно, для нее можно сфор мулировать задачу Б. Если найдены оптимальные управления и фазовые траектории задачи А (что проверяется выполнением условий теоремы 1), то оптимальные управления исходной задачи получаются выполнением обратных замен из выражений (13) и (15).

2. Исследование модельной задачи Практическое исследование предложенной схемы выполнялось на модельной задаче ОУ внеш ним долгом. Модель является продолжением развития моделей, описанных в [5, 6].

Минимизируемый функционал J(x, u) = x3 (T ).

Система дифференциальных уравнений и ограничения задачи uimin ui uimax, i = 1, 7, x = u1 + u2, u6 1 (x1 x4 ), x = u3 + u4, = µ 3 x 3 + u 1 + u 3 + u 5 k 1 u6, u7 2 (x2 x5 ), x u2 + u 4 u 7, x = 1 u6, u2 + u 4 + c u 7 + u 5.

x = 2 u7, Значения коэффициентов задачи, начальных и конечных условий 1 = 0.03, x1 (0) = 25, uimin = 0, i = 1, 7, 2 = 0.03, x2 (0) = 15, u1max = u3max = 0.1, 1 = 0.18, x3 (0) = 400, u2max = 0.5, 2 = 0.18, x4 (0) = 0, u4max = u5max = 0.3, k1 = 0.9, x5 (0) = 0, u6max = u7max = 2.0, x1 (T ) x4 (T ) = 25, µ3 = 0.002, c = 0.2, x2 (T ) x5 (T ) = 15.

T = 100, Задача решалась на отрезке t [0, 100]. Аналитическое решение задачи ОУ строится на основе гипотезы об оптимальной траектории, полученной с помощью системы “БАЛАНС-2” [3]. Полное аналитическое решение задачи приведено в [7]. Здесь укажем лишь значение минимизируемого функционала: J(x(T ), u) = x3 (T ) = 394.9574932.

При дискретизации задачи использовались схемы Эйлера первого и второго порядков точно сти. Внешний вид управлений и фазовых переменных при использовании разных схем не менял ся, однако значение минимизируемого функционала получалось точнее в случае использования схемы Эйлера второго порядка. Например, при N = 100 J1 = 395.1515419, J2 = 394.9622277. Чис ленные расчеты проводились при различных N от 100 до 700 с шагом 10, причем при N = J1 = 395.1515419, J2 = 394.9576010, т.е. для схемы второго порядка отличие наблюдается только в четвертом знаке после запятой.

Кроме того, исследовалась разностная схема с переменной разрядной сеткой. Сгущения узлов дискретизации делались в окрестности точек переключения управлений. Так, на участках посто янства множеств индексов активных ограничений дискретизация проводилась с шагом h 1 = 0.4, в окрестности точек переключения дискретизация осуществлялась с шагом h 2 = 0.02 (использо валась схема Эйлера второго порядка). Хотя при этом общее число шагов составило N = 535, но оценки для времен переключений получены с большей точностью, чем при постоянном шаге дис кретизации и N = 700. Точное решение дает: t1 = 7.689788139, t2 = 29.73687498, t3 = 45.46140320, t4 = 88.31270799. При решении с переменным шагом получаем оценки: 7.68 t 1 7.7, 29.72 t2 29.74, 45.46 t3 45.48, 88.3 t4 88.32. При решении с постоянным шагом (схема Эйлера второго порядка) при N = 700: 7.43 t1 7.71, 29.57 t2 29.71, 45.29 t3 45.43, 88.14 t4 88.29. Как видно из приведенных данных, использование дискретизации с перемен ным шагом повышает точность определения времен переключения.

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

Минимизируемый функционал xi (0)i (0) [x1 (T ) x4 (T )](1 2 ) [x2 (T ) x5 (T )](3 4 ) J(, ) = i= T T c2 4 (t)dt + [u1max 5 (t) + u2max 6 (t) +... + u7max 11 (t)]dt.

0 Система дифференциальных уравнений и ограничения задачи 1 i 0, i = 1, 11, 2 + 3 + 4 + 8 0, = 1 1, 2 1 3 + 5 0, 3 4 + 9 0, = 2 2, 1 + 3 + 4 + 6 0, k1 3 1 4 + 1 + 10 0, = µ 3 3, 4 = 1 1, quad 2 3 + 7 0, 2 5 + 2 3 4 + 11 0, = 2 2.

Краевые условия задачи 1 (T ) = 4 (T ) = 1 2, 2 (T ) = 5 (T ) = 3 4, 3 (T ) = 1.

Все параметры сопряженной задачи берутся из исходной задачи.

Для сопряженной задачи была построена дискретная аппроксимация, сформулирована и ре шена соответствующая задача ЛП. Решениями сопряженной задачи являются сопряженные пере менные, которые удовлетворяют принципу максимума Понтрягина. Проверка достаточных усло вий экстремума (10)–(12) гарантирует оптимальность решения прямой задачи. Кроме того, зна чения функционала в исходной и сопряженной задачах совпадают с высокой точностью.

Список литературы [1] Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оп тимизации. М.: Наука, 1982.

[2] Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. М.: Высш. школа, 2003.

[3] Умнов А.Е. Система содействия принятию решений Баланс. М.: 1991.

[4] Тер-Крикоров А.М. Оптимальное управление и математическая экономика. М.: Наука, 1977.

[5] Дикусар В.В., Синягин С.Ю. Качественные и численные методы в задаче оптимального управления внешним долгом // Сообщ. по прикл. матем. М.: ВЦ РАН, 2000.

[6] Чекарев Д.А. Модель экономической системы с эффектом накопления в задаче оптималь ного управления внешним долгом // Моделирование и обработка информации. М.: МФТИ, 2003. С. 39-43.

[7] Дикусар В.В., Чекарев Д.А. Численно-аналитический метод решения задач оптимального управления // Сообщ. по прикл. матем. М.: ВЦ РАН, 2004.

НЕРАВЕНСТВО ГАМИЛЬТОНА-ЯКОБИ И ДОСТАТОЧНЫЕ УСЛОВИЯ ОПТИ МАЛЬНОСТИ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ В.А. Дыхта Байкальский государственный университет экономики и права, Иркутск e-mail: dykhta@isea.ru Аннотация. Рассматривается управляемая распределенная система с частными производными в нормальной (канонической) форме Дьедонне-Рашевского и связанная с ней задача оптимального управления с функциональными ограничениями на состояние. С использованием множества вспомогательных проверочных функций, удовлетворяющих дифференциальному неравенству Гамильтона-Якоби, получены внешние оценки множества достижимых граничных состояний и достаточные условия глобальной оптимальности, сводящие задачу управления к ляпуновской.

Ключевые слова: распределенная система, неравенство Гамильтона-Якоби, множество достижимости, достаточные условия.

Введение Достаточные условия оптимальности в невыпуклых задачах оптимального управления (как в обыкновенных, так и в распределенных системах) традиционно связаны с использованием урав нения Гамильтона-Якоби-Беллмана (в динамическом программировании), или соответствующего неравенства (как в методе В.Ф. Кротова [1];

см. также [2]-[3]). Несколько особняком стоит метод сравнения, которого мы не касаемся. В этих подходах основные результаты формулируются с по мощью одной "проверочной" функции, удовлетворяющей (в подходящем смысле) неравенству или уравнению Гамильтона-Якоби.

В последнее время появились более общие достаточные условия такого типа, использующие произвольное множество решений уравнения Гамильтона-Якоби [4], или неравенства [5]. Эти ре зультаты относятся к классической задаче оптимального управления в обыкновенных системах. В их основе лежит простой факт: любое семейство решений уравнения (неравенства) Гамильтона Якоби порождает внешнюю оценку множества достижимости управляемой системы. Примене ние этого свойства к получению достаточных условий оптимальности кардинально отличается от методов Р. Беллмана и В.Ф. Кротова, основу которых составляет конструкция обобщенно го лагранжиана. То же самое можно сказать относительно более тонких версий этих методов, направленных на снижение предположений гладкости единственной проверочной функции.

В докладе упомянутый подход распространяется на распределенные задачи оптимального управления, в которых управляемая система записана в так называемой нормальной форме [6] или, иначе, в канонической форме Дьедонне-Рашевского [7]. Это весьма общая система в частных производных, к которой сводятся, в принципе, любые дифференциальные распределен ные системы [6], и применительно к которым были получены более ранние результаты [1]-[3], служащие предметом переосмысления и обобщения.

1. Постановка задачи В ограниченной области Rk с кусочно-гладкой границей := S рассмотрим распреде Работа выполнена при финансовой поддержке РФФИ (проекты 04-01-00187, 05-01-00187) ленную управляемую систему xi i = fj (t, x, u), i = 1, n, j = 1, k, tj u(t) U Rm.

Здесь t = (t1,..., tk ), x = (x1,..., xn ), функции fj для простоты предполагаются гладкими и удо i влетворяющими (в обобщенном смысле) условиям интегрируемости [6], [7] f i f i =, i = 1, n, j, p = 1, k,.

tj tp В естественной матричной записи эту систему будем записывать в виде x u(t) U.

= f (t, x, u), (1) t Класс управлений U ограничим кусочно-непрерывными функциями u(t), а класс состояний X – соответствующих решений дифференциальной системы – непрерывными, кусочно-непрерывно дифференцируемыми функциями x(t) на замыкании области. Нарушение гладкости функ ций состояния допускается на многообразиях, удовлетворяющих некоторым условиям допустимо сти, которые обеспечивают применимость формулы интегрирования по частям Остроградского Гаусса, и детальное описание которых опускается. Отметим, что ценой некоторых технических усложнений в построениях можно расширить класс U до лебеговского пространства L p (), а класс состояний X – до соболевского пространства Wp () p 1 (см. [2], [7]).

Система (1) рассматривается с граничными условиями типа B(t, x(t)) = 0 на S, (2) где B(t, x) – заданная вектор-функция на S Rn. Предполагается, что граничные условия обес печивают существование управлений u U, для которых решение x X системы (1), (2) в смысле почти всюду на существует (это решение не обязательно единственно). Поясним, что при надлежащим выборе компонент вектор-функции B условия (2) включают в себя граничные (начально-краевые) условия вида xi (t) = y i (t) на Si, i = 1, n, где Si – часть границы S, а y i (t) – заданные функции. Таким образом, условия (2), конечно, не определяют граничные значения состояния на всем множестве S.

Множество пар функций (x, u) U X, связанных системой (1), (2), обозначим через D f ;

таким образом, Df – множество процессов управляемой системы.

При указанных выше расширениях функций управления и состояния, решения системы (1) надо понимать в смысле Соболева, а граничные условия (2) – в смысле следов функций x X на границе. Уточнения, относящиеся к этому случаю, можно найти в [2], [7].

Переходя от управляемой системы к постановке задачи оптимизации, будем считать, что в пространстве X (S) следов функций состояния на S задано подмножество функций Y(S) и в задаче имеется ограничение (“терминального” типа) x(·) |S Y(S), (3) где слева стоит след функции x X на S. Пары функций (x, u) Df, удовлетворяющие этому дополнительному граничному ограничению, назовем допустимыми процессами;

обозначим мно жество допустимых процессов через D и предположим, что D =. На множестве D определим целевой функционал J(x, u) = l(t, x(t))ds, (4) S подлежащий минимизации. Поставленную таким образом задачу (1)-(4) обозначим через (P ).

Поясним, что ограничение вида (3) охватывает различные ограничения интегрального типа, сведение которых к равенствам и неравенствам для интегралов по границе осуществляется стан дартно. Тоже самое относится и к целевому функционалу [6], который, на первый взгляд, носит частный характер. Хотя отмеченные сведния практически не всегда удобны, для изложения e теории достаточных условий “терминальная” форма задачи (P ) является предпочтительной.

2. Неравенство Гамильтона-Якоби и внешняя оценка множества достижимости Для любой постоянной матрицы сопряженных переменных = j Rnm составим функ i цию Понтрягина k ii j · f j (t, x, ), H(t, x,, u) = j fj (t, x, ) = (5) i,j j= где j, f j – j-ые столбцы матриц, f, а j ·f j означает краткую запись скалярного произведения векторов. Определим также гамильтониан управляемой системы, положив H(t, x, ) = max H(t, x,, u) (6) uU с областью определения domH, состоящей из троек (t, x, ), для которых максимум в (6) дости гается.

Для любой гладкой вектор-функции (t, x) = (1, :, k )(t, x) C 1 () можно ввести следующие функции:

(jj + j · f j )(t, x, u) = jj + H(t, x, x, u), P [](t, x, u) = (7) x t t j j jj + H(t, x, x ).

P[](t, x) = (8) t j Пару условий P[](t, x) 0, (t, x, x ) domH (9) назовем дифференциальным неравенством Гамильтона-Якоби с неизвестной вектор-функцией.

В частном случае, когда так называемый беллмановский зазор P[] = 0 на R n, это неравенство переходит в уравнение Гамильтона-Якоби.

Если – любое решение дифференциального неравенства (9), то для произвольного процесса (x, u) Df с учетом правила дифференцирования суперпозиции и определения функции P [] получаем равенство j divj (t, x(t)).

P [](t, x(t), u(t)) = (t, x(t)) = tj j j Отсюда, на основании формулы Остроградского-Гаусса и очевидного неравенства (см. (5)-(8)) P [](t, x, u) P[](t, x) на Rn, интегрированием получаем divj (t, x(t))dt = (t, x(t)) · n(t)ds 0, j S где n(t) – единичный вектор внешней нормали к S в точке t.

Таким образом, все решения неравенства Гамильтона-Якоби характеризуются свойством (t, x(t)) · n(t)ds 0 (x, u) Df.

[](x) := (10) S Это неравенство служит основой дальнейших построений.

Обозначим через Xf (S) множество граничных состояний системы (1), достижимых при за данных граничных условиях (2), т.е.

Xf (S) = {x(·) |S : (x, u) Df } X (S).

Назовем Xf (S) множеством достижимости.

Пусть – произвольное семейство решений неравенства Гамильтона-Якоби. Из неравенства (10) следует, что каждое такое семейство порождает внешнюю оценку множества достижимости, а именно Xf (S) Z[Ф] := {y X (S) : [](y) 0 }. (11) Именно эта оценка позволяет получить достаточные условия оптимальности в задаче (P ), причем постановка последней в канонической ("терминальной" форме) играет при этом не последнюю роль.

3. Оценка значения задачи (P ) и достаточные условия оптимальности Предположим, что имеется некоторое семейство решений неравенства Гамильтона-Якоби.

Рассмотрим следующую экстремальную граничную задачу:

l(t, y(t))ds inf, I(y) := S B(t, y(t)) = 0, t S, y(·) Y(S), y(·) Z[].

Обозначим ее через (BP ()). Из оценки (11) очевидным образом вытекает Теорема. (а) Имеет место оценка inf J[P ] inf I[BP ()] (где фигурируют значения задач, указанных в квадратных скобках);

(б) если функция y(t) | t S является решением задачи (BP ()), то любой процесс (, u) x D, для которого выполняется равенство x(t) = y (t) на S, оптимален в задаче (P ).


(в) если последовательность функций {y (t) | t S} является минимизирующей в задаче (BP ()), то любая последовательность процессов {x, u } D, для которой x (t) = y (t) на S, является минимизирующей в задаче (P ).

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

В сравнении с другими подходами, которые также оперируют с неравенством Гамильтона Якоби [1]-[3], представленные результаты являются более гибкими и общими, поскольку множество проверочных функций доставляет больше информации об управляемой системе и задаче (P ), нежели одна функция, как в указанных работах. При этом надо отметить, что в задачах, допускающих аналитическое исследование, множество проверочных функций появляется почти автоматически даже в процессе поиска одной проверочной функции. Это объясняется тем, что, грубо говоря, аналитическое интегрирование любого дифференциального неравенства (уравнения) невозможно без этапа нахождения некоторого "общего решения", которое в распределенных уравнениях содержит функциональный произвол.

4. Заключение Поскольку рассмотренная каноническая задача оптимального управления охватывает раз личные управляемые системы, то представленный подход допускает детализацию по классам задач. Эта детализация представляет несомненный интерес, так как в столь общей управляемой системе, как (1), оказываются скрытыми важные свойства конкретных систем. В частности, есте ственное теоретическое приложение утверждения (б) теоремы – это получение наиболее общих достаточных условий оптимальности в форме принципа максимума Понтрягина с использова нием проверочных функций, линейных по фазовым координатам (по аналогии с классическими задачами [5], [8]). Но эта теорема "не сработает", если поставить цель обращения вариационного принципа максимума – наиболее сильного (в первом порядке) необходимого условия оптималь ности в гиперболических системах – в достаточное условие. Для этого необходимо перейти от проверочных функций к функционалам (см. [9]), что требует кардинальной перестройки подхо да, вряд ли возможной в канонической системе (1).

Список литературы [1] В.Ф. Кротов, В.И. Гурман Методы и задачи оптимального управления. М.: Наука, 1973, с.

[2] R. Kltzler On a general conception of duality in optimal control. - Lect. Notes Math. 1979, 703, o p. 189-196.

[3] E. Zeidler Nonlinear functional analysis and its applications. - Vol. 3. Variational methods and optimization. - Springer-Verlag, 1985, 662p.

[4] A.A. Milyutin, N.P. Osmolovskii Calculus of variations and optimal control. - American Math.

Society, Providence, Rhode-Island, 1998, 372 p.

[5] В.А. Дыхта Неравенство Ляпунова-Кротова и достаточные условия в оптимальном управ лении. - Итоги науки и техники. Совр. математика и ее приложения. ВИНИТИ РАН. 2002, т. 92, с. 21-52.

[6] К.А. Лурье Оптимальное управление в задачах математической физики. Наука, 1975, с.

[7] L. Cesari Multidimensional Lagrange problems of optimization in a xed domain and an application to a problem of magnetohydrodynamics - Arch. Rational Mech. Anal. V. 29, 1968, p. 81-104.

[8] Н.В. Антипина, В.А. Дыхта Линейные функции Ляпунова-Кротова и достаточные условия оптимальности в форме принцина максимума - Изв. вузов. Математика. 2002, №12, с. 11-21.

[9] В.А. Дыхта Достаточные условия оптимальности в задачах управления каноническими гиперболическими системами - Вестник Бурятского государственного университета. Серия 13: Математика и информатика. Вып. 1. Улан-Удэ: изд-во Бурятского госуниверситета. 2004, с. 77-85.

HAMILTON–JAKOBI INEQUALITY AND SUFFICIENT OPTIMALITY CONDI TIONS FOR A DISTRIBUTED SYSTEMS V.A. Dykhta Baikal State University of Economics and Law, Irkutsk State University, Irkutsk e-mail: dykhta@isea.ru Abstract. We consider the distributed-parameter optimal control problem of the partial dierential system in Diedonne-Rashevsky canonic form. An upper estimation of the boundary reachable set and sucient global optimality conditions are obtained by using an arbitrary family of the solutions to the Hamilton-Jakobi inequality.

Key words: canonic system, Hamilton-Jakobi inequality, reachable set, sucient conditions.

ОБ ОДНОМ КЛАССЕ УРАВНЕНИЙ ЭЙЛЕРА-ЛАГРАНЖА В.Д. Иртегов Институт динамики систем и теории управления СО РАН, Иркутск e-mail: irteg@icc.ru Аннотация. В работе выделен класс вариационных задач, лагранжианы которых редуци руются к квадратичным. Рассмотрены особенности качественных исследований уравнений Эйлера-Лагранжа с помощью соответствующих им редуцированных уравнений.

Ключевые слова: уравнения Эйлера-Лагранжа, редукция, стационарные решения, устойчи вость.

Введение.

Метод редукции хорошо известен, в первую очередь, как метод упрощения задач механики [1], теории управления [2], вариационного исчисления [3] и других разделов естественно-научных дисциплин. В данном докладе выделен такой класс вариационных задач, для которых лагран жианы с помощью преобразования Лежандра редуцируются к квадратичным с постоянными коэффициентами. Очевидно, уравнения Эйлера-Лагранжа редуцированных систем в этом случае будут линейными. Рассмотрены особенности качественного анализа таких уравнений Эйлера-Лагранжа с помощью редуцированных уравнений.

1. Об уравнениях Эйлера-Лагранжа, редуцируемых к линейным.

Продемонстрируем решение указанной выше задачи на простом примере. Пусть лагранжиан рассматриваемой задачи с одной позиционной и n-циклическими координатами имеет следующую структуру:

n+1 n+ Fi,j (qn+1 )qi qj dqn+1.

2L = (1) i=1 j= Соответствующие ему уравнения Эйлера-Лагранжа будут иметь циклические интегралы, кото рые мы запишем в следующем виде:

n Fk,j (qn+1 )qj = pk Fk,n+1 qn+1, k = 1, 2,..., n, pk = const.

(2) j= Поставим задачу так определить функции Fi,j (qn+1 ), j, i = 1,..., n + 1 в выражении (1), чтобы после преобразования Лежандра [4], соответствующая лагранжиану (1) функция Рауса (редуци рованная функция Лагранжа) стала квадратичной с постоянными коэффициентами. Для этого по известному алгоритму [4] получим функцию Рауса, соответствующую функции Лагранжа (1), исключая циклические скорости qj, j = 1, 2,..., n;

из R = L n pk qk с помощью системы k= (2). В результате будем иметь:

n n n n 1 qn+ R= pi pj ai,j + pi Fj,n+1 aj,i + 2 i=1 j=1 i=1 j= n n 12 [Fn+1,n+1 Fk,n+1 ak,j ] dqn+1, q Fj,n+1 (3) 2 n+1 j=1 k= где = det|Fk,j |- определитель системы (2), ai,j - алгебраические дополнения элементов Fi,j матрицы ||Fi,j || системы (2). Располагая выражением (3), потребуем, чтобы данная функция Рауса была квадратичной по переменным qn+1, qn+1. Для этого должны выполняться условия:

n ai,j = mi,j qn+1 + ni,j = i,j ;

Fj,n+1 aj,i = i qn+1 ;

i, j = 1, 2,..., n;

j= n n [Fn+1,n+1 Fj,n+1 Fk,n+1 ak,j ] = B;

(4) j=1 k= где mi,j, ni,j, i, B -некоторые постоянные. Найдем из системы (4) значения Fi,j (qn+1 ), что поз волит нам записать явный вид лагранжианов (1), которые редуцируются к квадратичным по переменным qn+1, qn+1 с помощью преобразования Лежандра.

В результате решения уравнений (4) будем иметь:

n D ||i,j || = Di,j ||k,l || = Di,j ||k,l ||;

i, j = 1, 2,..., n;

Fi,j = n2 i,j n n n Fk,n+1 = qn+1 j Fj,k ;

k = 1, 2,..., n;

Fn+1,n+1 = B + qn+1 j Fj,n+1, (5) j=1 j= где через Di,j ||.|| обозначены алгебраические дополнения элементов соответствующей матрицы.

Таким образом доказано, что к квадратичной функции Рауса :

n n n 2 2 pj j qn+1 qn+1 pi pj (mi,j qn+1 + ni,j ) dqn+1 ;

2R = B qn+1 + 2 (6) j=1 i=1 j= редуцируются все лагранжианы (1) с коэффициентами Fi,j, которые определяются формулами (5).

Уравнение Эйлера-Лагранжа (семейство уравнений с параметрами pj ), соответствующее се мейству функций Рауса (6), (редуцированные уравнения Эйлера-Лагранжа в дальнейшем будем называть уравнениями Рауса) выглядит так:

n n d R R ) ( = B qn+1 + (d + pi pj mi,j )qn+1 = 0. (7) dt qn+ qn+ i=1 j= и содержит, как и функция R, n параметров (определяет поток на каждом интегральном многообразии семейства первых циклических интегралов исходной системы Эйлера-Лагранжа при фиксированных значениях постоянных pj ). Обратим внимание на то, что уравнение (7) не содержит параметров j, входящих в функцию Рауса (6). Таким образом, каждому уравнению (7) (при фиксированном p) соответствует целое семейство функций Рауса и, следовательно, функций Лагранжа. Уравнения Эйлера-Лагранжа, определяемые функцией (1), со значениями коэффициентов, найденных выше, и их линейные по скоростям первые интегралы достаточно громоздки и здесь не приведены. В случае увеличения числа позиционных координат в лагран жиане сложность выражений быстро растет.

2. Инвариантные многообразия исходной и редуцированной задачи.

Для демонстрации простейших особенностей, возникающих при cопоставлении свойств ис ходных и редуцированных уравнений Эйлера-Лагранжа, ограничимся случаем системы с одной циклической и одной позиционной координатой. В таком случае лагранжиану:

m 2 q 1 2mq 2 )q 2 + dq2 ;

2L = q1 + q1 q2 + (k + (8) (aq2 + b) 2 2 (aq2 + b) (aq2 + b) с циклическим интегралом:

L 1 mq V= = 2 + b) q1 + (aq 2 + b) q2 = p;

q1 (aq2 после редукции соответствует квадратичная функция Рауса:

2R = k q2 + 2mpq2 (p2 a d)q2 p2 b.

2 Соответствующее последней функции дифференциальное уравнение k q2 + (p2 a d)q2 = 0, (9) не содержит параметра m и допускает интеграл Якоби: 2H = k q2 + (p2 a d)q2 = 2h. Покажем, 2 что наше дифференциальное уравнение имеет семейство инвариантных многообразий (ИМ), с параметром m, доставляющих стационарное значение функции Рауса. Уравнения, определяющие искомые ИМ, могут быть получены так. Запишем условия стационарности R по q 2, q2 и потребуем 2 (ak + m2 ) kd = 0. Тем самым равенства нулю определителя полученной линейной системы: p сведем последнюю только к одному уравнению, в котором p может принимать два значения при каждом m:


dk dk ;

p2 = y = k q2 + mpi q2 = 0, i = 1, 2;

p1 = +. (10) (ak + m2 ) (ak + m2 ) Легко проверить, что мы действительно находим так два семейства ИМ.

Если записать уравнение (9) в отклонениях от выделенных выше инвариантных многообра зий, вводя переменные: y1 = k q2 + mp1 q2 ;

y2 = k q2 + mp2 q2, то будем иметь такие два варианта уравнения возмущенного движения и два значения функции Рауса:

m dk m dk 12 y ;

y2 = y1 = y ;

2R1 = y1 ;

2R2 = y2. (11) 2) 1 2) k (ak + m k (ak + m k k Рассматривая последние выражения как функции Ляпунова, и вычисляя для R 1 и R2 производ ные в силу дифференциального уравнения (9), получим:

dR1 m dk dR2 m dk y2 ;

y2.

= =2 2) 1 (ak + m2 ) dt k (ak + m dt k Используя теперь известную теорему Зубова, можно сделать вывод, что при m 0 асимпто тически устойчиво второе ИМ и неустойчиво первое, и наоборот. Таким образом имеем здесь не очень обычный пример асимптотической устойчивости стационарного ИМ в консервативной системе. Легко проверяется, что элементы семейств ИМ (10) поднимаются в фазовые простран ства лагранжевых систем, соотнесенных уравнениям (9). Но не доставляют там стационарного значения лагранжиану при всяком p.

Остановимся еще на сопоставлении стационарных решений, их бифуркациях и устойчивости для исходной и редуцированной задачи. Выделим решения, доставляющие стационарное значение интегралу Якоби семейства уравнений (9).

Записывая необходимые условия экстремума H,и находя из них значения q 2 и q2,получим два типа решений. Это положения равновесия: q2 = 0;

q2 = 0, существующие при всех значениях параметра p, и однопараметрическое семейство положений равновесия: q 2 = 0;

q2 = r = const, которые имеют место только при действительных значениях p, удовлетворяющих уравнению p2 = da1.

Рассматривая вторую вариацию интеграла Якоби в окрестности элементов семейства стацио нарных решений первого типа (она, очевидно, совпадет с самим интегралом Якоби), получим до статочные условия устойчивости положений равновесия первого типа в виде: k 0;

(p 2 ad) 0, как условия знакоопределенности рассматриваемой квадратичной формы 2 H. Поскольку первое неравенство всегда выполняется, если мы будем считать систему механической, то наши положе ния равновесия будут устойчивы для всех уравнений (9), для которых параметр p удовлетворяет второму неравенству. Рассматривая характеристическое уравнение для (9), легко обнаруживаем, что при обратном знаке неравенства (p2 a d 0), будем иметь неустойчивость. Граница состоит из двух точек ( двух значений параметра p), в которых имеет место бифуркация стационарных решений (примыкание решений второго типа к решениям первого типа).

Для решений второго семейства в выражении интеграла Якоби остается только член, содер жащий скорость, поэтому можно говорить только об устойчивости по части переменных ( по q2 ).

Для уравнений Эйлера-Лагранжа, определяемых лагранжианом (8), естественно считать, что в соответствие с найденными выше стационарными положениями равновесия раусовой задачи должны ставиться решения, доставляющие стационарное значение полной линейной связке ин тегралов этой системы:

m 2 q 1 mq2 1 12 2 K = H V = 2 + b) )q2 + 2 kq2 (aq 2 + b) (q1 + mq2 q2 ).

q1 + q1 q2 + (k + 2 2 + b) 2(aq2 + b) (aq2 (aq2 Записывая условия стационарности K по всем переменным (q1, q2, q2 ), легко видеть, что из первых двух уравнений следует известный результат - на стационарных решениях, соответствующих полной линейной связке интегралов K, скорости должны принимать значения: q 1 = ;

q2 = 0.

Подставляя эти значения в последнее условие стационарности, получим следующее соотношение для определения координаты q2 :

a q2 [d + ] = 0.

(aq2 + b) Это уравнение позволяет выделить два типа решений. В первом случае q 2 = 0. Что соответствует однопараметрическому семейству решений q1 = ;

q2 = 0;

q2 = 0. Элементы этого семейства, естественно, сопоставляются тривиальным положениям равновесия семейства уравнений реду цированной задачи. Связь между параметрами p и устанавливается постановкой найденных стационарных решений первого типа в циклический интеграл. Она выглядит так: pb =. Во вто рую группу входят решения, значения координаты q2 для которых определяется из уравнений четвертой степени и имеют вид:

a2 b a2 q2 + 2abq2 + b 4 = 0;

q2,i = ± ± ;

i = 1, 2, 3, 4. (12) d a ad Ясно, что указанные решения существуют только тогда, когда параметры системы обеспечивают положительность подкоренных выражений в последней формуле. Если считать a 0, b 0, то из выражения (12) сразу следуют следующие условия действительности для q 2,i : d 0, ± b(da) 2. У редуцированной системы нет стационарных решений, которые могли бы быть взаимно однозначно сопоставлены указанным четырем семействам. Все семейства второго типа примыка ют к решениям первого типа при значениях параметра, удовлетворяющего уравнению a 2 = b2 d или, если учесть связь между параметрами p и, при ap2 = d.

Рассмотрим вопрос об устойчивости элементов выделенных семейств. В случае первого се мейства вторая вариация интеграла K и первая вариация циклического интеграла выглядят так:

a2 12 2 2 K = q1 + k q2 + (d + 2 )q2 ;

V = q1 = 0.

b b b Здесь для отклонения скорости первой координаты сохранено обозначение q 1.

Достаточные условия устойчивости невозмущенных решений по теореме Рауса-Ляпунова по лучатся как условия знакоопределенности 2 K на многообразии V = 0. Они выглядят так:

k 0, d + a2 b2 0. Поскольку первое условие всегда выполняется, если система механиче ская, то остается одно условие: d + a2 b2 0.

Сопоставляя это условие устойчивости с условиями устойчивости соответствующих нашим движениям положений равновесия редуцированной системы (bp = ), легко обнаруживаем из вестный факт, что они совпадают. Граница устойчивости соответствует точкам бифуркации вы деленных семейств стационарных движений, где от стационарных решений первого типа ответв ляются стационарные решения второго типа. В этих точках 2 K содержит только вариации ско ростей. Анализ здесь можно продолжить, привлекая члены более высокого порядка в разложении K.

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

Теперь заметим, что при анализе устойчивости стационарных решений второго типа уравне ний Эйлера-Лагранжа вторая вариация K в окрестности интересующих нас элементов указанных семейств решений,как и в случае уравнения Рауса, не содержит вариации координаты q 2. Но здесь возможно, в отличие от редуцированного случая, привлечь для анализа устойчивости более вы сокие члены разложения K. На этом исследовании в данной работе мы из-за ограниченности места останавливаться не будем.

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

Наконец, обратим внимание на то, что для линейных дифференциальных уравнений Рауса всегда существует общее решение, выражаемое в элементарных функциях. В частности, пери одическое по позиционным координатам, которое может быть поднято в фазовое пространство исходных уравнений Эйлера-Лагранжа. Это совсем просто видеть в случае лагранжиана (8).

Действительно, уравнение Эйлера-Лагранжа по позиционной координате здесь имеет вид:

(aq2 + b)(mq2 q1 + ((ak + m2 )q2 + kb)2 ) + aq2 q1 + m2 bq2 q2 + (aq2 + b)dq2 = 0.

2 2 2 q Исключая из этого уравнения переменную q1 и ее производную с помощью циклического интеграла q1 = p(aq2 + b) mq2 q2, получим дифференциальное уравнение относительно q2, совпадающее с уравнением Рауса (9).Что и доказывает в данном случае наше последнее утвер ждение. Условия устойчивости обсуждаемых решений, как известно, совпадают с условиями устойчивости тривиального решения нашей линейной системы.

Список литературы [1] А.В.Борисов, И.С.Матвеев Пуассоновы структуры и алгебры Ли в гамильтоновой механике.

Ижевск: Изд. дом "Удмуртский университет", 1999, 460c.

[2] В.И. Елкин Редукция нелинейных управляемых систем. М.: ФАЗИС-ВЦ РАН, 2003, 208c.

[3] Ф.Гриффитс Внешние дифференциальные формы и вариационное исчисление Н.: НФМИ, 1999, 358 с.

[4] А.И. Лурье Аналитическая механика. М.: ГИФМЛ, 1961, 824с.

ON ONE CLASS OF THE EULER-LAGRANGE EQUATIONS V.D. Irtegov Institute of Systems Dynamics and Control Theory Siberian Branch, Russian Academy of Sciences, Irkutsk. e-mail: irteg@icc.ru Abstract. The article represents a class of variational problems for which the lagrangians may be reduced to quadratic ones. The peculiarities of qualitative analysis of Euler-Lagrange equations are discussed. The analysis of the indicated equations are performed with the aid of reduced equations which correspond to initial ones.

Key words: Euler-Lagrange equations, reduction, stationary solution, stability.

ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ НА МНО ЖЕСТВЕ НОМИНАЛОВ ПАРАМЕТРОВ В ЗАДАЧЕ ПАРАМЕТРИЧЕСКОГО СИНТЕЗА Я.В. Катуева Институт автоматики и процессов управления ДВО РАН, Владивосток e-mail: gloria@iacp.dvo.ru Аннотация. В статье рассмотрена задача выбора оптимальных параметров аналоговых технических устройств и систем по стохастическим критериям. Предложен параллельный алгоритм дискретной оптимизации на множестве номиналов параметров, ориентированный на массивно-параллельные суперкомпьютеры.

Ключевые слова: оптимизация, надежность, параметрический синтез, параллельные алго ритмы.

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

1. Постановка задачи Задача оптимального параметрического синтеза [1] состоит в выборе номинальных значений внутренних параметров исследуемого устройства xnom = (x1 nom,..., xn nom ), обеспечивающих максимум вероятности его безотказной работы в течение заданного времени:

xnom = arg max P {X (xnom, t) Dx, t [0, T ]}, (1) где X (xnom, t) - случайный процесс изменения параметров;

Dx - область работоспособности;

T - заданное время эксплуатации устройства. Область работоспособности D x, как правило, неиз вестна, поэтому условия работоспособности обычно задаются системой неравенств:

aj yj (x) bj, j = 1,..., m, (2) {yj }m где y = - вектор выходных параметров устройства, причем yj = Fj (x1,..., xn ), а Fj (•) j= известный оператор зависящий от топологии исследуемого устройства.

В качестве количественного показателя надежности принимается вероятность:

P (Y(t) Dy, t [0, T ]) = P (y(X(t)) Dy, t [0, T ]) = Работа выполнена по программе фундаментальных исследований ОЭММПУ РАН "Проблемы анализа и синтеза интегрированных технических и социальных систем управления" = P yj (X(t)) [aj, bj ]t [0, T ], j = 1, m.

При t = 0 данное выражение служит для оценки серийнопригодности. Каждый шаг оптимизации требует проведения статического анализа для получения оценки критерия оптимальности. При этом на основе метода статистических испытаний (Монте-Карло) многократно рассчитывается исследуемая система (устройство) для различных значений случайных параметров элементов.

Если условия работоспособности выполняются, то реализация относится к числу хороших, в противном случае - плохих. Оценкой служит отношение числа хороших реализаций к общему числу реализаций случайных параметров элементов. Число расчетов N, равное числу реализа ций случайного вектора параметров, определяется из условия обеспечения необходимой точности оценки критерия. Обычно для этого на каждом шаге поиска проводится полный расчет системы от нескольких сотен до тысячи раз. Заметим, что в процессе статистических испытаний и на на каждом шаге поиска экстремума приходится проверять выполнение условий работоспособности (2).

Для расчета целевой функции (вероятности безотказной работы) привлекается метод крити ческих сечений [1], который основан на возможности представления случайного процесса Y (t) конечным числом случайных величин Yt, получаемых во временных t-сечениях исследуемого про цесса. Использование данного метода позволяет отнести реализацию системы к "хорошим"или "плохим"для всего заданного времени эксплуатации.

Если реализация процесса обладает вышеописанным свойством, то P (T ) = P {[a Y (t0 ) b a Y (t1 ) b... a Y (tK ) b]}, где a, b - заданные границы допуска;

t0, t1,..., tK - точки локальных экстремумов реализации на интервале [0, T ] (критические сечения), t0 = 0, tK = T.

Для монотонных случайных процессов изменения выходных параметров системы Y (t) веро ятность невыхода Y (t) за пределы [a, b], в течение заданного времени определится следующим образом:

P (T ) = P [a Y (0) b a Y (T ) b].

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

Число моделирований системы в точке при использовании метода критических сечений для линейных процессов изменения параметров можно представить как N tm + N P (x, 0)tm = tm (N + ng1 ), где P (x, 0) - серийнопригодность системы, tm - среднее время моделирования системы и про верки условий работоспособности, ng 1 - число точек, попавших в область работоспособности на первом временном сечении. Общие временные затраты решения задачи параметрического синтеза tp можно оценить следующим образом:

tI + M (to + N tm ) tp tI + M (to + KN tm ) где tI - накладные расходы на ввод-вывод, инициализацию системы, чтение данных, формиро вание модели устройства;

N - число моделирований системы методом Монте-Карло;

K - число критических временных сечений;

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

M - число шагов оптимизации;

to - накладные расходы на один шаг оптимизации.

Приведенную выше задачу можно считать классической оптимизационной задачей, в качестве целевой функции выступает вероятность безотказной работы объекта, а ограничениями являют ся условия эксплуатации и область реализуемых значений параметров устройства. Из-за того, что целевая функция вычисляется методом Монте-Карло с использованием метода критических сечений, не представляется возможным изучить специфику области допустимых решений и ре льеф целевой функции. Поэтому применение к задаче (1) методов оптимизации с порядком выше нулевого невозможно.

Распараллеливание вычислений на этапе получения оценки целевой функции дает высокую эффективность и ускорение, близкое к линейному при решении данной задачи на вычислите лях массивно-параллельного типа с использованием специальных библиотек параллельных ге нераторов случайных чисел [2]. Однако, эффективность данных алгоритмов часто ограничена характеристиками времени выполнения типового процесса, при большом количестве пробных точек (шагов оптимизации) будет существенно увеличиваться доля и время межпроцессорных обменов, поэтому более эффективной с точки зрения параллельных вычислений будет декомпо зиция алгоритма на более высоком уровне - непосредственно на этапе оптимизации. Поскольку номинальные значения параметров схемных элементов должны принадлежать ряду стандартных значений, регламентируемых техническими условиями или ГОСТами, иногда предпочтительнее искать оптимальный вектор номиналов параметров на дискретном множества номиналов, соот ветствующих стандартным значениям. Процедура полного перебора множества возможных ти пономиналов параметров соответствует дискретной (комбинаторной) оптимизации в задаче (1) или методу сканирования пространства поиска. Данный метод не зависит от вида и характера целевой функции, имеет цикличную поисковую процедуру и представляет возможность всегда найти глобальный экстремум.

Пусть известны множества типономиналов для каждого из n варьируемых параметров схем ных элементов исследуемого устройства:

nom1 = x1, x2,..., xr1, x1 x2... xr1 ;

... ;

11 1 1 1 nomn = x1, x2,..., xrn, x1 x2... xrn.

11 1 1 1 Определим дискретное множество Dn om, как множество возможных сочетаний типономина лов параметров:

Dnom = {x nom : x1 nom1,..., xn nomn }, n аL= - число элементов множества Dnom.

i=1 ri Тогда задача (1) будет эквивалентна задаче поиска номинала на дискретном множестве воз можных сочетаний типономиналов x opt = max Pr (xnom ).

nom xnom Dnom 2. Метод решения Решение данной задачи предлагается провести как двухэтапную параллельную процедуру.

На первом этапе предлагается уменьшить пространство поиска, проведя аппроксимацию об ласти работоспособности описанным параллелепипедом. Для этого определим брус допусков в пространстве параметров Rn B d = x Rn | x1 xi xrn, i = 1, n.

i i Используя изложенный в [3] параллельный алгоритм построения описанного бруса построим брус B0 Bd B 0 = x Rn | a0 xi b0, i = 1, n, i i где a0 = min xi ;

b0 = max xi.

i i xDx xDx Сформируем дискретное множество внутренних типономиналов параметров int Dnom = B0 Dnom, Dnom = x int : a0 x1 b0, xi nomi, i = 1, n.

int nom i i i Произведем упорядочивание типономиналов параметров:

a 0 x 1 x 2... x l1 b 0, 1 1 1...

a 0 x 1 x 2... x ln b 0.

n n n n n int Число R элементов множества Dnom вычисляется по формуле n R= li.

i= В общем случае R L.

В каждой точке x int дискретного множества Dnom необходимо найти оценку Pr x int. Ис int nom nom opt комый оптимальный вектор номиналов x nom находим, решая задачу:

x opt = maxup Pr x int.

nom nom xint Dnom nom Данная задача доставляет решение задачи параметрического синтеза (1) на дискретном мно жестве номиналов параметров.

В простейшем случае нахождение решения задачи сводится к полному перебору элементов множества Dnom, для каждого из которых ищется оценка вероятности Pr x int. Данный процесс int nom полного дискретного перебора составляет суть метода сканирования, относящегося к регулярным методам поиска.

Оценим общую трудоемкость задачи дискретной оптимизации в случае полного перебора эле int ментов множества Dnom. Если для получения оценки методом Монте-Карло для каждого элемен int та множества Dnom необходимо провести N испытаний, то общее число испытаний схемы составит от RN в случае оптимизации серийнопригодности до RN K при оптимизации параметрической надежности (где K - число временных сечений ).

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



Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.