Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

S 2]

•Схема Н. Н. Моисеева

191

Можно показать, что при некоторых ограничениях решение

дискретной задачи (5 )— (8) при измельчении шага

сетки

(точнее,

при

max

|/{+1 — 1( |- * 0 (N->~oo)) будет близко

в

некотором

0<£<ЛГ—1

смысле к решению непрерывной задачи (1) — (4); (см. гл.

9).

Следует, однако, сказать, что аналитическое выражение для

Bh(x),

uu(x)

при всех х ^ Х к в общем случае найти

не

удается,

используя какие-либо методы

минимизации функций

(например,

методы из гл. 1, 2). Согласно

(13) при вычислении Bh(x) нужно,

знать значения B k+\{Fk {x,u))

при некоторых ы, и здесь возможны

случаи,

когда точка

xk+i — Fk (x,u) не

принадлежит заранее выб­

ранному

множеству

узловых

точек,

а следовательно,

значение

В к+2 (х),

..., B N(x)

в новых дополнительных точках. На практике

в таких

случаях

недостающее значение Вк+\ (х) получают с по­

будем

называть

шкалой состояния и обозначать

через Я,-,

i = О,

1, ..., N. Шкалы состояний

H i

и H i+ i будем называть соседними.

На двух

соседних

шкалах

H i

и Яг+i

возьмем

точки х ^ Я г- и

у ^ Н {+ 1

и

рассмотрим

вспомогательную

задачу:

минимизировать

функционал

■ *1+1

/° (х (t), и [t), t) dt (х, у — фиксированы)

Jt (х, у, ц) =

j

(1)

192

ДИНАМ И ЧЕСКО Е ПРОГРАММИРОВАНИЕ.

ПРОБЛЕМА

СИНТЕЗА

\Гл.

4

при[условиях

x(t) =

/ (х (t), и (t),t),

ti <

t <

^i+1, *

(<t) =

х,

х (ti+i) =

у,

(2)

x ( t ) e o ( t ) ,

ft < f <

f , +lt

(3)

u(t)

кусочно-непрерывна и u(t)^V (t) при ^

< ti+l,

(4)

i= 0 ,

1,

N— 1. Следуя

[171],

задачу

(1)— (4)

будем

называть

элементарной операцией,

соединяющей точки х н у .

Через Ai(x,y)

обозначим

множество всех управлений

u(t)

из

(4),

для которых

соответствующая траектория

x(t) удовлетворяет

всем

условиям

(2) — (3). Положим Мь{х, у)

=

inf J i( x ,y ,u ) ;

если Ai { x , y ) = 0 ,

то будем считать М{(х, у) =

+ оо по определению.

Пусть все точки всех соседних шкал попарно соединены эле­

ментарными операциями.

Если

inf

J, (х, у, и)

достигается на

Д£(*.у)

некотором

управлении Ui(t)^Ai(x,y)

и соответствующей траекто­

рии Xi(t),

то величина

N— 1

£ Mi (ха г *ч -1./ш ) +

Ф (jcjv./дг), 4 i ,

= *

£=0

N— 1

Mi (xij., x i+ l,j.+i) + Ф (xN,jN)

£

i=0

по всевозможным наборам точек

(*o./. = x>*i./„ •••. xn.iN),

xi,i;

(f =

0, 1,

. . . , TV)

при всех х е Я 0..

Такая

аппроксимация

задачи

(1.1—4) имеет

смысл, конечно,

и в

том

случае,

когда

inf

(х, у, и) не дости-

194

Д ИНАМ И ЧЕ СКО Е ПРОГРАММИРОВАНИЕ. ПРОБЛЕМА

СИНТЕЗА

[Гл.

4

у) + С Л+1 (у) + Е .

В силу произвольности

ТОЧКИ

y<=Hk+1

и

величины е > 0 , отсюда имеем неравенство (6).

Теперь покажем, что в (6) на самом деле

знак

неравенства

можно заменить знаком

равенства. По определению

Ск(х) для

ходит

через точку уе ^ Н к+ь Ясно,

что отрезок

этого пути

от уЁ

до HN не меньше Ch+i(ye ), и

поэтому весь путь от х до

HN не

меньше Mh (x, г/е)+ С л + 1 (Ув).

Следовательно,

Мк(х,уе)~|-

+ Cft+1 (Уе)<^,Ск (х) + е . Так как

(/еЕ Я Л+|, то отсюда имеем

inf {Мк (х, у ) +

Ck+l(y)}<£Ck (x) + E

y£Hk+i

3.

Соотношения (5)

могут быть использованы

так же, как

уравнение

Веллмана (1.13).

Опишем порядок работы

с этими со­

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

состояний

Hi, i = l , 2,

..., N, содержит конечное число pi точек. Заметим, что в

этом

случае в (5) вместо inf можно писать min. Функция CN(x) =

= Ф

(*), хe tfjv нам известна. Для вычисления CN_i(x) с помощью

min [MN- X(x, у) -f Ф (у)] =

Cw- i (х),

y£HN

а также точку y ^ y N-\{x)^.HN, на которой этот минимум

дости­

гается.

Если Ch+i(x) и у — ук+\{х) при х<=Нк+\ уже

известны, то

для вычисления

Ск {х), x ^ H h соединим элементарными операция­

ми всевозможные

пары

точек из шкал

Нк и Нк+1.

Перебором

pk-Ph+i

величин Мк (х,у) + Ск+\(у) при всех x ^ H k, у ^ Н к+1 найдем

min. [Mk (х, у) + Сш

(у)]

=

Ск(х),

у^нк+1

а также

точку

у =

yk (x) £ Hk+1, х ^ Н к, на

которой

этот минимум

достигается, и т. д.

для всех k = N, N —

1, . . .

, 1., 0.

На

вычисле­

ние всех Ск (х) и у = ук (*)

при x £ H k, k — 0,

1,

.. - , N —

1,

понадо-

N —1

р; ■pi+i величин. Наконец,

х' 6 Н0 из

бится перебор

находим

условия

С0 (х*) =

£=0

inf С0 (х) . Для этого нужно перебрать еще р0величин.

*ея„