Динамическое
программирование
и современная
теория управления
Р. БЕЛЛМАН
Р. КА Л А Б А
Динамическое
программирование
и современная
теория управления
Р. ВЕЛЛМАН
₽. КАЛАБА
Перевод с английского
Е. Я. РОЙТЕНБЕРГА
Под редакцией
Б. G. РАЗУМИХИНА
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1969
6 Ф 6.5
Б 43
УДК 62-50
3-3-4
139-69
DYNAMIC PROGRAMMING
AND MODERN
CONTROL THEORY
Richard Bellman
UNIVERSITY OF SOUTHERN CALIFORNIA
LOS ANGELES, CALIFORNIA
Robert Kalaba
THE RAND CORPORATION
SANTA MONICA, CALIFORNIA
ACADEMIC PRESS
New York and London
ОГЛАВЛЕНИЕ
Предисловие редактора перевода.............. 6
Предисловие авторов......................... 7
Глава I
Многошаговые процессы....................... 9
1.	Введение............................... 9
2.	Системы................................ 9
3.	Многошаговые процессы.................. И
4.	Редукция информации................... 13
5.	Независимость от прошлого............. 14
6.	Рекуррентные соотношения.............. 15
7.	Бесконечные процессы.................. 18
8.	Процессы с заданными правилами остановки 19
9.	Нестационарные процессы............... 20
10.	Обсуждение............................. 22
И. Непрерывные многошаговые	процессы . .	22
12.	Траекторный процесс.................... 24
13.	Неоднородная атмосфера................. 27
14.	Причинность............................ 28
15.	Стохастические процессы................ 29
16.	Корреляция............................. 30
17.	Наблюдения при наличии шумов........... 31
18.	Скрытые переменные..................... 32
19.	Индуцированные процессы................ 33
20.	Косвенные и индуцированные	процессы . .	34
21.	Более общие стохастические	процессы	35
22.	Заключение............................. 36
23.	Библиография и комментарии............. 36
Глава II
Многошаговые процессы принятия решений 40
1.	Введение.............................  40
2.	Многошаговый	процесс	принятия решений 41
3.	Стратегия............................ 42
4.	Сепарабельные	критерии................ 43
5.	Принцип оптимальности................. 44
6.	Примеры.............................   44
7.	Другой вывод основного функционального
уравнения..................•.............. 46
4
ОГЛАВЛЕНИЕ
8.	Что является решением?................... 46
9.	Непрерывный многошаговый процесс приня-
тия решения................................ 47
10.	Вариационное исчисление................. 48
11.	Геометрические аспекты.................. 51
12.	Стохастический многошаговый процесс при-
нятия решения.............................. 52
13.	Управление с обратной связью............ 53
14.	Анализ уравнений........................ 54
15.	Последовательные приближения............ 55
16.	Приближение в пространстве стратегий	56
17.	Квазилинеаризация....................... 57
18.	Аналитические и вычислительные проблемы 58
19.	Принцип Ферма и уравнение эйконала	59
20.	Наикратчайшие пути через сети........... 61
Библиография и комментарии.................. 65
Глава III
Вычислительные аспекты...................... 63
1.	Введение................................. 68
2.	Цифровые вычислительные машины.........	68
3.	Численное решение процессов динамического
программирования........................... 69
4.	Приближения в пространстве	фуйкций	71
5.	Приближение в пространстве стратегий . .	72
6.	Вычислительная осуществимость............ 72
7.	Аппроксимация полиномами................. 73
8.	Устойчивость вычислительного	процесса	75
9.	Обсуждение..........................  .	77
10.	Задача о замене оборудования............ 77
Библиография и комментарии.................. 82
Глава IV
Аналитические результаты в теории управления
и теории связи	84
1.	Введение................................. 84
2.	Управление с обратной	связью........... 84
3.	Скалярный случай......................... 85
4.	Обсуждение............................... 87
5.	Стохастический вариант................... 88
6.	Обсуждение............................... 89
7.	Многомерный детерминированный случай . .	89
8.	Непрерывный случай.................... 91
9.	Теория прогнозирования................ 95
10.	Передача информации.................... 97
11.	Эффективный игрок....................   97
12.	Применение метода динамического програм-
мирования .................................. 99
13.	Обсуждение............................ 101
Библиография и комментарии................ 101
ОГЛАВЛЕНИЕ	5
Глава V
Процессы управления с адаптацией.......... 105
1.	Введение.............................. 105
2.	Линейный процесс управления с адаптацией 106
3.	Аналитическая формулировка............ 107
4.	Аналитические аспекты................. 109
5.	Обсуждение............................. ПО
6.	Априорная функция распределения	....	110
7.	Игра с адаптацией..................... 111
8.	Задача о двуруком бандите............. 112
9.	Общая формулировка.................. 114
10.	Задача оценивания..................... 115
11.	От функционалов к функциям............ 116
12.	Более общие процессы с адаптацией	116
Библиография и комментарии................ 117
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлагаемая вниманию читателей книга содержит
изложение и различные приложения одного из важней-
ших методов исследования управляемых процессов —
метода динамического программирования. Возможность
единого подхода к изучению процессов различной фи-
зической природы, как детерминированных, так и сто-
хастических, дает основание рассматривать книгу как
введение в математическую теорию управляемых про-
цессов.
Задачи управления процессами,, изучаемыми в физи-
ке, технике, экономике и биологии, требуют как совер-
шенствования аналитических методов, так и создания
достаточно простых математических моделей изучаемых
процессов. Оба пути имеют одну цель — получение со-
держательных численных результатов современными ог-
раниченными вычислительными средствами. Поэтому
большой интерес представляют обсуждения вычислитель-
ных аспектов теории управления. В книге обсуждаются
численные методы решения функциональных уравнений
метода динамического программирования, такие как ме-
тод последовательных приближений в пространстве функ-
ций, характеризующих процесс, или в пространстве стра-
тегий, метод аппроксимации искомых функций полино-
мами или системой ортонормированных функций и т. д.
Значительный интерес представляют рассмотренные
в книге примеры. Написанная с большим педагогиче-
ским мастерством, книга, несомненно, будет полезна
широкому кругу читателей, интересующихся проблема-
ми управления.
Б. С. Разумихин
ПРЕДИСЛОВИЕ АВТОРОВ
Цель этой книги более обширна, чем это указано в
ее названии. Нашей целью было дать введение в мате-
матическую теорию процессов. Процессы, изучаемые в
физике, технике, экономике, биологии, обладают мно-
жеством запутанных специальных особенностей: вектор
состояния может иметь конечную или бесконечную раз-
мерность, переход из одного состояния в другое может
быть детерминированный или стохастический; может иметь-
ся возможность влиять на процесс; возможно наличие
или отсутствие конкурирующего влияния; система управ-
ления может оказаться способной изучать в процессе
управления неизвестные стороны процесса. Для вдумчи-
вого исследователя существенно знать, как объединить
эти и многие другие свойства вместе в математические
модели ситуаций, которые мы желаем изучить. Помимо
этого, он должен быть в курсе возможностей и ограниче-
ний современных вычислительных машин и прямой взаи-
мосвязи между теоретическими формулировками и чис-
л енными р ешениями.
В некотором смысле построение реалистических мате-
матических моделей является простым. Реалистические
модели имеют, однако, неприятную особенность быстро
исчерпывать память и скоростные возможности совре-
менных вычислительных машин. Можно достичь прогрес-
са либо при искусном упрощении математической моде-
ли, позволяющем получить содержательные численные
исследования, либо когда аналитические достижения поз-
воляют изучить класс процессов, которые ранее счита-
лись слишком сложными.
Глава I посвящена общему описанию многошаговых
процессов, как детерминированных, так и стохастических,
как непрерывных во времени, так и дискретных. Это дает
нам возможность ввести идею о рекуррентных соотноше-
8
ПРЕДИСЛОВИЕ АВТОРОВ
ниях и наблюдать их в действии в различных условиях.
В главе II мы рассматриваем многошаговые процессы
принятия решения, в которых целью является получение
последовательности решений в течение процесса так,
чтобы максимизировать выигрыш от процесса. Теорети-
ческой структурой здесь является структура динамиче-
ского программирования. Приведены краткие экскурсы
в вариационное исчисление, теорию управления с обрат-
ной связью и математическую физику.
Глава III рассматривает ряд вычислительных аспек-
тов динамического программирования. Обсуждается ряд
теоретических вопросов, включая устойчивость числен-
ных методов и возможность понижения требований к
памяти, приводится программа для задачи о замене обо-
рудования. В главе IV мы обращаемся к некоторым про-
цессам передачи информации и процессам управления,
для которых можно получить аналитические результаты
в явном виде. Они играют роль трамплина для перехода
к рассмотрению более реалистических моделей при помо-
щи метода последовательных приближений.
Последняя глава вводит в новую увлекательную тему—
управление с адаптацией. В таких процессах система
управления одновременно влияет на течение процесса и
изучает неизвестные стороны этого процесса. Эта наука
пока переживает свое детство, но много обещает в буду-
щем.
Во всех главах мы приводим много задач, которые
потенциально делают книгу приемлемой как для учебной
аудитории, так и для самостоятельного изучения. Мы
надеемся, что настоящая книга будет стимулировать
читателя к применению изложенных методов в других
областях и к созданию новых методов для глубокого
проникновения в сложные процессы путем сочетания
современных вычислительных устройств и современных
математических теорий.
Ноябрь 1965
Санта Моника, Калифорния
Ричард Беллман
Роберт Калаба
Глава I
МНОГОШАГОВЫЕ ПРОЦЕССЫ
1.	Введение
В этой главе мы хотим ввести определенное число
фундаментальных математических понятий, которые бу-
дут использованы в этой книге при исследовании различ-
ных типов управления и процессов принятия решений.
Термин «процесс» будет точно определен и конкретизи-
рован в различных случаях: конечном, бесконечном,
неограниченном; детерминированном, • стохастическом;
дискретном, непрерывном; стационарном и нестационар-
ном. Используя основные понятия переменных состояния
и преобразований состояния, мы продемонстрируем силу,
многосторонность и гибкость рекуррентных соотноше-
ний и других типов функциональных соотношений.
2.	Системы
Сначала нас будет интересовать изучение систем (тер-
мин, который здесь еще не определен, но интуитивно
вполне понятен) и то, как они ведут себя с течением вре-
мени. Эта точка зрения позволяет нам ввести понятие
«процесса» простым и естественным способом. Зафикси-
руем на минуту наше внимание на системах. Чисто ана-
литически мы представляем себе систему как вектор сос-
тояния х (t) и правило для определения его значения в
любой момент времени t. В этой книге мы будем иметь
дело, для простоты, только с конечномерными векторами
	®i(0 МО	
x(t) =		(2.1)
XN (О
10
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ I.
Каждая компонента х (t) определяет различные свойства
системы. Число N называется размерностью системы.
Классически величина х (t) может быть задана следую-
щим образом:
=g(x (0)	дифференциальные ура-
внения,
g — 1))	— разностное уравнение,
= h (х (t), х (t — 1))	— дифференциально-разно- (2.2)
стное уравнение,
х (t) = и (t) +	(x(s), t) ds —интегральное уравнение,
а также в виде различных комбинаций этих типов. Уравне-
ния в частных производных вводят бесконечномерный век-
тор и этим определяют более общую систему. Хотя методы,
которыми мы пользуемся, могут быть применены к изу-
чению систем более сложной структуры, ниже мы огра-
ничимся системами конечной размерности. Только при
этом мы сможем сохранить вводный характер настоящей
монографии.
Сейчас важно подчеркнуть, что то, что мы называем
состоянием системы, не определяется только лишь фи-
зическими свойствами подлежащей изучению реальной
системы. Поэтому для нас здесь не так уж необходимо
углубляться во внутреннюю характеристику системы.
Наоборот, это сильно задержит нас на весьма частных и
зачастую извилистых путях математических описаний.
Все зависит или должно зависеть от того, что мы хотим
знать о физических процессах, что мы можем наблюдать
или измерить, от точности этих наблюдений и вообще
от научного и математического уровня на сегодняшний
день. Важно подчеркнуть значение гибкости в примене-
нии математических методов в научных исследованиях.
Не существует никаких готовых аналитических методов
и никаких готовых формулировок.
В прошлом большинство аналитических работ по
прикладной математике было связано с функциональными
уравнениями указанных выше типов. Эти работы содер-
жат важные результаты и нет сомнений в том, что по-
3]
МНОГОШАГОВЫЕ ПРОЦЕССЫ
11
ставленные в классической формулировке задачи будут
продолжать играть основную роль в современной теории
управления и в других областях. Однако, как новые за-
дачи, так и новые типы задач, возникшие в результате
научной революции, которую мы переживаем, показали
что классическая теория имеет существенные ограничения.
Новые методы, совместно с развитием и обобщением ста-
рых, позволяют дать ответ на новые и более глубокие
вопросы современной науки и техники и, в частности,
сделать более полным использование в науке того мас-
тера на все руки, ученика чародея, которым является
цифровая вычислительная машина. Это замечательное
устройство даже в его нынешнем младенческом возрасте
и при нашем скудном арсенале идей по части его исполь-
зования и возможностей уже в значительной мере и без-
возвратно изменило основные каноны математики в част-
ности, и науки вообще.
Ниже мы введем некоторые простые, но достаточно
мощные математические методы, которые позволят нам
сформулировать и проанализировать ряд проблем, кото-
рые не могут быть рассмотрены в рамках обычной тео-
рии. В этой главе мы сохраним тесный контакт с класси-
ческими идеями; в последующих главах нам предстоит
стать первооткрывателями.
3.	Многошаговые процессы
Введя чисто математическое определение понятия
«система», уточним теперь другую интуитивную концеп-
цию — определим понятие «процесс». Ради общности и
ради того, чтобы не быть даже визуально связанными со
старыми понятиями, мы заменим символ х (t) символом
считая р точкой множества или пространства R. Во
всем последующем изложении в этой книге R будет мно-
жеством точек М-мерного пространства, иногда М-мер-
ного куба, иногда будет состоять из вершин этого куба.
Например, R может состоять из положительных целых
чисел 1,2,..., М и 0. Однако это не обязательно для каж-
дого из приведенных выше типов в более общей ситуации.
Рассмотрим теперь функцию Т (р) — преобразование,
обладающее свойством, что преобразованная точка
12
МНОГОШАГО ВЫЕ ПРОЦЕССЫ
[ГЛ. I
р^Т (р) принадлежит R для всех точек из R. Мы можем
представить себе, что р изображает начальное состояние
системы, Pt = Т (р) — состояние на одну единицу вре-
мени позднее и вообще система векторов
[/>> Pi, р2,—(3.1)
где рь = /?, pn+1 — Т (рп), п — 0, 1, 2,..., изображает вре-
менную историю системы, наблюдаемую в дискретные
моменты времени п = 0, 1, 2, т. е. последовательные
состояния системы. Мы можем также написать рп — Тп (р),
что обозначает n-кратное применение преобразования
Г, и иногда мы будем применять это обозначение.
Мы называем эту бесконечную последовательность
векторов, появляющуюся в (3.1), многошаговым процессом,
что, кстати, и является определением этого термина. Удоб-
но ввести обозначение [р, Т (р)] или просто [р, Т]. Более
точно, это есть многошаговый процесс дискретного детер-
минированного типа. Так как, однако, это единственный
многошаговый процесс, который мы пока указали, то
ограничимся пока более простым термином. При рассмот-
рении других типов многошаговых процессов мы отме-
тим их дополнительные особенности.
Упражнения
1.	Пустьр есть скаляр, т. е. одномерный вектор, и пусть преоб-
разование Т имеет вид Т (р) = гр, где г — действительное число.
В зависимости от значения г определить поведение рп при п -► оо.
2.	Пусть р—- двумерный вектор, т. е. р ==	и пусть преобра-
зование Т есть матрица типа 2x2 следующего вида:
|i cqs 0 sin 0
“* — sin 0 cos 0
Показать, что геометрически Т представляет собой поворот на угол 0
в плоскости (хь я2)*
3.	Каково предельное поведение ^\п_х Tn(p)/N при N ->эо как
функции угла О?
4.	Пусть и есть решение скалярного дифференциального уравне-
ния du/dt = аип пусть Т есть преобразование, определяемое выраже-
нием и (1) в зависимости от и (0). Каков аналитический вид Т? Ка-
ково предельное поведение Тп при п оо как функции от а?
5.	Рассмотрим соответствующую задачу для случая, когда х
есть вектор, удовлетворяющий векторному дифференциальному
4]
РЕДУКЦИЯ ИНФОРМАЦИИ
13
уравнению dx/dt = Ах, х (0) = с, где А есть постоянная матрица
(см. R. Bellman, Introduction to Matrix Analysis, New fork:
Me Graw-Hill Book Company, Inc., 1960, Chapter 10).
6.	Рассмотрим линейное дифференциальное уравнение и +
+ аи — f (t), и (0) = с, и запишем решение в виде и — L (t, с, f),
обозначая явно зависимость от г, с и вынуждающей функции f (t).
Показать, что
(a) L (t, с, /) = Lx (*, с) + L2 (t, f),
где
(в) (t, cr + c2) = Li (t, ci) + Lj (t, c2),
(c) L2 (t, /i -f- /2) “ ^2 (^» /1) + ^2 (£? /2)»
7.	Преобразование от функции к числу называется функцио-
налом, а преобразование от функции к функции называется опера-
тором, Величина L2 (Г, /) есть линейный функционал от /. Показать,
что u2 (Г) есть квадратичный функционал, имеющий вид
т
и2 (Г) = а (71) & + 2с $ Ь (t, Т) / (0 dt +
о
т т
+ $ 5	f dtxdti,
0
и определить функции а (Т), Ь (t, Т) лк (tt, /2, Т).
4.	Редукция информации
В большинстве случаев многошаговый процесс, пред-
ставленный выражением типа (3.1), говорит значительно
больше, чем мы желаем знать, и обычно значительно боль-
ше, чем мы можем усвоить или проанализировать. Та-
кова ирония науки — для того, чтобы понять, мы долж-
ны отбросить часть информации. Мы не можем, по край-
ней мере на настоящем уровне нашего интеллектуального
развития, пытаться преодолеть высокий уровень слож-
ности. Следовательно, мы вынуждены упрощать.
Для начала будем рассматривать только часть много-
шагового процесса, ЛГ-шаговый процесс, последователь-
ность векторов
[р, А>	(4-1)
где, как и прежде, рк+1 = Т (рк),к = 0,1,2, ...,N — 1.
Мы хотим рассмотреть свойства различных скалярных
14
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
функций, зависящих от этого процесса. Если мы предполо-
жим, что эти функции {g (/>, рг, ..., pN)} имеют самую
общую форму, то, по-видимому, мы сможем сказать очень
мало существенного. Для того чтобы получить интерес-
ные и полезные результаты, мы должны надлежащим об-
разом выбрать структуру функции g, или, что эквива-
лентно, надлежащую структуру многошагового процесса.
Заметим еще раз, что такого рода привнесенная структу-
ра не обязательно свойственна основной физической
структуре. Например, мы можем рассмотреть функции
следующих видов:
N
(a)
2=0
(с) тах/г(д),
N
(Ь)	ГМ (рд,
г=0
N-1
(d) 2 h(Pi,pi+l).
i=0
.(4.2)
Во многих случаях (а на самом деле в большинстве слу-
чаев) физические процессы сами будут подсказывать
наиболее подходящие функции для своего описания.
Каждая из приведенных выше функций имеет много фи-
зических интерпретаций, и каждая возникает при рас-
смотрении интересных и значительных физических про-
цессов.
5.	Независимость от прошлого
Прежде чем получить аналитические следствия из
природы многошагового процесса, обсудим некоторые об-
щие аспекты. Мы предполагали, что в начальный момент
времени система определяется вектором состояния р, что
в последующем наблюдении на единицу времени позднее,
вектор состояния есть р± = Т (р), в следующем наблю-
дении вектор состояния есть р2 = Т (рг) и т. д. Как след-
ствие этого предположения последующее для А-й точки
(момента времени) состояние зависит только от р^, т. е.
от состояния в момент времени к. Мы не требуем каких-
либо сведений о предыстории системы для того, чтобы
определить будущее. Мы получаем, таким образом, яс-
5]
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
15
ные понятия «прошлое», «настоящее» и «будущее» в плане
многошаговых процессов.
Другой путь введения этих понятий состоит в том,
что можно рассматривать как N-e состояние на ЛГ-м
шаге процесса, начавшегося из начального положения р,
или (2V.— &)-е состояние процесса на (7V — &)-м шаге
процесса, начавшегося из состояния рк в момент времени
к. Символически это можно записать в виде уравнения
7N	(5Д)
Это соотношение может рассматриваться как аналити-
ческая формулировка причинной связи, или, другими сло-
вами, того факта, что будущее единственным образом оп-
ределяется настоящим. Если пользоваться классической
терминологией, это есть теорема единственности.
6.	Рекуррентные соотношения
Вернемся теперь к анализу возможности выполнения
необходимых вычислений для определения указанных в
(4.2) функций. Рассмотрим сначала функцию
N
2s h(pi),	(6.1)
1=0
где h (р) — заданная функция состояния, и заметим, что
рассматриваемая функция полностью определена началь-
ным состоянием р и числом шагов ЛГ, если задано прави-
ло, посредством которого рк получается из рь1, иными
словами, если задано преобразование Т. Так как анали-
тическим переложением фразы «зависит от» является фра-
за «есть функция от», то мы введем последовательность
функций {fN (р)}, определяемых соотношением
N
In(p) = Sh(Pi) =
1=0
=	h (р) + h (Т (р)) + h (Т2 (р)) + ... + h (Т* (р)>, (6.2)
где мы позволяем N принимать значения N — 0, 1, 2,...
и полагаем, что р принадлежит множеству R. Рассмотрим
16
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
для N 1 частичную сумму
h (Т (р)) + h (Т* (р)) + ...+ h (Т* (р)).	(6.3)
Мы видим, что это эквивалентно
h (pj + h (Т (рх)) + ...+ h (Т*-1 (P1)),	(6.4)
а следовательно, и функции (P1), определяемой пос-
ледовательностью функций {fN (р)}. Из этого следует,
что fN (р) удовлетворяет функциональному уравнению
(в данном случае рекуррентному соотношению)
fa (р) = h (р) + fN^ (Т (р)), N> 1,
/о(р) = Л(р).
Аналогично, если мы обратимся к функции (4.2Ь) и
напишем
N
/Нр)=ПМр<).	(6.6)
i=0
мы получим функциональное уравнение
In (р) = h (р)	(Т(р)).	(6.7)
Мы предоставляем читателю вывод соотношения
fN (р) = max [h (р), (Т (р))], N > 1,	(6.8)
для функции от N и р
fN(p) =	(6.9)
определенной в форме (4.2с). Таким же образом соотно-
шение
fN (р) = h (р, Т (р)):+ fN-. (Т (р))	(6.10)
может быть установлено для функции (4.2d).
Упражнения
1.	Рассмотрите бесконечную геометрическую прогрессию S =
= 1 + г + г2 + ... Запишите S в виде 5 = 1 + (1 + г + г2 +«.Л
и отсюда покажите, что S = 1/ (1 —- г), если [ г | < 1.
6]
РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
17
2.	Рассмотрите бесконечную цепную дробь
5 = 1 +--1—
Покажите формально, что 5=1 + 1/5, и отсюда, что 5 = (1 + ]^5)/2
при условии, что цепная дробь сходится. Покажите, что приведенное
выше выражение может быть определено как предел конечной цеп-
ной дроби.
3.	Рассмотрите бесконечную цепную дробь
5(я)=1+------
а?8
х
Покажите, что 5 (х) = 1 +	•
4.	Покажите, что если
S <=
4+ ..У2ап+...,
то 5 ~ 2, предполагая сходимость. Еще раз покажите, что формаль-
но бесконечное выражение может быть определено как предел конеч-
ного выражения.
5.	Рассмотрите скалярное соотношение un+1 = aun + Ь, щ =
fe_0 u^' Покажите, что fN (с) есть квадратич-
ный полином пос, /дг (с) =и# са + 2и^с + wjy. Используя рекуррен-
тное соотношение // (с) = с2 + х (ас + &), определите рекур-
рентные соотношения для коэффициентов uN, цу, и исследуйте
асимптотическое поведение при N -> оо.
6.	Обобщите эти результаты на случай, когда хп+1 = Ахп+ Ь,
я* = с, где хп — вектор, А — матрица и fN (с) =	(%п> хп)-
7.	Рассмотрите скалярное соотношение
_ aun + Ь
n+1 cun + d ’
Uq= V.
Записав
„ = aNV + bN
N c№ + dN ’
получите рекуррентное соотношение для ay tby ,cN и dy и исследуй*
те его асимптотическое поведение при N оо.
18
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
8.	Покажите, что итерация преобразования Т (и) = эк-
си + d
Бивалентна возведению матрицы	в последовательные
степени.
7.	Бесконечные процессы
Соотношения, полученные в разделе 6, значительно
упрощаются для бесконечных процессов, т. е. процессов,
которыми становятся ранее рассмотренные многошаговые
процессы при 7V — ос. Поступим формально и, не рас-
сматривая пока вопросов сходимости, напишем
/(Р)= SMa).	(7.1)
г=0
Заметим, что бесконечность числа шагов исключает за-
висимость от N и таким образом устраняет одну перемен-
ную, что весьма существенно. При этом аналогично пре-
дыдущему получим
оо
/(Р) = А(р)+ 2Ш), f(p) = h(p)+f(T(p)). (7.2)
г=1
Подобным же образом, если
/ (р) = max h (pi),	(7.3)
i
то, учитывая очевидное соотношение max [^, х2, ...] =
= max [атх, max [#2,...]], мы получаем
/ (р) = max lh (р), / (Т (р))].	(7.4)
На данном этапе мы можем согласиться с тем, что бес-
конечный процесс не имеет физической реализаци. Тем
не менее он представляет собой весьма удобную аппро-
ксимацию многих сложных конечно-шаговых процессов
большой длительности. Равным образом мы можем при-
нять противоположную аргументацию и утверждать, что
все процессы не ограничены, а конечные процессы пред-
ставляют собой удобное приближение ко многим трудным
8]
ПРОЦЕССЫ С ЗАДАННЫМИ ПРАВИЛАМИ ОСТАНОВКИ 19
бесконечным процессам. Весьма важно понять то, что мы
имеем возможность выбора любой из обеих концепций,
каждая из которых имеет свои достоинства и недостатки.
Во многих случаях функция fN (р) не имеет предела
при N -> оо . В самом деле, мы говорим о некотором
«среднем» поведении, или установившемся поведении,
выражаемом асимптотическим соотношением вида
N ~gi (р)	(7.5)
при N -> оо или даже соотношением вида
fN(p)^g^p)Nh(p).	(7.6)
Вообще физическое обоснование указывает нам тип
предельного поведения, которого следует ожидать,
и функции gi и g2 имеют физический, технический или эко-
номический смысл. Мы избегаем здесь, однако, какого-
либо обсуждения этих очень интересных, важных и труд-
ных вопросов, которые требуют, вообще говоря, детального
и довольно сложного исследования.
8.	Процессы с заданными правилами остановки
Во многих важных ситуациях мы сталкиваемся с ко-
нечными процессами, в которых число шагов заранее не
фиксировано, а зависит от начального состояния, т. е.
N = N (р). При этом мы приходим к соответствующим
функциям вида
N(P)
/(Р)=2МР<).	(8.1)
1=0
Первым простым примером этого вида процессов яв-
ляется процесс, в котором при затрате ресурсов на каж-
дом шаге приходится учитывать условие, согласно кото-
рому процесс остановится, как только иссякнут ресурсы.
Аналитически это условие можно выразить посредством
ограничения вида
N
(8.2)
20
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
Другой немаловажный пример дает нам исследование
траекторных процессов. Объект продолжает движение
до тех пор, пока он не окажется на некотором заранее
обусловленном расстоянии от другого объекта. Аналити-
чески, вводя метрику в Я, обозначая через d (/>, q) рассто-
яние между двумя элементами р и q в /?, мы ставим
условием, что процесс продолжается до тех пор, пока
d (TNp, q) е, где q и 8 заданы заранее.
Процессы этой общей структуры играют важную роль
в современной технике и экономике.
Рассмотрим траекторный процесс, который оканчи-
вается, как только d (pN, q) 8. Если ввести функцию
N
f(p)=
i=0
(8.3)
где N — N (р) определяется приведенным выше прави-
лом остановки, то мы получаем
/(Р) = h(Р),	если d(р, ?)<8,1
f (Р) = h (р)+ f (Т (р)), если d (р, q) > 8. J <8-4)
При рассмотрении процессов такого вида рекуррент-
ные соотношения (функциональные уравнения) зачастую
весьма полезны. Эти процессы являются примерами не-
ограниченных процессов, которые не обязательно долж-
ны быть бесконечными процессами.
9.	Нестационарные процессы
До сих пор мы предполагали, что вид преобразования
Т (/?) не зависит от шага. Другими словами, преобразо-
вание Т оставалось неизменным с течением времени. Про-
цессы этого типа называются стационарными. Предполо-
жим, что теперь мы рассматриваем более общий случай,
где
Pn+i = Тп (рп),	(9.1)
иными словами, случай, где преобразование зависит от
времени. В этом случае соотношение (5.1) неприменимо.
Для того чтобы получить аналогичный результат, мы
НЕСТАЦИОНАРНЫЕ ПРОЦЕССЫ
21
9?
должны учитывать момент времени, в который процесс
начался. В общем виде нестационарный процесс может
быть записан
1рт» Pm+l’-’Рп» -Л	(9.2)
где
Рт+1 ~ Тт (Рт)> Pm-tz —	(pm+j), ...	(9.3)
Мы можем при этом предположить, что и соответствую-
щие функции также зависят от времени, и рассмотреть
в связи с этим функции вида
N	N
(а) 2 MPfc), (b) П М/М» (с) max М/М- (9.4)
к=т	]i=m
Чтобы применить метод функциональных уравнений,
использованный нами в предшествующих параграфах,
заметим, что состояние можно определить вектором р и
моментом времени, в который процесс начался. Поэтому
чтобы изучить функцию
N
2 W	(9.5)
/С=7П
посредством функциональных соотношений, примененных
выше, мы пишем рт = р и указываем зависимость как от
р, так и от тп, вводя функцию вида
N
fN,m (Р) = 2 ^fc(Pfc)*	(9.6)
fcssm
удовлетворяющую соотношению
/зХ,тп (р) =	(р) “Ь /1Х,т+1 (Тт (Р))*
Если N фиксировано, то можно упростить обозначения
введением новой функции
%П (р) = fx,m (р)	(9.7)
и написать
фт (р) = hm (р) + фто+1 (Тт (/>)), 0 < т < NA
<Ыр) = Ыр)-	1 ( • )
22
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
Упражнения
1.	Рассмотрите одномерную систему S, определяемую перемен-
ной состояния хп, п = 0, 1, 2, и соотношение = ахп, х0 = с,
а > 1, с > 0. Рассмотрите новую управляемую систему, опреде-
ляемую уравнением хп+1 = ахп+ у (хп), Xq = с. где у (х) = 0,
0<я < 1, у (х) — — 1, х > 1. Определите поведение хппри п -> эо
двумя способами: графическим и аналитическим. Для каких значе-
ний а хп > сю при п —> эо?
2.	Пусть fn (с) обозначает значение хп в момент времени п. По-
кажите, что
/п+1 (с) = /п + у (с)), п > О,
/о (<?) = с.
10.	Обсуждение
Вплоть до этого места мы следовали классическому
пути, проложенному Пуанкаре, Биркгоффом, Адамаром
и другими, связывающему преобразования на дискрет-
ном интервале с теорией итераций. Наши дальнейшие ре-
зультаты будут связаны с иными направлениями в обла-
сти непрерывных процессов, процессов принятия решения
детерминированного, стохастического и адаптивного типа
и других процессов, удобных в аналитическом аспекте.
11.	Непрерывные многошаговые процессы
До сих пор мы молчаливо предполагали, что система
наблюдается только в дискретные моменты времени,
и поэтому речь шла о преобразованиях только в эти момен-
ты времени. Рассмотрим теперь случай, когда состояние
системы изменяется во времени непрерывно. Для этого
используем аппарат, разработанный для дискретных про-
цессов, устремив длину интервала времени между двумя
наблюдениями к нулю.
Пусть наблюдения ведутся в моменты времени t — 0,
Д, 2Д, ..., а преобразование Т (р) имеет вид
Т (р) = р + S (р)Д + о (Д),	(11.1)
где Д есть малая величина, которую мы впоследствии
устремим к нулю. Кроме того, пусть соответствующая
функция имеет вид g (р)Д + g (Т (р))Д + ...+ g(Tn (р)) Д.
И]
НЕПРЕРЫВНЫЕ МНОГОШАГОВЫЕ ПРОЦЕССЫ
23
Другими словами, мы предположим, что как состояние
системы, так и соответствующая функция мало изменяют-
ся в течение малого интервала времени. Тогда, полагая
t = nA, мы получим следующее рекуррентное соотноше-
ние:
Л+д(Р) = ё (Р)А + ft (Р + « (р)А + о (А))- (Н.2)
Рассмотрим М-мерный случай, когда
^2
Ж2И
*$1 (#г, ^2, •••»
A'jif (#1, #2? •••»
(Н.З)
Применяя известные обозначения векторного анализа
grad f = | : J, (/, h) = 2 /Л,	(H-4)
р//^м|	i=1
мы получим из (11.2)
A(p)+^A + o(A)-g(p)A + /t(P) +
+ (grad/, 5(/>)) Д+ о(Д), (11.5)
предполагая, что функция / имеет необходимые частные
производные. Переходя к пределу при А ->0, получим
дифференциальное уравнение в частных производных
==£(/>)+ (grad ДА (р)).	(11.6)
До сих пор мы действовали формально. Чтобы строго
определить непрерывный процесс, исходя из основных
предпосылок, можно следовать различными путями. Во-
первых, можно проделать приведенный выше анализ,
показав, что дискретные последовательности {/^д (р)},
{Рпд} сходятся по-разному, когда А ->0. Во-вторых,
можно определить непрерывный процесс при помощи пе-
ременной состояния р (i), удовлетворяющей дифферен-
циальному уравнению
р'(0=А(р), р(О)=ро,	(11.7)
24
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
и соответствующей функции, определяемой дифферен-
циальным уравнением в частных производных
' 1F =	+ (grad/,<S(p)), /(О) = /о.	(11.8)
Теперь возникает задача показать, что эти определения
являются содержательными в смысле существования и
единственности решений приведенных выше уравнений и
что эти решения обладают некоторыми желаемыми свой-
ствами.
Это — нетривиальные и зачастую очень трудные воп-
росы. По этой причине мы и предпочитаем далее сосредо-
точиться на дискретных процессах. Многошаговые про-
цессы принятия решений дискретного типа приводят нас
к достаточно большому числу концепций, а также к не
меньшему количеству аналитических и вычислительных
проблем. При этом мы вовсе не обязаны отвечать на за-
частую посторонние для нас деликатные вопросы сущест-
вования и единственности, связанные с непрерывными
процессами.
Упражнения
1.	Рассмотрим следующий процесс. Частица двигается на от-
резке [0, 1] до тех пор, пока она не достигнет его граничной точки.
В этот момент времени она изменяет направление движения и дви-
жется в обратном направлении до тех пор, пока она не достигнет
другой граничной точки, и так далее. Частица начинает движение
в точке с, двигаясь вправо по закону du/dt = а > 0. Движение
влево происходит по закону du/dt = — b < 0. Найдите выражение
для положения частицы в момент времени t.
2.	Предположите, что уравнения движения имеют вид du/dt =
= au, duldt = —Ьи соответственно, и решите ту же задачу.
3.	Для каждой системы уравнений движения рассмотрите выра-
жение v (t) — и Существует ли lim v (£)? Если он существует
#->оо
как функция с, то определите его свойства и, в частности, получите
функциональное уравнение.
12.	Траекторный процесс
Чтобы проиллюстрировать некоторые из предыдущих
идей, рассмотрим простой траекторный процесс^ Предпо-
ложим, что мы бросили вверх камень со скоростью г,
12]
ТРАЕКТОРНЫЙ ПРОЦЕСС
25
движения
(12.1)
направле-
(12.2)
(12.3)
и допустим, что после этого он движется под действием
лишь силы тяжести. Обычная трактовка этого процесса
достаточно проста. Пусть х (t) обозначает расстояние
камня от земли в момент времени t. Если пренебречь вли-
янием сопротивления воздуха, то уравнение
точечной частицы имеет вид
(Рх
--= —
dp ь
(ускорение является следствием гравитации и
но вниз) с начальными условиями
х (0) = 0, х' (0) = v,
где v > 0, Решение уравнения имеет вид
х = vt —	.
Отсюда мы видим, что максимальная высота достигается
при t = vlg и определяется выражением
Хтах —	•	(^2.4)
Частица заканчивает свой полет в момент времени t =
= 2??/g, когда она достигает земли.
Достаточно просто, но имеются некоторые избыточные
подробности. Предположим, что нас интересует лишь
максимальная высота полета. Можно ли определить ее,
не касаясь информации относительно остальной части
полета? В рассматриваемой задаче это может показаться
малосущественным, но в более сложных процессах эта
экономия усилий может быть значительной, в частно-
сти, если задачей исследования является лишь опреде-
ление зависимости максимальной высоты от начальной
скорости.
Применим изложенные выше идеи для того, чтобы
ответить на поставленный вопрос. Начнем с замечания,
что максимальная высота зависит от начальной скорости
v. Поэтому введем функцию / (г?) — максимальная высо-
та, достигаемая при начальной скорости v. Рассмотрим
движущуюся частицу как порождающую непрерывный
26
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
многошаговый процесс, в котором состояние системы
есть v. Для бесконечно малого интервала времени Д пре-
образование, определяющее состояние, имеет вид
г >1	Т (г?) = v - gk. (12.5)
I л) Следовательно, мы имеем соот-
ношение (рис. 1.1)
, J	/ (г?) = v к +f(v — gA) + о (Д).
(12.6)
О	Разлагая правую часть в ряд и
полагая Д ->0, получаем
Рис- 1Л-	О = v - gf (»). (12.7)
Это — дифференциальное уравнение для / (г?) с началь-
ным условием / (0) = 0. Интегрируя, мы получаем соот-
ношение (12.4).
Упражнения
1.	Собака преследует кролика, как показано на рис. 1.2. Пусть
скорость собаки а скорость кролика vr, и допустим, что vd >vr.
Предположим, что в любой момент
времени движение кролика на- „
правлено вдоль оси ж, а собака у
бежит по направлению к кролику. D(Ojty ч.
Составьте дифференциальное
уравнение движения собаки и
сравните «решение» в классиче-
ских терминах, т. е. в виде х (t)	________________________
как функции от t, с «решением» в л
терминах поставленной здесь зада-	19 '
чи погони как процесса пресле-
дования, имея в виду получение	Рис- I-2-
численного решения.
2.	Пусть / (г, d) обозначает момент времени, в который собака
схватит кролика. Покажите, что
/	Ad2 \
/ (г, d) = Д + / (г+ Д, d —	+ 0(A),
откуда, полагая А -> О,
»=*+<
d2 df
Vr*+ (P dd ’
где / (г, 0) = г/ (vd — г?г). Подобным же образом выведите уравнение
13]
НЕОДНОРОДНАЯ АТМОСФЕРА
27
в частных производных для величины g (г, d), т. е. точки на оси х,
в которой собака догонит кролика.
3.	Примените метод характеристик для Определения / (г, d) и
g (г, d) в явном аналитическом виде.
13.	Неоднородная атмосфера
Предположим теперь, что вместо уравнения (12.1)
мы имеем уравнение вида
jjr = h(x, х'}, я(0) = 0, ъ' (0) = р, (13.1)
которое получено при учете силы сопротивления воздуха,
зависящей от положения и скорости точки. В связи с не-
однородностью атмосферы мы должны ввести дополни-
тельную переменную состояния с, равную высоте точки в
начале процесса.
Рассмотрим поэтому две переменные состояния с и v
с законом преобразования
сх = Л (с>	~ с + vi = Т2 (с, v) = v + h (с, г?)Д
(13.2)
с точностью до о (Д). Если мы введем функцию
/ (с, г?) —максимальная высота, достижимая при старте
с высоты с со скоростью v,	(13.3)
то, как и выше,
/ (с, v) = г?Д + / (с 4- ^Д, v + h (с, г?)Д) 4- о (Д).
(13.4)
В пределе при Д —> 0 мы получаем дифференциальное
уравнение в частцых производных
0 = v + v + h <с’ • <13-5>
Вообще это уравнение не может быть решено анали-
тически. Численное решение можно получить рядом спо-
собов, используя начальное условие / (с, 0) = 0, но не-
обходимо отметить, что при этом мы встретимся с рядом
28
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
тонкостей, которые требуют опыта и умения. Обсуждение
вычислительных аспектов приводится в главе III. Для
получения численного решения можно также применить
метод характеристик.
14.	Причинность
Все полученные выше уравнения являются частными
примерами соотношений, вытекающих из принципа при-
чинности, или, иными словами, из детерминизма.	J
Пусть состояние системы в момент времени t будет
представлено функцией / (с, t), где с есть состояние в
момент времени t = 0. Мы можем представить себе сис-
_	тему стартующей из состоя- j
ния с в момент времени t — 0
и продолжающей движение
-------уг-------ys+t до момента времени s + £; :
в этом случае ее конечным |
состоянием будет f (с, s + t).
Рис. 1.3.	Можно также представить
себе систему стартующей из
состояния с в момент времени t ~ 0 и продолжающей
движение до момента времени £, в котором ее состояние 1
будет / (с, £), и далее движущейся в течение дополнитель- !
ного промежутка времени $, в каковом случае ее конеч- 
ное состояние будет / (/ (с, £), $) (рис. 1.3). Мы уже J
рассматривали дискретный вариант такого подхода в \
разделе 5.	I
Детерминизм утверждает, что обе процедуры ведут к 1
тому же самому конечному состоянию. Следовательно, |
мы имеем основное функциональное уравнение |
/ (с, $ + 0 = f (/ (с, s), t).	(14.1) I
Из этого соотношения могут быть получены многие пос-
ледующие результаты, как, например, результаты раз- |
дела 11.	1
Упражнения
1.	Используйте единственность решения уравнения и9 — аи,
и (0) == с, чтобы получить функциональное уравнение для экспонен»
циальной функции ea(s+f) = eas eat.
15]
СТОХАСТИЧЕСКИЕ ПРОЦЕССЫ
29
2.	Пользуясь соответствующим результатом для векторно мат-
ричного уравнения х' = Ах, х (0) = с, получите матричный аналог
^Д(8+О _ eAs eAta
3.	Аналогично, исходя из факта, что sin t и cos t суть решения
уравнения и" + и = 0, установите формулы
sin (s t) = sin s cos t + cos 5 sin t,
cos (s + t) = cos s cos t — sin s sin t.
IS.	Стохастические процессы
До сих пор мы предполагали, что результат преобра-
зования Т состоит в переходе вектора состояния р в век-
тор состояния рг, где р± определяется через р единствен-
ным образом. Во многих случаях мы встречаемся с тем
фактом, что Т не полностью известно. Это означает, что
простая детерминированная модель, которая применялась
нами, должна быть заменена более сложной моделью.
Чтобы частично обойти преграду отсутствия информации,
обратимся к классической теории вероятностей.
Вместо искреннего признания, что нам неизвестно,
мы предполагаем, что Т есть стохастическое преобразо-
вание, которое порождает случайный вектор р19 распре-
деление вероятностей которого определяется через р.
Последовательность векторов [р, рг, р^..Л определяет
теперь дискретный многошаговый процесс стохастическо-
го типа. Из этого следует, что значения соответствующих
функций будут также случайными величинами. Для воз-
можности получения численных результатов мы будем
оперировать с математическими ожиданиями функций
этих случайных переменных. Это — стандартная процеду-
ра при изучении стохастических процессов.
Для иллюстрации этих идей начнем с, пожалуй, про-
стейшего случая, когда р^ определяется соотношением
Pt = Т (р^, rk), к = 1, 2,.	(15.1)
где р0 = р и — независимые случайные переменные
с одинаковым распределением вероятности dG (г). Пред-
положим, что мы хотим определить математическое ожи-
дание для
g (р) = g (Pl) + —+ g(PN)-	(15.2)
30	МНОГОШАГОВЫЕ ПРОЦЕССЫ	[ГЛ. I
Как и ранее, начнем с замечания, что это математическое
ожидание зависит от начального состояния р и числа ша-
гов N. Напишем тогда для N 1
fN (р) = exp [g (р) 4- g (Pi) + ... + g (pN)].	(15.3)
Г
Здесь обозначение «ехр» указывает, что математическое
г
ожидание должно быть взято относительно случайных
переменных гх, г2, ..., rN. Как и выше, предполагаемая
независимость позволяет нам заключить, что
/n (Р) = exp [g (р) + /jf-х (Т (р, гх))] =
п
= g (Р) + $ fN-i (Т (р, гх)) dG (гх),	(15.4)
где /а (Р) = g (Р)-
Упражнения
1.	Пусть ип+2 = аип + гп, где гп — случайные независимые
величины с общей функцией распределения dG (г). Обозначим
fN (с)= ехР StL-o * Покажите, что /у (с) есть квадратичный
полином по с, и, используя вышеприведенное уравнение, полу-
чите рекуррентное соотношение для его коэффициентов. Покажите,
что jN, (с} зависит только от первого и второго моментов dG (г),
т. е. от величин rdG (r)t r2dG (г) и изучите асимптотическое
поведение /п (с) при N -+ оо.
2.	Дайте обобщение на векторно-матричный случай, когда
^+1 = ^ + ^, ^о = с.
16.	Корреляция
Во многих случаях предположение о независимости
rfc является неоправданным. В качестве первого шага в
направлении учета этой зависимости предположим, что
функция распределения для гк зависит только от зна-
чения гк_х, т. е. dG (rk) = dG (rR, rk_x). В этом случае
можно выбрать в качестве переменных состояния р —
текущее состояние системы, и г0 — предшествующее зна-
чение случайной величины г. По аналогии с (15.4) имеем
fN (Р, Г0) =g(p) + J/N_x (Т (Р, ri))dG (Гх, г0).	(16.1)
17]
НАБЛЮДЕНИЯ ПРИ НАЛИЧИИ ШУМОВ
31
Имеется много .других путей учета взаимной зависи-
мости гк. Предположения, сделанные выше, являются
наиболее удобными для метода функциональных уравне-
ний, который здесь применяется.
Упражнение
Рассмотрите уравнение мп+1 = aun + rn, где распреде-
ление гп есть dG (rn, rn^x). Пусть uQ — с и r_x Ъ. Обозначим
j N (c> &) = exp	• Покажите, что
In (c, b) = uN (b)c* 4- 2vn (b)c + wN (&),
и получите рекуррентное соотношение для , vN, из рекуррент-
ного соотношения для/# (с, Ъ). Изучите асимптотическое поведение
> Уу» и W.V ПРИ jv “* °О.
17.	Наблюдения при наличии шумов
Как только мы допускаем возможность неопределен-
ности где-либо в наших исходных предпосылках, мы дол-
жны учитывать ее всюду. Предположим, что мы хотим
учесть возможность значительной неопределенности в
наблюдениях состояния системы. Проще всего предпо-
ложить, что когда мы наблюдаем р, то мы знаем, что в
действительности состояние системы есть р + г, где г
есть случайная переменная с известным распределением.
Мы можем тогда представить себе два процесса: один
[р, />1, р2> •••!—действительное состояние системы, и
второй [#, gx, д2, ...] — наблюдения, сделанные над сис-
темой, т. е. информация, которой мы фактически распо-
лагаем. Справедливы следующие соотношения:
Р =
Pl = Т (р),
Ръ = Т (Р1),
91 — Р1 + г1»
92 = Pi + Г2»
(17Л)
Рп = Т (Рп-1),
Jn — Рп + ГП’
32
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
Если мы примем наши наблюдения в качестве состояний
системы, то как видно из приведенного выше, мы получим
стохастический многошаговый процесс [g, gr, g2, ...],
где
71 = Т (q) — ги
(71 — >1) —
I (17.2)
Qn ~ Т (Уп-1 Г п-1) гп,
т, е. процесс со взаимной зависимостью между гп, типа
описанного выше. Таким образом легко получить функ-
циональное уравнение для соответствующих функций.
18.	Скрытые переменные
Если рг = Т (р, д), где q есть вектор, самое суще-
ствование которого неизвестно нам, то это может побу-
дить нас рассматривать Т как случайное преобразование
в следующем смысле. Фиксируя р и повторяя процесс
преобразования, т. е. наблюдая набор из подобных систем,
мы найдем систему величин
Рп — Т (р, qj, р12 = Т (р, ?9)t(18.1)
т. е. различные значения ръ соответствующие тому же
самому значению /?, но различным значениям д, а именно
дх для первой системы, д2 для второй системы и т. д. Воз-
можный разброс в воспроизведении рх для того же самого
значения р может заставить нас поверить, что концепция
детерминизма не имеет силы. Желаем мы или не желаем
верить в детерминированные процессы как в основное и
считать стохастические процессы исключительно мате-
матическим способом учета неизвестных или «скрытых»
переменных или мы считаем, что модель природы в ос-
новном стохастическая с детерминизмом, получающимся
в результате осреднения (снова математический прием),—
вопрос разделяемой тем или иным лицом философской
точки зрения, которая, к счастью, мало влияет на пост-
роение возникающих здесь аналитических моделей.
191
ИНДУЦИРОВАННЫЕ ПРОЦЕССЫ
33
Важно, однако, отметить еще раз, что возможен зна-
чительный дрейф от прямолинейного направления в кон-
струировании математических моделей физических явле-
ний, и было бы несчастьем позволить научному догматиз-
му препятствовать формулированию и рассмотрению
удобных математических моделей.
19.	Индуцированные процессы
Отправляясь от процессов любого из приведенных
выше типов, можно получить другие процессы разнооб-
разными способами. Прежде всего, можно отдать предпо-
чтение той структуре процесса, при которой упрощается
аналитический вид соответствующей функции или умень-
шается размерность процесса. Проиллюстрируем первый
из этих вопросов на процессе, уже рассмотренном в уп-
ражнениях. Предположим, что
N
ип+1 = аип + Ь, u0 = c,fN = S и^.	(19.1)
n=0
Легко видеть, что /n — pN + 2qNc + rNc2, где pN, qN, rN
не зависят от с. Кроме того, преобразование первоначаль-
ной переменной состояния приводит к преобразованию
переменных (pNi qN, rN) при помощи рекуррентного соот-
ношения
(с) = c2 + fN (ас + Ъ)	(19.2)
или
Рл-н = PN + 2bqN + b2rN,
Qn+i = aqN + аЬгрц
rN+1 = а2гдг + 1.
(19.3)
Вместо (19.2) мы можем использовать эти преобразования
для изучения исходного процесса. Это — важное умень-
шение размерности и увеличение аналитической гибкости,
так как мы заменяем функцию /n (с), которая определена
при —-оо< c<z оо тройкой I/zzv, rN]. Мы вернемся
к этому в главах III и IV.
2 Р. Веллман, Р. Калаба
34
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
Аналогично предположим, что мы исходим из процесса
х (/), определяемого векторным уравнением
х(0) = с,	(19.4)
где х есть A-мерный вектор, и принимаем в качестве функ-
ции состояния g (хг (Z),...» хк (Т)), т. е. функцию от пер-
вых к компонент х. Так как решение уравнения (19.4)
имеет вид
x(t) = eAtc,	(19.5)
то мы видим, что, когда речь идет об этой функции состоя»
ния, новым вектором состояния будут первые к ком-
понент еАТ с, что уменьшает размерность от N до к. Дру-
гими словами, мы можем сгустить желаемую информацию
относительно системы до набора из к чисел. Это может
быть весьма важным для приложений как с аналитиче-
ской, так и с вычислительной точки зрения.
20.	Косвенные и индуцированные процессы
Мы предполагали выше, что новое состояние рг опре-
делялось при помощи преобразования Г, примененного к
предыдущему состоянию р. В некоторых процессах ситу-
ация не столь прямолинейна. Предположим, например,
что мы имеем процесс {хп} с правилом преобразования
Яп+i = А#п, = с,	(20.1)
Здесь хп есть A-мерный вектор с комплексными компо-
нентами. Пусть xni, i = 1,2,..., А, обозначают N компо-
нент вектора хп. Образуем новую систему из N величин
1яп(|2, * == 1,2,..., N. Если А есть унитарная матрица, т. е.
,	N
2 IW= 2 /<ч12,
<=1J	b]
то можно нормировать с так, чтобы
21] БОЛЕЕ ОБЩИЕ СТОХАСТИЧЕСКИЕ ПРОЦЕССЫ	35
и, таким образом, предположить, что величины |япг|2
являются вероятностями. Система [|яп1|2,..., |хл^2] обра-
зует новый процесс с законом преобразования, не принад-
* лежащим к рассмотренному до сих пор классу. Преобра-
зования этого типа, которые могут казаться непривычны-
ми, являются основными преобразованиями квантовой
механики. Мы, однако, не будем рассматривать их здесь,
равным образом как и те интригующие новые типы про-
цессов управления, которые они порождают.
21.	Более общие стохастические процессы
Как только мы позволяем неопределенности поднять
свою вопрошающую голову, мы вводим много чрезвычай-
но интересных новых типов процессов и, соответственно,
новых типов функциональных уравнений. Укажем кратко
различные пути, которыми можно модифицировать детер-
минированные процессы для того, чтобы получить важные
стохастические процессы.
Во-первых, вместо того чтобы ограничиться преобра-
зованиями, действующими на систему в предписанные
моменты времени, можно предположить, что промежуток
времени между преобразованиями сам является случай-
ной переменной. Это приводит нас в область ветвящихся
процессов, которые содержат, как специальный случай,
процессы восстановления. Процессы этого типа имеют важ-
ное значение в ядерной физике, современной теории уп-
равления запасами, теории управления и при исследова-
нии процессов обучения.
Во-вторых, можно рассматривать стохастический про-
цесс [/?, Т (р, г)], в котором на каждом шаге имеется не-
которая вероятность того, что существующее состояние
системы не может быть наблюдаемо. Практически это мо-
жет возникнуть вследствие потери связи или отказа при-
нимающих приборов.
Процессы этого более общего типа вынуждают нас,
в частности, заменить конечномерную переменную состо-
яния на бесконечномерную, исходя из распределения веро-
ятностей. Тогда используются различные методы замены
бесконечномерного вектора конечномерным. Так, например,
можно ограничиться лишь первым и вторым моментами
2*
36
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
или, эквивалентно, средними значениями и дисперсиями
в качестве новых переменных состояния.
Как упоминалось прежде, мы здесь не вдаемся в сколь-
ко-нибудь систематическое рассмотрение процессов,
требующих бесконечномерных векторов состояния.
22.	Заключение
Целью этой главы было ввести читателя в основные
понятия математической теории процессов и систем и
дать ему возможность приобрести некоторое ощущение
знакомства с функциональными уравнениями и рекуррент-
ными соотношениями. Этим мы имели в виду облегчить
«культурный шок» от введения понятий и методов дина-
мического программирования. Так как мы преследовали
только эту ограниченную цель, мы не позволили себе
углубляться во многие интересные вопросы, связанные с
классификацией процессов, их анализом и (или) их чис-
ленным решением. При изучении стохастических процес-
сов эти вопросы приводят к понятиям достаточных и
асимптотически достаточных статистик. Довольно стран-
но, что соответствующие концепции, несмотря на их оче-
видную важность, не были формально изучены для детер-
минированных процессов.
Много еще остается сделать в этих направлениях, пред-
ставляющих плодородную почву для исследований мо-
лодых ученых. Некоторые важные статьи и книги для бо-
лее подробного знакомства с этими вопросами указаны в
библиографии.
Библиография и комментарий
§ 1.	Точное и подробное обсуждение понятия «система» со многими
выясняющими суть дела примерами дано в книге
L. A. Z a d е h and G. A. D е s о е г, Linear System Theory,
The State Space Approach, McGraw-Hill Book Company, Inc.,
New York, 1963.
§ 2.	Имеется много доступных в настоящее время книг, в которых
рассматриваются дифференциальные, разностные и интегральные
уравнения. Теорию дифференциально-разностных уравнений см.,
например, в книге
Р. Веллман и К. Кук, Дифференциально-разност-
ные уравнения, «Мир», 1967.
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
37
§ 3.	Подробное изложение классической механики имеется в книге
Дж. Д. Б и р к г о ф, Динамические системы, ГИТТЛ, Моск-
ва — Ленинград, 1941. Здесь приводятся ссылки также на
труды Пуанкаре, Адамара, Леви-Чивита и других.
§ 7. Систематическое исследование существования предельного по-
ведения приводит к ряду классических вопросов анализа, теории
устойчивости, эргодичности, асимптотичности, суммируемости и
т. д. Укажем здесь работы
П. Р. X а л м о ш, Лекции по эргодической теории, ИЛ,
1959.
Р. Б е л л м а н, Теория устойчивости решений дифферен-
циальных уравнений, ИЛ, 1954.
Н. Г. де Брейн, Асимптотические методы в анализе
ИЛ, 1961.
§10. Читатель, интересующийся вопросами итераций, может обра-
титься к трудам
J. Hadamar d, Two Works on Iteration and Related Ques-
tions, Bull. Amer. Math. Soc., vol., 50, 1944, pp. 67—75.
T. E. Harris, The Theory of Branching Processes, Pren-
tice-Hall, Inc., Englewood Cliffs, New Jersey, 1964. '
§ 11. Много усилий в современной теории дифференциальных урав-
нений с частными производными посвящено обоснованию аппрокси-
мации непрерывных процессов дискретными процессами, которые
легче изучить при помощи цифровых машин. См., например,
G. Forsythe and W. W a s о w, Finite-Difference Me-
thods for Partial Differential Equations, John Wiley & Sons,
New York, 1960.
Более сложное введение в теорию непрерывных многошаговых про-
цессов может быть построено при помощи непрерывных групп преоб-
разований — теории Софуса Ли. Для первого знакомства см.
Е. L. Ince, Ordinary Differential Equations, Dover Publi-
cations, New York, 1944.
L. P. E i s e n h a r t, Continuous Groups of Transformation,
Dover Publications, Inc., New York, 1961.
§§ 12—13. Этот подход разобран в работе
R. Bellman, Functional Equations and Maximum Range,
Quart. Appl. Math., vol. 17, 1959, pp. 316—318.
§ 14. См. также обсуждение в главе 2 книги
Р. Веллман, Процессы регулирования с адаптацией,
«Наука», 1964, а также
J. Hadamar d, Lectures on Cauchy’s Problem in Linear
Partial Differential Equations, Dover Publications, New York,
1953.
Современная теория полугрупп ведет свое начало от работы Адамара,
рассмотренной в книге.
Э. Хилл, Функциональный анализ и полугруппы, ИЛ,
1951.
38
МНОГОШАГОВЫЕ ПРОЦЕССЫ
[ГЛ. I
Классическая теория основывается на времени, как на переменной
полугруппы. Теория инвариантного погружения содержит анало-
гичные функциональные уравнения в пространстве переменных сос-
тояния; см., например,
R. Bellman, R. К а 1 a b a and G. М. W i n g, Inva-
riant Imbedding and Mathematical Physics — I: Particle Pro-
cesses, J. Math. Phys., vol. 1,1960, pp. 280—308.
G. M. Wing, An Introduction to Transport Theory, John
Wiley and Sons, New York, 1962.
Для подробного ознакомления с теорией функциональных уравне-
ний рекомендуем
J. Aczel, Vorlesungen uber Funktionalgleichungen und
ihre Anwendungen, Birkhauser, Basel, 1961, English trans-
lation, Academic Press Inc., New York, 1965.
§15. Введение в теорию стохастических процессов и их применения
можно найти в работе
А. Т. Bharucha-Reid, Elements of the Theory of
Markov Processes and Their Applications, McGraw-Hill Book
Company, Inc., New York, 1960.
§ 18.	Вопрос о скрытых переменных вызвал много споров, начиная
с развития квантовой механики. См. по этому вопросу
L. deBroglie, Nonlinear Wave Mechanics, A Causal
Interpretation, Elsevier, Amsterdam, 1960,
где могут быть найдены также многие дополнительные ссылки.
§19.	Рекомендуем
R. Bellman and R. К а 1 a b a, Reduction of Dimensio-
nality, Dynamic Programming and Control Processes, J. Basic
Engr., vol. 83, 1961, pp. 82—84.
§ 20.	Детальный разбор приведен в статье
Е.	Montroll, Markoff Chains, W iener Integrals and Quan-
tum Theory, Comm. Pure Appl. Math., vol. 5, 1952, pp. 415—
453.
§ 21.	См. цитированную книгу Харриса, а также
К. J. Arrow, S. Karlin and H. Scarf, Studies in
the Mathematical Theory of Inventory and Production, Stan-
ford University Press, Stanford, California, 1958.
О «прерывающихся» процессах управления —
R. Bellman and R. К a 1 a b a, Interrupted Stochastic
Control Processes, Information and Control, vol. 4, 1961,
p. 346-349.
§ 22.	Читатель , интересующийся этими вопросами, может обратить-
ся к следующим работам:
R. Bellman, С. Clark, С. Craft, D. Malcolm
and F. Ri с с i а г d i, On the Construction of a Multi-person,
Multi-stage Business Game, Operations Research, vol. 5, 1957,
pp. 469—503.
Библиография и комментарий	39
R. Bellman and Р. В г о с к, On the Concepts of a Prob-
lem and Problem-solving, Amer. Math. Monthly, vol. 67, 1960,
pp. 119—134.
R. Bellman, Directions of Mathematical Research in
Nonlinear Circuit Theory, IRE Trans, on Circuit Theory, vol.
CT-7, 1960, pp. 542-553.
R. Bellman, Mathematical Model-making as an Adaptive
Control Process, Mathematical Optimization Techniques, R.
Bellman ed., University of California Press, Berkeley, Califor-
nia, 1963,pp. 333—339.
R. Bellman, Mathematical Experimentation and Biolo-
gical Research, Federation Proc., vol. 21, 1962, pp. 109—111.
R. Bellman, Dynamic Programming, Intelligent Machines,
and Self-organizing Systems, Proc, of the Symposium on Mat-
hematical Theory of Automata, 1962, Polytechnic Institute of
Brooklyn.
Глава II
МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИИ
1.	Введение
Мы теперь подготовлены к изучению многошаговых
процессов принятия решений, иными словами, теории
динамического программирования. Эти процессы являют-
ся математически важными по своему существу, как есте-
ственное и далеко идущее обобщение преобразований,
изучаемых в классическом анализе. Кроме того, как мы
увидим ниже, они занимают фундаментальное положение
в современной теории управления.
Для того чтобы перейти к теории динамического про-
граммирования, мы присоединим концепцию решение к
концепции многошаговый процесс. Как и выше, изложение
будет главным образом посвящено представлению абст-
рактных идей, в то время как упражнения будут со-
держать ряд примеров, иллюстрирующих методы, вме-
сте со ссылками на первоисточники для дальнейшего
чтения.
Важным новым понятием является понятие страте-
гии. В аналитических терминах оно приводит к некоторо-
му типу последовательных приближений, неизвестному
в классическом анализе, а именнот приближениям в про-
странстве стратегий. Это в свою очередь, как мы покажем,
приводит к аппарату квазилинеаризации, очень мощно-
му и гибкому подходу ко многим типам нелинейных функ-
циональных уравнений.
В главе III мы рассмотрим применение динамического
программирования в качестве вычислительного алгорит-
ма, способного давать численные ответы на численные
вопросы. В главе IV мы обсудим особый класс многоша-
говых процессов принятия решений, которые могут быть
изучены с некоторыми аналитическими подробностями.
2]
МНОГОШАГОВЫЙ ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ
41
2.	Многошаговый процесс принятия решений
Чтобы определить многошаговый процесс принятия
решений простейшего типа, дискретный и детерминиро-
ванный, мы начнем с уже известного нам понятия много-
шагового процесса [р, Т (/?)]. Напомним, что это есть по-
следовательность векторов
Ip. Pi. р2, ...,Рп,—1.
где = Т (рп), р0 — р. Теперь мы расширим это по-
нятие, полагая, что преобразование Т зависит от друго-
го вектора Т = Т (р, q). Предположим, что мы можем ока-
зать достаточное влияние на процесс в том смысле, что
на каждом шаге можем выбрать значение q из набора до-
пустимых векторов S (#). Пусть q. будет наш выбор на
i-м шаге, так что
Pl = Т (р, д0),	
Р2 = ? (Р1,	(2Л)
Рп±1-- Т (Рп, Qn)-
Вектор q. называется вектором решения или переменной
решения и выбор д. называется решением. Таким образом,
решение эквивалентно преобразованию. Мы будем иметь
дело с процессами, в которых qi выбирается так, чтобы
максимизировать предписанную скалярную функцию сос-
тояния и переменной решения
R (Р, Ръ Рг, — . $о» ?i. •••)•	(2-2)
То, что было выше функцией состояния, теперь является
функцией критерия или функцией дохода. JV-шаговый
процесс принятия решений (дискретного детерминирован-
ного типа, единственный род процессов, который мы зна-
ем в данный момент) есть последовательность векторов
Ip. Pi, Р2, —. Рю ?0. ?1, •••	(2-3)
где рп+1 = Г (рп, qn) для каждого п.
42 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. I
3.	Стратегия
Введем теперь важное понятие — стратегия. Как бы-
ло упомянуто выше, величины qk должны быть выбраны
на каждом шаге способом, который ввиду общего харак-
тера функции R зависит от текущего состояния системы,
прошлого и будущего состояний и также от прошлого и
будущего решений. Мы будем иметь здесь дело с крите-
рием 7?, обладающим структурой, которая позволяет нам
сосредоточить внимание исключительно на прошлой и
текущей истории процесса при поиске величин q. В не-
скольких последующих разделах мы продемонстрируем
функции критерия, обладающие этим важнейшим свойст-
вом. При этих предположениях мы можем ограничиться
функциями вида
9k = 9k (р, Pi, Рч, -,Pk', 9о, 91,	9k-i)-	(3.1)
Эта функция называется функцией стратегии или просто
стратегией. Нетрудно видеть, что описание процессов
управления стратегией такой структуры не является серь-
езным ограничением, так как принятие решения основы-
вается только на знании прошлого. Важно, однако, сде-
лать все предположения явными.
Стратегия, которая максимизирует функцию 2?, назы-
вается оптимальной стратегией. Наше изложение много-
шагового процесса принятия решения будет зависеть от
вида оптимальной стратегии *).
Пока еще выражение (3.1) имеет достаточно общий вид.
Обратимся к стратегиям, имеющим сравнительно простой
вид
9k = 9k (Рк)	(3.2)
функции текущего состояния и шага процесса. Это допол-
нительное упрощение является следствием дальнейшей
детализации структуры функции критерия/?, такой струк-
туры, которая позволяет принять оптимальное решение
по одним лишь сведениям о текущем состоянии системы.
•) Вид оптимальной стратегии определяется информацией о
состояниях системы, которой мы располагаем или которую мы ис-
пользуем для формирования стратегии. (Прим, ред.)
4]
СЕПАРАБЕЛЬНЫЕ КРИТЕРИИ
43
Предварительно мы подчеркнули, что под состоянием
системы здесь понимается математическое описание моде-
ли этой системы. Посредством простого способа введения
нового состояния
Л* = \Pk, Ра-i,—]	(3.3)
в пространстве более высокой размерности можно всегда
написать
9а = 9л (ла).	(3.4)
Следовательно, достоинство функционального соотноше-
ния вида (3.2) может оцениваться только в смысле ана-
литической и вычислительной легкости и осуществимости.
Весьма существенно, чтобы размерность pk была малой и
чтобы функциональное соотношение было сравнительно
простым.
Мы вернемся к этому вопросу в главе III в связи с
вычислительными аспектами динамического программи-
рования.
4.	Сепарабельные критерии
К счастью, некоторое количество важных критериев
обладает этим жизненно необходимым свойством разъеди-
нения прошлого и настоящего. Вообще, легко предвидеть
это свойство из самой сущности исходного многошаго-
вого процесса принятия решения. В ряде ситуаций требу-
ются, однако, некоторые размышления или изменения
формулировок. Примеры этого свойства, которые мы бу-
дем проверять ниже, даются следующими критериями:
a)	2 ?(Рь9а),
/с=о
Ь)	g (Pn) (терминальное управление),
с) maxg(/7fc,9s).
Отметим, что последний критерий связан с бесконечно-
шаговым процессом.
44 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
5.	Принцип оптимальности
Далее будем предполагать, что мы имеем дело с про-
цессами принятия решений, формулировка которых по-
зволяет нам ограничиться рассмотрением стратегий, зави-
сящих только от текущего состояния. В этом особенном,
но чрезвычайно важном случае оптимальная стратегия
характеризуется очень просто:
Принцип оптимальности. Оптимальная
стратегия обладает тем свойством, что, каковы бы ни
были первоначальное состояние и первоначальное решение,
последующее решение должно определять. оптимальную
стратегию относительно состояния, полученного в резуль-
тате первоначального решения.
Чтобы проиллюстрировать этот интуитивный принцип,
предположим, что мы имеем TV-шаговый процесс, облада-
ющий требуемой отделимостью прошлого от будущего,
начинающийся в положении р, с оптимальной последова-
тельностью решений g0, qr, ..., qu-i, так что р±~Т (р, qQ),
Ръ = Т (Рп <h) и т. д. Тогда qr, q2, ...,qN_! должны пред-
ставлять собой оптимальную последовательность решений
для (N — 1)-шагового процесса, начинающегося в положе-
нии рх. Используя это соображение, получим уравнение,
которое позволит нам изучить как аналитически, так и
численно оптимальную стратегию и максимальный доход.
6.	Примеры
Рассмотрим задачу о максимизации функции дохода
w
R (Р, Р1...М 00, 91,...) = 2 s (Рь 9k).	(6.1)
fc=0
Для того чтобы быстро решить вопрос о существовании
максимума, мы можем либо ограничить р и q конечным
набором значений, либо наложить разумные ограничения
на непрерывность функций g (р, g) и Т (р, q). Так как по-
лучение численного решения требует конечности в неко-
тором смысле, то первое предположение почти не сужает
класса доступных для решения задач. Обычно этот мо-
мент редко вызывает трудности при использовании TV-ша-
61
ПРИМЕРЫ
45
говых процессов. Поэтому мы отошлем читателя к дру-
гим источникам для обсуждения вопроса о существова-
нии оптимальной стратегии для многошаговых процессов
общего вида и сосредоточим внимание на формальных
аспектах.
Максимальное значение R, зависящее только от на-
чального состояния р и числа шагов А, обозначим через
/n (р)* Другими словами,
/л (р) = общему N-шаговому доходу при начальном состоя-
нии р, получаемому при оптимальной стратегии. (6.2)
Принцип оптимальности позволяет нам заключить, что
при любом начальном решении д0 мы имеем для N > 1
g (р, 9о) + te (Pi, Qi) + ••• + g (Pn, Qn)] =
= g(p, «о) + O' (P, ?o))- (6.3)
Так как это справедливо для всех начальных решений
qQ, то, чтобы найти максимальный доход fN (р), мы долж-
ны найти максимум (6.3) по qQ. Таким образом, мы полу-
чили основное функциональное уравнение
fN (р) = max [g (р, q0) + /w_j (Г (р, g0))], 2V > 1, (6.4)
go
где
fo(Z>) = maxg(p,g0).	(6.5)
go
Аналогично для задачи оптимального управления (4.1b)
мы имеем
/о (р) = g (р), /n (Р) == max fN^ (Т (р, ?0)).	(6.6)
д>
Для третьей функции дохода согласно (4.1с) будем иметь
/ (р) = max max g (рк, qk\	(6.7)
{g} к>о
и, таким образом, так как max ик = max [ux, maxu*],
I >2
/ (p) = max max [g (p), / (Г (p, g0))l =
= max [g(p), max/(Z(p, g0))b	(6.8)
ge	дэ
46 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
В связи с уравнением (6.8) важно отметить, что воз-
можны большие трудности в изучении вопросов существо-
вания и единственности решения этого уравнения. Эти
вопросы легче разрешить, если принять вместо (4.1с)
функцию дохода
max g (Рк, qk),	(6.9)
связанную с TV-шаговым процессом. Мы рассмотрим этот
вопрос в разделе 15.
7-	Другой вывод основного функционального уравнения
Для тех, кто с некоторым правом на этом раннем эта-
пе усомнится в принципе оптимальности, мы дадим вы-
вод уравнения (6.4), следуя обычным путем. Имеем
max R — max max R.	(7.1)
йо, Qi, gjy]	Qo [Qi, Зг, Зде]
Следовательно,,
fN(p)= max [g (р, q0) + g (Pi, <h) + — + g (Pni<In)] =
[3o»3i,...,3iV]
= max max [g (p, g0) + •..] = max [g (p, q0) +
3o [3i,32,...,3tf]	3o
+ max (g(Pi,gi)4-g(p8,ga)+...+ g(pw,gw)]] =
= max [g (p, g0) + /n-i (T (p, q0))].	(7.2)
3o
Здесь мы пользовались лишь очевидными свойствами опе-
рации отыскания максимума и учитывали сепарабельность
структуры функции дохода R, В случае более сложных
процессов обычно значительно проще исходить из понятия
многошагового процесса, чем опираться на универсаль-
ные аналитические методы.
8.	Что является решением!
Посредством метода функциональных уравнений ди-
намического программирования мы привели задачу об
определении последовательности решений, которая мак-
симизирует функцию критерия, к задаче отыскания реше-
9]
НЕПРЕРЫВНЫЙ МНОГОШАГОВЫЙ ПРОЦЕСС
47
ния функционального уравнения. Используя уравнение
(7.2) для того, чтобы конкретизировать обсуждение, вы-
ясним, что мы понимаем под «решением».
В классической трактовке решение означает алгоритм
для определения последовательности {fa (р)}, который
имеет более простой вид, чем рекуррентное соотношение
(7.2). В контексте динамического программирования мы
имеем больше гибкости. Решение может быть дано в тер-
минах последовательности {fa^tp)}, последовательности
функций дохода, или последовательности {qN (р)}, пос-
ледовательности функций стратегии. Легко видеть, что
каждая из этих последовательностей определяет другую.
Заметим, однако, что имеется только одна последователь-
ность оптимальных функций дохода, хотя может быть
много оптимальных стратегий, которые дают тот же са-
мый максимальный‘’’доход.
В разделе 11 эта двойственность будет исследована с
геометрической точки зрения.
9.	Непрерывный многошаговый процесс
принятия решения
Для того чтобы ввести важное и полезное понятие
непрерывного многошагового процесса принятия реше-
ний, мы перейдем, как и выше, от дискретного к непре-
рывному процессу при помощи предельного перехода.
Пусть Д — бесконечо малая величина, функция дохода
л
(9-1)
к—О
а рассматриваемое преобразование амеет вид
т (р, д) => +. $ (Р, q) V	(9.2)
Пусть решения принимаются в моменты времени О, Д,
2Д, ... Обозначим АГД,’= Т. Тогда если обозначить че-
рез /дг (р) = / (р, Т) максимум функции дохода, то мы
получим известным способом
f (Р, Т) = max [g(p, q) + f(p + S(p, q)b,T~ A)].	(9.3)
48
МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
Разложив правую часть в ряд по степеням А и переходя
к пределу при А ->0, мы получим формально дифферен-
циальное уравнение в частных производных
-gr = max [g (р, q) + (grad /, S {р, g))J (9.4)
с начальным условием / (р, 0) = 0. Мы проиллюстрируем
этот метод в следующем разделе в связи с некоторыми за-
дачами вариационного исчисления. В рассуждениях, при
помощи которых получено уравнение (9.4), имеется ряд
моментов, требующих строгого обоснования, которое
может быть получено несколькими различными путями,
требующими, однако, достаточной изобретательности и ана-
литического мастерства.
10.	Вариационное исчисление
Наиболее интересный и значительный пример непре-
рывного многошагового процесса принятия решения дает
вариационное исчисление. Рассмотрим задачу о мак-
симизации интеграла
т
J (и) = g (и, и') dt	(10.1)
о
по всем функциям и (£), определенным на интервале
[0, Т],для которых интеграл существует и удовлетворяет
начальному условию и (0) = с. Поступая формально и
предполагая, что все условия для существования макси-
мума удовлетворены, введем функцию
f (с, Т) = max J (и).	(10.2)
и
В момент времени t переменная состояния с = и (£),
а оставшееся для процесса время составляет Т — t. Реше-
ние должно содержать выбор направления, т. е. значения
uf (t). Предположим, что мы имеем дело с достаточно
гладкими процессами, для которых существует вторая
производная от и (£); тогда выбор и' (t) определяет и (t)
на бесконечно малом интервале U, t + А].
10]
ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ
49
Рассмотрим теперь задачу об определении начального
наклона и' (0), который мы обозначим через v (рис. 2.1).
Записав.
т д т
о	о	Д
и производя аппроксимацию
д
5 g (и, и’) dt = g (с, v) А + о (А),
о
(10.4)
мы видим, что принцип оптимальности дает соотношение
/ (с, Т) = max [g (с, v) A -|- f (с + i?A, Т — A)] 4- о (А). (10.5)
V
Разложив правую часть в ряд по степеням Д и переходя
к пределу при А ->0, мы
получим дифференциаль-
ное уравнение в частных
производных
g = max[g(c, 0+^],
(10.6)
где / (с, 0) = 0. Это урав-
нение определяет как максимальное значение интег-
рала, так и функцию стратегии v — v (с, Т).
Отметим, что эта задача с начальным значением, тогда
как обычная постановка задачи приводит к уравнению
Эйлера
т. е. к двухточечной краевой задаче. Решение (или реше-
ния) определяется начальным условием и (0) — с и усло-
вием
=0.	(10.8).
ди	'
50 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
Рассмотрим теперь случай, когда наложено ограниче-
ние на скорость изменения и, а*именно
0<*<Т.	- (10.9)
Это вводит много усложнений при классической постанов-
ке задачи. Что касается метода динамического программи-
рования, то здесь достаточно заменить (10.6) соотношением
/(с, 0) = 0.	(10.10)
Как мы указывали в главе III, наложение ограничений
этого типа существенно упрощает отыскание численного
решения.
Упражнения
то
Т
1.	Покажите, что если / (с, Т) = min \ [и2 + у2] rfi, где
W J
it = аи + w (ш = и? (£)), и (0) = с,
/т = min [с2 + у2 + (ас + v) fc], f (с, 0) = 0
v
и, таким образом, .
/т=с24-вс/с —•
2.	Покажите, что / (с, Т) = c2g (Г), где
(Т) = 1 + 2ag (Г) - g* (Г), g (0) = 0.
Определите / (с, Т) и v (с, Г) явно и найдите их асимптотическое по-
ведение при Т оо. Проверьте решение, используя уравнение Эй-
лера.
3.	Покажите, что задача максимизации
т
J (w) = ^g(u, u', t)di, и(а) = с
/ (Г, с) = 0
приводит к нелинейному дифференциальному уравнению с частными
производными
---~- = max [g (с, г>, а) + г>
да v ц
для функции / (а, с) = max J (и).
и
11]
ГЕОМЕТРИЧЕСКИЕ АСПЕКТЫ
51
4.	Покажите, что задача максимизации
т
J(u) = ^g(u,v} dt
о
по г, где du/dt — h (и, i?), и (0) = с, приводит к уравнению
Л- = max Г?(с, р) + h (с, v)
oi v L	0с
5.	Рассмотрите задачу максимизации
т
J(w) = ^g(u, v)dt
о
т
по I?, где du/dt = h (и, 0, и (0) = с и к (u, v) dt < а, двумя
о
способами: во-первых, принимая а в качестве переменной сос-
тояния, во-вторых, используя множители Лагранжа. Получите
связь между этими двумя подходами (см. S. Dreyfus, Dynamic
Programming and the Calculus of Variations, J. Math. Anal. Appl.,
vol. 1, 1960, pp. 228—239).
6.	Получите уравнение в частных производных для наименьше-
го характеристического числа в задаче и” + %<р (i) и = 0, и (0) = 0,
и (а) = 0, рассматривая соответствующую вариационную задачу
а
минимизации ^(u')2cft при условиях
о
а
= 1; u(a) = c, а(0) = 0.
о
11.	Геометрические аспекты
Поучительно сравнить метод динамического программи-
рования с классическим методом в применении к изло-
женной выше вариационной задаче. В классическом ме-
тоде ищется кривая и = и (£), которая определена на
заданном интервале [0, Т] и доставляет максимум функ-
ционалу. Неизвестная функция и рассматривается как
точка в пространстве функций. В нашем подходе в каж-
дой точке мы ищем направление, которое является опти-
мальным; решение получается в виде стратегии, системы
инструкций для выполнения процесса.
52 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
В геометрическом изложении мы можем сказать, что
с классической точки зрения кривая есть геометрическое
место точек, в то время как динамическое программиро-
вание рассматривает кривую как огибающую касатель-
ных (рис. 2.2). Следо-
вательно, обе теории
двойственны относи-
. X тельно друг друга, факт,
который проявляется
гj постоянно. Эта двойст-
Диндмическое венность и эквивалент-
проераммирование ность имеют, однако,
Рис. 2.2.	силу лишь для детерми-
нированных процессов.
Из этого следует, что совместное применение обоих ме-
тодов будет более мощным и глубже проникающим, чем
использование одного или другого метода по отдельности.
Это справедливо как для аналитических, так и для вычи-
слительных проблем, где в обеих областях дуальные ме-
тоды играют фундаментальную роль.
12.	Стохастический многошаговый процесс
принятия решения
Учтем теперь стохастические эффекты, но ограничим-
ся обсуждением лишь процессов дискретного типа, чтобы
сохранить умеренный математический уровень. Для це-
лей иллюстрации достаточно взять преобразование, имею-
щее вид Т = Т (р, q, г), и предположить, что мы желаем
максимизировать математическое ожидание; оно не обя-
зательно должно быть самой функцией дохода, а может
быть средним какой-либо функции от функции дохода.
Упражнения будут содержать несколько примеров та-
кого рода.
Предположим, мы желаем максимизировать математи-
ческое ожидание случайной величины
N
(12.1)
к—о
где р0 = р и ps+i = Т (pk, qk, rj, в предположении, что
131
УПРАВЛЕНИЕ С ОБРАТНОЙ СВЯЗЬЮ
53
гк — независимые случайные переменные с одной и той
же функцией распределения dG (г). Как и выше, пусть
/n (р) обозначает максимальное значение. Тогда
/о(Р) = max g(p, qQ),	(12.2)
и для TV > 1 мы получаем, применяя принцип оптималь-
ности,
fN (р) = max [g (р, qQ) +	(71 (р, qQ, r0)) dG (r0)]. (Д2.3)
Важно отметить, что как детерминированный, так и
стохастический процессы принятия решения изучаются
при помощи одного и того же формализма, а также то, что
метод функционального уравнения манипулирует с мно-
гошаговыми процессами принятия решений так же, как
с многошаговыми процессами других типов.
13.	Управление с обратной связью
Существенно установить точную структуру процесса,
рассматриваемого нами. Пусть мы наблюдаем, что систе-
ма находится в положении р; мы выбираем д0, тогда г0
определяется по функции распределения dG (г); наконец,
тем самым порождается и наблюдается рг = Т (р, д0, го)*
Зная новое состояние, выбираем qt\ затем выбираем
по функции распределения dG (г) и т. д. Это —- основная
концепция управления с обратной связью.
В детерминированном случае последовательный выбор
q^ как описано выше, или одновременный выбор
всех как в обычной формулировке, является вопросом
аналитического или вычислительного удобства. Макси-
мум дохода и оптимальная стратегия будут теми же са-
мыми. Эта случайная эквивалентность (дуальность евк-
лидовой геометрии в частных случаях; см. раздел 11)
делает, к сожалению, неясным различие между этими
совершенно разными типами оптимизации. Отметим в свя-
зи с этим, что в детерминированном случае аспекты уп-
равления с обратной связью могут быть игнорированы,
если применить адекватную математическую теорию
54 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
общих многошаговых процессов принятия решений для
соответствующих моментов времени.
В стохастическом случае эти два подхода соответст-
вуют совсем различным процессам, занимающим крайние
места в некоторой совокупности процессов. В рассмот-
ренном выше случае мы предполагаем, что состояние
системы на каждом шаге доступно наблюдению. С другой
стороны, если мы не можем наблюдать состояния системы
после начала процесса, то мы вынуждены выбирать век-
торы д0,	вначале и максимизировать функцию
exp R относительно этих векторов.
г
Мы видим, что управление с обратной связью вклю-
чает в себя выбор функций {qk (р)}, т. е. функций стра-
тегии. Следовательно, это более высокая ступень, чем
обычная максимизация по векторам q.. Тем не менее она
более доступна как для аналитических, так и для числен-
ных методов.
Укажем, наконец, что можно породить бесконечный
класс стохастических процессов управления, варьируя
типы информации о состоянии процесса, которые задаются
при принятии решения. Как было указано выше, многие
из них индуцируют бесконечномерные процессы принятия
решения, где состояние есть распределение вероятностей.
14.	Анализ уравнений
Когда различные классы процессов принятия решения
сформулированы в точных аналитических терминах, мы
сталкиваемся с задачей получения полезной информации
из уравнений. В частности, мы можем задать следующие
вопросы:
1.	Для каких классов процессов можно получить про-
стые аналитические выражения для функций дохода и
стратегии?
2.	При каких условиях можно получить структурную
характеристику оптимальной стратегии?
За. Когда можно получить решение при помощи циф-
ровой вычислительной машины?
ЗЬ. При каком условии можно найти простую асимп-
тотику для установившейся стратегии и функции дохода?
15]
ПОСЛЕДОВАТЕЛЬНЫЕ ПРИБЛИЖЕНИЯ
55
Так как в этих направлениях предстоит еще много
сделать, то подробные ответы на некоторые из этих воп-
росов далеко уведут нас от нашего намерения дать лишь
вводное изложение. Мы, однако, сделаем несколько ссы-
лок в упражнениях и в библиографии в конце главы. Кро-
ме того, мы сделали ниже несколько более общих замеча-
ний и рассмотрим некоторое количество важных специ-
альных процессов в главах IV и V.
15.	Последовательные приближения
Так как мы имеем дело главным образом с конечно-
шаговыми процессами, то большинство функциональных
уравнений берется в виде нелинейного рекуррентного
соотношения
fN (р) = max [g (р, q) + /w_x (Т (р, q))],	(15.1)
Q
где /0 (р) = max g (р, q) или, во всяком случае, известная
а
функция. Из этого следует, что никаких вопросов суще-
ствования или единственности последовательности функ-
ций дохода {/п (/?)} при рассмотрении уравнений этого
типа не возникает. Задавая /0, мы определяем /х, затем
/2 и т. д.
Если мы рассмотрим, в качестве приближения к
решению (15.1) для случая, когда 2V^>1, случай беско-
нечного числа шагов, мы получим уравнение
/ (р) = max [g (р, q) + f(T (р, q))],	(15.2)
Я
которое естественно возникает при рассмотрении различ-
ных обобщенных траекторий и процессов управления.
Классический метод построения решения уравнения этого
типа, при соответствующих гипотезах относительно функ-
ций g (р, q) и Т (р, q), базируется на методе последова-
тельных приближений. Это обычно выполняется следую-
щим образом. Мы выбираем начальное приближение /0(р)
и затем продолжаем рекуррентно определять последующие
56 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
приближения к f (р)
fi (?) = max [g (р, q) 4- /0 (Т (р, q))],	(15.3)
Mi (?) = max [g (p, q) + /п (T (p, g))]. q	
Во многих процессах нетрудно установить сходимость
последовательности {fn (р)} к решению (15.2). Детали
этих доказательств при различных предположениях могут
быть найдены в работах, ссылки на которые даны в кон-
це этой главы.
16.	Приближение в пространстве стратегий
В теории динамического программирования мы рас-
полагаем еще одним типом аппроксимации — аппрокси-
мацией в пространстве стратегий. Как было указано в
разделе 8, функциональное уравнение вида (15.2) опреде-
ляет две функции: функцию дохода / (р) и функцию стра-
тегии q (р). Тот факт, что каждая из них определяет дру-
гую, есть ключ к обсуждаемому здесь методу.
Начнем с приближения q (р) функцией qQ (р). Затем
определим /0 (р) при помощи уравнения
/о (?) = g (р, 0о) + f (Т (р,.<1о)) =
= g (р, ?о) + g (Т(р, Зо), £о') +•••. (16.1)
где q0' = q0 (Т (р, q0)), и т. д. Другими словами, /0 (р)
есть полный доход, получаемый при применении страте-
гии qQ (р). Усовершенствуем эту стратегию, опреде-
лив функцию qr (р), которая максимизирует g (р, q) +
+ /о (р> <?)),и затем определим /х (р) при помощи урав-
нения
А (?) = g (?, «J + А (Т (р, ?1))-	(16.2)
Так как qr = qr (р), то можно написать
А (?) = g (?) + А (А (?)),	(16.3)
17]
КВАЗИ ЛИНЕ АРИЗАЦИЯ
57
где g и h — известные функции, h (р) ~ Т (/?, q1 (р)). При
правдоподобных предположениях относительно этих функ-
ций мы можем найти Д (р) методом итераций. Таким об-
разом,
fi (р) = g (р) + g (h (р)) + g (№(р)) + ...	(16.4)
Иными словами, Д (р) получено при стратегии q± (р). Так
как
/о (р) = g (Р, <7о) /о+ {Т (р, д0)) <
< max [g (р, q) + /0 (Т (р, g))J = g (р, qj + f0 (Т (р, qj)),
g
(16.5)
то мы видим, что
/о (р)< g (р) + /о (h (р)) < (р) + g (h(p)) +
+ g(№(p)) + ... (16.6)
Следовательно, снова при разумных условиях можно по-
казать, что /0 (р) Д (р). Продолжая таким образом, мы
получаем новую стратегию q2 (р) для функции Д (р) и
далее по индукции — последовательность {fn (/?)} при-
ближений к / (р), которая монотонно возрастает при уве-
личении и, Д < Д < ... <7п< /•
Одно из преимуществ этого метода состоит в том, что
во многих процессах существуют интуитивные последо-
вательные приближения в пространстве стратегий, кото-
рые могут быть легко использованы. К тому же (и это
наиболее важно), в том, что касается применений, описан-
ная процедура дает систематический аппарат для улучше-
ния существующих стратегий.
17.	Квазилинеаризация
Одним из важных применений этой идеи последователь-
ных приближений в пространстве стратегий является
теория квазилинеаризации. Мы начнем с уравнения вида
L(f(p))=N(f(p)\	(17.1)
где/, — линейный оператор, аЛ" — нелинейный оператор,
и попытаемся преобразовать это уравнение к виду (15.2).
Для этого выразим правую часть в виде максимума.
58 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
Предположим для простоты, что N (и) есть скалярная функ-
ция. которая выпукла по и. Тогда, как легко видеть либо
геометрически, либо аналитически,
/V (и) = max [TV (i>) + (u — v) N' (p)].	(17.2)
V
Следовательно, (17.1) можно записать так:
L(f) = max [TV (g) + (/ - q) TV' (q)].	(17.3)
Q
Это уравнение выглядит так, как если бы оно было свя-
зано с многошаговым процессом принятия решений, и с
ним можно оперировать так, как будто оно действительно
описывает такой процесс. Применяя последовательные
приближения в пространстве стратегий, зачастую можно
получить очень быстро сходящиеся последовательные
приближения к решению (17.1). Имеется много важных
приложений этого аппарата, описанных в ряде источни-
ков, ссылки на которые даны в конце главы.
18.	Аналитические и вычислительные проблемы
Могут ли уравнения, выведенные на предыдущих стра-
ницах, быть использованы для получения аналитических
и численных результатов? Ответ будет положительным
(«да»). Как обычно в математических теориях, он зависит
от задачи. В главе IV мы рассмотрим несколько важных
типов процессов, где может быть достигнуто вполне удов-
летворительное аналитическое продвижение. В главе Ш
мы обсудим вычислительный аппарат, который позволит
нам иметь дело с общими классами процессов динамиче-
ского программирования в условиях применения новей-
ших вычислительных машин.
Как мы увидим в дальнейшем, нет ничего установив-
шегося в применении цифровых вычислительных машин
для получения численных решений. Здесь требуется мно-
го аналитического мастерства и изобретательности и глав-
ным образом требуется большое понимание как научной
сути задачи, так и математического аппарата. Лишь тогда,
когда мы имеем алгоритм для получения численных ре-
зультатов, можно считать, что задача полностью решена.
19]
ПРИНЦИП ФЕРМА И УРАВНЕНИЕ ЭЙКОНАЛА
59
19.	Принцип Ферма и уравнение эйконала
В качестве интересного применения указанных выше
идей рассмотрим задачу о распространении света в неод-
нородной двумерной среде. Наша цель — показать, что
применением принципа оптимальности в соединении с
принципом наименьшего времени Ферма можно простым
и непосредственным способом получить основное уравне-
ние геометрической оптики, уравнение эйконала.
Предположим, что среда характеризуется показателем
преломления, который является функцией положения
п — п (х, у). Тогда, если мы положим
=	(19.1)
то v будет скоростью света в точке (ж, г/), где с — скорость
света в вакууме. Согласно принципу Ферма при переходе
в среде от одной точки (х, у) к другой точке (я0, у0) луч
света выбирает путь, соответствующий наименьшему вре-
мени. Обозначим время, которое затрачивает частица
света при переходе от точки (ж, у) к фиксированной точке
(я0, Уо) в соответствии с вышеприведенным принципом,
через t (ж, у). Если частица покидает точку (х, у) и пере-
мещается вдоль линии, составляющей угол 0 с осью х,
на расстояние А, то она придет в точку (х + AcosG,
Asin 0) по истечении времени A/v (я, у) (мы пренебре-
гаем членами второго и высших порядков относительно А).
Отсюда следует, что
t (х, у) = min |	+ t (х + Д cos 0, у + A sin 9) + о (Д)|,
(19.2)
Из этого мы видим, что
О = min j	+ Ых cos 0 + Afv sin 9 + о (A)}, (19.3)
откуда, разделив на А и устремляя А к нулю, получим
— у-1(я:,у) — min{fxcos9 + fvsin9). (19.4)
60 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
Это — новый вид уравнения эйконала. Значение 0, кото-
рое минимизирует выражение в скобках в полученном
выше уравнении, есть решение уравнения
—^sinO + ty cos0 = 0	(19.5)
или
tg0 = 4~-	(19.6)
Lx
Подставляя это значение 0 в уравнение (19.4), мы полу-
чаем желаемый результат
=	(19.7)
который может быть записан в виде
+ =	(19.8)
Уравнение (19.8) есть уравнение эйконала. Отметим те-
перь, что если возмущение начинается в точке (я0, у0)
в момент времени, равный нулю, то время Т распростра-
нения волнового фронта этого возмущения
Т = t (х, у).	(19.9)
Наклон пути, проходящего через точку (х, у), есть ty/tx
согласно уравнению (19.6), и наклон волнового фронта
есть — txlty Это показывает, что лучи и волновые фронты
ортогональны в рассматриваемом случае.
Упражнения
1.	Рассмотрите случай неоднородной и анизотропной среды, для
которой п = п (х, у, у'). В частности, найдите связь между лучами
и волновыми фронтами.
2.	Найдите уравнения для лучей в изотропном случае.
3.	Исследуйте случай, в котором п (а?, у) = у. Покажите, что
лучи являются дугами окружностей с центрами на оси х.
4.	Обсудите концепцию последовательных приближений в про-
странстве стратегий в применении к уравнению (19.4), альтернатив-
ному виду уравнения эйконала.
5.	Принцип Гюйгенса вторичных небольших волн дает мощный
метод для исследования уравнения эйконала. Сформулируйте прин-
цип и примените его к уравнению (19.4) (см. обсуждение этого вопро-
са в книге: С. Л а н ц о ш, Вариационные принципы механики, гл.
VIII и книгу Гюйгенса, Распространение света).
20]
НАИКРАТЧАЙШИЕ ПУТИ ЧЕРЕЗ СЕТИ
61
20.	Наикратчайшие пути через сети
Рассмотрим сеть, состоящую из N узлов, занумерован-
ных 1, 2, ...,7V, и взаимосвязанных звеньев. Пусть время,
которое занимает прохождение звена (f, /), будет >0.
В частности, отметим, что не обязательно должно быть
равным Мы желаем определить путь через сеть, кото-
рый соединяет два заданных узла, полное время прохож-
дения по которому по крайней мере не больше, чем для
любого другого пути, соединяющего заданные узлы. Яс-
но, что эта задача имеет важное значение при выборе
маршрутов самолетов и автомобилей по транспортным
сетям и при передаче сообщений по сетям связи. Помимо
того, эти вопросы важны при изучении оптимальных
по быстродействию систем управления с обратной связью.
Чтобы показать это, мы интерпретируем N узлов как
возможные состояния системы, а звенья — как преобра-
зования от одного состояния к другому. Часто мы хотим
перевести систему из заданного начального состояния в
желаемое состояние за минимальное время. Эта задача
может быть также рассмотрена как дискретная версия
оптической задачи, содержащей принцип Ферма, рассмот-
ренной в разделе 19. Наконец, интерпретируя числа t#
как топливо или любые другие расходуемые ресурсы,
можно рассматривать нашу задачу как задачу перевода
системы из заданного начального состояния в требуемое
конечное состояние наиболее эффективным образом,
в смысле затрат ресурсов.
Будем рассматривать узел N как желаемый для конца
заданного интервала времени узел, и введем величины
и. = время перевода системы из начального состояния i
в желаемое состоянием вдоль кратчайшего пути
i =1,2, ...,7V.	(20.1)
Мы положим
uN = 0.	(20.2)
Применяя принцип оптимальности, получим основную
систему нелинейных алгебраических уравнений
=	г = 1,2,	, 2V-1, 1
I (20.3)
Un = 0.	-I
62 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
Они могут рассматриваться как дискретная форма урав-
нения эйконала (см. раздел 19). В противоположность
многим другим системам уравнений, полученным из прин-
ципа оптимальности, никакой последовательный метод
определения неизвестных здесь непосредственно не ус-
матривается. Следовательно, мы должны применить ме-
тод последовательных приближений. Сначала установим
единственность решения уравнений (20.3) для того, чтобы
получить уверенность, что последовательность, которая
сходится к решению, сходится к искомому нами решению,
т. е. определяет желаемый минимальный промежуток
времени. Заметим, однако, что, в то время как величины
ux, и2,..., Un определяются однозначно, пути, при прохож-
дении вдоль которых эти значения достигаются, могут
быть не единственными.
Пусть ux, u2, ...,uw и иъ U2,	— два различных
решения системы (20.3). Пусть т есть индекс, для кото-
рого разность U— Uj, j = 1, 2, N, есть максимум.
Мы хотим показать, что этот максимум разности равен
нулю. Пусть
ит = tmn + ип < tmr + Ur, (20.4)
ит ~ ^тг “Ь	(20.5)
Из этого следует, что
Um	UT'	(20.6)
и так как т есть индекс, для которого разность Um — ит
есть максимум, то знак равенства должен быть удержан
как в (20.6), так и в (20.4). Кроме того, ясно, что
m=j=r.	^(20.7)
Подобным же образом мы можем найти узел 5, где
s^=r,	(20.8)
для которого	*
ит — ит	= Ur — ur =	U8 — и8.	(20.9)
В конце концов, так	как имеется	лишь	конечное	число
узлов, мы должны подойти к узлу 7V, для которого
UN-uN = 0.	(20.10)
20]
НАИКРАТЧАЙШИЕ ПУТИ ЧЕРЕЗ СЕТИ
63
Этим заканчивается доказательство единственности. Вер-
немся теперь к отысканию численного решения путем при-
менения приближений в пространстве стратегий. Одно-
временно мы установим как существование решения сис-
темы (20.3), так и эффективный способ для вычисления
решения.
В качестве исходного приближения 40), i = 1,2,...
...,2V, положим
= tiN, i = 1, 2...N, tNN = Q, (20.11)
что соответствует стратегии перевода системы непосред-
ственно из ее начального состояния в желаемое конечное
состояние. Если не имеется никакого звена от i к 2V, так
ЧТО tlN = ОО, то мы положим = Ю30 или какому-ни-
будь другому подходящему большому числу. Этот про-
стой прием устраняет трудные топологические вопросы
связности. Следующее приближение получим из формулы
= min {ti} + uj0)}, i = 1, 2,..., N — 1, (20.12)
i$> = 0.	(2o:i3)
Операции, указанные в формуле (20.12) быстро выпол-
няются вычислительно. Значения одной строки матрицы
(t^) требуются в качестве значений исходного приближе-
ния / = 1,2, ...,2V. Минимизация делается путем не-
посредственного сравнения встречающихся сумм, одной
за другой. Таким образом, как время вычисления, так и
требования к быстродействию памяти невелики. Мы пе-
реходим от А-го к (к + 1)-му приближению при помощи
соотношений
i4*+1> = min {tu + «Н. г = 1,2,... Л -1, (20.14)
Mi
иГ> = 0.	(20.15)
Формулы (20.12) — (20.15) имеют простую физическую
интерпретацию. Величина соответствует минималь-
ному времени перехода от узла i к узлу 2V без промежу-
точных узлов. Величина иОр есть минимальное время
64 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
перехода от узла i к узлу N при наличии не более одного
промежуточного узла. Аналогично есть минимальное
время перехода от узла i к узлу N при наличии не более
к промежуточных узлов. Из этой физической интерпрета-
ции мы видим, что последовательные приближения моно-
тонно убывают, т. е.
0<14кн1Ч4к), i =	(20.16)
Это иллюстрация эффективности метода приближе-
ний в пространстве стратегий. Отметим, кроме того, что
эта процедура аппроксимации конечна по своему сущест-
ву, Так как оптимальный путь от i к N не может
иметь никаких петель, он может содержать не более
N — 2 промежуточных узла. Из этого следует, что
величины и<^\ i == 1, 2,..., N — 1, должны удовлетво-
рять уравнениям (20.3), что означает, что мы будем иметь
не более N — 2 итераций.
Для определения оптимальной траектории из какого-
нибудь начального состояния в любое конечное состояние
можно применить только что рассмотренный метод N раз.
Иначе говоря, мы можем ввести величины
= минимальное время перехода системы из состояния
I' в состояние j, используя путь с не более чем к-промежу-
точными состояниями,	(20.17)
Из принципа оптимальности следуют уравнения
= min+ «$}, к = 0,1,2, ...,N-3.	(20.18)
Для вычислительных целей, возможно, выгоднее продви-
гаться вперед при помощи формулы
<+1) = min{^ + u^},	(20.19)
Э^г
которая позволяет определить последовательность матриц
(wy’), (i4?), (4Г), (4?), («08)),...
В различных случаях бывает желательно определить
предпочтительные субоптимальные пути. Покажем, как
20]
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
65
определить второй наикратчайший путь. Пусть
г?. = длина второго наикратчайшего пути от i до N,
i = 1, 2,..., N.	(20.20)
Мы отметим, что если мы сперва проходим из положения
i в положение /, то переход из положения / в конечное
положение N должен быть наикратчайшим путем, или
вторым наикратчайшим путем. Применяя обозначение
min2 (ах, а2,..., а?с) = второму наименьшему из а19 а2,..
..., ак в предположении, что они не все равны, (20.21)
мы можем написать
= mm2(^ + uh + of), i = 1, 2,
vN =3 0.
(20.22)
Предполагая, что и. уже определены, мы можем исполь-
зовать вышеприведенную процедуру для определения v..
Упражнения
1.	Пусть число узлов сети будет N ~ 3, 4 и 5 и пусть	= i + j.
Найдите наикратчайший путь от узла 1 к узлу N в каждом случае.
2.	Во многих ситуациях только небольшое число из всех возмож-
ных звеньев будет в наличии. Как видоизменяет этот факт получен-
ные выше уравнения?
3.	Предположим, что мы хотим прийти от i к N таким образом,
чтобы наибольшее из чисел ty на звеньях, вдоль которых мы путеше-
ствуем, было как можно меньше. Покажите, что это приводит к функ-
циональным уравнениям
— min max (t^, Sj), i — 1, 2, ..., N — 1,
SN = 0.
Библиография и комментарии
§ 1. Подробное изложение теории и приложений динамического
программирования дано в книгах:
Р. Веллман, Динамическое программирование, ИЛ,
1960.
Р. Веллман и С. Дрейфус, Прикладные задачи
динамического программирования, «Наука», 1965.
Р. Веллман, Процессы регулирования с адаптацией,
ИЛ, 1964.
11<2? Р. Веллман, Р. Калаба
66 МНОГОШАГОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [ГЛ. II
R. Aris, Discrete Dynamic Programming, An Introduction
to the Optimization of Staged Processes, Blaisdell Publishing
Company, New York, 1964. ’
С. M. Робертс, Динамическое программирование в про-
цессах химической технологии и методы управления, М., 1965.
К. Arrow, S. Karlin and Н. Scarf, Studies in the
Mathematical Theory of Inventory and Production, Stanford
Univ. Press, Stanford, California, 1958.
P. Ховард, Динамическое программирование и марков-
ские процессы, «Советское радио», 1964.
§ 8. Дальнейшее обсуждение этих идей
R. Bellman and Р. Brock, On the Concepts of a Prob-
lem and Problem-solving, Amer. Math. Monthly, vol. 67, 1960,
pp. 119—134.
§10. Для дальнейшего обсуждения связи между динамическим про-
граммированием и вариационным исчислением предлагаем
S. Dreyfus, Dynamic Programming and the Calculus of
Variations, J. Math. Anal. AppL, vol., 1, 1960, pp. 228—239.
S. Dreyfus, Variational Problems with Constraints, J.
Math. Anal. AppL, vol. 4, 1962, pp. 297—308.
L. Berkovitz, Variational Methods in Problems of Cont-
rol and Programming, J. Math. Anal. AppL, vol. 3, 1961, pp.
145—169.
О связи между принципом максимума и динамическим программи-
рованием
С. D е s о е г, Pontriagin’s Maximum Principle and the Prin-
ciple of Optimality, J. Franklin Institute, vol. 271, 1961, pp.
361—367.
Л. Розоноэр, Принцип максимума Л, С. Понтрягина в
теории оптимальных систем, «Автоматика и телемеханика»,
т. XX, № 10, И, 12, 1960.
Обсуждение взаимной связи между динамическим программирова-
нием, принципом Ферма и некторыми идеями Паскаля приведено в
R. F о rt е t, Remarques sur la Programmation Dynamique,
Ann. de la Faculte des Sciences de Г Universite de Clermont,
vol. 2, 1962, pp. 41—51.
[Строгое математическое обоснование метода динамического
программирования для случая дифференциальных уравнений сде-
лано в статье
Болтянский В. Г., Достаточные услрвия оптимально-
сти и обоснование метода динамического программирования,
Изв. АН СССР, серия матем., т. 28, 1964, стр. 481^-514,
а также в книге
Болтянский В. Г., Математические методы оптималь-
ного управления, изд. 2-е, «Наука», 1969. (Прим, перев.)]
§ 12. Рекомендуем
R. Bellman, On the Foundations of a Theory of Stochastic
Variational Processes, Proc. Tenth Symposium in Applied Ma-
thematics, Amer. Math. Soc., Providence, Rhode Island, 1961.
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
67
Исследование стохастических процессов непрерывного типа см.
H.J. Kushner, On Stochastic Extremum Problems:
Calculus, J. Math., Anal. AppL, in press.
H. J. Kushner and F. C. Schweppe, A. Maximum
Principle for Stochastic Control Systems, J. Math. Anal. AppL,
in press.
§ 13. Историю концепции управления с обратной связью см.
R. Bellman and R. К а 1 a b a (eds.), Selected Papers on
Mathematical Trends in Control Theory, Dover Publications,
New York, 1964
и в частности, статьи Bateman и Bode.
§16. Некоторые приложения приближения в пространстве стра-
тегий указаны в цитированных выше книгах Р. Веллмана и С/Дрей-
фуса и Ховарда.
§ 17.
R. Bellman, Functional Equations in the Theory of Dy-
namic Programming — V: Positivity and Quasi-linearity,
Proc. Nat. Acad. Sci. USA, vol. 41, 1955, pp. 743—746.
R. К a 1 a b a, On Nonlinear Differential Equations the Ma-
ximum Operation, and Monotone Convergence, J. Math. Meeh.,
vol. 8, 1959, pp. 519—574.
R. Bellman and R. К a 1 a b a, Quasilinearization and
Nonlinear Boundary-value Problems, American Elsevier Publis-
hing Co., New York, 1965.
§ 19. R. К a 1 a b a, Dynamic Programming, Fermat’s Principle
and the Eikonal Equation, J. Opt. Soc. Amer., vol. 51. 1961,
pp. 1150—1151.
§ 20. R. В e 11 m a n, On a Routing Problem, Quart. AppL Math.,
vol. 16, 1958, pp. 87—90.
R. Bellman and R. К a 1 a b a, On &th Best Policies,
J. Soc. Indust. AppL Math., vol. 8, 1960, pp. 582—588.
R. К a 1 a b a, Graph Theory and Automatic Control, Chapter
8 of Applied Combinatorial Mathematics, E. F. Beckenbach,
ed., John Wiley & Sons, Inc., New York, 1964.
3*
Глава III
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
1.	Введение
В предыдущих двух главах мы показали применение
аналитического аппарата теории динамического програм-
мирования к изучению общего вида многошаговых про-
цессов принятия решений. Вернемся теперь к вопросу о
возможности получения численного решения при помощи
этого подхода и, в частности, к вопросу получения чис-
ленного решения при помощи цифровой вычислительной
машины. Мы подчеркнем здесь лишь несколько наиболее
важных моментов, отсылая интересующегося читателя к
другим работам, в которых можно найти детальное и ис-
черпывающее изложение.
Весьма важный момент, значение которого необходи-
мо особенно подчеркнуть, состоит в том, что каждая вы-
числительная процедура должна заключать в себе про-
цесс регулирования, при котором неизбежные погреш-
ности, сопровождающие арифметические операции, не
выходили бы из допустимых границ. Поэтому аппарат
динамического программирования может быть использо-
ван в численном решении классических функциональных
уравнений, обыкновенных дифференциальных уравнений
и дифференциальных уравнений с частными производны-
ми и в численном решении функциональных уравнений
самого динамического программирования. Мы дадим нес-
колько указаний относительно такого рода приложений,
не входя, однако, глубоко в исследование этих идей.
2.	Цифровые вычислительные машины
Цифровая вычислительная машина есть устройство
для выполнения арифметических действий, иными слова-
ми, для выполнения четырех фундаментальных операций:
з] РЕШЕНИЕ ПРОЦЕССОВ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ 69
сложения, вычитания, умножения и деления. Ее выдаю-
щееся положение в современной науке является следст-
вием того факта, что в отличие от человека она может
выполнять эти действия точно и чрезвычайно быстро. В
настоящее время два десятка чисел могут быть умножены
друг на друга в течение одной стотысячной доли секунды.
Главный недостаток цифровой вычислительной машины
состоит в том, что в отличие от человека каждая задача,
к которой она может быть применена, должна быть при-
ведена, часто довольно утомительным способом, к после-
довательности арифметических задач.
Отметим, что мы не утверждали, что цифровая вычис-
лительная машина есть «просто» арифметическое устрой-
ство. Способность быстро и точно производить миллиарды
арифметических операций сама по себе глубоко затраги-
вали любой аспект современной жизни и философии. Зна-
чительные изменения в количестве предопределяют и
значительные изменения в качестве.
Имеются другие типы вычислительных устройств, та-
ких как аналоговые вычислительные устройства, которые
не ограничены лишь арифметическими действиями. Одна-
ко пока они ограничены тем, что могут быть применены
для рассмотрения лишь специальных классов задач. Эта
ситуация может, однако, измениться в ближайшем буду-
щем. Ниже мы хотим обрисовать пути применения цифро-
вой вычислительной машины к определению оптимальных
стратегий и функций дохода.
3.	Численное решение процессов динамического
программирования
Рассмотрим типичное рекуррентное соотношение
fN(p)= max [Л (р, g) +/w_t (Т (р, g))],	2V>1, (3.1)
g
с заданной функцией /0 (р). Для того чтобы рекуррентно
вычислить как функцию дохода, так и функцию страте-
гии, мы поступим следующим образом. Рассмотрим урав-
нение для /х (р),
А(р) = max ifi (р, я) + /о (Т (р,«))].	(3.2)
ч
70
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
1ГЛ. Ш
Для того чтобы подсчитать значения Д (р), необходи-
мо иметь значения h (р, q), Т (р, q) и /0 (р) в запоминаю-
щем устройстве машины или иметь алгоритмы для обра-
зования этих значений. Предположим на минуту, что
мы только запомнили эти значения. Впоследствии мы об-
судим более сложный подход.
Так как невозможно запомнить все значения /0 (/?),
если р принимает значения из бесконечной последователь-
ности чисел, и весьма трудно это сделать, даже если число
членов этой последовательности конечно, но велико, мы
запомним лишь дискретный набор значений {/0 (/?.)},
i = l,2,..., М. Другие значения /0 (р) будут получены
при помощи экстраполяции или интерполяции, как пот-
ребуется. Чтобы найти максимум по q в (3.2), мы анало-
гично ограничим q конечным набором значений {д7},
/ =1,2,..., 7?, и приступим к непосредственному сравне-
нию значений. Мы вычислим выражения h (рх, q) +
+ /о {Т (/?!, д)) для q = gx, g2,..., Qr и выберем g, назовем
его gx, которое максимизирует это выражение. Максими-
зация по дискретной системе значений является арифме-
тической" операцией, которая может быть выполнена на
цифровой вычислительной машине. Если несколько зна-
чений дают максимум, мы запоминаем их все.
Вышеизложенная процедура определяет (р±) и
Qi (Pi)- Повторяя эту процедуру для каждого из состоя-
ний р., i =4,2,..., М, мы получим функцию дохода Д (р)
и функцию стратегии qt (р) для этого набора состояний.
Заменяя (3.2) соотношением
/2 (р) = шах[Л'(р, q) + fa (Т(р, g))],	(3.3)
получим описанным выше путем /2 (р) и д2 (р) снова для
конечного набора р = ри Ря,..-, рм- Таким образом, ре-
куррентно мы вычислили последовательности {fn(p)} и
{9п (р)}-
Прежде всего отметим, что вышеизложенная процеду-
ра является итеративной. Мы применяем одну и ту же
процедуру на каждом шаге, чтобы по заданному /п (р)
вычислить/п+1 (/?). Следовательно, система вычислительных
инструкций будет относительно небольшой, и ее можно
легко записать на одном из новых простых вычислитель-
4]
ПРИБЛИЖЕНИЯ В ПРОСТРАНСТВЕ ФУНКЦИЙ
71
ных языков, таких как ФОРТРАН или АЛГОЛ. Эта ите-
ративность или периодическая повторяемость весьма важ-
на для применения цифровой вычислительной машины.
Отметим также, что, как только Д (р) использована для
определения /2 (р) и #2 (/О, согласно (3.3), ее можно сте-
реть из памяти. Для того чтобы определить /3 (р) и q3 (р),
мы нуждаемся только в /2 (р)- Это чрезвычайно важный
факт, ибо, как мы увидим, в настоящее время при отно-
сительной ограниченности памяти вычислительных машин
возможность применения запоминающего устройства с
малым временем выборки является решающей для успеха
динамического программирования.
Наконец, отметим, что если мы имели ограничения ви-
да q GE 8 (р), то число возможных значений q, по которым
на каждом шаге надо вести поиск, уменьшается. Это
уменьшает время вычислений. Следовательно, чем боль-
ше ограничений на функцию стратегии, тем легче приме-
нить аппарат динамического программирования. Это яв-
ляется важным преимуществом аппарата динамического
программирования по сравнению с классическими спо-
собами учета ограничений.
4.	Приближения в пространстве функций
Ряд важных процессов приводит к функциональным
уравнениям вида
/ (р) = max [h (р, q)+f(T (р, q))],	(4.1)
Q
как это было показано в главе II. Чтобы применить для
численного решения уравнений этого типа процедуру ре-
шения уравнений рекуррентного типа, изложенную в раз-
деле 3, обратимся к классическому методу последователь-
ных приближений. Полагая, что /0 (р) представляет собой
начальное приближение, полученное из математических
или физических соображений, рассмотрим последователь-
ность {/п (/?)}, порождаемую соотношением
7n+i(p)= max[/i(p, q) + fn(T (р, q))], n = 0,1,2,... (4.2)
q
72
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. III
Можно показать, что при определенных предполо-
жениях относительно функций h (р, q), Т (р, q) и /0 (р)
эта последовательность сходится к решению уравнения
(4.1). Вообще говоря, те же самые предположения могут
быть использованы для установления единственности ре-
шения.
5.	Приближение в пространстве стратегий
Возможностью, которой обладает динамическое прог-
раммирование и которая не имеет места в классическом
анализе, является приближение в пространстве страте-
гии. Как было подчеркнуто выше, функция дохода опре-
деляется оптимальной стратегией и, наоборот, оптимальная
стратегия определяется функцией дохода. В предыду-
щем разделе мы следовали классическим путем в приб-
лижении к функции дохода. Еще раз отметим, что мы
можем также применять приближения в пространстве стра-
тегий. Это было обсуждено в разделе 16 главы II и ил-
люстрируется в разделе 10 этой главы. Аналитическая
и вычислительная действенность здесь зависит от глубины
проникновения в существо изучаемого процесса принятия
решений и изобретательности исследователя.
6. Вычислительная осуществимость
Исследуем теперь в некоторых деталях алгоритм, дан-
ный в разделе 3. Осуществима ли описанная вычислитель-
ная процедура в настоящее время и даже в будущем, пос-
кольку речь идет о цифровых вычислительных машинах?
Мы имеем в виду запоминающее устройство с малым вре-
менем выборки объемом в 105 или, самое большее, 106.
Рассмотрим случай, когда р есть вектор размерности 2
р = (я, у), так что f (р) = f (х, у). Предположим, что х и
у изменяются в интервалах 0 х, у 1 и что мы запо-
минаем значения / в 100. точках по я и 100 точках по у,
всего в 104 точках. Это находится в пределах наших воз-
можностей. Таким образом, для одномерного или двумер-
ного случаев мы в состоянии применить описанную про-
цедуру получения численного решения.
7]
АППРОКСИМАЦИЯ ПОЛИНОМАМИ
73
Если размерность вектора р более высокая, например
4, то обычный метод, описанный выше, требует объема
памяти в 10s значений. Таким объемом памяти мы будем
располагать, по-видимому, лет через двадцать пять *).
Для изучения таких процессов при современных техни-
ческих средствах требуются более тонкие алгоритмы.
7.	Аппроксимация полиномами
В большинстве важных приложений динамического
программирования набор чисел, связывающих функцию
/ (р) с набором допустимых векторов состояния, определя-
ется не очень просто. Фукция / (/>) является функцией,
обладающей структурой, подразумевающей, прежде все-
го, «гладкость» функции относительно р. Иными словами,
имеется большая корреляция между значениями / (р) для
различных значений р.
Из этого следует, что вместо простого запоминания
набора значений {/ (у?.)}, i = 1, 2,..., М, благоразумнее
хранить в памяти различные правила или предписания
для воспроизведения значений / (р). Рассмотрим один из
простейших приемов — метод полиномиальной аппрокси-
мации. Ссылка на более изящный способ, такой как диф-
ференциальная аппроксимация, будет дана в конце этой
главы.
Чтобы сохранить обозначения, применяемые в теории
управления, рассмотрим случай, когда р — одномерный
вектор, который определен на отрезке [0, 1]. Запишем
f (р) = f (х), где 0 х 1. Метод, приведенный выше,
в разделе 3, восстанавливает функцию / (х), когда это
необходимо, при помощи интерполяции по набору ее зна-
чений / (к/М), к — 0, 1, 2,..., М. Выясним, можно ли
вместо этого получить приближенное представление для
/ (ж) в виде
р
/ (^) = 2 а&1с‘
к—9
(7.1)
*) Мы консервативны: 10 лет, по-видимому, более точная оценка.
Через 25 лет, вероятно, можно ожидать объема памяти в 10го.
4 р. Веллман, Р. Калаба
74
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. III
Если это так, то можно хранить значения / (х) в виде
Р + 1 коэффициентов а0,	аР вместе с указаниями
для вычисления полинома от х с этими коэффициентами.
Если / (ж) — гладкая функция, то требуется сравни-
тельно небольшое число коэффициентов. Простейший
способ определения коэффициентов состоит в применении
среднеквадратичной аппроксимации. Мы требуем, чтобы
коэффициенты минимизировали квадратичную форму
1	р
$ (/(*)-2	(7.2)
о	fc==o	'
Для того чтобы избежать алгебраических и вычисли-
тельных проблем, возникающих при такой постановке,
можно вместо (7.1) применить аппроксимацию
р
/ (*) = 2 М/М	(7.3)
4=0
где фа (х) — ортонормированные полиномы на [0, 1] *).
В этом случае условие среднеквадратичной аппроксима-
ции дает соотношения
1
$/(ж)<рк(л:)с?а:.	(7.4)
о
Мы теперь столкнемся с трудностями численного полу-
чения Ьц. Для того чтобы преодолеть их, воспользуемся
численной квадратурой
м
3	(7.5)
г=1
Отсюда следует, что требуется запоминать лишь значения
{/ (х.)}. Подробное обсуждение вопросов определения и
вычисления (х) и численного интегрирования дано в
конце главы.
На первый взгляд мы извлекли большую выгоду, за-
менив хранение / (х) в памяти хранением в памяти зна-
чений {/ (ж.)}. Мы действительно выиграли, поскольку
*) Точнее, они являются сдвинутыми полиномами Лежандра.
8]
УСТОЙЧИВОСТЬ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
75
речь идет о запоминающем устройстве с малым временем
выборки. Но мы теряем время на запоминание. Много
времени расходуется на вычисление коэффициентов Ьк,
а затем на вычисление / (ж), согласно (7.3), для других
значений х. Это обнаруживается, в частности, на ряде пу-
тей, которыми мы пытаемся обойти указанным способом
проклятие размерности.
Рассмотрим, например, применимость этих способов
аппроксимации к функциям большого числа переменных.
Предположим, что / (р) есть функция четырех переменных,
скажем / (^, #2, #3, ж4). Если мы теперь запишем
*	р
/ (Х1, Х2, «з, Х4)	2	«КтпфИ^Фг^Фт^фп^л),
fc, Z, т,
(7.6)
где akimn вновь определяются из требований среднеквад-
ратичной аппроксимации, то мы видим, что для запоми-
нания / (р) требуется хранение (Р + I)4 коэффициентов.
При Р = 4 это будет 54 = 625. Если Р = 9, то это будет
104 = 10 000. Эти цифры указывают на значительное пре-
имущество по сравнению с требованием запоминания
/ (р) в узлах четырехмерной решетки.
Можно значительно уменьшить время, требуемое для
вычисления /, используя более низкую степень аппрок-
симации в подобластях. Так, например, можно разделить
область 0	х2,	#4	1 на 256 областей и применить
аппроксимацию квадратичной формой в каждой.
Работа в этой решающей области аппроксимирования
только началась, и имеется много нерешенных проблем,
которые досаждают нам. Нашей целью в этом разделе
было указать, что существует некоторое количество пер-
спективных способов и что изобретательность будет воз-
награждена сторицей.
8.	Устойчивость вычислительного процесса
При применении метода, обрисованного в разделе 2,
численные погрешности возникают следующим образом:
При вычислении g (р, q) и Т (р, q) может войти ошибка
округления.	(8.1а)
4*
76
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. III
При вычислении fn^ (Т (р, q)) может потребоваться
интерполяция.	(8.1Ь)
При нахождении максимума по q может быть внесена
ошибка, так как мы учитываем лишь конечный набор
допустимых значений q.	(8.1с)
Из этого следует, что численное определение последо-
вательности {fn (р)} порождает новый многошаговый про-
цесс {фп (р)}, управляемый соотношением
Фп (р) = max te (Р, <?) + Фп-1 (7* (Р, <?))] + “п (р), (8.2)
где ип (р) изображает накопление различных упомянутых
выше ошибок. Мы надеемся, что, взяв достаточно много
значений р. и qj, можно сохранить | ип (р) | достаточно
малым, а это в свою очередь означает, что | fn (р) — <рп (р) |
мало. Если это так, то наш вычислительный процесс яв-
ляется устойчивым; если это не так, то все результаты,
полученные численно, надо рассмотреть с пристрастием.
Покажем теперь сравнительно просто, что процесс вычис-
ления {/п (р)} устойчив.
Пусть q — максимизирующее значение в исходном
функциональном уравнении
/п (р) = max [g (р, q) + /п_х (Г (р, q))],	(8.3)
a Q - максимизирующее значение в (8.2). Тогда
fn (р) = g (Р, Я) + /п-1 (?’ (Р, ?)) >g(P,Q) +
±fn-i(T(p,.Q)),
Фп (Р) = ё (Р, Q) + Фп-1 {Т (Р, <?)) + “п (Р) >
> g (Р, Я) + Фп-1 (Т (р, д)) + “п (р).
(8.4)
Следовательно,
fn (р) — Фп (р) > /п-1 (Т (р, <?)) — Фп-1 (Т (P,Q)> — ип (р),
< /п-1 (У (р> <?)) — Фп-1 (У (Р, <?)) — “п (р)
(8.5)
и, таким образом,
/п (р) — Фп (р) | < шах[| /п_! (р, Q) — фп—1 (Т (Р, Q)) |,
I /п-i (Т (Р, ?)) — Фп-i (Т (Р, <?)) | ] + I “п (Р) |-	(8-6)
10]
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
77
Предположим теперь, что мы рассматриваем случай, ког-
да I ип (р) I < е для р ^R. Тогда
max | /п (р) — <рп (р) | < max | /nJ (р) — <pn_! (р) | + е (8.7)
R	R
и, таким образом,
max | fn (р) — <рп (р) | < пг.	(8.8)
Линейный порядок роста максимума ошибки означает
устойчивость вычислительного процесса.
9.	Обсуждение
В это краткое изложение вычислительных аспектов
динамического программирования мы не включили не-
которые очень интересные и важные вопросы, как, напри-
мер, переформулирование задачи на языке функций мень-
шей размерности, применение множителей Лагранжа,
методы поиска, стохастическую аппроксимацию, т. е.
вопросы, к которым надо обратиться вслед за нашим до-
вольно поверхностным описанием методов 'аппроксима-
ции. Библиография по этим и родственным вопросам при-
водится в конце главы.
Нашей целью в этой главе до сих пор являлось крат-
кое описание основных приемов, встречающихся при чис-
ленном решении функциональных уравнений динамиче-
ского программирования. В следующем разделе мы рас-
смотрим некоторые детали.
10.	Задача о замене оборудования
Много интересных многошаговых процессов принятия
решений неожиданной математической глубины возникает
при управлении производственными предприятиями. Сос-
редоточим наше внимание на вопросах замены оборудо-
вания. Предположим, что определенная совокупность
- оборудования характеризуется покупательной ценой р
и функцией чистого ежегодного дохода п (£), где
п (t) — чистый доход от эксплуатации оборудования
в течение времени от момента t
до момента t + 1, t = 0, 1,2,... (10.1)
78
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. Ш
Пусть эта функция будет невозрастающей функцией от t.
Предположим еще, что рассматриваемое оборудование
является специальным и поэтому не имеет продажной
ценности. В начале каждого года необходимо принять ре-
шение сохранить или заменить оборудование. Нашей
целью является определение политики замены, которая
дает максимальный полный доход в течение TV-летнего
периода эксплуатации. Более точно, мы хотим решить
задачу управления с обратной связью, т. е. мы хотим
определить, сохранить или заменить оборудование, ко-
торому t лет, когда оставшееся время процесса составляет
К лет для всех целых чисел К и t. Введем, как обыч-
но, оптимальную функцию дохода fK (£),
/к (0 — чистый доход для К-летнего процесса,
вначале которого оборудованию уже t лет, при применении
оптимальной политики замены оборудования, К — 1,
2,...; t = 0, 1,2.	(10.2)
Из принципа оптимальности непосредственно выте-
кает функциональное уравнение
/к (t) = max [п (0 + /K_J (t + 1), — р + П (0) + /к-i (1)1,
К = 2, 3,...; t = 0, 1, 2,...	(10.3)
Кроме того, для одношагового процесса мы имеем
/х (t) = max [n (t), —p + n (0)].	(10.4)
Первый член в скобках в правей части уравнения (10.3)
соответствует непосредственн шу доходу .в результате
решения сохранить оборудование плюс наибольший до-
ход от оставшейся части процесса, начинающегося с обо-
рудованием годовой давности. Второй член возникает от
покупки нового оборудования, использования его в те-
чение одного года и вступления его в оставшуюся часть
процесса, имея уже годовую давность.
Сузим теперь ситуацию и составим программу ФОРТ-
РАН, которая даст как оптимальную политику, так и
доход. Предположим, что
п (t) = 10 - t, £ = 0,1;2,..., 10,1
n(0 = 0,	t=ll,12,..., j
10]
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
79
И
р = 10.	(10.6)
Уравнения (10.3) и (10.4) принимают вид
/1 (t) = max [n (t), 0] = n (t),	(10.7)
fK (0 = max [n (0 + /K-i (t + 1),	(1)].	(10.8)
Ниже мы воспроизводим программу ФОРТРАН IV с вы-
ходом на печать.
Программа подобна тем, которые применяются при
решении многих более сложных задач. Утверждения,
обозначенные числом 41, используются для определеных
начальных целей, как, например, выработки функции
п (t), которая запоминается как вектор XN (J), J = 1,2,...
..., 12. Переменная К есть указатель, который содержит
след числа остающихся шагов. «ПО-цикл», который на-
чинается с «DO 8 NT = 1,11», охватывает большую часть
вычислений. Вычисляется доход, который используется
для нахождения решения «сохранить» или «заменить»
ХКЕЕР и XRPL для оборудования, которому NT лет
при оставшихся К шагах. Выбирается наибольшее его
значение, отмечается и называется F (NT, 2). Полученное
решение записывается. Мы положим NQ (NT) = 1, если
правильным решением является «сохранить», 0 — если
правильное решение есть «заменить» и 2 — если доходы
от обоих решений одинаковы. Состояния
DO 10,1 = 1, 12, ‘ 10F (I, 1) = F (I, 2)
сдвигают уже вычисленные оптимальные значения функ-
ции дохода F (1,2) в устройство временной памяти F (1,2),
так что при следующем прохождении цикла мы будем
вычислять оптимальный доход для процесса, продолжи-
тельность которого больше на один год. Вычисления про-
изводятся для процессов продолжительностью в 25 и
менее лет.
Печатающее устройство записывает оптимальный до-
ход и оптимальное решение. Доходы обозначаются в Е-
системе обозначений. Например, 0,100 Е 0,2 есть 0,1 X
X102 = 10. Записи в десятой строке показывают, что
/ю(0)= 70 и при нулевом возрасте оборудования и остав-
шихся 10 годах правильным решением будет «сохранить».
80
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. ш
$JOB	2967, EQUIP, К0160, 1, 20, 20, G
$IBJOB EQUIP MAP
jlBFTG MAIN LIST
G	EQUIPMENT REPLACEMENT DIMENSION F(12,2), NQ (12), XN(12) DOI	J =1,11 E = J —1
1	XN(J) = 10.0 —E XN (12) = 0.0 DO3 J = 1,12
2 3	F(J, 1) = XN(J) NQ(J) = 1 PRINT4, (F(J, 1), NQ(J), J = 1,6)
4	FORMAT (1HO6(E13.3, 13)) K = 1
41	K = K + 1 DO8 NT = 1, 11 XKEEP = XN(NT) + F(NT 4-1, 1) XRPL=F(2, 1) IF(XKEEP-XRPL) 7, 6, 5
5	F(NT, 2) = XKEEP NQ (NT) = 1 GOTO8
6	F(NT, 2) = XKEEP NQ (NT) = 2 GO TO 8
7	F(NT, 2) = XRPL NQ (NT) = 0
8 ’	CONTINUE F(12, 2) = F (2, 1)
9	NQ (12) = 0 PRINT 4, (F(I, 2), NQ (I), 1 = 1,6) DO10 1 = 1, 12
10	F(I,1) = F(I, 2) IF(K —25.) 11,12,12
11 12 13	GO TO 41 CALL EXIT END
SENTRY	MAIN
$IBSYS	END JOB
101
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
81
<м
<м
<м
(М
см
см
<М
<м
<м
<М
м
<м
(М
<м
<М
eq
(М
см
(М
м
<м
(М
<М
eq
см
см
eq
см
(М
со
со
и
8 S
СО
И
и
Ы
ы
Ы
S
и
о
ш
со
<м
(М
<м
eq
см
<м
<м
<м
<м
м
И
со
(М
ы
И
<Х)
к
и
ы и
И
<М
<м
м
со
см
(М
см
(М
и
<м
м
И
см
ы
оо
и
00
н
8
о
и
И
СМ
и
и
и
<м
СМ <м
н ы
<М
<м
м
И
к
И
со
и
LD
и
о
СМ
СМ
И
f
И
М
и
и
<м
и
о
£3
и
ы
и
и
и
и
И
ы
и
и
и
и
о
(М см со со
<м
(М
(М
СМ
LQ
см
Ю
Ю
8
60
о
о
и Ы И
тН > со
м N
<М М
см
<М
<М <М
м
н
н
(М
<м <м
и и
и
и
LQ
eq
н
eq
и
Н
см
о
ю
и
оо
м
ы
и.и
и
И
И И
н
и
ю со со
<м
о
eq
(М
eq
см
W
СМ
И
оо
и
и
СМ

<м
ы
8
IQ
и
ы
н
и и и
и
8
W
И
<м
ы
И
СМ
ы
0,136Е	03	1	0,132Е	03	1	0,129Е	03	1	0Д27Е	03	1	0,126Е	03
0.142Е	03	1	О,133Е	03	1	0,135Е	03	1	0,133Е	03	1	0,132Е	,03
0,148Е	03	1	0,144Е	03	1	0.141Е	03	1	0.139Е	03	1	0.138Е	03
0,154Е	03	1	0.150Е	03	1	0,147Е	03	1	0,145Е	03	1	0.144Е	03
0,160Е	03	1	0,156Е	03	1	0.153Е	03	1	0,151Е	03	1	0,150Е	03
82
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
[ГЛ. Ш
Упражнения
1.	Обратитесь к «выходу на печать» для рассмотренной в тексте
задачи. Рассмотрите 10-шаговый процесс, начинающийся с оборудо-
ванием пятилетней давности. Определите оптимальный способ за-
мены.
2.	Заметим, что для табулированного процесса больше чем И по
продолжительности, увеличение опримального дохода для каждого
прибавленного года есть 6. Прокомментируйте это. Установите тео-
рему, используя это замечание, и докажите ее по индукции.
3.	В общих вычислительных программах для решения задачи
динамического программирования имеются три расположенных гнез-
дами цикла. Один относится к решению, другой — к состоянию и
третий — к шагам. Перепишите приведенную в тексте программу,
чтобы показать это явно.
4.	Напишите программу для решения другой какой-либо зада-
чи, рассмотренной в тексте.
Библиография и комментарии
§§ 1—6. Детальное обсуждение этого материала, а также обширные
приложения см. в книге.
Р. Веллман и С. Дрейфус, Прикладные задачи
динамического программирования, «Наука», 1965.
§ 7. Дальнейшее обсуждение и приложение этого аппарата см. в
цитированных выше книгах и в
R. Bellman, R. К а 1 a b a and М. Prestrud, Invariant
Imbedding and Radiative Transfer in Slabs of Finite Thickness,
American Elsevier Publishing Co., Inc., New York, 1963.
R. Bellman, H. Kagiwada, R. Kalaba and
M. Prestrud, Invariant Imbedding and Time-dependent
Processes, American Elsevier Publishing Co., Inc., New York,
1964.
R. Bellman, S. Dreyfus and S. A z e n, Some Ap-
plications of Polynomial Approximation to Dynamic Program-
ming, The RAND Corporation, RM-3728-PR, August 1963.
R. Bellman and S. Dreyfus, Fuctional Approxima-
tions and Dynamic Programming, Math. Tables and Other Aids
to Computation, vol. 13, 1959, pp. 247—251.
Приложения к численному решению дифференциальных уравнений в
частных производных можно найти в книге
R. Bellman, R. Kalaba and В. К о t k i n, On a
New Approach to the Computational Solution of Partial Diffe-
rential Equations, Proc. Nat. Acad. Sci. USA, vol. 48, 1962,
pp. 1325-1327.
Приложение динамического программирования к задачам прибли-
жения функций при помощи полигональных функций рассмотрено в
R. Bellman, On the Approximation of Curves by Line Seg-
ments Using Dynamic Programming, Comm. Assoc. Computing
Machinery, vol. 4, 1961, p. 284.
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
83
R. Bellman and В. К о t к i n, On the Appi oximation
of Curves by Line Segments Using Dynamic Programming,
The RAND Corporation, RM-2978-PR, December 1961.
B.	G 1 u s s, Least Squares Fitting of Planes to Surfaces Using
Dynamic Programming, Comm. Assoc. Comput. Machinery,
vol. 6, 1963, pp. 172-175.
B.	G 1 u s s, Further Remarks on Line Segment Curve-fitting
Using Dynamic Programming, Comm. Assoc. Comput. Machi-
nery, vol., 5, 1962, pp. 441—443.
B.	G 1 u s s, An Alternative Method for Continuous Line Seg-
ment Curve-fitting, Information and Control, vol. 7, 1964,
pp. 200—206.
B.	G ] u s s, A Line Segment Curve-fitting Algorithm Related
to Optimal Encoding of Information, Information and Control,
vol. 5, 1962, pp. 261—267.
Полиномиальная аппроксимация является примером аппроксимации
функции / (х) при помощи решений линейного дифференциального
уравнения вида + btu^N~^ + • и ~ 0. Обсуждение и при-
ложение этого аппарата приведено в
R.	Bellman and В. К а 1 a b a, Quasilinearization and
Nonlinear Boundary-value Problems, American Elsevier Pub-
lishing Company, Inc., New York, 1965.
§ 8.	Общие вопросы теории устойчивости рассмотрены в книгах
Р. Веллман, Теория устойчивости решений дифференци-
альных уравнений, ИЛ, 1954.
Р. Веллман и К. Кук, Дифференциально-разностные
уравнения, «Мир», 1967.
§ 9.	Обсуждение некоторых моментов, упомянутых в этом разделе
и другие ссылки указаны в книге, упомянутой в разделе 1 и в
R. Bellman, On the Reduction of Dimensionality for
Classes of Dynamic Programming Processes, J. Math. Anal.
AppL, vol. 3, 1961, pp. 358—360.
§10.	Дальнейшее обсуждение можно найти в книгах:
R. Bellman, Equipment Replacement Policy, J. Soc.
Ind. AppL Math., vol. 3, 1955, pp. 133—136.
R. К a 1 a b a and M. Juncos a, General Systems Appro-
aches to Telecommunications Optimization Problems, 1957,
IRE National Convention Record, Part 8, pp. 203—208.
D.D. McCracken, A. Guide to FORTRAN Programming,
John Wiley & Sons, Inc., New York, 1961.
Глава IV
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ В ТЕОРИИ
УПРАВЛЕНИЯ И ТЕОРИИ СВЯЗИ
1.	Введение
В первых двух главах мы дали абстрактное рассмот-
рение как многошаговых процессов, так и многошаговых
процессов принятия решения, а в главе III мы рассмот-
рели, хотя и кратко, вычислительную осуществимость
алгоритмов динамического программирования. В этой
главе мы хотим исследовать в деталях процессы, возни-
кающие в управлении и теории связи, структура которых
такова, что как стратегия, так и функции дохода могут
быть получены в простой и явной форме при помощи ме-
тодов функциональных уравнений динамического прог-
раммирования.
Мы рассмотрим как детерминированные, так и стоха-
стические процессы для того, чтобы подготовить путь для
изучения адаптивных процессов. Подготовив фундамент
посредством анализа специальных процессов, мы сможем
тогда продолжить в следующей главе изучение общего
вида многошаговых процессов принятия решений адап-
тивного типа.
2.	Управление с обратной связью
Рассмотрим подробно общий процесс управления де-
терминированного типа с обратной связью. Мы принимаем
линейное соотношение
== Ахп + уп. х0 = с,	(2.1)
где хп и уп суть JV-мерные векторы состояния и страте-
гии соответственно, а А есть матрица типа N х N.
Мы будем иногда называть уп вектором управления.
Мы предполагаем, что вектор уп выбран так, чтобы
3]
СКАЛЯРНЫЙ СЛУЧАЙ
85
минимизировать квадратичную функцию критерия, на-
пример,
N
Kn (Ж, у) = 2 [(жь Вхк) +	3/fc)] + («W» xn)- (2.2)
fc=o
Это не наиболее общая функция критерия этого типа, но
она может служить для иллюстрации общих методов, ко-
торые мы применяем. Если В = 0, то мы получим пример
того, что обычно называют управление конечным состоя-
нием (terminal control).
Полученные результаты оказываются весьма интерес-
ными и имеют много непосредственных приложений. Их
наиболее важное значение состоит, однако, в том, что они
могут служить отправной точкой при исследовании более
сложных процессов путем аппроксимации как в прост-
ранстве стратегий, так и в пространстве функций дохода.
3.	Скалярный случай
Для того чтобы проиллюстрировать особенности полу-
чающихся результатов, не усложняя обозначений и вы-
числений, начнем со скалярного случая. Найдя аналити-
ческую структуру решения, нетрудно будет получить
аналогичные результаты для векторно-матричного случая.
Пусть {ип} -у скалярная последовательность, опре-
деляемая соотношением
un+1 = аип + vn, и0 = с,	(3.1)
и пусть vn выбирается так, чтобы минимизировать ска-
лярную функцию
N-1
2 (ип 4“ yn) + un»	(3.2)
п=9
Обозначим значение этого минимума через fN (с). Тогда
обычным способом получим рекуррентное соотношение
fN (с) = min [с2 + V2 + /n-1 (ас + t>)]	(3.3)
86
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
для N > 1, где /0 (с) = с2. Легко показать по индукции
или иным способом, что fN (с) квадратична по с. Так как
fN (с) является, очевидно, четной функцией по с и fN (0) =
= 0, то
/n (с) = uNc2,	(3.4)
где uN есть постоянная, зависящая от N, но не от с. Под-
ставляя (3.4) в (3.3), получим соотношение
uNc2 = min [с2 + v2 + uN^ (ас + г)2]	(3.5)
\	V
или
ин = min [1 4~ w2 -f- un_i (а + w)2],	(3.6)
w
где w — v/c. Минимум определяется уравнением
w + Ujv-j (a + w) = 0,	(3.7)
откуда
Подставляя это соотношение в (3.6), получим рекуррент-
ное соотношение
.	a^uN-y
uN = 1 + -д-j---------,
(i + Mw-i)
(3.9)
где u0 = 1. Оптимальная стратегия описывается уравне-
нием
„	_ auN-lc
“	(1 + «w-1)
(3.10)
Мы получили функции стратегии и дохода, т. е. полное
решение задачи оптимизации. В упражнениях мы укажем,
как можно пойти далее и получить uN и vN явно в виде
функции от N.
Упражнения
1.	Напишите, используя (3.9)
а2
“№(l + a2)"(l + «w_1)’
41
ОБСУЖДЕНИЕ
87
и покажите, что последовательность ип, монотонно возрастая, стре-
мится к пределу й, определяемому как положительное решение
уравнения
и2 = 1 -р- а2и.
2.	Покажите, что uN может быть выражено явно в виде функции
от решения линейного разностного уравнения второго порядка и
получите аналитическое выражение для и ?.
3.	Покажите, что uN — и = О (kN) для некоторого % из интер-
вала 0 < X < 1, и определите X при 7V оо.
4.	Рассмотрите случай, когда функция критерия имеет вид
7V—1
n—Q
и изучите зависимость решения от X при X оо.
5.	Рассмотрите случай, когда функция критерия имеет вид
N—1
2, ^п+%(^-б)г.
о
Приближается ли при X оо оптимальная стратегия управления к
1
оптимальной
стратегии управления в задаче минимизации
У2
п
при условии на границе иу = Ь?
6.	Покажите непосредственно из определения (3.3), что fa (с)
монотонна по N для фиксированного с.
7.	Взяв и0 — —е, покажите, что /у (с)	2с2, и, следовательно,
используя упражнение 6,что /у (с) сходится при N -> ос.
4.	Обсуждение
Сделаем несколько замечаний по поводу полученного
выше решения. Во-первых, полная стоимость процесса
остается конечной при N оо. Во-вторых, оптимальное
управление линейно, т. е. на каждом шаге v пропорцио-
нально и. В-третьих, коэффициент пропорциональности,
согласно (3.10), стремится к константе, при N -> оо, при-
чем достаточно быстро. Все эти свойства имеют место
для многошагового процесса общего вида, рассмотренного
в разделе 2.
88
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
5.	Стохастический вариант
Рассмотрим теперь стохастический вариант рассмот-
ренного выше процесса. Вместо (3.1) мы напишем
»ntl = оип + vn + гп, г0 = с,	(5.1)
где гп — независимые случайные величины с заданной
функцией распределения. Величины vn надо выбрать,
используя управление с обратной связью, которое обсуж-
далось в разделе 13 главы II, так, чтобы минимизировать
математическое ожидание для
ЛГ—1
2 (4 + 4)	(5*2)
П=0
Пусть fN (с) обозначает минимум математического ожи-
дания. Как и выше, получим рекуррентное соотношение
fN (с) = min [(с2+ у2) + £ /N_i (ас + v + г) dG (г)], (5.3)
• v	J
предполагая для простоты, что dG (г) — общая функция
распределения для случайных переменных. Вновь нет-
рудно показать по индукции или другим способом, что
функция fN (с) квадратична по с. Следовательно, можно
написать
fN (с) = uN с2 + vNc + wN,	(5.4)
где uN, vN и wN не зависят от с. Подставляя в (5.3), будем
иметь
UtfC2 + VjyC +wN = min [(с2 + l?2) 4-
v
+ § [a/v-i (ас + v + г)2 + Улг-! (ас + v) + Мдг-i] dG(r). (5.5)
Мы можем теперь выразить минимизирующее значение
v непосредственно через uN1 и и таким образом по-
лучить рекуррентное соотношение для тройки vN,
wN] в зависимости от [u^i, г>я~и . Мы не будем вхо-
дить в детали, так как вычисления здесь простые и их
лучше предоставить читателю в качестве упражнения.
7]
МНОГОМЕРНЫЙ ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ
89
Упражнения
1.	Когда vn тождественно равно нулю?
2.	Получите аналоги результатов, установленные в упражне-
ниях 2 и 3 в конце раздела 3.
3.	Рассмотрите случай, когда гп не являются независимыми слу-
чайными переменными, начиная со случая, когда функция распре-
деления для гп имеет вид dG (г, rn-i)» т. ©• зависит от величины
Каково асимптотическое поведение функции управления в этом
сл учае?
6. Обсуждение
Отметим, что функция распределения для гп входит
только через ее первый и второй моменты. Следовательно,
любые две функции распределения с одинаковыми двумя
моментами приводят к той же самой функции дохода и
оптимальной стратегии, хотя обе реализации процессов
могут оказаться совершенно различными.
Отсюда ясно, что введение случайных переменных не
затрагивает существенно ни функцию стратегии, ни функ-
цию дохода. Следовательно, стохастическая теория уп-
равления, базирующаяся на линейных уравнениях и
квадратичном критерии, может быть принята лишь с
некоторыми оговорками. На первый взгляд кажется, что
она сложнее детерминированной теории управления, но
в действительности это не так. Лишь при применении бо-
лее точных методов оценки отклонений, в совокупности
с учетом нелинейности уравнений, стохастические свой-
ства вносят важные и радикальные отличия от детерми-
нированной трактовки.
.7- Многомерный детерминированный случай
Используя незначительное количество матричных обоз-
начений, можно теперь обратиться к многомерному ва-
рианту детерминированного процесса управления с об-
ратной связью, описанного в разделе 2. Пусть хп и уп —
М-мерные векторы, а А — матрица типа М х М • Для
заданного преобразования
*^п-+1 Ахп -]- J/n,	с,	(7»1)
5 р. Веллман, Р. Калаба
90
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
где хп изображает вектор состояния в момент времени п,
уп — вектор управления, надо выбрать уп так, чтобы
минимизировать функцию критерия
N
= S &хк) +	Зй’)] +	(7.2)
k=Q
где, как обычно, (х, у) обозначает скалярное произведе-
ние, т. е.
м
(x,y)=^xiyi,	(7.3)
а х. и у. — соответствующие i-e компоненты х и у. Пола-
гая fa (с) — min Ядн получим рекуррентное соотношение
Wk)
fN (с) = min [(с, Вс) + (у, у) + /;v-i (Ас + г/)], TV > 1, (7.4)
У
где /0 (с) = (с, с). Заметив, что fN (с) является квадратич-
ной формой относительно с, результат, который получа-
ется интуитивно, по индукции, или непосредственно из
исходной вариационной задачи, мы запишем fa (с) =
= (с, Флс). Подставляя это равенство в (7.4), получим со-
отношение
(с, Qnc) = min [(с, Вс) + (у, у) + (Ас + у, Qn-i (Ас + ?/))],
У
(7.5)
где Qq = Е. Обычный вариационный подход приводит к
линейному закону управления
ytE+Cfa-J + Q^Ac^O	(7.6)
или
У = - (£ + Qn^Qn-iAc.	(7.7)
Значение минимума легко вычислить, если заметить,
что
(у, У) + Ис + у, (Ас + у)) — (Ac, Qn-iAc) +
+ (У> У + Qw—iy + Qn—iAc) + (у, Qn—xAc). (7.8)
8]
НЕПРЕРЫВНЫЙ СЛУЧАЙ
91
В силу (7.6) и (7.7) это приводится к виду
(с, ^2ус)=(Лс, Qn^Ac)—((E+Qn-i^Qn-iAc. Q2У_1Лс)==
- (Ac. Qn-iAc) - ((E + Qn^ x
X (/?+(?n-i ^4c, Qn-iAc)) -p ((E+	i)-rAc. Qn-iAc) ==
= ((E+Qn^iY1Ac. Qn^Ac).
Приравнивая коэффициенты, получим из (7.5)
Q N= В + A'Qn^ (E + Qn-iY'A.	(7.9)
где Qo = E. Это позволяет рекурсивно вычислить QN.
Записывая (7.9) в виде
Qn ~ В + Af (Е + Qn~i) (Е + Qn-iY1 А —
- А' (Е + Qn-iY1 А - В + А’А - А' (Е + Qn-iY1 А.
(7Л0)
мы видим, что Qn равномерно ограничена и монотонно
возрастает в том смысле, что матрица QN — Qn-i является
положительно определенной.
Упражнения
1.	Покажите, что если {(Zv) есть ограниченная последователь-
ность положительно определенных матриц с таким свойством, что
матрица QN — Qn-i является неотрицательно определенной, то Q ?
сходится при N оо.
2.	Покажите, что Qn > удовлетворяющая (7.10), может быть полу-
чена посредством решения системы разностных уравнений поряд-
ка 2М.
3.	Рассмотрите стохастический процесс, порождаемый соотно-
шением
®n+1==^n + ?/n + rn, ®0 = с,
где гп — независимые случайные векторы. Получите аналоги при-
веденных выше результатов.
8. Непрерывный случай
Соответствующие результаты для непрерывного про-
цесса управления также являются довольно элегантными.
Рассмотрим задачу минимизации функционала
т
= Bx) + (y,y)]dt	(8.1)
О
5
92
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
по всем у, где векторы х и у связаны соотношением
=	+	х(0) = с.	(8.2)
Обозначая f(c, Т) = min J (у), из тех же рассуждений,
У
что и выше, получим
/(с,Г) = min [[(с, Вс) + (у,у)] Д + /(с + (4с + у)Д,Г —
~Д)] + о(Д). (8.3)
В пределе при Д -> О это приводит к дифференциальному
уравнению в частных производных
-^г = (с, Вс) + min [(у, р) + (Лс + р, grad/)], (8.4)
где, как обычно,
grad / =
2L
дс±
df
дсМ
(8-5)
Здесь через сх,с2,...,С1и обозначены компоненты вектора с.
Оптимальное управление в этом случае
grad/
(8.6)
Обозначая / (с, Т) = (с, Q (Т)с), имеем grad / = 2Q (Т)с.
Следовательно, оптимальное управление является линей-
ным
v = —Q(T)c	(8.7)
и (8.4) дает уравнение Риккати
= (8.8)
где Q (0) - 0.
8]
НЕПРЕРЫВНЫЙ СЛУЧАЙ
93
Упражнения
1.	Покажите, что (8.8) можно привести к линейному уравнению
при помощи подстановки Q = YZ1, где Y и Z удовлетворяют линей-
ным дифференциальным уравнениям.
2.	Покажите двумя способами, что Q (Г) стремится к пределу
при Т -> оо.
3.	Выше изложенные методы могут быть применены для изуче-
ния изменения функций Грина линейных функциональных уравне-
ний. Начнем с линейного дифференциального уравнения второго
порядка
и" + q (х)и — v (х), а < х < 1, и (а) = и (1) == О
и оставим последующие шаги в качестве серии упражнений для чи-
тателя. Покажите, что решение приведенного выше уравнения мож-
но записать в виде
1
и (х} = К (х, у, a) v(y) dy,
а
где К строится из решений однородного уравнения. Ядро К (х, у, а)
называется функцией Грина, соответствующей определенным гра-
ничным условиям.
4.	Определите К (х, у, а) в случае, когда функция q (х) по-
стоянна.
5.	Покажите, что уравнение Эйлера, связанное с задачей мини-
мизации функционала
1
J (и) — [7 (х) и2 — (и')2 — 2vu] dx,
а
является линейным дифференциальным уравнением второго порядка
и” — q (х)и — и с граничными условиями, определяемыми из ус-
ловий относительно и.
6.	Покажите, что если min J (и} — / (а, с), где и (а) — с, то
и
-^- = q(a)c2 — 2» (а) с +
4
7.	Покажите, используя уравнение Эйлера, что
11
f (а, с) = ^К (х, у, a) v (я) v (у) dx dy + 2cLi (г) + c2g (а),
а а
где ГА (v) есть линейный функционал по и.
8.	Подстановкой в уравнение из упражнения 6 получите урав-
нение
дк	дк дк^
~§а (X, у, а) =	(х, а, а) (а, у, а).
94
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
9.	Пользуясь уравнением и" + (q (х) + Xr (х))и = v (ж), полу-
чите аналогичную формулу для резольвенты и таким образом найдите
формулы, определяющие зависимость характеристических значений
и функций в конечной точке а. (См. R. Bellman and R. S. L e h-
m an, Functional Equations in the Theory of Dynamic Programming —
X: Resolvents, Characteristic Functions and Values, Duke Math.,
J., vol. 27, 1960, pp. 50-70.)
10.	Рассмотрите интегральное уравнение Фредгольма
т
и (ж) + v (х) 4-	(х, y)u(y)dy = 0,	0 а Т,
а
с единственным решением
т
и (х) = — v (х) +	(х, у, a.) v (у) dy.
а
Пользуясь методами динамического программирования, минимизи
руйте квадратичный функционал
т	т
J (и) = u2 (х) dx + 2 и (х) v.(x) dx 4-
а	а
Т Т
4- К (х, у) и (х) и (у) dx dy
а а
и получите уравнение
(*> У> a) =Q («> a) Q (а. У, а).
(См. R. В е ] 1 m а п, Frunctional Equations in the Theory of Dynamic
Programming — VII: A Partial Differential Equation for the Fred-
holm Resolvent, Proc. Amer. Math. Soc., vol. 8, 1957, pp. 433—440.
Дальнейшие применения методов динамического программирования
можно найти в книге R. Bellman and Н. Osborn, Dynamic
Programming and the Variation of Green’s Functions, J. Math.
Mecn., vol. 7, 1958, pp. 81—86 и в главе 9 книги R. Bel-
lman, Introduction to Marix Analysis, McGraw-Hill Book Co., Inc.,
New York, 1960).
11.	Рассмотрите задачу минимизации квадратичного функцио-
нала
т
J (и) = (и2 4- и'2) dt
о
9]
ТЕОРИЯ ПРОГНОЗИРОВАНИЯ
95
при условиях и (0) — с, | и' К т для 0 < t < Т. Обозначив
/ (с, Т) — min J (и), покажите, что
и
/т = min [с2 4- »2 4- г>/с].
12* Получите аналитический вид / (с, Т) и вид оптимальной стра-
тегии, определяя f (с, Т) сначала для малых Т, а затем увеличивая
значение Т до тех пор, дока не встретится ограничение.
(Для систематического подхода к вариационным задачам с ог-
раничениями при помощи леммы Неймана — Пирсона см. моногра-
фию Р. Веллман, И. Гликсберг, О. Гросс, Некоторые
вопросы математической теории процессов управления, ИЛ, 1962.
Для подхода, использующего классические вариационные методы
и их обобщения, полезно прочитать L. D. Berkovitz, Varia-
tional Methods in Problems of Control and Programming, J. Math.
Anal. AppL, vol. 3,	1963, pp. 145—169. Л. С. П о н т-
рягин, В. Г. Болтянский, Р. В. Гамкрелидзе
и Е. Ф. М и щ е н к о, Математическая теория оптимальных про-
цессов, М., 1961).
13. Рассмотрите задачу минимизации функционала
т
J (u) = ^(u'2 4- g(u))dt, u((Y)~c.
о
Пусть Un будет n-м приближением и пусть un+J есть функция, мини-
мизирующая
т
(* Г	(и—и„)2	1
Лг(«О = ) L'2+g(“„)+(«-“„)g'(“n) + —~	k
0 L	J
При каких условиях последовательность {un} сходится к функции
и (0, минимизирующей / (и). (См. М. А о k L On the Approximation
of Trajectories and its Applications to Control Systems Optimization
Problems, J. Math. Anal, and AppL, vol. 9, 1964, pp. 23—41.)
9.	Теория прогнозирования
Фундаментальной целью науки является прогнозиро-
вание будущего на основе знания прошлого и настоящего.
Так как классические методы базируются на дифферен-
циальных уравнениях, требующих большего объема све-
дений, чем мы обычно располагаем, за последние годы
получили развитие разные подходы, основанные на веро-
ятностных рассмотрениях.
96
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
Рассмотрим, в частности, задачу получения оценки ап
для всех п 0, задавая последовательность {ап} для
п = 0, —1, —2, ... Вообще, пусть даны две после-
довательности: {afe} и {bfe}; как получить наилучшую
оценку для если известны только ак и различные кор-
реляции?
Один из путей подхода к этой задаче, который выте-
кает из аналитических соображений, а также интуитивно
из электротехнических аналогий, состоит в отыскании
третьей последовательности {и].}, обладающей свойством
м
Z==0
(9.1)
Следуя Колмогорову и Винеру, целесообразно потребо-
вать, чтобы щ определялись из условия минимизации
квадратичного выражения
я	и
2 (^-£«Л-02.	(9.2)
fc==0	z=o
Легче исследовать предельную задачу, где (9.2) принимает
вид
N	N
(fck-2 Wt-i)1	(9.3)
или вид
Т	R
§ (b (t) — a (t — s) и (s) ds)* dt.	(9.4)
о	*o
Как можно было ожидать из предыдущего анализа
вариационные задачи такого рода могут быть легко и
систематически рассмотрены при помощи метода функ-
циональных уравнений динамического программирова-
ния, примененного в предыдущих разделах. Интересую-
щегося читателя мы отсылаем к ряд} источников, указан-
ных в конце главы.
И]
ЭФФЕКТИВНЫЙ ИГРОК
97
10.	Передача информации
Обратимся к другой интересной области современных
исследований, которая занимает центральное место в тео-
рии передачи информации. Мы можем разложить процесс
на пять частей: (а) образование данных; (Ь) кодирование
данных для их передачи; (с) передача закодированных дан-
ных; (d) декодирование полученного в результате пере-
дачи сигнала; (е) использование декодированного сигнала.
Процесс может быть значительно усложнен при вве-
дении контура обратной связи для целей проверки.
В прошлом, и в значительной мере в настоящем, име-
лась неудачная, но понятная тенденция изучать эти части
порознь, мало зная или вовсе не признавая существова-
ния других частей. В лучшем случае эта «великолепная»
изоляция приводит к неполным результатам; в худшем
случае она приводит к полностью ошибочным результа-
там. Таким, в частности, будет случай, когда результаты,
полученные при идеализированной пропускной способ-
ности канала связи, применяются при недостаточных све-
дениях об основном процессе и его целях.
Весьма существенно при изучении этих сложных за-
дач учитывать взаимодействие указанных выше различ-
ных частей систем связи. Для иллюстрации подхода, ко-
торый можно применить, мы обсудим задачу, впервые
поставленную и частично решенную Келли. Применяя
методы динамического программирования, можно решить
исходную задачу и обобщить ее рядом способов. Чтобы
упростить изложение, мы игнорируем здесь вопросы ко-
дирования и декодирования. Существенный момент сос-
тоит в том, что передача информации используется для
целей принятия решения.
11.	Эффективный игрок
Предположим, что неразборчивый в средствах игрок
получает априорную информацию относительно результа-
тов спортивных событий по телефону при наличии боль-
шого шумового фона. Так как время весьма ограничено,
ему передают только слова «выигрыш» или «проигрыш»,
и он должен действовать, базируясь на этой информации.
98
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ IV
Из-за трудностей связи имеется вероятность, что он слы-
шит то или иное слово неправильно. Имея это в виду и
зная вероятность неправильного приема, сколько он дол-
жен ставить в каждом случае?
Ясно, что его тактика заключения пари должна в зна-
чительной мере зависеть от функции критерия, которым
он пользуется для оценки выгоды. Если, например, он
хочет максимизировать математическое ожидание выиг-
рыша, то он держит пари на полное свое состояние вся-
кий раз, когда считает, что вероятность получения пра-
вильной информации превышает 1/2. Ясно, что это очень
рискованная политика, так как не исключена возможность
полного краха в последовательности его ставок.
Следовательно, по-видимому, целесообразнее пользо-
ваться более гибким критерием, таким, который предот-
вращает полный крах, независимо от того, что произой-
дет. Мы можем обеспечить более осторожное поведение
путем принятия других критериев. Например, игрок мо-
жет решить держать пари так, чтобы максимизировать
математическое ожидаемое логарифма полной суммы де-
нег, которая будет в его распоряжении в конце игры.
Чтобы увидеть, как это воздействует на политику зак-
лючения пари, предположим, что р есть вероятность того,
что информация является правильной, что игрок обладает
в начале игры х долларами и что он хочет сделать ставку
у, которая максимизирует математическое ожидание ло-
гарифма полной суммы денег, которую он будет иметь
после того, как пари будет оплачено, при том или ином
результате игры. Математическое ожидание имеет вид
Е (у) = р log (х + у) + (1 — р) log (ж — у). (11.1)
Как нетрудно видеть, максимум достигается при у =
= (2р — 1)я, если р 1/2, и при у = 0 в противном слу-
чае. Рассмотрим теперь наиболее интересный случай,
когда р 1/2. Максимальное значение Е (у) будет
Ятах = log X + log 2 + р log р + q log q, (11.2)
где q ~ 1 — p. Первые два члена определяют математи-
ческое ожидание при полной информации р = 1. Вторые
два члена, которые являются отрицательными, и будут ме-
12]
ПРИМЕНЕНИЕ МЕТОДА
99
рой потерь от дезинформации и, таким образом, могут
быть использованы для оценки влияния помех передачи.
Рассмотрим теперь многошаговый процесс заключе-
ния пари, в котором игрок получает информацию, делает
ставку, выигрывает или проигрывает, получает второй
сигнал и т. д. Какова должна быть теперь его оптималь-
ная политика?
12.	Применение метода динамического
программирования
Следуя обычным путем, обозначим
fN (х) — математическое ожидание логарифма оконча-
тельного капитала, полученное в результате N-шагового
процесса заключения пари, который начинался при ито-
говой сумме х и соответствовал оптимальной политике.
(12Л)
Принцип оптимальности дает рекуррентное соотно-
шение
fN(x)= max [р/w-i (ж + 2/) + (1 — p)/x-i(^ — г/)], (12.2)
О^У-^х
где N > 2, a f^x), как было показано выше, имеет вид
Здесь
Л (я) =	+ К.
(12.3)
log 2+ р log р+(1 — р) log (1— р),
О
(12.4)
Рекуррентное соотношение (12.2) остается тем же са-
мым, несмотря на ограниченность функции, которой мы
пользуемся. Начальная функция (х) определяет струк-
туру оптимальной политики. До некоторой степени по-
разительное свойство логарифма то, что при такой
функции удается получить простое явное решение урав-
нения (12.2) при начальном условии (12.3).
Покажем теперь по индукции, что
/ (х) = log х + NK	(12.5)
100
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
для TV > 1 и что оптимальная политика не зависит от N
и имеет в точности вид, приведенный выше, а именно,
1
2 ’
1
(2р — i)x,
2/ =
(12.6)
0
Предположим, что этот результат справедлив для N.
Тогда
Mi (*) = max [р (log (х + у) + NK) + (1 — р) X
X [log (я — у) + NK]] = NK+ max [р log (х + у) +
4-	(1 — р) log (х — у)] = NK + log х + К =
~log;r + (/V + l)X. (12.7)
Это доказывает оба утверждения.
Упражнения
1.	Рассмотрите случай, в котором свойства передачи изменяются
со временем, так что на^-м шаге вероятность правильной передачи
есть рк, где р% > 1/2. Покажите, что максимум математического
ожидания логарифма к*. питала по истечении N шагов дается выраже-
нием
N
log х + N log 2 + 2 (Pk log Pk + (1 — Pk) log (1 — Pit))-
te=l
2.	Рассмотрите случай, когда вероятность правильной передачи
&-го сигнала зависит от того, правильно или неправильно будет
передан — 1)-й сигнал
3.	Рассмотрите ситуацию, когда М различных сигналов может
быть передано на любом шаге и игрок располагает следующими
данными:
= условная вероятность того, что сигнал j излучался ис-
точником, если наблюдателем был принят сигнал i.
qi — вероятность того, что наблюдатель на любом шаге полу-
чит сигнал i,
r-t = доход от выигранного пари, отнесенный к одной единице
сигнала j.
М
Игрок получает сигнал / и заключает пари на величину z^,	ж,
i =1
утверждая, что в действительности начальный сигнал был i.
ЁЙБЛИОГРАфЙЯ и КОЙМЁ111АРЙЙ
101
4.	Рассмотрите случай континуума сигналов, —ос < и < оо,
где задана условная вероятность dG (и, v) того, что сигнал с отметкой
между v и v + dv послан, если был принят сигнал и и, кроме того,
заданы все другие, относящиеся к делу величины.
(Об этих и других результатах можно прочитать в R. В е 1-
Iman and R. К а 1 a b a, Dynamic Programming and Statistical
Communication Theory, Proc. Nat. Acad. Sci. USA, vol. 43, 1957, pp.
749—751. R. Bellman and R. К a 1 a b a, On Communication
Processes Involving Learning and Random Duration, 1958, IRE Na-
tional Convention Record. Part 4, pp. 16—20. R. Bellman and
R. К a 1 a b a, Dynamic Programming and Adaptive Processes:
Mathematical Foundations, IRE Trans. Automatic Control, vol. AC-5,
1960, pp. 5—10. P. Веллман, Процессы регулирования с адап-
тацией, Физматгиз, 1964.)
5.	Что должен делать игрок, если р < 1/2?
13. Обсуждение
Весьма важный результат, который непосредственно
вытекает из изложенного, состоит в том, что функция
критерия 1о§зд позволяет отделить влияние начальных
ресурсов от влияния помех передачи. При этих усло-
виях мы можем забыть о назначении сигналов и изучать
свойства канала связи сами по себе. Оказывается также,
что та же самая функция р log р + (1 — р) log (1 — р}
возникает при изучении некоторых специальных задач
кодирования, как результат важного структурного свой-
ства, и в статистической механике в виде энтропии.
Известно несколько интересных применений функции
энтропии в теории передачи информации и, к сожалению,
значительно большее число необдуманных и ведущих к
заблуждению попыток ее применения. Вышеприведенный
анализ показывает, как тесно функция энтропии связана
с функцией критерия log х^. При применении иных кри-
териев и дополнительном учете других обстоятельств,
мы получим совершенно иную меру для оценки влияния
помех в канале связи, однако не сможем отделить влияния
начальных ресурсов от влияния канала связи.
Библиография и комментарии
§§ 1—3. См. гл. X в книге
Р. Веллман и С. Дрейфус, Прикладные задачи
динамического программирования, «Наука», 1965 и главу
IX книги
102
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
R. Bellman, Introduction to Matrix Analysis, McGraw-
Hill Book Co., New York, 1960,
где имеются дополнительные ссылки.
§ 4. Рекомедуем работы
D. S. Adorno, The Asymptotic Theory of Control Systems
— I: Stochastic and Deterministic Processes, Jet Propulsion
Lab., Technical Release 34—73, June 30, 1960.
R. Bellman and R. В u c y, Asymptotic Control Theory,
J. SIAM Control, vol. 2, 1964, pp. 11—18.
§ 5. О стохастических процессах управления см.
Y. Sawaragi, Y. Sunahara, Т. Ono, A Study on
Dynamic Optimization of Control Systems with Gaussian Ran-
dom Outputs, Technical Reports of the Engineering Research
Institute, Kyoto Univ., vol. 14, 1964, Report No. 114, pp.
61-87.
J.J. Florentin, J. H. Westcott and J. D. Pear-
son, Approximation Methods in Optimal and Adaptive Con-
trol, Proc. IFAC Second Congress, Basel, Switzerland,
1963.
J. J. Florentin, Optimal Control of Continuous Time,
Markov, Stochastic Systems, J. Elec. & Control, vol. 10, 1961,
pp. 473-488.
H. Cox, On the Estimation of State Variables and Parameters
for Noisy Dynamic Systems, IEEE Trans, on Automatic Cont-
rol, vol. AC-9, 1964, pp. 5—12.
H. Cox, On Estimation of State Variables and Parameters,
Joint AIAA-IMS-SIAM-ONR Symposium on Control and Sys-
tem Optimization, U.S. Naval Postgraduate School, Monterey,
California, January 27—29, 1964.
J. T. T о u and В. V adhanaphuti, Optimum Cont-
rol of Nonlinear Discrete-data Systems, AIEE Trans., vol. 80,
1961, pp. 166—171.
J. T. T о u, Design of Optimum Digital Control Systems via
Dynamic Programming, Proc. Dynamic Programming Works-
hop, J. E. Gibson, ed., Purdue University, Lafayette,
Indiana, 1961, pp. 37—66.
J. E. Gibson, Optimum Design of Digital Control Systems,
Academic Press Inc., New York, 1963.
R. E. К a 1 m a n, New Methods and Results in Linear Pre-
diction and Filtering Theory, RIAS, Technical Report 61-1,
1960.
§ 7. Cm.
R. Beckwith, Analytic and Computational Aspects of
Dynamic Programming Processes of High Dimension, Jet Pro-
pulsion Lab., 1959.
C. W. Merriam, III, An Algorithm for the Iterative Solu-
tion of a Class of Two-point Boundary Value Problems, J. SIAM
Control, vol. 2, 1964, pp. 1—10.
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
103
С.	W . Merriam, III, A Class of Optimum Control Systems,
J. Franklin Institute, vol. 267, 1959, pp. 267—281.
C.	W . Merriam, III, Computational Considerations for
a Class of Optimum Control Systems, Proc. First Internal.
Congress of IFAC, J. F. Coales, ed., Butterworth & Co., Ltd.,
London, 1961, vol. II. pp. 694—701.
C.	W. M e r r i a m, III, Use of a Mathematical Error Criterion
in the Design of Adaptive Control Systems, AIEE Trans., vol.
78, 1960, pp. 506—512.
C.	W. Merriam, III, An Optimization Theory for Feedback
Control System Design, Information and Control, vol. 3, 1960,
pp. 32—59.
Обсуждение процессов с запаздыванием см.
J.	D. К ramer, Information and Control, vol. 3, 1960, pp.
299-326.
§ 8.	Результаты этого вида впервые получены в
R. Bellman, On a Class of Variational Problems, Q. AppL
Math., vol. 14, 1957, pp. 353-359.
§ 9.	См. приложение H. Левинсона в книге
N.	W i e n e r, The Extrapolation, Interpolation and Smoot-
hing of Stationary Time Series and Engineering Applications,
John Wiley and Sons, New York, 1942.
См. также главу IX книги «Matrix Analysis», стр. 155 и цитированную
выше статье Калмана. Калман систематически применял теорию
динамического программирования к задачам проектирования и уп-
равления и получил весьма обстоятельные результаты. Некоторые
его последующие результаты см. в
R.	Е. К alman and J.E. Bertram, A Unified Appro-
ach to the Theory of Sampling Systems, J. Franklin Insti-
tute, vol. 267, 1959, pp. 405—436.
R.	E. К alman and J.E. Bertram, General Synthesis
Procedure for Computer Control of Single-loop and Multiloop
Linear Systems, AIEE Trans., vol. 77, 1959, pp. 602—609.
R.	E. К alman and R. W. К о e p c k e, The Role of
Digital Computers in the Dynamic Optimization of Chemical
Reactions, Proc. Western Joint Computer Conference, San Fran-
cisco, California, March 1959, pp. 107—116.
§10.	Исходные результаты Кэлли см. в
J.	Kelly, ANew Interpretation of Information Rate, Bell
System Tech. J., vol. 35, 1956, pp. 917—926.
Приведенный в разделе 12 подход был дан в статьях, цитированных в
конце раздела 12. Дальнейшее обсуждение этих вопросов см. в
J.	Marshak, Remarks on the Economics of Information,
Cowles Foundation Discussion Paper No. 70, April 1959.
Большое внимание было сосредоточено на управляемых процессах,
описываемых линейными дифференциальными уравнениями вида
я* — Ах + у, где компоненты вектора у удовлетворяют ограниче-
ниям |^|	0 t Г и должны быть выбраны так, чтобы
104
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[ГЛ. IV
минимизировать время, требуемое для переводахв начало координат.
Математическая глубина этих вопросов весьма поразительна, и
для их изучения был применен ряд мощных математических средств.
См.
R.	Bellman, I. Glicksberg and О. G г о s s, On
the Bang-bang Control Problem, Q. Appl. Math., vol. 14,
1956, pp. 11—18.
P.	Веллман, И. Гликсберг, О. Гросс, Некото-
рые вопросы математической теории процессов управления,
ИЛ, 1962.
J.P. LaSalle, On Time-optimal Control Systems, Proc.
Nat. Acad. Sci. USA, vol. 45, 1959, pp. 573—577,
где могут быть найдены дополнительные ссылки.
Глава V
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
1.	Введение
Перейдем теперь к некоторым более реалистическим и,
естественно, более общим и интригующим вариантам не-
определенности и соответствующим этим вариантам про-
цессам управления. Процессы, которые мы обсудим,
являются математически совсем новыми. Они, однако, но-
вы в научном отношении лишь в том смысле, что большин-
ство математиков, инженеров и ученых до последнего
времени категорически отказывались даже допускать
мысль об их существовании. Тем не менее они всегда,
хотя и будучи незванными гостями, присутствовали за
банкетным столом науки.
В нашем изучении детерминированных процессов уп-
равления мы делали традиционные предположения о том,
что переменные состояния идентифицируемы и наблюдае-
мы, что последовательность возможных решений извест-
на, что исходные причины и взаимные влияния также
известны, а цели изучаемого процесса принятия решений
хорошо определены. Математические результаты, полу-
ченные таким путем, будут более или менее достоверными
приближениями. Когда же речь идет о приложениях,
то «риск — за счет потребителя», так как в науке нет
своего рода «Закона о пище и лекарствах», требующего
ярлыка с указанием содержимого.
Первым шагом на пути отказа от полностью детерми-
нистской концепции и шагом, имеющим существенное
значение, является классическая теория вероятностей с
ее введением случайных переменных. В этой главе мы
хотим указать существование еще более высокого уровня
неопределенности и показать, что метод функциональных
уравнений теории динамического программирования
106
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[ГЛ. V
может быть использован для получения аналитических фор-
мулировок даже в этих’ более сложных условиях.
Чтобы ориентировать читателя в этих новых направ-
лениях, не отпугивая его от них насколько это возможно,
мы изложим в некоторых деталях сравнительно простые
процессы с адаптацией — аналоги процессов, рассмот-
ренных выше в детерминированной и стохастической
постановке. Следуя этому, мы пересмотрим наши методы
и укажем подход к исследованию общего вида процессов
управления с адаптацией. Соответствующий многошаго-
вый процесс принятия решений приводит к аналитиче-
ским трудностям и требует больших усилий для получения
численных решений при помощи вычислительных машин.
Эта область содержит много проблем, заслуживающих
исследования.
2.	Линейный процесс управления с адаптацией
В главе IV рассматривалась задача о минимизации
функции критерия
N
Rn= ^{Un + vl)	(2.1)
71=0
по всем г?п, где
= аип + vn, и0 = с.	(2.2)
Для определения функции стратегии и функции дохода
был применен метод функциональных уравнений. Затем
мы обратились к задаче минимизации математического
ожидания Bjv, применяя управление с обратной связью,
где ип и vn —случайные переменные, связанные соотно-
шением
ип+1 = аип + vn + rn, и0 = с,	(2.3)
со случайными переменными гп. Наиболее легким явля-
ется случай, когда гп — независимые случайные пере-
менные с известной общей функцией распределения; без
чрезмерных трудностей можно изучить и случай наличия
корреляций, когда функция распределения гп зависит от
значений rn-i, rn_2,...,rn-fc.
3]
АНАЛИТИЧЕСКАЯ ФОРМУЛИРОВКА
107
Рискнем теперь отправиться дальше в неизвестность,
полагая, что существование функции распределения из-
вестно, однако точный вид ее неизвестен. Так как интере-
сующие нас процессы не рассматривались выше, мы долж-
ны вновь точно определить, что мы имеем в виду под
оптимальной стратегией и математическим ожиданием. На-
шей целью является обеспечить какую-либо единообраз-
ную аналитическую формулировку процессов управле-
ния, возникающих в ситуациях этого характера. Заметим,
что мы говорили... «какую-либо» единообразную форму-
лировку, а не «единообразную» формулировку. Как мы
укажем впоследствии, имеется много путей, которым
можно следовать, и каждый из них имеет ряд как привле-
кательных, так и непривлекательных особенностей. Эта
свобода возможно и рассеивает внимание студента, но
это часть платы за риск на пути в незнаемое.
3.	Аналитическая формулировка
Мы начнем; как обычно, с упрощения. Вместо того
чтобы считать, что функция распределения полностью
неизвестна, предположим, что ее аналитическая струк-
тура известна, но некоторые параметры неизвестны. Так,
например, мы можем использовать гауссову функцию рас-
пределения с неизвестными средним значением и дис-
персией, или распределение Пуассона с неизвестным сред-
ним значением, или общее распределение Пирсона с не-
известными параметрами и т. д.
Рассмотрим сперва простейший, пожалуй, случай,
когда г имеет биномиальное распределение. Переменная
г принимает значение 4-1 с вероятностью р и —1с веро-
ятностью (1 — р). Как указывалось в предыдущем параг-
рафе, мы, однако, не располагаем какими-либо сведения-
ми о численном значении />, помимо очевидного факта,
что p<Z 1- Мы желаем поэтому оценить р на каждом
шаге на основе последовательности значений г, которые
появились на предыдущих шагах. Это, по-видимому, це-
лесообразная процедура. В процессах этого типа мы стал-
киваемся с проблемой одновременного обучения и функ-
ционирования. Вместо термина «обучение», который пе-
ренасыщен психологическим содержанием, мы примем
108
ПРОЦЕССЫ УПРАВЛЕНИЯ с АДАПТАЦИЕЙ [ГЛ. V
термин «адаптация», так как этот термин пока еще жестко
не фиксирован. Следовательно, процессы этого типа бу-
дем мы называть процессами управления с адаптацией.
Упрощая вновь, предположим, что достаточно просто
записать число раз, когда +1 или —1 появлялись в прош-
лом. То, что здесь принято в качестве математического
предположения, зачастую может оказаться естественным
ограничением в том смысле, что часто на практике лишь
часть полной информации используется для принятия
решения; сбор более обширной информации может ока-
заться слишком дорогостоящим или требующим чрезмер-
ной затраты времени. G другой стороны, может оказаться,
что дальнейшая информация относительно процесса уже
не является более необходимой. Мы вернемся ниже к
этому вопросу о «достаточных статистиках».
Согласимся оценивать р при помощи формулы
__ т + 1	/Ч 4\
Ртп— fn + n+2 1
если наблюдались т раз +1 и п раз —1. Снова вопрос,
почему принята эта процедура оценки, должен и будет
обсужден. Мы обратимся теперь к вычислению математи-
ческого ожидания. Нашим основным предположением
является то, что мы вычисляем математическое ожидание
так, как если бы оценки вероятностей были бы действи-
тельными вероятностями в стохастическом процессе уп-
равления того типа, который мы уже рассматривали. Этот
стохастический процесс управления есть один из описан-
ных в (2.3) с известной функцией распределения для г.
Оптимальная стратегия теперь определяется как страте-
гия, которая минимизирует математическое ожидание
функции критерия.
Наконец, отметим, что концепция переменной состояния
существенно расширяется. В дополнение к текущему фи-
зическому состоянию мы должны также включать некото-
рую прошлую историю процесса. Одним из преимуществ
метода динамического программирования является то, что
он автоматически распространяется на эти более общие
ситуации. Мы остановимся более подробно на этой идее
в последующих разделах.
41
АНАЛИТИЧЕСКИЕ АСПЕКТЫ
109
После этих предварительных указаний вернемся к
аналитическому описанию. Как и ранее, мы возьмем функ-
цию критерия простого аналитического вида
N—1
Rn == 5 (ип + уп) +	(3.2)
п — 0
Введем функцию
fN (с, т, п) ~ математическое ожидание RN, полученное
при применении оптимальной стратегии, начинающейся
в состоянии с при наблюдениях т раз -\-i и п раз— 1.
(3.3)
Принцип оптимальности дает функциональное уравнение
fN(c, т, п) = min [(с2 + г2) + Ртп /n-i (ас 4- v + 1, т +
V
+ 1,п) + (1— Pmn)fN-i(ac + v — 1, т, «4-1)1 (3.4)
для N > 1, где /0 (с, т, п) = с2, а ртп вычисляется сог-
ласно (3.1). Мы таким образом привели изучение процес-
са управления с адаптацией к задаче получения аналити-
ческого или численного решения функционального урав-
нения.
4.	Аналитические аспекты
Легко видеть, что, как и выше,
fN п) — UN п)с* + VN (m> п)с + WN (т, ^), (4.1)
где uN, vn и wn не зависят от с. Подставляя (4.1) в (3.4),
получим уравнение
uN (т, п) с2 + vn п) с +^2v (m> и) = min [(с2 + ^2) +
+ Ртп (uN-i (т + 1, п) с2 + (те 4- 1, га) с 4-
+ WN-1 (те 4- 1, «)) + (1 — Ртп) (“N-1 (те, п4-1)с2 +
+ ^-1(те,п4-1)с4-^_1(те, «4-1))]. (4.2)
Отсюда мы вновь видим, что оптимальное управление
является линейным, и можем получить рекуррентное
соотношение для тройки luN(m, м), vN (т,п), ivn (т,п)]. Мы
но
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[ГЛ. V
предоставляем это читателю для выполнения в качестве
упражнения. Предостережем его, однако, указав, что
определение асимптотического поведения этих величин
при N оо уже больше, чем упражнение.
5.	Обсуждение
Сделав определенное число предположений при поста-
новке задачи, хотелось бы провести некоторую проверку,
некоторый контроль в наших математических эксперимен-
тах. Например, следовало бы показать, что с вероятностью
1 вышеприведенный процесс сходится к стохастическому
процессу управления, для которого р известно. Под схо-
димостью мы здесь понимаем, что оптимальная стратегия
для одного процесса сходится к оптимальной стратегии
для другого и что сходятся также функции дохода. Хотя
результаты такого рода представляются ясными интуи-
тивно, строгого доказательства пока не дано и мы здесь
имеем обширное поле для исследований. Как увидит
читатель, не так просто использовать рекуррентные соот-
ношения, полученные согласно (4.2), для аналитических
или вычислительных целей.
6.	Априорная функция распределения
Рассмотрим теперь более трудный случай, когда мы
располагаем априорной функцией распределения dG для
т. е. вероятностью для вероятности. Как следует видо-
изменить эту функцию распределения на основе наблю-
дений над процессом? Согласимся вновь применить ме-
тод Байеса для рассмотрения и обсуждения этого вопроса.
Если из наблюдения над г получена величина +1, то мы
заменяем dG новой функцией распределения
dG*=,	(6.1)
J pdG
о
а если наблюдалась величина —1, то мы пользуемся
следующей функцией распределения:
dG_ = <L~P)dGW .	. (в 2)
1(1 -p)dG
О
7]
ИГРА G АДАПТАЦИЕЙ
111
Интересно, что здесь вновь достаточно только сохра-
нить след числа плюсов и минусов в значении г. Не обя-
зательно, в частности, указывать зависимость от dG (г).
Если мы возьмем dG (г) = dr, то функциональное урав-
нение в точности совпадает с уравнением (3.3) и правило
для вычисления ртп сведется к полученному в разделе
3 правилу (3.1).
Имеются различные пути для обоснования преобразо-
ваний (6.1) и (6.2), базирующиеся на теории игр и ста-
тистических решений. Однако эти обоснования требуют
еще дальнейшего обоснования и т. д. Мы лишь предста-
вим наши предположения в более удобном виде.
7.	Игра с адаптацией
Вернемся теперь к задаче об игроке, использующем
несовершенный канал связи, задаче, которой мы уделили
некоторое место в главе IV. Предположим теперь, что
игрок даже не знает вероятности того, что сигнал будет
передан неправильно, но он знает, что вероятность эта
существует и не меняется со временем. Сформулируем за-
дачу оптимального проведения игры в вышеприведенных
терминах.
Как и выше, мы можем постулировать априорную
функцию распределения dG (р) для р и согласиться,
в соответствии с формулами раздела 6, преобразовать
dG (р) в
dGmn{p) = ^m^^P)	(7<1)
О
после того, как отмечено т успешных игр и п неуспешных.
Если мы обозначим
fN (х, т, п) = математическое ожидание log## при
начальном капитале х и информации, что до сих пор
имелось т успехов и п неудач, и применении оптимальной
политики,	(7.2)
то мы получим уравнение
fN (х, т, п) = max [pmnfN~i (x + y,m + i,n) +
+ (1 — Ртп) Jn-1 (х — у,т,п + 1)], (7.3)
112
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[ГЛ. V
где
/1 (х, т, п) = max [ртп log (х + у) + (1 - ртп) log (х — у)].
0<У<х
(7.4)
Нетрудно, как и выше, показать по индукции, что
fx (я, n) = log х + cN (m, n),	(7.5)
где cN n) удовлетворяет линейному рекуррентному
соотношению довольно сложного вида. Тем не менее оп-
тимальная политика имеет еще простой интуитивный вид
( (%Ртп 1) •Г»
У “
1 О
если ртп
в другом случае,
(7.6)
1
гДе Ртп — ^pdGmTf Таким образом, структура оптималь-
о
ной политики не изменилась даже в условиях большей
неопределенности.
Упражнения
1.	Покажите, что если dG (р) — ра-1(1 — р)ь~г dp/B (а, Ь)9
где В (а, Ь) есть бета-функция, то
т + «
Ртп т а п >
и что после т выигрышей и п проигрышей ставка игрока составляет
долю его капитала, равную
((тп + а) — (п + b)) / (w 4- а) + (п + &).
2.	Если функция критерия есть а > 0, то каковы функ-
ция дохода и оптимальная политика?
8.	Задача о двуруком бандите
Продолжая в этом направлении, обсудим теперь зада-
чу, которая возникала в работе У. Р. Томпсона при ис-
пытании новых лекарств, С тех пор она приобрела коло-
8]
ЗАДАЧА О ДВУРУКОМ БАНДИТЕ
113
ритное название, данное позже, и в связи с этим мы вместо
лекарств рассмотрим игральные автоматы *).
Предположим, что мы имеем два игральных автомата,
один с известными свойствами и другой с неизвестными
свойствами. Когда рукоятка первого автомата включена,
имеется известная вероятность 5 получения доллара;
когда играет второй автомат, имеется фиксированная, но
неизвестная вероятность р успеха. Предполагается, что
процесс имеет следующий вид. Мы испытываем второй
автомат несколько раз, чтобы определить результаты,
и тогда решаем, пользоваться ли нам первым автоматом.
Интуитивно ясно, и это можно легко показать, что, ре-
шив однажды пользоваться автоматом с известными ха-
рактеристиками, мы никогда не вернемся к автомату с
неизвестными свойствами. Однако возможно также, что
мы никогда не обратимся к первому автомату.
Чтобы упростить анализ и проиллюстрировать при-
менение функции критерия, которой мы до сих пор не
пользовались, предположим, что мы желаем максимизи-
ровать математическое ожидание
оо
/? = 2 zni
п=0
(8Л)
где 0< a<Z 1 и zn обозначает доход, полученный в п-м
испытании. Если, как и выше,
fmn = математическое ожидание дохода при оптималь-
ной политике после т успехов и п неудач, которые
наблюдались при игре на втором автомате,	(8.2)
и dG (р) обозначает априорную функцию распределения
для р, то мы легко получаем функциональное уравнение
Ann = max
(1 + л/ш+1,п) Ртп + а (1 — Ртп)
(8.3)
♦) Следствие большей близости Лос-Анжелоса к Лас Вегасу,
чем к Рочестеру, штат Миннесота. [В обиходной американской
речи игральные автоматы часто называют «одноруким» и «дву-
руким бандитом», в зависимости от числа рукояток. (Прим. реЭ.)].
114
ПРОЦЕССЫ УПРАВЛЕНИЯ С АПАДАПТАЦИЕЙ
[ГЛ. V
где вновь
1
j (1 — р)П dG (р)
Ртп ~ i	•	(8.4)
J ргп(1 — p)^G(p)
О
Соотношение (8.3) может быть использовано для даль-
нейшего изучения структурных свойств оптимальной по-
литики или для получения численного решения. Предос-
тережем читателя, что определение структуры оптималь-
ной политики является делом нелегким.
9.	Общая формулировка
Теперь, после обсуждения трех частных случаев в раз-
делах 2—8, мы в состоянии дать общую формулировку
процессов управления с адаптацией, которые рассматри-
вались нами. Мы предполагаем, что
Pi = Т (р, q. г),	(9.1)
где, как обычно, р — переменная состояния, q — пере
менная, относительно которой принимается решение, г —
случайная переменная с фиксированной, но неизвестной
функцией распределения. Пусть dG (г) — априорная оцен-
ка для этой неизвестной функции распределения. Физиче-
ским состоянием является р, но состояние управляемого
процесса есть пара (р, G).
Нашей целью является применение стратегии управ-
ления, которая максимизирует математическое ожидание
функции критерия
Rn = g (р, Я1, гг) + g (Pl, q2, Г2) + ...+ g (pN_lt qN, rN).
(9.2)
Для того чтобы точно поставить задачу, выразим явно
наши предположения.
Мы можем наблюдать состояние системы на каждом
шаге.	(9.3а)
На каждом шаге мы рассматриваем априорную оценку
как истинную функцию распределения. Математические
ожидания получаются на этой основе.	(9.3b)
10]
ЗАДАЧА ОЦЕНИВАНИЯ
115
У нас имеется систематическая процедура для моди~
фикацииэтой априорной функции распределения, по мере
того как развертывается процесс; эта процедура сама по
себе может быть процедурой с адаптацией. (9.3с)
В результате выбора qr мы имеем преобразования
Л = Т (Р’ 31,	\	(а
dG^r) — S (г, р,	r\,G), Г	(УЛ)
что можно выразить так: новая функция распределения
зависит от старой функции распределения, от величины
г\, которая получена из наблюдений, от начального сос-
тояния р, нового состояния рг и решения qt.
Пусть
(р, G) — математическое ожидание RN, полученное при
оптимальной стратегии, начатой в состоянии (р, G). (9.5)
Тогда принцип оптимальности дает функциональное
уравнение
/n (Р, G) = max [ [g (р, qlt rt) +
'	+	(Р, ri), &1)] dG (гх)],	(9.6)
где Gx является такой же, как в (9.4), для N 2, а для
N — 1 мы и? еем
/i (Р, G) = max [ Jg (Р, 31, п) dG (гх)].	(9.7)
Не очень трудно записать эти соотношения, но боль-
шие трудности представляет получение аналитических
или численных результатов из этих уравнений.
10.	Задача оценивания
Подчеркнем, что в силу предположения (9.3с) мы обош-
ли одну из фундаментальных трудностей, связанных с
процессами с адаптацией, именно задачу оценивания.
Существенной частью процесса управления с адаптацией
116
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[ГЛ. V
является процесс обучения, обеспечивающий оптимальное
использование информации по мере ее поступления. Как
следует модифицировать априорные предположения на
основе опыта?
Мы применяли байесову процедуру оценивания по при-
чине ее простоты и интуитивного характера. Нет основа-
ний считать, что эта процедура является оптимальной
процедурой оценивания во всех случаях; наоборот, можно
быть уверенным, что это не так. Ссылки на некоторые
работы в этом направлении приводятся в конце главы.
11.	От функционалов к функциям
Соотношение (9.6) может быть использовано для уста-
новления теорем существования и единственности, для
определения структуры оптимальных стратегий и изу-
чения их асимптотического поведения. Менее полезно
оно для вычислительных целей вследствие появления
функционалов. Поэтому введем хорошо известную кон-
цепцию «достаточных статистик». Мы предположим, что
G (г) принадлежит к семейству распределений G (г, а),
где а теперь конечномерный вектор, и что результат вы-
числительной процедуры, подразумеваемой в (9.3с) и
(9.4), состоит в замене а на где аг зависит от а, р
и qr.
В этом случае G) заменяется на f^(p^ а) и (9.6)
принимает вид
fN (Р, а) = max [ J [g (р, qt, rx) +
+ fN-i(T(Ру 9ь ^i), ах)] dG (rx)],	(11.1)
где аг = Я(а, р, т\), а функция Н фиксирована. Этот
метод был нами применен в трех рассмотренных выше
примерах.
12.	Более общие процессы с адаптацией
Мы никоим образом не исчерпали пределов неопреде-
ленности. Во-первых, мы можем рассмотреть случай,
когда преобразование (9.1) содержит фиксированные, но
БИБЛИОГРАФИЯ И КОММЕНТАРИИ
117
неизвестные параметры, скажем,
Pi = Т (р, q, г, Ь),	(12.1)
вновь с априорной функцией распределения. Во-вторых,
мы можем предположить, что р само по себе не может
быть точно определено на каждом шаге и что известна
лишь функция распределения для р. В-третьих, мы мо-
жем предположить, что цель процесса вначале не совсем
ясно определена. Наконец, мы можем поставить задачи
исследования как при наличии, так и при отсутствии
стохастических воздействий, скрытых переменных, а
также при наличии воздействий враждебного характера.
Ясно, что имеет большой смысл попытка формулировать
на этом уровне теории управления, что мы подразуме-
ваем под общим видом процесса управления с адапта-
цией. Ясно также, что имеется безграничная область
для проявления воображения и таланта в этих вопросах
и для каждого, кто заинтересуется этими вопросами,
откроется обширное поле деятельности.
Библиография и комментарии
§ 1.	Дальнейшее обсуждение и ссылки см. в следующих книгах:
Р. Б е л л м а н, Процессы регулирования с адаптацией.
«Наука», 1964.
А. А. Фельдбаум, Основы теории оптимальных автома-
тических систем, «Наука». 1966.
J. Т. Ton, Optimal Design of Digital Control Systems,
Academic Press Inc., New York, 1963.
А. В а л ь д, Последовательный анализ, Физматгиз, 1960.
§ 2.	Процессы этого типа обсуждаются в
М. F г е i m er, A Dynamic Programming Approach to
Adaptive Control Processes, Lincoln Laboratory, 1959; also
published in IRE Trans., vol. AC-4, 1959, pp. 10—15.
§ 7.	Эти результаты получены в
R. Bellman and R. ZK a 1 a b a, Dynamic Programming
and Statistical Communication Theory, Proc. Nat. Acad. Sci.
USA, vol. 43, 1957, pp. 749—751.
R. Bellman and R. К a 1 a b a, On the Role of Dynamic
Programming in Statistical Communication Theory, IRE
Trans, on Information Theory, vol. IT-3, 1957, pp. 197—203.
118	ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ [ГЛ. V
R. Bellman and К. Kalaba, On Communication Pro-
cesses Involving Learning and Random Duration, IRE Natio-
nal Contention Record, Part IV, 1958, pp. 16—20.
§ 8. Cm.
W. R. Thom pson, On the Likelihood that One Unknown
Probability Exceeds Another in View of the Evidence of Two
Samples, Biometrika, vol. 25, 1933, pp. 285—294.
W.K. Thompson, On the Theory of Apportionment,
Amer. J. Math., vol. 57, 1935, pp. 450—456.
R.Bellman, A Problem in the Sequential Design of Ex-
periments, Sankhya, vol. 16, 1956, pp. 221—229.
Ричард Веллман
Роберт Калаба
Динамическое программирование
и современная теория управления
М., 1969 г., 120 стр. с илл.
Редактор Д. С. Фурманов
Техн, редактор И. Ш. Аксельрод
Корректор В. П. Сорокина
Сдано в набор 20/III 1969 г. Подписано к печати
9/IX 1969 г. Бумага 84X108!/J2 Физ. печ. л. 3,75
Условн. печ. л. 6,3 Уч.-изд. л. 5,73
Тираж 18500 экз.	Цена книги 42 коп.
Заказ № 2048
Издательство «Наука»
Главная редакция
физико-математической литературы
Москва, В-71, Ленинский проспект, 15.
2-я типография издательства «Наука»
Москва, Шубинский пер., 10
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
Москва, В-71, Ленинский проспект, 15
ИМЕЮТСЯ В ПРОДАЖЕ:
Бесконечные антагонистические игры. Теория игр. Под ред.
Н. Н. Воробьева. Физматгиз, 1963, 504 стр., 1 р. 43 к.
Д ы н к и н Е. Б., Юшкевич А. А., Теоремы и задачи в
процессах Маркова. «Наука», 1967, 232 стр., 93 к.
Казаков И. Е., Доступов Б. Г., Статистическая дина-
мика нелинейных автоматических систем. Физматгиз, 1962,
342 стр., 1 р. 24 к.
Красносельский М. А., Оператор сдвига по траекто-
риям дифференциальных уравнений. «Наука», 1966, 332 стр.,
1 р. 21 к.
Красовский А. А., Статистическая теория переходных
процессов в системах управления. «Наука», 1968, 240 стр., 97 к.
Ладыженская О. А. и др., Линейные и квазилинейные
уравнения параболического типа. «Наука», 1967, 736 стр.,
2 р. 55 к.
Л е й т м а н Дж., Введение в теорию оптимального управле-
ния, Перев. с англ., «Наука», 1968, 192 стр., 78 к.
Основы автоматического управления. Под ред. В. С. Пуга-
чева. Изд. 2-е, исправл. и дополн., «Наука», 1968, 680 стр.,
2 р. 90 к.
Первозванский А. А., Случайные процессы в нели-
нейных автоматических системах. Физматгиз, 1962, 352 стр.,
1 р. 08 к.
Требуйте эти книги в магазинах Книготорга. Письменный
заказ можно направить также в ближайший отдел «Книга-поч-
той» республиканского, областного, краевого книготорга.
Литература будет выслана наложенным платежом.
В случае отсутствия этих книг на месте заказы можно на-
правлять по адресу: Москва, К-50, ул. Медведева, 1, магазин
№ 8 Москниги, отдел «Книга-почтой».