Автор: Беллман Р. Калаба Р. Скалабан Д.Х.
Теги: регулирование и управление машинами, процессами программирование теория управления
Год: 1969
Текст
Динамическое
проrраммирование
и современная
теория управления
Р. БЕЛЛМАН
Р. КАЛАБА
Перевод с анrлийс:коrо
Е. л. РОЙТЕНБЕрrА
Под редакцией
Б. с. РА3УМИХИНА
ИЗДАТЕЛЬСТВО «НАУКА»
rЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСНВА 1969
6 Ф 6.б
Б 43
УДК 62-50
3-3-(
139-69
DYNAMIC PROGRAMMING
AND MODERN
CONTROL THEORY
Richard Bellтan
UNIVERSITY OF SOUTHERN CALIFORNIA
LOS ANGELES, CALIFORNIA
Robert Kalaba
ТНЕ RAND CORPORATION
SANTA MONICA, CALIFORNIA
ACADEMIC PRESS
N ew У ork аnа Loпdoп
оrЛАВЛЕНИЕ
Предисловие редактора перевода . . .
Предисловие авторов . . . . . . . . . .
rлава 1
Миоromаrовые процессы . . . . . . .
1. Введение . . . . . . .
2. Системы . . . . . . . . .
3. Мноrошаrовы(\ процессы . . .
4. Редукция информации . . .
5. Независимость от прошлоrо .
6. Рекуррентные соотношения. . .
7. Бесконечные процессы . . . . . . . . . .
8. Процессы с заданными правилами остановки
9. Нестационарные процессы . . . . . . . . .
10. Обсуждение . . . . . . . . . . . . . .
11. Непрерывные мноrошаrовые процессы . .
12. Траекторный процесс . . . . . . . .
13. Неоднородная атмосфера. . .
14. Причинность . . . . . . . . .
15. Стохастические процессы . . . . . . . . .
16. R о р реляция . . . . . . . . . . . . . · .
17. Наблюдения при наличии шумов . . . . .
18. Скрытые переменные . . . . . . . .
19. Индуцированные процессы . . . . . .
20. Косвенные и индуцир ванные процессы . .
21. Более общие стохастические процсссы
22. Заключение . . . . . . · · · ·
23. Библиоrрафия и комментарии . . . . · . ·
r л а в а 11
Мноrоmаювые процессы ПРИНJlТИJl решений
1. Введение . · . . · · . · · . · · · · ·
2. мноrоmаrовый процесс принятия решений
3. Стратеrия . . . · · · · . · · · · · · · · ·
4. Сепарабельвые критерии . . . . . . . · ·
5. П ринцип оптимальности · . . · · · . · · ·
6. П риме ры . . . . . . . . . · · . · . . · ·
7. Друrой вывод OCHOBHoro функциональноrо
уравнения . . . . . . . . .. . . . . . . .
6
7
9
9
9
11
13
14
15
18
19
20
22
22
24
27
28
29
30
31
32
33
34
35
36
36
40
40
41
42
43
44
44
46
4
оrЛАВЛЕНИЕ
8. Что является решением? .. . . . . . . .. 46
9. IIепрерывный мноrошаrовый процесс приня-
тия решения. . . . . . . . . . . . . . .. 47
10. Вариационное исчисление . . . . . . . .. 48
11. rеометрические аспекты . . . . . . . . .. 51
12. Стохастический мноrоmаrовый процесс при-
нятия решения . . . . . . . . . . . . .. 52
13. Управление с обратной связью . . . . .. 53
14. Анализ уравнений. . . . . . . . . . . .. 54
15. Последовательные приближения . .. . . .. 55
16. Приближение в пространстве стратеrий 56
17. Rвазилинеаризация . . . . . . . . . . .. 57
f8. Аналитические и вычислительные проблемы 58
19. Принцип Ферма и уравнение эйконала 59
20. Наикратчайmие пути через сети . . . .. 61
Библиоrрафия и коммеН1 1 арии . . . . . . . .. 65
r л а в а 111
ВЫЧИCJIительные аспекты ... . . . . . . .. 63
1. Введение . . . . . . . . . . . . . 68
2. Цифровые вычислительные машины . . . .. 68
3. Численное решение процессов динамическоrо
проrраммирования . . . . . . . . . . .. 69
4. Приближения в пространстве hУнкций 71
5. Приближение в пространстве стратеrий .. 72
6. Вычислительная осуществимость . .. . . .. 72
7. Аппроксимация полиномами . . . . . . .. 73
8. Устойчивость вычислительноrо процесса 75
9. Обсуждение . . . . . . . . . . . . 77
10. Задача о замене оборудования . . . . .. 77
Библиоrрафия и комментарии . . . . . . . .. 82
r л а в а IV
Аналитические результаты в теории упрвмеНИJl
и теории связи 84
1. В ведение . . . . . . . . . . . . 84
2. Управление с обратной связью . 84
з. Скалярный случай . . . . 85
4. Обсуждение . . . . . . . . . . . . . 87
5. Стохастический вариант . . . . . . . . .. 88
6. Обсуждение . . . . . . . . . . . . . . .. 89
7. Мноrомерный детерминированный случай . 89
8. Непрерывный случай . . . . . . . . . .. 91
9. Теория проrнозирования . ...... 95
10. Передача информации. . . . . . . 97
11. Эффективный иrрок . . . . . . . . . . 97
12. Применение метода дипамическоrо проrрам-
мирования. . . . . . . . . . 99
13. Обсуждение . . . . . . . . . . . . . . .. 101
Биб.пиоrраmия и комментарии . . . . . . . .. 101
оrЛАВЛЕНИЕ 5
rпaBa V
Процессы управлении с адаптацией . . . . .. 105
1. Введение . . . . . . . . . . . . . . . .. 105
2. Линейный процесс управления с адаптаllиеii 106
3. Аналитическая формулировка . . . 107
4. Аналитические аспекты . . . . . . . . .. 109
5. Обсуждение . . . . . . . . . . . . . 110
6. Априорная фУНКЦИЯ распределения . 110
7. Иrра с адаптацией. . . . . . . . 111
8. Задача о ДВУРУКОМ бандите .... 112
9. Общая формулировка . . . . . . . . . .. 114
10. Задача оценивания . . . . . . . 115
11. От ФУПRциопалов R функциям . .. 116
12. Более общие процессы с адаптацией 116
Библиоrрафия и комментарии . . . . . . . .. 117
ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА
Предлаrаемая вниманию читателей книrа содержит
изложение и различные приложения одноrо из важней-
ших методов исследования управляемых процессов-
метода динамическоrо проrраммирования. Возможность
единоrо подхода к изучению процессов различной фи-
зической природы, как детерминированных, так и сто-
хастических, дает основание рассматривать книrу как
введение в математическую теорию управляемых про-
цессов.
Задачи управления процессами, изучаемыми в физи-
ке, технике, экономике и биолоrии, требуют как совер-
шенствования аналитических методов, так и создания
достаточно простых математических моделей изучаемых
процессов. Оба пути имеют одну цель - получение со-
держательных численных результатов современными or-
раниченными вычислительными средствами. Поэтому
большой интерес представляют обсуждения вычислитель-
ных аспектов теории управления. В книrе обсуждаются
численные методы решения функциональных уравнений
метода динамическоrо проrраммирования, такие как ме-
тод последовательных приближений в пространстве ФУНК-
ций, характеризующих процесс, или в пространстве стра-
теrий, метод аппроксимации искомых функций полино-
мами или системой ортонормированных функций и Т. д.
Значительный интерес представляют рассмотренные
в книrе примеры. Написанная с большим педаrоrиче-
ским мастерством, книrа, несомненно, будет полезна
широкому Kpyry читателей, интересующихся проблема-
ми управления.
Б. с. Р aayJ;tuxuи
ПРЕДИСЛОВИЕ АВТОРОВ
Цель этой книrи более обширна, чем это указано в
ее названии. Нашей целью было дать введение в мате-
матическую теорию процессов. Процессы, изучаемые в
физике, технике, экономике, биолоrии, обладают мно-
жеством запутанных специальных особенностей: вектор
состояния может иметь конечную или бесконечную раз-
мерность, переход из одноrо состояния в друrое может
быть детерминированный или стохастический; может иметь-
ся возможность влиять на процесс; возможно наличие
или отсутствие конкурирующеrо влияния; система управ-
ления может оказаться способной изучать в процессе
управления неизвестные стороны процесса. Для вдумчи-
Boro исследователя существенно знать, как объединить
эти и мноrие друrие свойства вместе в математические
модели ситуаций, которые мы желаем изучить. Помимо
этоrо, он должен быть в курсе возможностей и оrраниче-
ний современных вычислительных машин и прямой взаи-
мосвязи между теоретическими формулировками и чис-
ленными решениями.
В некотором смысле построение реалистических мате-
матических моделей является простым. Реалистические
модели имеют, однако, неприятную особенность быстро
исчерпывать память и скоростные возможности совре-
менных вычислительных машин. Можно достичь nporpec-
са либо при искусном упрощении математической моде-
ли, позволяющем получить содержательные численные
Исследования, либо коrда аналитические достижения поз-
воляют изучить класс процессов, которые ранее счита-
лись слишком сложными.
rлава 1 посвящена общему описанию мноrошаrовых
процессов, как детерминированных, так и стохастических,
как непрерывных во времени, так и дискретных. Это дает
нам возможность ввести идею о рекуррентных соотноmе-
8
ПРЕДИСЛОВИЕ АВТОРОВ
ииях и наблюдать их в действии в различных условиях.
В rлаве 11 мы рассматриваем мноrошаrовые процессы
принятия решения, в которых целью является получение
последовательности решений в течение процесса так,
чтобы максимизировать выиrрыш от процесса. Теорети-
ческой структурой здесь является структура динамиче-
CKoro проrраммирования. Приведены краткие экскурсы
в вариационное исчисление, теорию управления с обрат-
ной связью и математическую физику.
rлава 111 рассматривает ряд вычислительных аспек-
тов динамическоrо проrр'аммирования. Обсуждается ряд
теоретических вопросов, включая устойчивость числен-
ных методов и возможность понижения требований к
памяти, приводится nporpaMMa для задачи о замене обо-
рудования. В rлаве IV мы обращаемся к некоторым про-
цессам передачи информации и процессам управления,
для которых можно получить аналитические результаты
в явном виде. Они иrрают роль трамплина для перехода
к рассмотрению более реалистических моделей при помо-
щи метода п'оследовательных приближений.
Последняя rлава вводит в новую увлекательную тему-
управление с адаптацией. В таких процессах система
управления одновременно влияет на течение процесса и
изучает неизвестные стороны этоrо процесса. Эта наука
пока переживает свое детство, но MHoro обещает в буду-
щем.
Во всех rлавах мы приводим MHoro задач, которые
потенциально делают книrу приемлемой как для учебной
аудитории, так и для самостоятельноrо изучения. Мы
надеемся, что настоящая книrа будет стимулировать
читателя к применению изложенных методов в друrих
областях и к созданию новых методов для rлубокоrо
проникновения в сложные процессы путем сочетания
современных вычислительных устройств и современных
математических теорий.
Ноябрь 1965
Санта Моника, Калифорния
Ричард Б е.ltJ1,Жан,
Роберт Када6а
rлава I
мноrОШАrОВЫЕ ПРОЦЕССЫ
1. Введение
В этой rлаве мы хотим ввести определенное число
фундаментальных математических понятий, которые бу-
дут использованы в этой книrе при исследовании различ-
ных типов управления и процессов принятия решений.
Термин «процесс» будет точно определен и конкретизи-
рован в различных случаях: конечном, бесконечном,
неоrраничеином; детер:м:инированном, стохастическом;
дискретном, непрерывном; стационарном и нестационар-
ном. Используя основные понятия переменных состояния
и преобразо аний состояния, мы продемонстрируем силу,
мноrосторонность и rибкость рекуррентных соотноше-
ний и друrих типов функциональных соотношений.
1. Системы
Сначала пас будет интересовать изучение систем (тер-
мин, который здесь еще не определен, но интуитивно
вполне понятеп) и то, как они ведут себя с течением вре-
мени. Эта точка зрения позволяет нам ввести понятие
«процесса>} простым и естественным способом. Зафикси-
руем на минуту наше внимание на системах. Чисто ана-
литически мы представляем себе систему как вектор сос-
тояния х (t) и правило для определения ero значения в
любой момент времени t. В этой кпиrе мы будем :Иметь
дело, для простоты, только С конечномерными векторами
Хl (t)
Х2 (t)
х (t) =
(2.1 )
XN (/)
10
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл 1.
Каждая компонента х (t) определяет различные свойства
системы. Число N называется размерностью системы.
Классически величина х (t) может быть задана следую-
щим образом:
dx
dt ==g(x (t))
- дифференциальные ура-
внения,
- разностное уравнение,
х (t)= g (x(t - 1))
dx )
dt == h (х (t), х (t -1)
- дифференциально-разно- (2.2)
ствое уравнение,
х (t) = и(t) + g (x(s), t) ds -интеrральное уравнение,
а также в виде различных комбинаций этих типов. Уравне-
ния в частных производных вводят бесконечномерный век-
тор и этим определяют более общую систему. Хотя методы,
которыми мы пользуемся, MoryT быть применены к изу-
чению систем более сложной структуры, ниже мы orpa-
ничимся системами конечной размерности. Только при
ЭТОМ мы сможем сохранить вводный характер настоящей
моноrрафии.
Сейчас важно подчеркнуть, что то, что мы называем
состоянием системы, не определяется только лишь фи-
зическими свойствами подлежащей изучению реальной
системы. Поэтому для нас здесь не так уж необходимо
уrлубляться во внутреннюю характеристику системы.
Наоборот, это сильно задержит нас на весьма частных и
зачастую извилистых путях математических описаний.
Все зависит или должно зависеть от Toro, что мы хотим
знать о физических процессах, что мы можем наблюдать
или измерить, от точности этих наблюдений и вообще
от научноrо и математическоrо уровня на сеrодняшний
день. Важно подчеркнуть значение rибкости в примене-
нии математических методов в научных исследованиях.
Не существует никаких rOToBblx аналитических методов
и никаких rOToBblx формулировок.
В прошлом большинство аналитических работ по
прикладной математике было связано с функциональными
уравнениями указанных выше типов. Эти работы содер-
жат важные результаты и нет сомнений в том, что по-
З]
мноrОШАrОВЫЕ ПРОЦЕССЫ
11
ставленные в :классической формулировке задачи будут
продолжать иrрать основную роль в современной теории
управления и в друrих областях. Одна:ко, как новые за-
дачи, так и новые типы задач, возникшие в результате
научной революции, :которую мы переживаем, показали
что классичес:кая теория имеет существенные оrраничения.
Новые методы, совместно с развитием и обобщением ста-
рых, позволяют дать ответ на новые и более rлубокие
вопросы современной науки и техники и, в частности,
сделать более полным использование в науке Toro мас-
тера на все ру:ки, ученика чародея, которым является
цифровая вычислительная машина. Это замечательное
устройство даже в ero нынешнем младенческом возрасте
и при нашем с:кудном арсенале идей по части ero исполь-
зования и возможностей уже в значительной мере и без-
возвратно изменило основные :каноны математики в част-
ности, и науки вообще.
Ниже мы введем некоторые простые, но достаточно
мощные математические методы, :которые позволят нам
сформулировать и проанализировать ряд проблем, кото-
рые не MoryT быть рассмотрены в рамках обычной тео-
рии. В этой rлаве мы сохраним тесный :контакт с класси-
ческими идеями; в последующих rлавах нам предстоит
стать первооткрывателями.
3. Миоrоwаrовые процессы
Введя чисто математическое определение понятия
«система», уточним теперь друrую интуитивную концеи...
цию - определим понятие «процесс». Ради общности и
ради Toro, чтобы не быть даже визуально связанными со
старыми понятиями, мы заменим символ х (t) символом
р, считая р точкой множества или пространства R. Во
всем последующем изложении в этой книrе R будет мно-
жеством точек M-мерноrо пространства, иноrда М-мер-
Horo :куба, иноrда будет состоять из вершив этоrо куба.
Например, R может состоять из положительных целых
чисел 1,2,..., М и о. Однако это не обязательно для каж-
доrо из приведенных выше типов в более общей ситуации.
Рассмотрим теперь фун:кцию Т (р) - преобраЗQвание,
обладающее свойством, что преобразованная точка
12
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. 1
Рl = т (р) принадлежит R для всех точек р из R. Мы може1.{
представить себе, что р изображает начальное состояние
системы, Рl == Т (р) - состояние на одну единицу вре-
мени позднее и вообще система венторов
[р, Рl' Р2'...' Рn,...], (3.1)
rде Ро == р, Рn+l = т (Рп), п == О, 1,2,..., изображает вре-
менную историю системы, наблюдаемую в дискретные
моменты времени n == О, 1,2, ..., т. е. последовательные
состояния системы. Мы можем также написать Рn = т n (р),
что обозначает n-кратное применение преобразования
Т, и иноrда мы будем применять это обозначение.
Мы называем эту бесконечную последовательность
векторов, ПОЯВЛЯIОЩУЮСЯ в (3.1), жuоеошаеовыJJt процессом,
что, кстати, и является определением этоrо термина. У доб-
но ввести обозначение [р, Т (р)] или просто [р, Т]. Более
точно, это есть мноrоmаrовый процесс дискретноrо детер-
минированноrо типа. Так как, однако, это единственный
мноrоmаrовый процесс, который мы пока указали, то
оrраничимся пока более простым термином. При рассмот-
рении друrих типов мноrоmаrовых процессов мы отме-
тим их дополнительные особенности.
УпражнениSl
1. Пустьр есть скаляр, Т. е. одномерный вектор, и пусть преоб-
разование Т имеет вид Т (р) = тр, rде r - действительное число.
В зависимости от значения r определить поведение Рn при n -+ 00.
2. Пусть P-ДВУ}fерный вектор, т. е. р = (Xl' )' П пусть преобра.
зовавие Т есть матрица типа 2 Х 2 следующеrо вида:
1 1 сов 6 sin 611
Т= d- sin6 COB6 '
Показать, что rеом:етрически Т представляет собой поворот на уrол в
в ПЛОСКОС1'И (Хl, Х2).
3. Наково предельное поведение L; : 1 тn(р) / N при N -+ Х) как
функции уrла О?
4. Пусть и есть решение скалярноrо дифференциальноrо ypaBHe
ния dи/dt = аи и пусть Т есть преобраэование, определяемое выраже-
нием и (1) в зависимости от и (О). Каков аналитичеСJ{ИЙ вид Т? Ка..
ново предельное поведение ТN при п 00 как функции от а?
5. Рассмотрим соответствующую задачу для случая, коrда ж
есть вектор. удовлетворяющий векторному дифференциальному
]
РЕДVНЦИЯ ИUФОРМАЦйй
13
уравнению dx/dt = Ах, х (О) = с, rде А есть постоянная матрица
(см. R. В е ] 1 m а n, Introduction to Matrix A.nalysis, New J ork:
Мс Graw-IIill Book Сотрапу, Iпс., 1960, Chapter 10).
6. Рассмотрим линейное дифференциальное уравнение и' -1-
+ аu = f (t), и (О) = с, и запишем решение в виде и = L (t, с, !),
обозначая явно зависимость от f, с и вынул(дающей функции / (t).
Показать, что
(а) L (t, с /) = L 1 (t, с) + L z (t, !),
rде
(В) L 1 (t, сl + С2) = L 1 (t, сl) + L 1 (t, С2),
(с) L 2 (t, /1 + 12) = L 2 (t, 11) + L z (t, 12).
7. Преобразование от функции к числу называется фуп"цuо-
палом, а преобразование ОТ функции к функции называется опера-
тором. Величина L 2 (Т, f) есть линейный фУНRционал от j. Показать,
что и 2 (Т) есть квадратичный Функциоиал, имеющий ВИД
т
и S (Т) = а (Т) c S + 2с Ь (t, Т) f (t) dt +
о
тт
+ k (t 1 , t s , Т)! (t 1 ) t (t s ) dt 1 dt s .
о о
и определить функции а (Т), Ь (t, Т) и k (lt, t z , Т).
4. Редукция информации
В большинстве случаев мноrошаrовый процесс, пред-
став ленный выражением типа (3.1), rоворит значительно
больше, чем мы желаем знать, и обычно значительно боль-
ше, чем мы можем усвоить или проанализировать. Та-
кова ирония науки - для Toro, чтобы понять, мы долж-
НЫ отбросить часть информации. Мы не можем, по край-
ней мере на настоящем уровне Hamero интеллектуальноrо
развития, пытаться преодолеть высокий уровень слож-
Ности. Следовательно, мы вынуждены упрощать.
Для начала будем рассматривать только часть MHoro-
maroBoro процесса, N-mаrовый процесс, последователь-
Ность векторов
[р, Рl' Р2' ...,PN], (4.1)
rде, как и прежде, Pk+l = Т (Pk) , k = 0,1,2, ..., N - 1.
Мы хотим рассмотреть свойства различных скалярных
14
мноrоmАrОВЫЕ ПРОЦЕССЫ
[rЛ.I
фУНRЦИЙ, зависящих от этоrо процесса. Если мы предполо-
жим, что эти фУНRЦИИ {g (р, Рl, ..., PN)} имеют самую
общую форму, то, по-видимому, мы сможем СRазать очень
мало существенноrо. Для Toro чтобы получить интерес-
ные и полезные результаты, мы должны надлежащим об-
разом выбрать струнтуру функции g, или, что эквива-
лентно, надлежащую структуру мноrошаrовоrо процесса.
Заметим еще раз, что TaRoro рода привнесенная струнту-
ра не обязательно свойственна основной физической
структуре. Например, Мы можем рассмотреть фУНRЦИИ
следующих видов:
N
(а) h (Pi),
i=o
N
(Ь) П h (Pi),
i=o
N-l
(d) h (Pi, Pi+l).
i=o
(4.2)
(с) шах h (Pi),
O i N
Во мноrих случаях (а на самом деле в большинстве слу-
чаев) физичеСRие процессы сами будут подсказывать
наиболее подходящие ФУНRЦИИ дЛЯ cBoero описания.
Каждая из приведенных выше функций имеет MHoro фи-
зических интерпретаций, и каждая возникает при рас-
смотрении интересных и значитеЛЬНJ,.IХ физичеСRИХ про-
цессов.
5. Независимость от npownoro
Прежде чем получить аналитические следствия из
природы мноrошаrовоrо процесса, обсудим некоторые об-
щие аспеRТЫ. Мы предполаrали, что в начальный момент
времени система определяется вектором состояния р, что
в последующем наблюдении на единицу времени позднее,
вектор состояния есть Рl == Т (р), в следующем наблю-
дении вектор состояния есть Р2 == Т (Рl) и Т. д. Как след-
ствие этоrо предположения последующее для k-й точки
(момента времени) состояние зависит только от Pk, т. е.
от Состояния в момент времени k. Мы не требуем Rаких-
либо сведений о предыстории системы для Toro, чтобы
определить будущее. Мы получаем, таRИМ образом, яс-
5]
РЕНУРРЕНТНЫЕ СООТНОШЕНИЯ
15
ные понятия «прошлое», «настоящее» и «будущее» в плане
мноrоmаrовых процессов.
Друrой путь введения этих понятий состоит в том,
что PN можно рассматривать как N -е состояние на N-M
mare процесса, начавшеrося из начальноrо положения р,
или (N - k)-e состояние процесса на (1У' k)-M mare
процесса, начавшеrося из состояния Pk В момент времени
k. Символически это можно записать в виде уравнения
TN == TN-K (Tk).
(5.1)
Это соотношение может рассматриваться как аналити-
ческая формулировка причинной связи, или, друrими сло-
вами, Toro факта, что будущее единственным образом оп-
ределяется настоящим. Если пользоваться классической
терминолоrией, это есть теорема единственности.
6. Рекуррентные соотношения
Вернемся теперь к анализу возможности выполнения
необходимых вычислений для определения указанных в
(4.2) функций. Рассмотрим сначала функцию
N
h (Pi),
(6.1 )
i=O
rде h (Р) - заданная функция состояния, и заметим, что
рассматриваемая функция полностью определена началь-
ным состоянием Р и числом шаrов N, если задано прави-
ло, посредством KOToporo Pk получается из Pk-(, иными
словами, если задано преобразование Т. Так как анали-
тическим переложением фразы «зависит от» является фра-
за «есть функция от», то мы введем последовательность
функций {fN (р)}, определяемых соотношением
N
fN(p) = h(Pi) =
i=o
= h (Р) + h (Т (р» + h (Т2 (р» + ... + h (TN (р», (6.2)
rде мы позволяем N принимать значения N == О, 1, 2,...
и полаrаем, ЧТО р принадлежит множеству R. Рассмотрим
16
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. 1
для N > 1 частичную сумму
h (Т (р)) + h (Т2 (р» + ...+ h (TN (р»). (6.3)
Мы видим, что это эквивалентно
h (Рl) + h (Т (Рl) + ... + h (TN-l (Рl))' (6.4)
а следовательно, и ФУНКЦИИ fN-l (Рl), определяе IОЙ пос-
ледовательностью функций {fN (р)}. Из этоrо следует,
что fN (р) удовлетворяет функциональному уравнению
(в данном случае рекуррентному соотношению)
fJ<7 (р) = h (р) + !N-l (Т (Р)), N;> 1,} (6.5)
10 (р) = h (Р).
Аналоrично, если мы обратимся к функции (4.2Ь) и
напишем
N
fN (Р) = П h (Pi),
i=o
(6.6)
МЫ получим функциональное уравнение
fN (р) = h (р) fN-l (Т(р».
(6.7)
Мы предоставляем читателю вывод соотношения
fN (р) = шах [h (р), fN-l (Т (р))], N :> 1, (6.8)
для функции от N и р
fN(P) = maxh(pi), (6.9)
O i N
определенной в форме (4.2с). Таким же образом соотно-
шение
fN (р) = h (р, Т (р» + fN-1 (Т (р» (6.10)
может быть установлено для функции (4.2d).
УпражнениSl
1. Рассмотрите бесконечную rеоиетрическую проrрессию S =
= 1 + r + r2 + ... Запишите S в виде S = 1 + r (1 + r + т 2 +...)
и отсюда ПОRажите, что S = 1/ (1 - т), если I r I < 1.
6]
РЕНУРРЕНТНЫЕ СООТНОШЕНИЯ
17
2. Рассмотрите бесконечную цепную дробь
8=1+
1+ 1
1 +...
1
Покашите формально, что S = 1 + 1/ s, и отсюда, что S = (1 + У5)/2
при условии, что цепная дробь сходится. Покажите, что приведенное
выше выражение может быть определено как предел Rонечноii цеп-
ной дроби.
3. Рассмотрите бесконечную цепную дробь
s (х)= 1 +
1 + х 2
1+
1 + х 8
1 + ...
х
ПОRашите, что S (х) = 1 + 1 + S (х 2 ) ·
4. Покажите, что если
S = J/ 1 + У2+ V4+. .У 2 Вn + ...,
то S = 2, предполаrая сходимость. Еще раз uокажите, что формаль-
но беСRонечв:ое выражение может бы'rь определено как i.редел конеч-
Horo выражения.
5. Рассмотрите СRалярное соотношение " n + 1 = аи.ll + Ь, uo =
= с. Пусть f N (с) = N Uk 2 . ПОI{ажите, что fN (с) есть Rвадратич-
L2k=O
ный полином ПО с, f N (с) =ин с 2 + 2vNC + Шн. Используя рекуррен-
тное соотношение f v (с) = с 2 + fN _ 1 (ас + Ь), определите рекур-
рентные соотношения для коэффициентов U N , VJ.V, wN И исследуйте
асимптотическое поведение при N 00.
6. Обобщите эти результаты на случай, коrда Х n + 1 = Ах 7 ! + Ь,
1N
:lo = с, rде ХN - вектор, А - матрица и t N (с) = /, (х n , х n )'
-.n=о
7. Рассмотрите скалярное соотношение
и 1 = аи n + Ь t "о = v.
n+ сиn + d
Записав
aNv+ b N
U N =
CNv+dN
получите рекуррентное соотношение для ан ,b. v ,CN и d v и исследуй.
Те ero асимптотическое поведение при N -+ 00.
18
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rЛ.I
8. Покажите, что итерация преобразования l' (и) === аи + ь эк-
си+ d
вивалентна: возведению матрицы А = \\ \\ в последовательные
степени.
7. &есконечные процессы
Соотношения, полученные в разделе 6, значительно
упрощаются для бесконечных процесеов, т. е. процессов,
которыми становятся ранее рассмотренные мноrоmаrовые
процессы при N == 00. Поступим формально и, не рас-
сматривая пока вопросов сходимости, напишем
()')
f (р) == h (Pi).
i=O
(7.1)
Заметим, что бесконечность числа шаrов исключает за-
висимость от N и таким образом устраняет одну перемен-
ную, что весьма существенно. При этом аналоrично пре-
дыдущему получим
со
j(p)=h(p) + h(Pi), f(p)==h(p)+f(T(p»). (7.2)
i=l
Подобным же образом, если
I (р) === шах h (Pi),
i
(7.3)
TO t учитывая очевидное соотношение шах [Х 1 , Х 2 , ...] ==
=:::. тах [X 1 , шах [Х2,...]]' мы получаем
f (р) == шах [h (р), f (Т (р))].
(7.4)
На данном этапе мы можем соrласиться с тем, что бес-
конечный процесс не имеет физической реализаци. Тем
не менее он представляет собой весьма удобную аппро-
ксимацию мноrих сложных конечно-шаrовых процессов
большой длительности. Равным образом мы можем при-
нять противоположную арrументацию и утверждать, что
все процессы не оrраничены, а I\онечные процессы пред-
ставляют собой удобное приближение ко мноrим ТРУДНЫМ
8]
ПРОЦЕССЫ С ЗАДАННЫМИ ПРАВИЛАМИ ОСТАНОВКИ
19
бесконечным процессам. Весьма важно понять то, что мы
имеем возможность выбора любой из обеих концепций,
каждая из которых имеет вои достоинства и недостатки.
Во мноrих случаях функция fN (р) не имеет предела
при N 00 . В самом деле, мы rоворим о некотором
«среднем» поведении, или установившемся поведении,
выражаемом асимптотическим соотношением вида
t N (Р) ( )
N """"gl Р
при N 00 или даже соотношением вида
(7.5)
fN (Р) g2\(p)Nh (р).
(7.6)
Вообще физическое обоснование указывает нам тип
предельноrо поведения, KOToporo следует ожидать,
и функции gl И g2 имеют физический, технический или эко-
номический смысл. Мы избеrаем здесь, однако, KaKoro-
либо обсуждения этих очень интересных, важных и труд-
ных вопросов, ноторые требуют, вообще rоворя, детальноrо
и довольно сложноrо исследования.
8. Процессы с заданными правияами остановки
Во мноrих важных ситуациях мы сталкиваемся с ко-
нечными процессами, в которых число шаrов заранее не
фиксировано, а зависит -от начальноrо состояния, Т. е.
N = N (р). При этом мы приходим К соответствующим
функциям вида
N (р)
f(p) = h(Pi).
i=O
(8.1)
Первым простым примером этоrо вида процессов яв-
ляется процесс, в котором при затрате ресурсов на каж-
дом mare приходится учитывать условие, соrласно кото-
рому процесс остановится, как только иссякнут ресурсы.
Аналитически это условие можно выразить посредством
оrраничения вида
N
k(Pi)<a.
i
(8.2)
20
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rЛ.I
Друrой немаловажный пример дает нам исследование
траекторных процессов. ОбъеI\Т продолжает движение
до тех пор, пока он не окажется на некотором заранее
обусловленном расстоянии от друrоrо объекта. Аналити-
чески, вводя метрику в R, обозначая через d (р, q) рассто-
яние между двумя элементами р и q в R, мы ставим
условием, что процесс продолжается до тех пор, пока
d (TN p , q) < в, rде q и В заданы заранее.
Процессы этой общей структуры иrрают важную роль
в современной технике и экономике.
Рассмотрим траекторный процесс, который оканчи-
вается, как только d (PN, q) < в. Если ввести фУНКЦ}JЮ
N
f (р) = h (Pi),
(8.3)
i=O
rде N = N (р) определяется приведенным выше прави-
лом остановки, то мы получаем
j(p)=h(p), если d(P,Q)<B,}
t (р) == h (р)+ t (Т (р», если d (р, q) > В.
(8.4)
При рассмотрении процессов TaKoro вида рекуррент-
ные соотношения (функциональные уравнения) зачастую
весьма полезны. Эти процессы являются примерами не-
оrраничеН:8ЫХ процессов, которые не. обязательно долж-
ны быть бесконечными процессами.
9. Нестационарные процессы
До сих пор мы предполаrали, что вид преобразования
т (р) не зависит от шаrа. Друrими словами, преобразо-
вание Т оставалось неизменным с течением времени. Про-
цессы этоrо типа называются стацuо1tарпь жи. Предполо-
жим, что теперь мы рассматриваем более общий случай,
rде
Рn+l = т n (Рn), (9.1)
иными словами, случай, rде преобразование зависит от
времени. В этом случае соотношение (5.1) неприменимо.
Для Toro чтобы получить аналоrичный результат, МЫ
9
НЕСТАЦИОНАРНЫЕ ПРОЦЕССЫ
21
ДОЛЖНЫ учитывать момент времени, в который процесс
начался. В общем виде нестационарный процесс может
быть записан
[Р т , Р т +l' ..., Рn, ...],
(9.2)
rде
Рт+l = т т (Р т ), Pm-t2 = т т+l (Рт+l)' ... (9.3)
Мы можем при этом предположить, что и соответствую-
щие функции также зависят от времени, и рассмотреть
в связи с этим функции вида
N
(а) /lk (Pk),
К=т
N
(Ь) П h k (Pk), (с) шах h k (Pk).
1f=т m k N
(9.4)
Чтобы применить метод функциональных. уравнений,
использованный нами в предшествующих параrрафах,
заметим, что состояние можно определить вектором Р и
:моментом времени, в который процесс начался. Поэтому
чтобы изучить функцию
N
h k (Pk) (9.5)
k=m
посредством функциональных соотношений, примененных
выше, мы пишем Р т = Р и указываем зависимость как от
р, так и от т, вводя функцию вида
N
fN,m (Р) = h k (PK)'
kr:::::m
(9.6)
удовлетворяющую соотношению
fN.m (р) == h m (Р) + fN,m+l (Т т (р).
Если N фиксировано, то можно упростить обозначения
введением новой функции
СРт (р) = fN,m (Р)
(9.7)
и написать
q>m(p) hm(P)+CPт+1(Tm(p», O,<т<N,} (9.8)
CPN (р)-= h N (Р).
22
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. I
Упражнения
1. Рассмотрите оцномерную систему S, определяемую перемев-
ной состояния х n , n == о, 1, 2, ..., и соотношение Х n + 1 == ах n , хо == с,
а > 1, с > о. Рассмотрите новую управляемую систему, опреде-
ляемую уравнением Х n + 1 == ахn + у (хn), ХО == с, тде у (х) == о,
0< х < 1, у (х) == -1, х > 1. Определите поведение х n при n 00
двумя способами: rрафиqеским и аналитическим. Для каких значе-
ний а Xп. 00 при п оо?
2. Пусть fn (с) обозначает значение Х11 в момент времени n. По-
кажите, что
! n+ 1 (С) == ! n (ас + у (с», n о,
!о(с)==с.
10. Обсуждение
Вплоть до этоrо места мы следовали классическому
пути, проложенному Пуанкаре, Биркrоффом, Адамаром
и друrими, связывающему преобразования на дискрет-
ном интервале с теорией итераций. Наши дальнейшие ре-
зультаты будут СВЯ3lР""' I с иными направлениями в обла-
сти непрерывных процессов, процессов принятия решения
детерминированноrо, стохастическоrо и адаптивноrо типа
и друrих процессов, удобных в аналитическом аспекте.
11. Непрерывные MHorowaroBble процессы
До сих пор мы молчаливо предполаrали, что система
наблюдается только в дискретные моменты времени,
и поэтому речь шла о преобразованиях только в эти момен-
ты времени. Рассмотрим теперь случай, коrда состояние
системы изменяется во времени непрерывно. Для этоrо
используем аппарат, разработанный для дискретных про-
цессов, устремив длину интервала времени между двумя
наблюдениями к нулю.
Пусть наблюдения ведутся в моменты времени t = О,
, 2L\, ..., а преобразование Т (р) имеет вид
т (р) == р + s (р)!1 + о (!1), ( 11.1 )
rде !1 есть малая величина, которую мы впоследствии
устремим к нулю. Кроме Toro, пусть соответствующая
функцияимеетв:идg (р)!1 + g (Т (p))L\ + ...+ к(т n (р))А.
11]
НЕПРЕРЫВНЫЕ мноrОШАrОВЫЕ ПРОЦЕССЫ
23
Друrими словами, мы предположим, что как состояние
системы, так и соответствующая функция мало изменяют-
ся в течение малоrо интервала времени. Тоrда, полаrая
t == n , мы получим следующее рекуррентное соотноше-
ние:
ft+A (р) = g (p) + ft (Р + S (p) + о ( )). (11.2)
Рассмотрим М-мерный случай, коrда
X 1 I 81 (x 1 " Х2' ..., ХМ)
р == Х2, S (р) == : . ( 11.3)
.
.
.
Хм
s м (Х1, Х2, ..., хм)
Применяя известные обозначения BeKTopHoro анализа
'д пдХ 1! м
g1 1 ad f == : , (/, h) == /ihi' (11.4)
д!/дхм I i=l
мы получим из (11.2)
ft (р) + L\ + о (М = g (р) L\ + ft (р) +
+ (grad f, S (р)) Ll + о (Ll), (11.5)
предполаrая, что функция f имеет необходимые частные
Производные. Переходя к пределу при о, получим
дифференциальное уравнение в частных производных
: = g (р) + (gradf, S (р».
( 11.6)
До сих пор мы действовали формально. Чтобы cTporo
определить непрерывный процесс, исходя из основных
предпосылок, можно следовать различными путями. Во-
первых, можно проделать приведенный выше анализ,
показав, что дискретные последовательности {!nА (р)},
{РnА} сходятся по-разному, коrда L\ о. Во-вторых,
можно определить непрерывный процесс при помощи пе-
ременной состояния р (t), удовлетворяющей дифферен-
циальному уравнению
р' (t) = S (р), р (о) == Ро, (11. 7)
24
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. 1
и соответствующей функции, определяемой дифферен-
циальным уравнением в частных проиэводных
= g(p) + (gradj, S(p», 1(0) = 10.
(11.8)
Теперь возникает задача показать, что эти определения
являются содержательными в смысле существования и
единственности решений приведенных выше уравнений и
что эти решения обладают некоторыми желаемыми свой-
ствами.
Это - петривиальпые и зачастую очень трудные воп-
росы. По этой причине мы и предпочитаем далее сосредо-
точиться на дискретных процессах. Мноrоmаrовые про-
цессы принятия решений дискретноrо типа приводят нас
к достаточно большому числу концепций, а также к не
меньшему количеству аналитических и вычислительных
проблем. При этом мы вовсе не обязаны отвечать на за-
частую посторонние для нас деликатные вопросы сущест-
вования и единственности, связанные с непрерывными
процессами.
Упражнения
1. Рассмотрим следующий процесс. Частица двиrается на ОТ-
резке [О, 1] до тех пор, пона она не достиrнет ето rраничной точки.
В этот момент времени она иаменяет направление движения и дви-
жется в обратном направлении ДО тех пор, пока она не доетиrнет
друrой rраничной точки, и таи далее. 'Частица начинает движение
в точке с, двпrаясь вправо по заRОНУ du/dt = а > о. Движение
влево происходит по закону dи/dt = -Ь < О. Найдите выражение
для положения частицы в момент премеIПI t.
2. Предположите, что уравнения движения имеют вид dи/dt =
= аи, duldt = -Ьи соответственно, и решите ту же задачу.
3. Для каждой системы уравнений движения рассмотрите выра-
жение v (t) = и (t)/t. Существует ли lim v (t)? Если он существует
t oo
как функция С, то определите ero свойства и, в частности, получите
функциональное уравнение.
12. Траекторный процесс
Чтобы ПрОИЛЛIострировать некоторые из предыдущих
идей, рассмотрим простой траекторный процесс. Предпо-
ложим, что мы бросили вверх камень со скоростью V,
12]
ТРАЕRТОРНЫЙ ПРОЦЕСС
25
и допустим:, что после этоrо он движется под действием
лишь силы тяжести. Обычная трактовка этоrо процесса
достаточно проста. Пусть х (t) обозначает расстояние
камня от земли в момент времени t. Если пренебречь вли-
янием сопротивления воздуха, то уравнение дви)нения
точечной частицы имеет вид
а 2 х
_-_а
dt 2 - Ь
(12.1)
(ускорение является следствием rравитации и направле-
но вниз) с начальными условиями
х (о) == о,
х' (о) == V,
(12.2)
rде v > о. Решение уравнения имеет вид
gt 2
х= vt -2.
(12.3)
Отсюда мы видим, что максимальная высота достиrается
при t = v/g и определяется выражением
v 2
Х таХ = 2g ·
(12.4)
Частица заканчивает свой полет в момент времени t ==
= 2v/g, коrда она достиrает земли.
Достаточно просто, но имеются HeI{OTOpble избыточные
подробности.. Предположим, что нас интересует лишь
максимальная высота полета. Можно ли определить ее,
не касаясь информации относительно остальной части
полета? В рассматриваемой задаче это может по казаться
малосущественным, но в более сложных процессах эта
экономия усилий может быть внаЧJiтельной, в частно-
сти, если задачей исследования является лишь опреде-
ление зависимости максимальной высоты от начальной
скорости.
Применим изложенные выше идеи для Toro, чтобы
ответить на поставленный вопрос. Начнем с замечания,
Что максимальная высота зависит от начальной скорости
v. Поэтому введем функцию f (v) - максимальная высо-
та, достиrаемая при начальной скорости v. Рассмотрим
ДВИЖУЩУЮGЯ частицу как порождающую непрерывный
26
мноrОШАrоВЫЕ nРОЦЕССЫ
rrл. 1
мноrошаrовый процесс, в котором состояние системы
есть v. Для бескопечно малоrо интервала времени пре-
образование, определяющее состояние, имеет вид
т (v) == v-g .
(12.5)
иi1
Следовательно, мы имеем СООТ-
ношение (рис. 1.1)
f (v) == v + t(v-gl1) + 0(11).
(12.6)
f(и-gL1j
((и)
Разлаrая правую часть в ряд и
полаrая -+ О, получаем
О == v - gf' (v). (12.7)
Это - дифференциальное уравнение для t (v) с началь-
ным условием t (О) == о. Интеrрируя, мы получаем соот-
ношение (12.4).
о
Рис. 1.1.
Упражнения
1. Собака преследует кролика, вак показано на рис. 1.2. Пусть
скорость собаки Vd, а скорость кролика V r , И допустим, что Vd >V r .
Предположим, что в любой момент
времени движение кролика на- !I
правлено вдоль оси х, а собака
бежит по направлению к КРОЛИRУ. о(о,l1
Составьте дифференциальное
уравнение движения собаки и
сравните «решение» в классиче-
ских терминах, Т. е. в виде х (t)
как функции от t, с «решением» в
терминах поставленной здесь вада-
чи поrоии как процесса пресле-
дования, имея в виду получение
числепноrо решения.
2. Пусть f (Т, d) обозначает момент времени, в который собака
схватит кролика. Покажите, что
f (Т, d) = А + f (Т+ А, d - -y : d 2 ) + о(А),
откуда, полаrая А О,
О - 1 д! rJ:I.!L
- + дт - -у т 2 + d2 ad
rAe f (Т, О) = Т/ (Vd - V r ). ПОДQбвым же образом выведите уравнение
,
........
,
,
.......
,
"
о
1l(i;.O)
z
Рис. 1.2.
13]
НЕОДНОРОДНАЛ АТМОСФЕРА
27
в частпы производпых для величины g (Т, d), т. е. точки на оси Х ,
В которои собака доrопит кролика.
3. Примепите метод характеристик ДЛЯ определения f (r, d) и
g (r, d) в явном аналитическом виде.
13. Неодиородная атмосфера
Предположим теперь, что вместо уравнения (12.1)
мы имеем уравнение вида
: =h(x,x'), х(О)=О,х'(О) = V,
(13.1)
которое получено при учете силы сопротивления воздуха,
зависящей от положения и скорости точки. В связи с не-
однородностью атмосферы мы должны ввести дополни-
тельную переменную состояния С, равную высоте точки в
начале процесса.
Рассмотрим поэтому две переменные состояния с и v
с законом преобразования
С 1 = Т 1 (с, v) == с + и , v 1 == Т 2 (с, v) == v + h (с, v)
(13.2)
с точностью до о (/1). Если мы введем функцию
f (с, v) =ма1tСUЖаАъиая 8ысота, достuжuжая при старте
с ebLCOтbl, с со ск,оростъю v, (13.3)
то, как и выше,
f (с, v) == v!1 + f (с + v , v + h (с, v) ) + о ( ).
(13.4)
в пределе при -+ о мы получаем дифференциальное
уравнение в частных производных
д! д!
О = v + v ас + h (с, и) av ·
( 13.5)
Вообще это уравнение не может быть решено анали-
тически. Численное решение можно получить рядом спо-
собов, используя начальное условие f (с, О) = О, но не-
обходимо отметить, что при этом мы встретимся с рядом
28
мноrОШАrОБЫЕ ПРОЦЕССЫ
[rл. 1
тонкос-тей, которые треБУIОТ опыта и умения. Обсуждение
вычислительных аспектов приводится в rлаве 111. Для
получения численноrо решения можно также применить
метод характеристик.
14. Причинность
Все полученные выше уравнения являются частными
примерами соотношений, вытекаIОЩИХ из принципа при-
чинности, или, иными словами, из детерминизма.
Пусть состояние системы в момент времени t будет
представлено функцией f (с, t), rде с есть состояние в
момент времени t = о. Мы можем представить себе сис-
тему стартующей из состоя-
ния с в момент времени t = о-
и продолжающей движение
s+t до момента времени s + t;
в этом случае ее конечным
состоянием будет f (с, s + t).
Можно также представить
себе систему стартующей из
состояния с в момент времени t = О и продолжающей
движение до момента времени t, в котором ее состояние
будет 1 (с, t), и далее движущейся в течение дополнитель..
Horo промежутка времени s, в каковом случае ее конеч-
ное состояние будет 1 (1 (с, t), s) (рис. 1.3). Мы уже
рассматривали дискретный вариант TaKoro подхода в
разделе 5.
Детерминизм утверждает, что обе процедуры ведут к
тому же самому конечному состоянию. Следовательно,
мы имеем основвое функциональное уравнение
1 (с, s + t) = 1 (1 (с, s), t). (14.1)
Иа этоrо соотношения MoryT быть получены мноrие пос-
ледующие результаты, как, например, результаты раз-
дела 11.
о
Рис. 1.3.
Упражнения
1. Используйте единственность решения уравнения и' = аи"
и (О) = с, чтобы получить Функциоиальное уравнение для Эl(сцовеq.
циальвой функции ea{s+t) = e as e at .
15]
СТОХАСТИЧЕСRИЕ ПРОЦЕССЫ
29
2. Пользуясь спответствующим результатом для векторно ма'!'-
ричноrо уравнения х' = Ах, х (О) = с, получите матричный аиалоr
eA(s+t) = е Аз e At .
3. АналоrиЧIIО, ИСХОДЯ из факта, что sin t и cos t суть реm иия
уравнения и" + и = О, установите формулы
sin (s + t) = sin s cos t + сов s sin t,
соз (8 + t) = cos s соэ t - sjn s sin t.
15. Стохастические процессы
До сих пор мы предполаrали, что результат преобра-
зования Т состоит в переходе вектора состояния р в век-
тор состояния Рl' rде Рl определяется через р единствен-
ным образом. Во мноrих случаях МЫ встречаемся с тем
фактом, что Т не полностью известно. Это означает, что
простая детерминированная модель, которая применялась
нами, должна быть заменена более сложной моделью.
Чтобы частично обойти преrраду отсутствия информации,
обратимся к классической теории вероятностей.
Вместо искреннеrо признания, что Рl нам неизвестно,
мы предполаrаем, что Т есть стохастическое преобразо-
вание, которое порождает случайный вектор Рl' распре-
деление вероятностей KOToporo определяется через р.
Последовательность векторов [р, Рl' Р2'... ] определяет
теперь дискретный мноrоmаrовый процесс стохастическо-
ro типа. Из этоrо следует, что значения соответствующих
функций будут также случайными величинами. Для воз-
Можности получения численных результатов мы будем
оперировать с математическими ожиданиями функций
этих случайных переменных. Это - стандартная процеду-
ра при изучении стохастических процессов.
Для иллюстрации этих идей начнем с, пожалуй, про-
стейmеrо случая, коrда Pk определяется соотношением
Рк = т (Pk-l' Т к ), k = 1, 2,. ..,
(15.1)
rде Ро = Р и Т к - независимые случайные перемениые
с одинаковым распределением вероятности dG (Т). Пред-
положим, что :мы хотим определ;итъ математическое ожи-
дание для
g (р) = g (Pl) + ...+ g (PN). (15.2)
30
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. 1
Как и ранее, начнем с замечания, что это математическое
ожидание зависит от начальноrо состояния р и числа ша-
rOB N. Напишем тоrда для N :;> 1
tN (р) = ехр [g (р) + g (Pl) + ... + g (PN)}.
r
(15.3)
Здесь обозначение «ехр» указывает, что математическое
r
ожидание должно быть взято относительно случайных
переменных '1' '2' ..., 'N. Как и выше, предполаrаемая
независимость 'k позволяет нам заключить, что
fN (р) = ехр [g (р) + fN-l (Т (р, r1»] ==
rl
= g (р) + fN-l (Т (р, rl)) dG (r 1 ),
rде 10 (р) == g (р).
(15.4)
Упражнения
{. Пусть и n + 2 = аиn + 'n, rде 'n - случайные иезависииые
величины с общей функцией распределения dG (r). Обозначим
f N (с) == ехр N_ и · Покал{ите, что /.., (с) есть Rвадратичиый
r LJn-о
полином по с, И, используя вышеприведенное уравнение, полу-
чите рекуррентное соотношение для ero коэффициентов. Покажите,
что f N (с) зависит только от первоrо и BTOpOro моментов dG (r),
т. е. от величии rdG (Т), r 2 dG (Т) И изучите асимптотическое
поведение fn (с) при N 00.
2. Дайте обобщение на векторно-матричпый случай, коrда
Х n + 1 = Ах n + ' n ' хо = С.
16. КорреnSlЦМSI
Во мноrих случаях предположение о независимости
'k является неоправданным. В качестве первоrо mara в
напраВJIении учета этой зависимости предположим, что
функция распределения для '1\ зависит только от зна-
чения rk-l' т. е. dG (Т1\) = dG ('k' rk-l). В этом случае
можно выбрать в качестве переменныx состояния р-
текущее состояние системы, и '0 - предшествующее зна-
чение случайной величи ы r. По аналоmи с (15.4) имеем
tN (р, '0) = g (р) + S IN-l (Т (р, Т1) dG (r1, '0). (16.1)
17]
НАБЛЮДЕНИЯ ПРИ НАЛИЧИИ ШУМОВ
31
Имеется MHoro друrих путей учета взаимной зависи-
мости r7;,. Предположения, сделанные выше, являются
наиболее удобными для метода функциональных уравне-
ний, I\ОТОРЫЙ здесь применяется.
Упражнение
Рассмотрите уравнение U n + 1 = аun + r n , rде распреде-
ле1Лlе r n есть dG (r n , r n - 1 ). Пусть uo = с и r -1 = 1.). Обозначим
f N (с, Ь) == ехр N_ и . Покажите, что
r 11-0
fN (с, Ь) = UN (Ь)с 2 + 2VN (Ь)с + WN (Ь),
и получите рекуррентное соотношение для ин, VN, WN из реRурреит-
Horo соотношения ДАН fN (с, Ь). Изучите асимптотическое поведевие
UN, V.v, И Ш: .; при N -+ 00.
17. НаБЯlOденн" при наянчни ШУМОВ
Как только мы допускаем возможность неопределен-
ности rде-либо в наших исходных предпосылках, мы дол-
жны уч:ит:ы:вать ее всюду. Предположим, что мы хотим
учесть возможность значительной веопределенноети в
наблюдениях состояния системы. Проще Bcero предпо-
ложить, что коrда мы наблюдаем р, то мы знаем, что в
действительности состояние системы есть р + r, rде r
есть случайная переменная с известным распределением.
Мы можем тоrда представить себе два процесса: один
[р, Pl, Р2,...] - действительное состояние системы, и
второй [q, Ql, Q2' ...] - наблюдения, сделанные над сис-
темой, т. е. информация, которой мы фактически распо-
лаrаем. Справедливы следующие соотношения:
р = q,
Рl = Т (р),
Р2 = Т (Рl),
ql = Рl + rl,
q2 = Р2 + r2,
.
.
(17.1)
.
Рn = т (pn-l),
ln=pn+ r n.
32
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rЛ.I
Если мы примем наши наблюдения в качестве состояний
системы, то как видно из приведенноrо выше, мы получим
сто!Хастический мноrошаrовый процесс [q, ql' q2' ...],
rде
ql = т (q) '- '1, )
:2 = т (ql - Тl) - Т2. l
. . I
qn = т (qn-l- rn-l)- r n , J
(17.2)
т. е. процесс со взаимной зависимостью между 'n' типа
описапноrо выше. Таким образом леrко получить функ-
циональное уравнение для соответствующих функций.
18. Скрытые переменные
Если Рl = Т (р, q), rде q есть вектор, самое СУIце-
ствование KOToporo неизвестно нам, то это может побу-
дить нас рассматривать Т как случайное преобразование
в следующем смысле. Фиксируя р и повторяя процесс
преобрааования, т. е. наблюдая набор из подобных систем,
мы найдем систему величин
Рl1 = Т (р, Ql), Р12 = Т (р, Q,,), ..., (18.1)
т. е. различные значения Pl, соответствующие тому же
самому значению р, но различным значениям q, а именно
ql для первой системы, q2 для второй системы и т. д. Воз-
можный равброс в воспроизведении Рl для Toro же caMoro
значения р может заставить нас поверить, что концепция
детерминизма не имеет силы. Желаем мы или не желаем
верить в детерминированные процессы как в основное и
считать стохастические процессы исключительно мате-
матическим СПОСQбом учета неив ествых или «скрытых»
переменных или мы считаем, что модель природы в ос-
новном стохастическая с детерминизмом, получаюlЦИМСЯ
в результате Qсреднения (снова математический прием),-
вопрос разделяемой тем или иным лицом философской
точки зрения, которая, к счастью, мало влияет на пост-
роение возникающих здесь аналитических моделей.
19]
ИНДУЦИРОВАННЫЕ ПРОЦЕССЫ
33
Важно, однако, отметить еще раз, что возможен зна-
чительный дрейф от прямолинейноrо направления в кон-
струировании математических моделей физических явле-
ний, и было бы несчастьем позволить научному доrматиз-
му препятствовать формулированию и рассмотрению
удобных математических моделей.
19. Индуцированные процессы
Отправляясь от процессов любоrо из приведенных
выше типов, можно получить друrие процессы разнооб-
разными способами. Прежде Bcero, можно отдать предпо..
чтение той структуре процесса, при которой упрощается
аналитический вид соответствующей функции или умень-
шается размерность процесса. Проиллюстрируем первы:й
из этих вопросов на процессе, уже рассмотренном в уп.
ражнениях. Предположим, что
N
и n +l == аи n + Ь, и о == С, /N == и;.
n=о
(19.1)
Леrко видеть, что fN == PN + 2QNC + rNc 2 , rде PN, QN, rN
не зависят от с. Кроме Toro, преобразование первоначаль-
ной переменной состояния приводит К преобразованию
переменных (PN, QN, rN) при помощи peKyppeHTHoro соот-
ношения
fN-tl (с) = с 2 + fN (ас + Ь)
(19.2)
или
PN+l = PN + 2bqN + b 2 rN, I
qN+l = aqN + abrN,
rN+l = a 2 rN + 1.
Вместо (19.2) мы можем использовать эти преобразования
для изучения исходноrо процесса. Это - важное умень-
mен:ие размерности и увеличение аналитической rибкости,
так как мы заменяем функцию fN (с), которая определена
пр:и: -00 < с< 00 тройкой [PN, QN, rN]. Мы вернемся
R этому в rлавах 111 и IV.
(19.3)
34
мноrОШАrОБЫЕ ПРОЦЕССЫ
[rл. 1
Аналоr:ично предположим, что мы исходим из процесса
х (t), определяемоrо векторным уравнением
ах
dt = Ax(t),
х (О) = С,
(19.4)
rде х есть N -мерный вектор, и принимаем в качестве ФУНК-
цИИ состояния g (Хl (Т), ..., Xk (Т», т. е. функцию от пер-
вых k компонент х. Так как решение уравнения (19.4)
имеет вид
х (t) = eAtc,
(19.5)
то мы видим, что, коrда речь идет об этой функции состоя.
ния, новым вектором состояния будут первые h ком-
понент е АТ С, что уменьшает размерность от N до k. Дру-
rими словами, мы можем сrустить желаемую информацию
относительно системы до набора из k чисел. Это может
быть весьма важным для приложений как с аналитиче-
ской, так и с вычислительной точки зрения.
20. Косвенные и индуцированные процессы
Мы предполаrали выше, что новое состояние Рl опре-
делялось при помощи преобразования Т, примененноrо к
предыдущему состоянию р. В некоторых процессах ситу-
ация не столь прямолинейна. Предположим, например,
что мы имеем процесс {Х n } справилом преобразования
Х n +l = Ах n ,
ХО = с.
(20.1 )
Здесь х n есть N -мерный вектор с Rомплекеными компо-
нентами. Пусть Xni, i = 1,2, ...,N, обозначают N компо-
нент вектора Х n . Образуем новую систему ив N величин
IX n ti 2 , i = 1,2,..., N. Если А есть унитарная матрица, т. е.
N .N
r Xni 12 = I Ci 12,
i=lj i=1
ТО можно нормировать с так, чтобы
N
{Ci 12 = 1,
t==l
21]
БОЛЕЕ ОБЩИЕ СТОХАСТИЧЕСНИЕ ПРОЦЕССЫ
35
и, таким образом, предположить, что величины I X nl 1 2
являются вероятностями. Система [)x n1 1 2 , ..., lxnNl2] обра-
зует новый процесс с законом преобразования, не принад-
лежащим к расс:м:отренному до сих пор классу. Преобра-
зования этоrо типа, которые MoryT казаться непривычны-
ми, являются основными преобразованиями квантовой
механики. Мы, однако, не будем рассматривать их здесь,
равным образом как и те интриrующие новые типы про-
цессов управления, которые они порождают.
21. &оnее общие стохастические процессы
Как только мы позволяем веопределенности поднять
свою вопрошающую rолову, мы вводим MHoro чрезвычай-
но интересных новых типов процессов и, соответственно,
новых типов функциональных уравнений. Укажем кратко
различные пути, которыми можно модифицировать детер-
минированные процессы для Toro, чтобы получить важные
стохастические процессы.
Во-первых, вместо Toro чтобы оrраничиться преобра-
зованиями, действующими на систему в предписанные
моменты времени, можно предположить, что промежуток
времени между преобразованиями сам является случай-
ной переменной. Это приводит нас в область ветвящихея
процессов, которые содержат, как специальный случай,
процессь" восстановления. Процессы этоrо типа имеют важ-
ное значение в ядерной физике, современной теории уп-
равления запасами, теории управления и при исследова-
нии процессов обучения.
Во-вторых, можно рассматривать стохастический про-
цесс [р, т (р, r)), в котором на каждом mare имеется не-
которая вероятность Toro, что существующее состояние
системы не может быть наблюдаемо. Практически это мо-
жет возникнуть вследствие потери связи или отказа при-
нимающих приборов.
Процессы этоrо более общеrо типа вынуждают нас,
в частности, заменить конечномерную переменную состо-
ЯВИЯ на бесконечномерную, исходя из распределения веро-
ЯТностей. Тоrда используются различные методы замены
бесконечномерноrовектораконечномерным.Так, например,
Можно оrраничитъся лишь первым и вторым моментами
36
мноrОШАrОВЫЕ ПРОЦЕGСЫ
[rл. 1
или, ::>квивалентно, средними значениями и дисперсиями
в качестве новых переменных состояния.
Как упоминалось прежде, мы здесь не вдаемся в сколь-
ко-нибудь систематическое рассмотрение процессов,
требующих бесконечномерных векторов состояния.
22. ЗаКПlOчение
Целью этой rлавы было ввести читателя в основные
понятия математической теории процессов и систем и
да1:Ь ему возможность приобрести некоторое ощущение
знакомства с функциональными уравнениями и рекуррент-
ными соотношениями. Этим мы имели в виду облеrчить
«культурный шок» от введения понятий и методов дина-
мическоrо проrраммирования. Так как мы преследовали
только эту оrраниченную цель, мы не позволили себе
уrлубляться во мноrие интересные вопросы, связанные с
классификацией процессов, их анализом и (или) их чис-
ленным решением. При изучении стохастических процес-
сов эти вопросы приводят К понят:иям достаточных и
асимптотически достаточных статистик. Довольно стран-
но, что соответствующие концепции, несмотря на их оче-
видную важность, не были формально изучены для детер-
минированных процессов.
Миоrо еще остается сделать в этих направлениях, пред-
ставляющих плодородную почву для исследований мо-
лодых ученых. Некоторые важные статьи и книrи для бо-
лее подробноrо знакомства с этими вопросами указаны в
библиоrраф:ии.
6ибпиоrрафия и комментарии
1. Точное и подробное обсуждение понятия «система» со мноrими
выясняющими суть дела примерами дано в книrе
L. А. Z а d е h and С. А. D е s о е r, Linear System Theory,
The State Врасе Approach, McGraw-Нil1 Book Company, Inc.,
New York, 1963..
2. Имеется MHoro доступных в настоящее время Rниr, в ROTOpblX
рассматриваются дифференциальные, разностные и ин'rеrральные
уравнения. Теорию дифференциально-разностных уравнений СМ.,
например, в книrе
Р. Б е л л м а н и К. К у к,. Дифференциально-разност-
вые уравнения, «Мир», 1967.
БИБлиоrРАФИЛ и RОММЕНТАРИИ
37
э 3. Подробное изложение классической механиии имеется в иниrе
Дж. д. Б и Р к r о ф, Динамические системы, rиттл, Моск-
ва - Ленинrрад, 1941. Здесь приводятся ссылки также на
труды Пуанкаре, Адамара, Леви-Чивита и друrих.
7. Систематическое исследование существования предельноrо по-
ведения приводит к ряду классических вопросов анализа, теории
устойчивости, эрrодичности, асимптотичности, суммируемости и
Т. д. Укажем здесь работы
п. Р. Х а л м о ш, Лекции по эрrодической теории, ИЛ,
1959.
Р. Б е л л м а н, Теория устойчивости решений дифферен-
циальных уравненип, ИЛ, 1954.
Н. r. д е Б рей н, Асимптотические методы в анализе
ИЛ, 1961.
э 10. Читатель, интересующийся вопросами итераций, может обра-
титься к трудам
J. Н а d а m а r d, Two Works оп Iteration and Related Ques-
tions, Bull. Amer. Math. Soc., vol., 50, 1944, рр. 67-75.
Т. Е. Н а r r i в, The Theory of Branching Processes, Pren-
tice-Hall, Inc., Englewood Cliffs, New Jersey, 1964.
11. MHoro усилий в современной теории дифференциальных урав-
нений с частными производными посвящено обоснованию аппрокси-
мации непрерывных процессов дискретными процессами, которые
леrче изучить при помощи цифровых машин. См., например,
G. F о r s у t h е and w. w а s о w, Finite-Difference Ме-
thods for Partia1 Differentia1 Equations, J ohn Wiley & Sons,
New York, 1960.
Более сложное введение в теорию непрерывных мноrоmаrовых про-
цессов может быть построено при помощи непрерывных rрупп преоб-
разований - теории Софуса Ли. Для первоrо знакомства см.
Е. L. 1 n с е , Ordinary Differential Equations, Dover Publi-
cations, New York, 1944.
L. Р. Е i s е n h а r t, Continuous Groups о! Transformation,
Dover Publications, Inc., N ew York, 1961.
12-13. Этот подход разобран в работе
R. В е 11 m а n, Functional Equations and Maximum Range,
Quart. Appl. Math., уоl. 17, 1959, рр. 316-318.
14. СМ. также обсуждение в rлаве 2 квиrи
Р. Б е л л м а н, Процессы реrулировапия с адаптацией,
«Наука)), 1964, а также
х. Н а d а m а r d, Lectures оп Cauchy's Problem in Linear
Partial Differential Equations, Dover Publications, New York,
1953.
Современная теория полуrрупп ведет свое начало ОТ работы Адамара,
раСсмотренной в Rниrе.
э. Х и л л, ФУНRциональный анализ и полуrруппы, ИЛ,
1951.
38
мноrОШАrОВЫЕ ПРОЦЕССЫ
[rл. 1
RлассичеСRая теория основывается на времени, пак на переменной
полуrруппы. Теория инвариавтноrо поrружения содержит анало-
rичные функциональны1e уравнения в пространстве переменных сос-
тояния; СМ., например,
R. Be1lman, R.Ka1aba and G.M.Wing, Inva-
riant Imbedding and Mathcmatica1 Physics - 1: Particle Pro-
cesses, Х. Math. Phys., vol. 1, 1960, рр. 280-308.
G. М. W i n g, An Introduction to Transport Theory, J ohn
Wiley and Sons, New York, 1962.
Для подробноrо озпакомления с теорией функциональных уравне-
ний рекомендуем
J. А с z е 14 V orlesungen iiber Funktionalg1eichungen und
ihre Anwendungen, Birkhauser, Basel, 1961, English trans-
lation, Academic Press Inc., New York, 1965.
15. Введение в теорию стохастических процессов и их применения
можно найти в работе
А. Т. В h а r u с h а - R е i d, Elements of the Theory of
{arkov Processes and Their Applications, McGraw-Нi11 Book
Сотрапу, Inc., New York, 1960.
18. Вопрос о скрытых переменных вызвал MHoro споров, начиная
с развития Rвантовой мехаНИRИ. См. по этому вопросу
L. d е В r о g 1 i е, N onlinear Wave Mechanics, А Causal
Interpretation, Elsevier, Amsterdam, 1960,
rде MoryT быть найдены также мвоrие дополнительные ссылки.
19. Рекомендуем
Н. В е 11 m а n and R. К а] а Ь а, Reduction of Dimensio-
na1ity, Dynamic ProgrammilOg and Contro1 Processes, Х. Basie
Engr., vol. 83, 1961, рр. 82-84.
20. Детальный разбор приведен в статье
Е. М о n t r о 11, Markoff Chains, Wiener Integrals and Quan-
tum Theory, Соmт. Pure Аррl. Math., vol. 5, 1952, рр. 415-
453.
21. См. цитированную Rниrу Харриса, а таRже
К. J. А r r о w, s. к а r 1 i n and Н. S с а r {, Studies i.
the Mathematica1 Theory of Inventory and Production, Stan-
ford University Press, Stanford, California, 1958.
О «прерывающихся» процессах управления-
R. В е 11 т а n and R. К а 1 а Ь а, Iпtеrrпрtеd Stochastic
Contro1 Processes, Information and Control, vol. 4, 1961.
р. 346-349.
22. Читатель, интересующийся этими вопросами, может обратить-
ся к следующим работам: J
R. В е 11 m а п, с. С 1 а r k, с. С r а f t, D. М а 1 с о 1 n
and F. Ri с с j а r d i, Оп the Construction of а Multi-person
Multi-stage Business Game t Operations Research, vol. 5, 1957
рр. 469-503.
БИБлиоrРАФИЯ ИНОММЕНТАРИИ
39
R. В е 11 m а n and Р. B'r о с k, Оп tlle Concepts ()f а Prob-
lет and Problem-solving, Amer. Math. Monthly, vol. 67, 1960,
рр. 119-134.
R. В е 11 m а n, Directions of Mathematical Research in
Nonlinear Circuit Theory, IRE Trans. оп Circuit Theory, vol.
СТ-7, 1960, рр. 542-553.
R. В е 11 m а п, Mathematical Model-making as ап Adaptive
Control Process, Mathematica1 Optimization Techniques, R.
Bellman ed., University of California Press, Berkeley, Califor-
nia, 1963,рр. 333-339.
R. В е 11 m а п, 1\1athematical Experimentation and Biolo-
gica1 Research, Federation Proc., vol. 21, 1962, рр. 10!:\-111.
R. В е 11 m а n, Dynamic Programming, Intelligent fachines,
and Self-organizing Systems, Proc. of the Symposium оп Mat-
hematical Theory of Automata, 1962, Polytechnic Institute of
Brooklyn.
r л а в а 11
мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЯ
1. Введение
Мы теперь подrотовлены к изучению мноrошаrовых
процессов принятия решений, иными словами, теории
динамическоrо проrраммирования. Эти процессы являют-
ся математически важными по своему существу, как есте-
ственное и далеко идущее обобщение преобразований,
изучаемых в классическом анализе. Кроме Toro, как мы
увидим ниже, они занимают фундаментальное положение
в современной теории управления.
Для Toro чтобы перейти к теории динамическоrо про-
rраммирования, мы присоединим концеПЦИIО решеuие к
концепции lttuоеошаеовъltй процесс. Как и выше, изложение
будет rлавным образом посвящено представлению абст-
рактных идей, в то время как упражнения будут со...
держать ряд примеров, иллюстрирующих методы, вме-
сте со ссылками }la первоисточники для дальнейmеrо
чтения.
Важным новым понятием является попятие страте-
еии. В аналитических терминах оно приводит к некоторо-
му типу последовательных приближений, пеизвестному
в классическом анализе, а именно, приближениям в про-
странстве стратеrий. Это в свою очередь, как мы покажем,
приводит к аппарату квааилинеаризации, очень мощно-
му и rибкому подходу ко мноrим типам нелинейных функ-
циональных уравнений.
В rлаве 111 мы рассмотрим применение динамическоrо
проrраммирования в качестве вычислительноrо алrори
ма, способноrо давать численные ответы на численные
вопросы. В rлаве lУ мы обсудим особый класс MHoroma-
rOBblx процессов принятия решений, которые MoryT быть
изучены с некоторыми аналитическими подробностями
2]
мноrОШАrовый ПРОЦЕСС ПРИНЯТИЯ РЕШЕНИЙ
41
1. Мноrошаrовый процесс принятия решений
Чтобы определить мноrоmаrовый процесс принятия
решений простейmеrо типа, дискретный и детерминиро-
ванный, мы начнем с уже известноrо нам понятия MHoro-
maroBoro процесеа [р, Т (р)]. Напомним, что это есть по-
следовательность векторов
[р, Рl, Р2, ...,Рn,...],
rде Pn-tl = т (p ), Ро = р. Теперь мы расширим это по-
нятие, полаrая, что преобразование Т зависит от друrо-
ro вектора Т = Т (р, q). Предположим, что мы можем ока-
зать достаточное влияние на процесс. в том смысле, что
на каждом шаrе можем выбрать значение q из набора до-
пустимых векторов S (q). Пусть qi будет наш выбор на
i-M mare, так что
Pl = т (р, qo), 1
Р2 = Т (Рl, ql),
\
Pnt 1 = т (Рn, qn). J
(2.1)
.
Вектор qi называется ве"тором, решения или переменной
решепия и выбор q i называется решением. Таким образом,
решение эквивалентно преобразованию. Мы будем иметь
дело с процессами, в которых qi выбирается так, чтобы
максимизировать предписанную скалярную функцию сос-
Тояния и переменной решения
R (р, Рl, Р2, ..., Qo, Ql' ...). (2.2)
То, что было выше функцией состояния теперь 1):вляется
фуuпцией прит,ерия или фуnпчией дохода. N-шаrовый
процесс принятия решений (дискретноrо детерминирован-
IIoro типа, единственный род процессов, который мы зна-
ем в данный момент) есть последовательность векторов
[р, Рl' Р2, ..., PN; qo, Ql' ... QN], (2.3)
rде Рn+l = т (Рn, qn) ЛЯ каждоrо n.
42 МНОfОШАfОВЫЕ ПРОЦЕССЫ ПРИНЯТИЛ РЕШЕНИЙ [fЛ. 1
3. Стратеrия
Введем теперь важное понятие - стратеrия. Как бы-
ло упомянуто выше, величины qk должны быть выбраны
на каждом шаrе способом, который ввиду общеrо харак-
тера функции R зависит от текущеrо состояния системы,
прошлоrо и будущеrо состояний и также от прошлоrо и
будущеrо решений. Мы будем иметь здесь дело с крите-
рием R, обладающим структурой, которая позволяет нам
сосредоточить внимание исключительно на прошлой и
текущей истории процесса при поиске величин q. В не-
скольких последующих разделах мы продемонстрируем
функции критерия, обладающие этим важнейшим свойст-
вом. При этих предположениях мы можем оrраничиться
функциями вида
qk = qk (р, Рl' Р2, ..., P/l; qo, Ql' ..., qk-l). (3.1)
Эта функция называется фуuпцuеи стратееии или просто
стратееией. Нетрудно видеть, что описание процессов
управления стратеrией такой струнтуры не является серь-
езным оrраничением, так как принятие решения основы-
вается только на знании проmлоrо. Важно, однако, сде-
лать все предположения явными.
Стратеrия, которая максимизирует функцию R, назы-
вается опти.ма,л,Ь1/;ОЙ страте2ией. Наше изложение MHoro-
шаrовоrо процесса принятия решения будет зависеть от
вида оптимальной стратеrии *).
Пока еще выражение (3.1) имеет достаточно общий вид.
Обратимся к стратеrиям, имеющим сравнительно простой
вид
qk = qk (Pk)
(3.2)
функции текущеrо состояния и mara процесса. Это допол'"
нителъное упрощение является следствием дальнейшей
детализации структуры функции критерия R, такой струк-
туры, которая позволяет принять оптимальное решение
по одним лишь сведениям о текущем состоянии системы.
.) Вид оптимальной стратеrии определяется информацией о
состояниях системы, RОТОрОЙ мы располаrаем или RОТОРУЮ мы ис-
пользуем для формирования етратеrии. (Прuм,. ред.)
4]
СЕПАРАБЕЛЬНЫЕ НРИТЕРИИ
43
Предварительно мы подчеркнули, что под состоянием
системы здесь понимается математическое описание моде-
ли этой системы. Посредством npocToro способа введения
HOBoro состояния
1tk = [Pk' Pk-l'...]
(3.3)
в пространстве более высокой размерности можно всеrда
написать
qk = qlJ (Лk).
(3.4)
Следовательно, достоинство Функциональноrо соотноше-
ния вида (3.2) может оцениваться только в смысле ана-
литической и вычислительной леrкости и осуществимости.
Весьма существенно, чтобы размерность Pk была малой и
чтобы функциональное соотношение было сравнительно
простым.
Мы вернемся к этому вопросу в rлаве 111 в связи с
вычислительными аспектами динамическоrо проrрамми-
рования.
4. Cenapa6enbHble критерии
R счастью, некоторое количество важных критериев
обладает этим жизненно необходимым свойством разъеди-
нения проmлоrо и настоящеrо. Вообще, леrко предвидеть
это свойство из самой сущности исходноrо мноrошаrо-
Boro процесса принятия решения. В ряде ситуаций требу-
ются, однако, некоторые размышления или изменения
формулировок. Примеры этоrо свойства, которые мы бу-
дем проверять ниже, даются следующими критериями:
N
а) g (Рк, Qk),
k =O
Ь) g (PN) (терминальное
с) шах g (р,,-, qk).
k o
)
I
управление), I
J
(4.1)
Отметим, что последний критерий связан с бесконечно-
IПаrовым процессом.
44 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЛ РЕШЕНИЙ [rл. 11
5. ПрИНЦИП оптимаnьноети
Далее будем предполаrать, что мы имеем дело с про-
цессами принятия решений, формулировка которых по-
зволяет нам оrраничиться рассмотрением етратеrий, зави-
сящих только от текущеrо состояния. В этом особенном,
но чрезвычайно важном случае оптимальная стратеrия
характеризуется очень просто:
При н ц и поп т и м а л ь н о с т и. Опти.ма.лъnая
стратееия обладает тем свойством, что, "Кa"Кoвь бы ии
6ь ли первоnача.лъnое состояnие и первоnачалъиое решение,
последующее решеиие должио определять оптимальную
стратееию относительио состояиия, получеииоео в резулъ-
тате первоnачалъnоео решеиия.
Чтобы проиллюстрировать этот интуитивный принцип,
предположим, что мы имеем N-шаrовый процесс, облада-
ющий требуемой отделимостью прошлоrо от будущеrо,
начинающийся в положении р, с оптимальной последова-
тельностью решений qo, Ql, ..., QN-l, так что Рl = Т (р, Qo),
Р2 = Т (Рl, ql) И т. д. Тоrда Ql' Q2' ..., qN-} должны пред-
ставлять собой оптимальную последовательность решений
дЛЯ (N - 1)-mаrовоrо процесса, начинающеrося в положе-
нии Рl. Используя это соображение, получим уравнение,
которое позволит нам изучить как аналитически, так 11
численно оптимальную стратеrию и максимальный доход.
6. Примеры
Рассмотрим задачу о максимизации функции дохода
N
R (р, Рl, ..., qo, ql'...) = g (Pk' qk).
К=О
(6.1)
Для Toro чтобы быстро решить вопрос о существовании
максимума, мы можем либо оrраничить р и q конечным
набором значений, либо наложить разумные оrраничения
на непрерывность функций g (р, g) и Т (р, Q). Так как по-
лучение численноrо решения требует конечности в неко-
тором смысле, то первое предположение почти не сужает
класса доступных для решения задач. Обычно этот мо-
мент редко вызывает трудности при исполь овании N -ша-
8]
ПРИМЕРЫ
45
rOBblX процессов. Поэтому мы отошлем читателя к дру-
rим источникам ДЛЯ обсуждения вопроса о существова-
нии оптимальной стратеrии для мноrошаrовых процессов
общеrо вида и сосредоточим внимание на формальных
аспектах.
Максимальное значение R, зависящее только от на-
чальноrо состояния р и числа maroB N, обозначим через
fN (р). Друrими словами,
fN (р) == общему N-шаеовом,у доходу при пачалы-tом состоя-
пии р, получаемому при оптимальпой стратееии. (6.2)
Принцип оптимальности позволяет нам заключить, что
при любом начальном решении qo мы имеем для N > 1
g (р, qo) + [с (Pl' ql) + ...+ g (PN, qN)] =
= g (р, qo) + fN-l (Т (Р, qo)). (6.3)
Так как это справедливо для всех начальных решений
qo, то, чтобы найти Iаксимальный доход fN (р), МЫ долж-
ны найти максимум (6.3) по qo. Таким образом, мы полу-
чили основное функциональное уравнение
fN (р) = шах [g (р, qo) + !N-l (Т (р, qo»], N 1, (6.1 )
qo
rде
/0 (р) = шах g (р, qo).
qo
(6.5)
Аналоrично для задачи оптимальноrо управления (4.tb)
мы имеем
/0 (р) = g (р), fN (р) = шах !N-l (Т (р, qo)). (6.6)
q..,
Для третьей функции дохода соrласно (4.1с) будем иметь
f (р) = шах maxg (Ph, Qk), (6.7)
{q) k>o
и, таким образом, так как тах Uk = шах [иl, шах ик],
k l h 2
t (р) = шах шах [g (р), f (Т (р, qo»] =
qo
= тах [g (р), шахl (Т (р, qo»)]. (6.8)
q. q)
46 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯ:ТИЯ: РЕШЕНИЙ [rл. 11
в связи с уравнением (6.8) важно отметить, что воз-
можны большие трудност:и в изучении вопросов существо-
вания и единственности решения этоrо уравнения. Эти
вопросы леrче разрешить, если принять вместо (4.1с)
функцию дохода
шах g (Pk' Qk),
o<:k N
(6.9)
связанную с N-mаrовым процессом. Мы рассмотрим этот
вопрос в разделе 15.
7. Друrой ВЫВОД OCHOBHoro фуикционаnьноrо уравнения
Для тех, кто с некоторым правом на этом раннем эта-
пе усомнится в принципе оптимальности, мы дадим вы-
вод уравнения (6.4), следуя обычным путем. Имеем
шах R = тах шах R. (7.1)
[Чо, qJ., ..', qN] qo [ql, Q2, ..., qNJ
Следовательно"
fN (р) = шах [g (р, qo) + g (Рl, ql) + ... + g (PN, QN)] =
[qo,qt",. ,QN] ,
= шах шах [g (р, qo) + ...] = шах [g (р, qo) +
ч. [Qt,Q2,...,QN] qo
+ шах [g (Pl, ql) + g (Р2, q,,) +...+ g (PN, qN)]] =
[QI,Q2,..' ,QN]
= шах [g (Р, qo) + !N--l (Т (р, qo»]. (7.2)
ч,
Здесь мы пользовались лишь очевидными свойствами опе-
рации отыскания максимума и учитывали сепарабельностъ
структуры функции дохода R. В случае более сложных
процессов обычно звачительно проще исходить из попятия
MHoromaroBoro процесса, чем опираться на универсаль-
ные аналитические методы.
8. Что явпяется решениемl
Посредством метода функциональных уравнений ди-
намическоrо проrраммирования мы привели задачу об
определении последовательности решений, которая мак-
симизирует функцию критерия, к задаче отыскания реше-
9]
НЕПРЕРЫВНЫЙ мноrОШАrовый ПРОЦЕСС
47
ния функциональноrо уравнения. Используя уравнение
(7.2) для Toro, чтобы конкретизировать обсуждение, вы-
яспим, что мы понимаем под «решением».
В классической трактовке решение означает алrоритм
ДЛЯ определения последовательности {!N (р)}, который
имеет более простой вид, чем рекуррентное соотношение
(7.2). В контексте динамическоrо проrраммирования мы
имеем больше rибкости. Решение может быть дано в тер-
минах последовательности {!N (р)}, последовательности
функций дохода, или последовательности {qN (р)}, пос-
ледовательности функций стратеrии. Леrко видеть, что
каждая из этих последовательностей определяет друrую.
Заметим, однако, что имеется только одна последователь-
ность оптимальных функций дохода, хотя может быть
мпоrо оптимальных стратеrий, которые дают тот же са-
мый максимальный доход.
В разделе 11 эта двойственность будет исследована с
rеометрической точки зрения.
9. Непрерывный мноrошаrовый процесс
прииятия решения
Для Toro чтобы ввести важное и полезное понятие
непрерывноrо MHoromarOBoro процесса принятия реше-
ний, мы перейдем, как и выте, от дискретноrо к непре-
рывному процессу при помощи предельпоrо перехода.
Пусть /). - бескопечо малая величина, функция дохода
N
Lj g (Pk, qk) , (9.1)
k==O
а рассматриваемое преобразование имеет вид
т (р, q) = р + S (р, q) .
(9.2)
Пусть решения припимаются в моменты времени О, 11,
2!:!, ... Обозначим N /). = Т. Тоrда если обозначить че-
рез tN (Р) = t (р, Т) макси;мум функции дохода, то мы
получим известным способом
'(р, Т) = шах [g (р, q) + f (р + S(p, q) d, Т - .1)]. (9.3)
q
48 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ rrЛ.II
Разложив правую часть в ряд по степеням и переходя
к пределу при Д. -+ О, мы получим формально дифферен-
циальное уравнение в частных производных
: =max[g(p, q) + (gradj, S(p, q))] (9.4)
q
с начальным условием f (р, О) = о. Мы проиллюстрируем
этот метод в следующем разделе в связи с некоторыми за-
дачами вариационноrо исчисления. В рассуждениях, при
помощи которых получено уравнение (9.4), имеется ряд
моментов, требующих cTpororo обоснования, которое
может быть получено несколькими различными путями,
требующими, однако, достаточной изобретательности и ана-
литическоrо мастерства.
10. Вариационное исчиспение
Наиболее интересный и значительный пример пепре-
рывноrо MHorome.roBoro процесса принятия решения дает
вариационное исчисление. Рассмотрим задачу о мак-
симизации интеrрала
т
J (и) = g (и, и') dt
о
(10.1)
по всем функциям и (t), определенным на интервале
[О, TJ, дЛЯ которых интеrрал существует и удовлетворяет
начальному условию и (О) = с. Поступая формально и
предполаrая, что все условия для существования макси-
мума удовлетворены, введем функцию
f (с, Т) == шах J (и).
u
(10.2)
в момент времени t переменная состояния с = и (t),
а оставшееся для процесса время составляет Т - t. Реше-
ние должно содержать выбор направления, т. е. значения
и' (t). Предположим, что мы имеем дело с достаточно
rладкими процессами, ДJIЯ которых существует вторая
производная от и (t); тоrда выбор и' (t) определяет и (t)
па беС:J\овеЧIiО малом интервале [tt t + 11].
10]
ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ
49
Рассмотрим теперь задачу об определении начальноrо
наклона и' (О), который мы обозначим через v (рис. 2.1).
Записав
т т
= +
о о
(10.3)
и производя аппроксимацию
g (и, и') dt = g (с, v) /),. + -о (/),.),
о
(10.4)
мы видим, что принцип оптимальности дает соотношение
I (с, Т) = шах [g (с, v) Ll + I (с + vLl, Т - Ll)] + о ( ). (10.5)
ti
Разложив правую часть в ряд по степеням
к пределу при О, мы
получим дифференциаль- и
ное уравнение в частных
производных
и переходя
lJ(d)=c+uJJ
д! [ д! ]
дТ = т:х g (с, v) +vaё '
(10.6)
о
I
.d
т
rде f (с, О) = о. Это урав-
нение определяет как максимальное значение интеr-
рала, так и функцию стратеrии V = V (с, Т).
Отметим, что эта задача с начальным значением, тоrда
как обычная постановка задачи приводит к уравнению
Эйлера
Рис. 2.1.
ag d ( a g )
аи- dt ди' == О,
(10.7)
т. е. к двухточечной краевой задаче. Решение (или реше-
ни:я) определяется начальным условием и (О) = с и усло-
в:ием
.3.L/ = о
ди' 1=7' ·
(10.8)
50 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [rл. 11
Рассмотрим теперь случай, коrда наложено оrраниче-
ние на скорость изменения и, а именно
'и' (t) 1< k,
0< t < Т.
(10.9)
Это вводит MHoro усложнений при классической постанов-
ке задачи. Что касается метода динамическоrо проrрамми-
рования, то здесь достаточно заменить (10.6) соотношением
д! [ д! ]
дТ == шах g (с, v) + v т '
Jvl k с
f (с, О) = о.
(10.10)
Как мы указывали в rлаве 111, наложение оrраничений
этоrо типа существенно упрощает отыскание численноrо
решения.
Упражнения
то
т
1. ПОRажите, что если f(c, T)=m n )[U 2 +v 2 ]dt, rде
о
и' = аи + lD (ш = w (t), и (О) = с t
t T == min [с 2 + V'! + (ас + v) fc], f (с, 0)= О
v
и, таRИМ образом,
f T =C 2 +ac!c- i: ·
2. ПОRажите, что f (с, Т) = c 2 g (Т), rде
g' (Т) = 1 + 2ag (Т) - g2 (Т), g (О) = о.
Определите f (с, Т) и v (с, Т) явно и найдите их асимптотическое по-
ведение при Т -+ 00. Проверьте решение, используя уравнение Эй.
лера.
3. ПОRажите, что задача максимизации
т
J(u)= g(и, и', t)dt, и(а)=с
..
а
приводит R нелинейному дифференциальному уравнению с частными
производными
- =mах[g(Сtv,а)+v J t f(T,c)=O
да v дс
для функции f (а, с) = шах J (и).
и
1 {]
rЕОМЕТРИЧЕСНИЕ АСПЕНТЫ
51
4. Покажите, что задача максимизации
т
J (и) = g (и, Р) dt .
о
по v, rде dи/dt = h (и, v), и (О) = С, приводит К уравнению
..!.L = шах [g (с, v) + h (с, v)!.LJ.
дТ v дс
5. Рассмотрите задачу максимизации
т
J (и) = g (и, Р) dt
о
т
по Р, rде dи/dt=h(и, р), и(О)=с и k(и, v)dt,a, двумя
о
способами: во-первых, принимая а в качестве переменной сос-
тояния, во-вторых, используя множители Лаrранжа. Получите
связь между этими двумя подходами (см. S. D r е у f u s, Dynamic
Programming and the Calculus of Variations, J. Math. Anal. Appl.,
уоl. 1, 1960, рр_ 228-239).
6. Получите уравнение в частных производных для наимепьmе-
ro хараRтеристическоrо числа в задаче и" + л<р (t) и = О, и (О) = О,
и (а) = О, рассматривая соответствующую вариационную задачу
а
мииимизации (и')2 dt при УСЛОВИIIХ
О
а
<р (е) и 2d t = {; и (а) = с, и (О) = О.
о
11. rеометрические аспекты
Поучительно сравнить метод динамическоrо проrрамми-
рования с классическим методом в применении к изло-
женной выше вариационной задаче. В классическом ме-
тоде ищется кривая и = и (t), которая определена на
заданном :интервале [О, Т] и доставляет максимум функ-
ционалу. Неизвестная функция и рассматривается как
Точка в пространстве функций. В нашем подходе в каж-
дой точке мы ищем направление, которое является опти-
мальным; решение получается в виде стратеrии, системы
:инструкций для выполнения процесса.
52 м1l0rошАrовыIE nРОЦЕССЫ nрйнятиа РЕШЕНИЙ [rл. 11
в rеометрическом изложении мы можем сказать, что
с классической точки зрения кривая есть rеометрическое
:место точек, в то время как динамическое проrраммиро-
вание рассматривает кривую как оrибающую касатель-
ных (рис. 2.2). Следо-
вательно, обе теории
", -.. ........ двойственны относи-
тельно друr друrа, факт,
который проявляется
О т постоянно. Эта двойст-
AUHONUll8CKOB венность и эквивалент-
l1f!0ap l1MNllp08dHoe ность имеют, однако,
силу лишь для детерми-
нированных процессов.
Из этоrо следует, что совместное применение обоих ме-
тодов будет более мощным и rлубrRе проникающим, чем
использование одноrо или друrоrо метода по отдельности.
Это справедливо как для аналитических, так и для вычи-
слительных проблем, rде в обеих областях дуальные ме-
тоды иrрают фундаментальную роль.
fL
II
о
Клосси'lеекuu
поОко"
r
Рис. 2.2.
11. Стохастический мноrошаrовый процесс
принятия решения
"Учтем теперь стохастические эффекты, но оrраничим-
ся обсуждением лишь процессов дискретноrо типа, чтобы
сохранить умеренный математический уровень. Для це-
лей иллюстрации достаточно взять преобразование, имею-
щее вид Т = Т (р, q, т), и предположить, что мы желаем
максимизировать математическое ожидание; оно не обя-
зательно должно быть самой функцией дохода, а может
быть средним какой-либо функции от функции дохода.
"Упражнения будут содержать несколько примеров та-
Koro рода.
Предположим, мы желаем максимизировать математи-
ческое ожидание случайной величины
N
g (Pk, Q1i), (12.1)
k=Q
rде Ро = Р и Pk-tl = Т (Pk, Qk, T k ), в предположении, что
1Я]
УПРАВЛЕНИЕ С ОБРАТНОЙ связью
53
' к - независимые случайные переменные с одной и той
же функцией распределения dG (Т). Как и выше, пусть
fN (р) обозначает максимальное значение. Тоrда
10 (р) = maxg (р, qo),
q()
(12.2)
и для N > 1 мы получаем, применяя принцип оптималь-
ности,
f N (Р) = шах [g (р, qo) + fN-l (Т (р, qo, r o » dG (ro)]. (!2.3)
qo
Важно отметить, что как детерминированный, так и
стохастический процессы припят:ия решения :изучаются
при помощи одноrо :и Toro же формализма, а также то, что
метод функциональноrо уравнения манипулирует с мно-
rошаrовыми процессами принятия решений так же, как
с мноrоmаrовыми процессами друrих типов.
13. Управпение с обратной связыо
Существенно установ:ить точную структуру процесса,
рассматриваемоrо нами. Пусть мы наблюдаем, что систе-
ма наход:ится в llоложени:и р; мы выбираем qo, тоrда ' о
определяется по функци:и распределения dG (Т); наконец,
тем самым порождается и наблюдается Рl = Т (р, qo, То).
Зная новое состояние, выбираем ql; затем выбираем ' 1
по функции распределения dG (Т) и т. д. Это - основная
концепция управления с обратной связью.
В детерминированном случае последовательный выбор
qh" как описано выше, или одновременный выбор
всех q , как в обычной формулировке, является вопросом
аналитическоrо или вычислительноrо удобства. Маl{СИ-
мум дохода и оптимальная стратеrия будут теми же са-
мыми. Эта случайная эквивалентность (дуальность евк-
лидовой rеометрии в частных случаях; см. раздел 11)
делает, к сожалению, неясным различие между этими
совершенно разными типами оптимизации. Отметим в свя-
зи с этим, что в детерминированном случае аспекты уп-
равления с обратной связью MoryT быть иrнорированы,
если применить адекватную математическую теорию
54 мноrОШАrОВЫЕ процЕссы ПРИНЯТИЯ РЕШЕНИй [fЛ. 11
общих мноrошаrовых процессов принятия решений для
соответствующих моментов времени.
В стохастическом случае эти два подхода соответст-
вуют совсем различным процессам, занимающим крайние
места в не которой совокупности процессов. В рассмот-
ренном выше случае мы предполаrаем, что состояние
системы на каждом шаrе доступно наблюдению. С друrой
стороны, если мы не можем наблюдать состояния системы
после начала процесса, то мы вынуждены выбирать век-
торы qo, Ql,...,QN вначале и максимизировать функцию
ехр R относительно этих векторов.
r
Мы видим, что управление с обратной связью вклю-
чает в себя выбор функций {Qk (р)}, т. е. функций стра-
теrии. Следовательно, это более высокая ступень, чем
обычная максимизация по векторам q i. Тем не менее она
более доступна как для аналитических, так и для числен-
ных методов.
"Укажем, наконец, что можно породить бесконечный
класс стохастических процессов управления, варьируя
типы информации о состоянии процесса, которые задаются
при принятии решения. Как было указано выше, мноrие
из них индуцируют бесконечномерные процессы принятия
решения, rде состояние есть распределение вероятностей.
14. Анаnиз уравнений
Rоrда различные классы процессов принятия решения
сформулированы в точных аналитических терминах, мы
сталкиваемся с задачей получения полезной информации
из уравнений. В частности, мы можем задать следующие
вопросы:
1. Для каких классов процессов можно получить про-
стые аналитические выражения для функций дохода и
стратеrии?
2. При каких условиях можно получить структурную
характеристику оптимальной стратеrии?
За. Rоrда можно получить решение при помощи циф-
ровой вычислительной машины?
зь. При каком условии можно найти простую асимп-
тотику для установивmейся стратеrии и функции дохода?
15]
ПОСЛЕДОВАТЕЛЬНЫЕ ПРИБЛИЖЕНИЯ
55
Так как в этих направлениях предстоит еще MHoro
сделать, то подробные ответы на некоторые из этих воп-
росов далеко уведут нас от нашеrо намерения дать лишь
вводное изложение. Мы, однако, сделаем несколько ссы-
лок в упражнениях и в библиоrрафии в :конце rлавы. Кро-
ме Toro, мы сделали ниже несколько более общих замеча-
ний и рассмотрим некоторое количество ваiI\НЫХ специ-
альных процессов в rлавах IV и V.
15. ПоспеДОS8тепьные прибпнження
Так как мы имеем дело rлавным образом с конечно-
mаrовыми процессами, то большинство функциональных
уравнений берется в виде нелинейноrо peKyppeHTHoro
соотношения
!N (р) == шах [g (р, q) + !N-l (Т (р, q)], N>1, (15.1)
q
тде 10 (р) = тах g (р, q) или, во всяком случае, известная
q
функция. Из этоrо следует, что никаких вопросов суще-
ствования или единственности последовательности Функ-
.а;:ий дохода {In (р)} при рассмотрении уравнений этоrо
типа не возникает. Задавая 10' мы определяем 11, затем
12 и т. д.
Если мы рассмотрим, в :качестве приближения к
решению (15.1) для случая, котда N > 1, случай беско-
печноrо числа шаrов, мы получим уравнение
! (р) = тах [g (р, q) + f(T (р, q»],
q
(15.2)
которое естественно возникает при рассмотрении различ-
ных обобщенных траекторий и процессов управления.
Классический метод построения решения уравнения это о
типа, при соответствующих rипотезах относительно функ-
ций g (р, q) и Т (р, q), базируется на методе последова-
тельных приближений. Это обычно выполняется следую-
щим образом. Мы выбираем начальное приближение lo(p)
и затем продолжаем рекуррентно определять последующие
56 мноrоmАrОВЫЕ ПРОЦЕССЫ ПРИНЛТИЛ РЕШЕНИЙ [rл. 11
приближения к 1 (р)
1
/nн (Р) = шах [g (р, q) + fn (Т (р, q))). 1
q J
/1 (р) = шах [g (р, q) + 10 (Т (р, q)],
q
(15.3)
Во мноrих процессах нетрудно установить сходимость
последовательности {/n (р)} к решению (15.2). Детали
этих доказательств при различных предположениях MoryT
быть найдены в работах, ссылки на которые даны в кон-
це этой rлавы.
16. Прибnижение в пространстве стратеrиА
В теории динамическоrо проrраммирования мы рас-
полаrаем еще одним типом аппроксимации - аппрокси-
мацией в пространстве стратеrий. Как было указано в
разделе 8, функциональное уравнение вида (15.2) опреде-
ляет две функции: функцию дохода / (р) и функцию стра-
теrии q (р). Тот факт, что каждая из них определяет дру-
rую, есть ключ к обсуждаемому здесь методу.
Начнем с приближения q (р) функцией qo (р). Затем
определим lo{p) при помощи уравнения
10 (р) = g (р, qo) + / (Т (р, qo)) =
= g (р, qo) + g (Т(р, qo), qo') +..., (16.1)
rде qo' = qo (Т (р, qo), и т. д. Друrими словами, 10 (р)
есть полный доход, получаемый при применении страте-
rии qo (р). Усовершенствуем эту стратеrию, опреде-
лив функцию ql (р), которая максимизирует g (р, q) +
+ 10 (Т (р, q»), и затем определим 11 (р) при помощи урав-
нения
11 (р) = g (р, ql) + /1 (Т (р, ql».
(16.2)
Так как ql = ql (р), то можно написать
11 (р) = g (р) + 11 (h (р»,
(16.3)
17]
НВА3ИЛИНЕАРИ3АЦИЯ
57
rде g и h - известные функции, h (р) = т (р, ql (р)). При
правдоподобных предположениях. относительно этих функ-
ций мы можем найти 11 (р) меТОДОl\1 :итераций. Таким об-
разом,
11 (р) = g (р) + g (h (р)) + g (h(2)(p)) + ...
(16.4)
Иными словами, 11 (р) получено при стратеrии ql (р). Так
как
10 (р) = g (р, qo) 10+ (1' (р, qo)) <
< шах [g (р, q) + 10 (Т (р, q»] = g (р, ql) + 10 (Т (р, ql»,
q
(16.5)
то мы видим, что
10 (р) < g (р) + 10 (h (р» < g (р) + g (h(p) +
+ g (h(2) (р)) + ... (16.6)
Следовательно, снова при разумных условиях можно по-
казать, что 10 (р) < 11 (р). Продолжая таким образом, мы
получаем новую стратеrию q2 (р) для функции 11 (р) И
далее по индукции - последовательность {/n (р)} при-
ближений к 1 (р), которая монотонно возрастает при уве-
личении п, 11 < 12 < ... < In < 1.
Одно из преимуществ этоrо метода состоит в том, что
во мноrих процессах существуют интуитивные последо-
вательные приближения в пространстве стратеrий, кото-
рые MoryT быть леrко использованы. К тому же (и это
на:иболее важно), в том, что касается применений, описан-
ная процедура дает систематический аппарат для улучше-
ния существующих стратеrий.
17. Квазипинеаризация
Одним из важных применений этой идеи последователь-
ных приближений в пространстве стратеrий является
теорuя liвааuлunеарuаацuu. Мы начнем с уравнения вида
L (/ (р» = N (/ (р»),
(17.1)
rде L - линейный оператор, а N - нелинейный оператор,
и попытаемся преобразовать это уравнение к виду (15.2).
Для этоrо выразим правую часть в виде максимума.
58 мноrошАrовыE ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [rл. II
Предположим для простоты, что N (и) есть скалярная ФУНК-
ция. которая выпукла по и. Тотда, как леrко в:идеть либо
rеометрически, либо аналитически,
iV (и) == шах [1У (v) + (и - и) N' (v)].
v
(17.2)
Следовательно, (17.1) можно записать так:
TJ (t) == шах [1У (q) + (! - q) N' (q)] .
q
Это уравнение выrлядит так, как если бы оно было свя-
зано с MHoromaroBblM процессом принятия решений, и с
ним можно оперировать так, как будто оно действительно
описывает такой процесс. Применяя последовательные
приближения в пространстве стратеrий, зачастую можно
получить очень быстро сходящиеся последовательные
приближения к решению (17.1). Имеется MHoro важных
приложений этоrо аппарата, описанных в ряде источни-
ков, ссылки на которые даны в конце rлавы.
(17.3)
18. Анаnитичееиие н вычнеnитеnьные пробnемы
Мотут ли уравнения, выведенные на предыдущих стра-
ницах, быть использованы для получения аналитичеСIiИХ
и численных результатов? Ответ будет положительным
((да»). Как обычно в математических теориях, он зависит
от задачи. В rлаве IV мы рассмотрим несколько важных
типов процессов, rде может быть достиrнуто вполне удов-
летворительное аналитическое продвижение. В rлаве 111
мы обсудим вычислительный аппарат, который позволит
нам иметь дело с общими классами процессов дипамиче-
cKoro проrраммирования в условиях применения новей-
ших вычислительных машин.
Как мы увидим в дальнейшем, нет ничеrо установив-
шеrося в применении цифровых вычислИтельных машин
для получения численных решений. Здесь требуется мно-
то аналитическоrо мастерства и изобретательности и rлав-
ным образом требуется большое понимание как научной
сути задачи, так и математическоrо аппарата. Лишь тотда,
котда мы имеем алrоритм для получения численных ре-
зультатов, можно считать, что задача полностью решена.
19]
ПРИНЦИП ФЕРМА И УРАВНЕНИЕ ЭйНОНАЛА
59
19. ПРИНЦИП Ферма и уравнение эйконапа
в :качестве интереспоrо применения у:казанных выше
идей рассмотрим задачу о распространении света в неод-
нородной двумерной среде. Наша цель - по:казать, что
применением принципа оптимальности в соединении с
принципом наименьшеrо времени Ферма можно простым
и непосредственным способом получить основное уравне-
ние rеометрической оптики, уравнение эйконала.
Предположим, что среда характеризуется показателем
преломления, который является функцией положения
п == п (х, у). Тоrда, если мы полоя{им
с
V(X'Y)== п(X,y) ,
(19.1)
то v будет с:коростью света в точке (х, у), rде с - скорость
света в вакууме. Соrласпо принципу Ферма при переходе
в среде от одной точки (х, у) к друrой точке (хо, уо) луч
света выбирает путь, соответствующий наименьшему вре-
мени. Обозначим время, которое затрачивает частица
света при переходе от точки (х, у) :к фиксированной точ:ке
(х о , уо) в соответствии с вышеприведенным принципом,
через t (х, у). Если частица покидает точку (х, у) и пере-
мещается вдоль линии, составляющей уrол е с осью х,
на расстояние , то она придет в_ точку (х + cos е,
У+ sin 8) по истечении времени l1./v (х, у) (мы пренебрEr
raeM членами BToporo И высших порядков относительно ).
Отсюда следует, что
t (х, у) = in { v ( ,y) + t (х + Ll cos8, у + Ll sin8) + о (Ll)}.
(19.2)
Из этоrо мы видим, что
O=min{ /' ) + L\txcos8+L\tllsine + о (Ll)}, (19.3)
. v Х, у
откуда, разделив на L1 и устремляя l1 к нулю, получим
- v- 1 (х, у) = min {t x cos 8 + t y sin 8}.
8
(19.4)
60 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [rл. 11
Это - новый вид уравнения эйконала. Значение 8, кото-
рое минимизирует выражение в скобках в полученном
выше уравнении, есть решение уравнения
-txsin 8 + t y cos 8 == О
(19.5)
или
t
tg 8 = -.1L
t ·
х
(19.6 )
Подставляя это значение 8 в уравнение (19.4), мы полу-
чаем желаемый результат
t 2 + t 2 -2
х y=V,
(19.7)
который может быть записан в виде
2 2 п 2 (ху)
t x + t y = с 2 .
(19.8)
Уравнение (19.8) есть уравнение эйконала Отметим те-
перь, что если возмущение начинается в точке (х о , уо)
в момент вре:м:ени, равный нулю, то время Т распростра-
нения волновоrо фронта этоrо возмущения
т == t (х, у). (19.9)
Наклон пути, проходящеrо через точку (х, у), есть t'l//t x
соrласно уравнению (19.6), и наклон волновоrо фронта
есть - tx/t y . Это показывает, что лучи и волновые фронты
ортоrональны в рассматриваемом случае.
Упражнения
1. Рассмотрите случай веоднородной и анизотропной среды, для
которой п = п (х, у, у'). в частности, найдите связь между лучами
и волновыми фровтами.
2. Найдите уравнения для лучей в изотропном случае.
3& Исследуйте случай, в котором n (х, у) = у. Покажите, что
лучи являются дуrами окружностей с центрами на оси х.
4. Обсудите концепцию последовательных приближений в про-
странстве стратеrий в применении R уравнению (19.4), альтернатив-
ному виду уравнения эйконала.
5. Принцип rюйrенса вторичных не больших волн дает мощный
метод для исследования уравнения эйконала. Сформулируйте прин-
ЦИП и примените ero к уравнению (19.4) (см. обсуждение этоrо вопро-
са в книrе: с. Л а н Ц о ш, Вариационные принципы механики, rл.
VIII и книrу r ю й r е н с а, Распространение света).
20]
НАИНРАТЧАЙШИЕ ПУТИ ЧЕРЕЗ СЕТИ
61
20. Наикратчайwие пути через сети
Рассмотрим сеть, СОСТОЯЩУIО из N узлов, занумерован-
ных 1, 2, ..., N, и взаимосвязанных звеньев. Пусть время,
которое занимает про хождение звена (i, j), будет tij > о.
в частности, отметим, что t ij не обязательно должно быть
равным tji. Мы желаем определить путь через сеть, кото-
рый соединяет два заданных узла, полное время прохож-
дения по которому по крайней мере не больше, чем для
любоrо друrоrо пути, соединяющеrо заданные узлы. Яс-
но, что эта задача имеет важное значение при выборе
маршрутов самолетов и автомобилей по транспортным
сетям и при передаче сообщений по сетям связи. Помимо
Toro, эти вопросы важны при изучении оптимальных
по быстродействию систем управления с обратной связью.
lIтобы по казать это, мы интерпретируем N узлов как
возможные состояния системы, а звенья - как преобра-
зования от одноrо состояния к друrому. Часто мы хотим
перевести систему из заданноrо начальноrо состояния в
желаемое состояние за минимальное время. Эта задача
может быть также рассмотрена как дискретная версия
оптической задачи, содержащей принцип Ферма, рассмот-
ренной в разделе 19. Наконец, интерпретируя числа tij
как топливо или любые друrие расходуемые ресурсы,
можно рассматривать нашу задачу как задачу перевода
системы из заданноrо начальноrо состояния в требуемое
Конечное состояние наиболее эффективным образом,
в смысле затрат ресурсов.
Будем рассматривать узел N как желаемый для конца
заданноrо интервала времени узел, и введем величины
U i = время перевода системь1, из uачалъпО20 состояния i
в желаемое состояние N вдоль 1hратчайшеео пути
i = 1, 2, ..., N. (20.1 )
МЫ положим
UN == о. (20.2)
Применяя принцип оптимальности, получим основную
систему нелинейных алrебраических уравнений
U i == in (tij + из), i == 1, 2, ... , N - 1, }
J=I=1.
UN = о.
(20.3)
62 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИй [rл. 11
Они MoryT рассматриваться как дискретная форма урав-
нения эйконала (см. раздел 19). В противоположность
мноrим друrим системам уравнений, полученным из прин-
дипа оптимальности, никакой последовательный метод
определения неизвестных здесь непосредственно не ус-
матривается. Следовательно, мы должны применить ме-
тод последовательных приближений. Сначала установим
единственность решения уравнений (20.3) для Toro, чтобы
получить уверенность, что последовательность, которая
сходится к решению, сходится к искомому нами решению,.
т. е. определяет желаемый минимальный промежуток
времени. Заметим, однако, что, в то время как величины
и 1 , и 2 , ..., UN определяются однозначно, пути, при прохож-
дении вдоль RОТОрЫХ эти значения достиrаются, MoryT
быть не единственными.
Пусть и 1 , и 2 , ..., UN И и 1 , и 2 , ..., U N - два различных
решения системы (20.3). Пусть т есть индекс, для кото-
poro разность U j - и j, j = 1, 2, ..., N, есть максимум.
Мы хотим показать, что этот максимум разности равен
нулю. Пусть
U т = t тn + U n -< t тr + и т ,
и т = t тr + и т .
Из этоrо следует, что
и т - и т < и т - и т , (20.6)
и так как т есть индекс, для KOToporo равность U т - и т
есть максимум, то знак равенства должен быть удержан
как в (20.6), так и в (20.4). Нроме Toro, ясно, что
т =1= r . (20. 7)
(20.4)
(20.5)
Подобным же образом мы можем найти узел s, rде
s =!= т, s =!= r, (20.8)
для KOToporo
и т - и т = U r - U r == ив - UЗ. (20.9)
В Rонце концов, так как имеется лишь конечное число
узлов, МЫ должны подойти к узлу N, дЛЯ KOToporo
и N - uN = о. (20.10)
20]
НАИНРАТЧАЙШИЕ ПУТИ ЧЕРЕЗ СЕТИ
63
Этим заканчивается доказательство единственности. Вер-
немся теперь к отысканию численноrо решения путем при-
менения приближений в пространстве стратеrий. Одно-
временно мы установим как существование решения сис-
темы (20.3), так и эффективный способ для вычисления
решения.
В качестве исходноrо приближения и O), i = 1,2, ...
...,N, положим
и O) == t i N , i = 1, 2, ... , N, t N N == о,
(20.f1)
что соответствует стратеrии перевода систеl\'IЫ непосред-
ственно из ее начальноrо состояния в желаемое конечное
состояние. Если не имеется никакоrо звена от i к N, так
что tiN == 00, то мы положим tiN == 1030 или какому-ни-
будь друrому подходящему большому числу. Этот про-
стой прием устраняет трудные тополоrические вопросы
связности. Следующее приближение получим из формулы
и l) == min {t ij + и O)}, i == 1, 21 ... ,N -1, (20.12)
J:;ei
u ) == о. (20.13)
Операции, указанные в формуле (20.12) быстро выпол-
няются вычислительно. Значения одной строки матрицы
(tij) требуются в качестве значений исходноrо приближе.
ния и O), j == 1,2, ..., N. Минимизация делается путем не-
посредственноrо сравнения встречающихся сумм, одной
за друrой. Таким образом, как время вычисления, так и
требования к быстродействию памяти невелики. Мы пе-
реходим от k-ro к (k + 1)-му приближению при помощи
СОотношений
и k+l) = min {tij + и K)},
j:;ei
и +l) = о.
i = 1, 2, ... , N - 1, (20.14)
(20.15)
Формулы (20.12) - (20.15) имеют простую физическую
Интерпретацию. Величина и O) соответствует минималь-
ному времени перехода от узла i к узлу N без промежу-
Точных узлов. Величина и l) есть минимальное время
64 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [rл. 11
перехода от узла i к узлу N при наличии не более одноrо
промежуточноrо узла. Аналоrично u\К) есть МИНИ:l\Iальное
время перехода от узла i к узлу N при наличии не более
k промежуточных узлов. Из этой физической интерпрета-
ции мы видим, что последовательные приближения мопо-
тонно убывают, т. е.
О" uf k -fl) " и K), i == 1,2, ..., N. (20.16)
Это иллюстрация эффективности метода приближе-
ний в пространстве стратеrий. Отметим, кроме Toro, что
эта процедура аппроксимации конечна по своему сущест-
ву. Так как оптимальный путь от i к N не может
иметь никаких петель, он может содержать не более
N - 2 промежуточных узла. Из этоrо следует, что
величины u N-2), i == 1,2,..., N - 1, должны удовлетво-
рять уравнениям (20.3), что означает, что мы будем иметь
не более N - 2 итераций.
Для определения оптимальной траектории из KaKoro-
нибудь начальноrо состояния в любое конечное состояние
можно применить только что рассмотренный метод N раз.
Иначе rоворя, мы можем ввести величины
u J) == м,unu:мальnое время перехода cucmeMbl из состояnuя
i в состояnuе j, uспользуя путь с nе более чем k-промежу-
точnы.ми состояnuямu. (20.17)
Из принципа оптимальности следуют уравнения
K+l) _ . {t.. + (Д)} k - О 1 2 N 3
и т - m ln 3 и}т, -", ..., -.
1:j6i
(20.18)
Для вычислительных целей, возможно, выrоднее продви-
rаться вперед при помощи формулы
и 1K+п == min{ul + и },
j*i
(20.19)
которая позволяет определить последовательность матриц
( (п» ( (' » (3» ( (7» ( (15»
Uij , Uij , (ин , Uij , Uij ,...
в различных случаях бывает желательно определить
предпочтительные субоптимальные пути. Покажем, как
20]
БИБлиоrРL\ФИЯ и НО\1:МЕН rлрии
65
определить второй наикратчайmий путь. Пусть
v == длиnа второао l-lаuкратчайшеео пути от i до N,
z
== 1, 2,..., N. (20.20)
Мы отметим, что если мы сперва проходим из положения
i в положение j, то переход ИЗ положепия j в конечное
положение N должен быть наикратчайшим путем, или
вторым наикратчайшим путем. Применяя обозначение
IпiП 2 (а 1 , а 2 ,..., al ) == вп opo:мy nаUJпеnъшеJпУ UЗ а 1 , а 2 ,..
..., a, в предпОЛОJlCеnuu, что 0ии nе все paenbL, (20.21)
l\IЫ мо}нем написать
и 1 == ln in 2 (! 1] t- из, t 11 + vз),
VN -=- о.
i = 1,2, ..., N -1, }<20.22)
Предполаrая, что U z уже определены, мы можем исполь-
зовать вышеприведенную процедуру для определения vz.
Упражнения
1. Пусть число узлов сети будет N == 3, 4 и 5 и пусть t zj == i + j.
I-Iайдите наикратчайший путь от узла 1 к узлу N в каждом случае.
2. Во мноrих ситуациях только небольшое число из всех возмож
ных звеньев будет в наличии. Как видоизменяет этот факт полуqен
ные выше уравнения?
3. Предположим, что мы хотим прийти от i к N таким образом,
чтобы наибольшее из чисел t ZJ на звеньях, вдоль которых мы путеше-
ствуем, было как можно меньше. Попажите, что это приводит К фунп-
Циональным уравнениям
81 == minmax (t ц , 8 з ), i == 1,2, ..., N -1,
з#:
SN -= о.
&иБJШоrрафнSI и комментарии
1. Подробное изложение теории и приложений ДIlнамическоrо
проrраммированил дано в книrах:
Р. Б е л л м С\ н, Динамическое проrраммирование, ИЛ,
1960.
Р. Беллман и с. Дрейфус, Прикладные задачи
динамцческоrо проrраммирования, «Наука», 1965.
Р. Б е л л м а н, Процессы реrулирования с адаптацией,
ИЛ, 1964.
66 мноrОШАrОВЫЕ ПРОЦЕССЫ ПРИНЯТИЯ РЕШЕНИЙ [rл. 11
R. А r i s, Discrete Dynamic Programming, An Introduction
to the Optimization of Staged Processes, Blaisdell Publishing
Company, New York, 1964.
С. М. Р о б е р т с, Динамическое проrраммирование в про-
цессах химической технолоrии и методы управления, М., 1965.
К. А r r о w, S. к а r 1 i n and Н. S с а r f, Studies in the
Mathematical Theory of Inventory and Production, Stanford
Univ. Press, Stanford, California, 1958.
Р. Х о в а р д, Динамическое проrраммировавие и марков-
ские процессы, «Советское радио», 1964.
8. Дальнейшее обсуждение этих идей
R. В е 11т а n and Р. в r о с k.. Оп the Concepts of а Prob-
lет and Problem-solving, Amer. Math. Month1y, уоl. 67, 1960,
рр. 119-134.
Э 10. Для дальнейшеrо обсуждения связи между динамическим про-
rраммированием и вариационным исчислением предлаrаем
S. D r е у f u s, Dynamic Programming and the Calculus of
Variations, :r. Math. Anal. Аррl., уоl., 1, 1960, рр. 228-239.
S. D r е у f u s, Variational Problems with Constraints, J.
Math. Anal. Appl., уоl. 4, 1962, рр. 297-308.
L. В е r k о v j t z, Variational Methods in Problems of Cont-
rol and Programming, J. Math. Anal. Appl., vol. 3, 1961, рр.
145-169.
О связи между принципом максимума и динамическим проrрамми-
ровапием
С. D е s о е r, Pontriagin's Maximum Principle and the Prin-
ciple о! Optimality, J. Frank1in Institute, уоl. 271, 1961, рр.
361-367.
Л. Роз о н о э Р, Принцип максимума Л. с. Понтряrина в
теории оптимальных систем, «Автоматика и телемеханика»,
т. ХХ, М 10, 11, 12, 1960.
Обсуждение взаимной связи между динамическим проrраммирова-
нием принципом Ферма и некторыми идеями Паскаля приведено в
, R. F о r t е t, Remarques sur lа Programmation Dynamique,
Апп. de la Faculte des Sciences de l' Universite de Clermont.,
уоl. 2, 1962, рр. 41-51.
[CTporoe математическое обоснование метода )Jинамическоrо
проrраммирования для случая дифференциальных уравнений сде-
лано в статье
Б о л т я н с к и й В. r., Достаточные условия оптимально-
сти и обоснование метода динамическоrо проrраммирования,
Изв. АН СССР, серия матем., т. 28, 1964, стр. 481-514,
а также в квиrе
БОJIТЯНСКИЙ В. r., Математические методы оптималь-
ното УIJравления, изд. 2-е, «Наука», 1969. (Прu-м. перев.)]
Э 12. Рекомендуем
В. В е 11 m а п, Оп the Foundations о! а Theory of Stochastic
Variational Processes, Proc. Tenth Symposium in Applied Ма-
thematics, Amer. Math. Soc., Providence, Rhode Island, 1961.
БИБлиоrРАФИЯ и НОММЕНТАРИИ
67
Исследование стохастических процессов непрерывноrо типа см.
Н. 1. К u s h n е r, Оп Stochastic Extremum Problems:
Calculus, 1. Math., Anal. Appl., in press.
Н 1. К u s h n е r and F. С. S с h 'v е р р е, А. Махimпm
Principle for Stochastic Control Systems, J. Math. Апаl. Appl.,
in press.
13. Историю концепции управления с обратной связью см.
R. В е 11 m а n and R. К а 1 а Ь а (eds.), Selected Papers оп
Mathematical Trends in Control Theory 7 Dover Publications,
New York, 1964
и в частности, статьи Bateman и Bode.
16. Некоторые приложения приближения в пространстве стра-
теrий указаны в цитированных выше книrах Р. Беллмана и С. Дрей-
фуса и Ховарда.
э 17.
R. в е 11 m а n, Functional Equations in the Theory of Dy-
namic Programming - У: Positivity and Quasi-1inearity,
Proc. Nat. Acad. Sci. USA, уоl. 41, 1955, рр. 743-746.
Н. К а 1 а Ь а, Оп Nonlinear Differential Equations the Ма-
ximum Operation, and Monotone Convergence, J. Math. Mech.,
уоl. 8, 1959, рр. 519-574.
R. В е 11 m а n and R. К а 1 а Ь а, Quasilinearization and
N onlinear Boundary-value Problems, American Elsevier Publis-
hing Со., New York, 1965.
Э 19. R. К а 1 а Ь а, Dynamic Programming, Fermat's Principle
and the Eikonal Equation, 1. Opt. Soc. Amer., уоl. 51.. 1961,
рр. 1150-1151.
s 20. R. В е 11 m а n, Оп а Routing Problem, Quart. Аррl. Math.,
уоl. 16, 1958, рр. 87-90.
R. В е 11т а n and R. К а 1 а Ь а, Оп k th Best Policies,
J. Soc. Indust. Appl. Math., vol. 8, 1960, рр. 582-588.
R. К а 1 а Ь а, Graph Theory and Automatic Control, Chapter
8 of Applied Combinatoria1 Mathematics, Е. F. Beckenbach,
ед., :1" ohn W iley & Sons, Inc., N ew York, 1964.
r л а в а 111
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ
1. Введение
В предыдущих двух rлавах мы показали применение
апалитическоrо аппарата теории динамическоrо проrрам-
мирования к изучению общеrо вида мноrошаrовых про-
цессов принятия решений. Вернемся теперь к вопросу о
возможности получения числеНI-Iоrо решения при помощи
этоrо подхода и, в частности, к вопросу получения чис-
ленноrо решения при помощи цифровой вычислительной
машины. Мы подчеркнем здесь лишь несколько наиболее
важных моментов, отсылая интересующеrося читателя к
цруrим работам, в которых можно найти детальное и ис-
черпывающее изложение.
Весьма важный мо:м:ент, значение KOToporo необходи-
мо особенно подчеркнуть, состоит в том, что каждая вы-
числительная процедура должна заключать в себе про-
цесс реrулирования, при котором неизбежные поrреш...
ности, сопровождающие арифметические операции, не
выходили бы из допустимых rраниц. Поэтому аппарат
динамическоrо проrраммирования может быть иСпользо-
ван в численно:м: решении классических ФУНКI иональных
уравнений, обыкновенных дифференциальных уравнений
и дифференциальных уравнений с частными производны-
ми и в численном решении функциональных уравнений
caMoro динамическоrо проrраммирования. Мы дадим нес-
колько указаний относительно TaKoro рода приложений,
не входя, однако, rлубоко в исследование этих идей.
2. Цифровые вычиспитепьные машины
Цифровая вычислительная машина есть устройство
для выполнения арифметических действий, иными слова-
ми, для выполнения четырех фундаментальных операций:
з] РЕШЕНИЕ ПРОЦЕССОВ ДИНАМIIЧЕСRоrо проrРАММИРОВАНИН 69
сложения, вычитания, умножения и деления. Ее выдаю-
щееся положение в современной науке является следст-
вием Toro факта, что в отличие от человека она может
выполнять эти действия точно и чрезвычайно быстро. В
настоящее время два десятка чисел MoryT быть умножены
друr на друrа в течение одной стотысячной доли секунды.
fлавный недостаток цифровой вычислительной машины
состоит в том, что в отличие от человека каждая задача,
к которой она мо}нет быть применена, должна быть при-
ведена, часто довольно утомительным способом, к после-
довательности арифметических задач.
Отметим, что мы не утверждали, что цифровая вычис-
лительная машина есть «просто» арифметическое устрой-
ство. Способность быстро и точно производить миллиарды
арифметических операций сама по себе rлубоко затраrи-
вали любой аспект современной жизни и философии. 3на-
чительн:ые изменения в количестве предопределяют и
значительные изменения в качестве.
Имеются друrие типы вычислительных устройств, та-
ких как аналоrовые вычислительные устройства, которые
не оrраничены лишь арифметическими действиями. Одна-
ко пока они оrраничены тем, что MoryT быть применены
для рассмотрения лишь специальных классов задач. Эта
ситуация может, однако, измениться в ближайшем буду-
щем. Ниже мы хотим обрисовать пути применения цифро-
вой вычислительной машины к определению оптимальных
стратеrий и функций дохода.
3. Чиепенное решение процеееов динамичееиоrо
проrраммирования
Рассмотрим типичное ренуррентное соотношение
!N (р)== шах [h (р, q) + !N-l (Т (р, q»], N > 1, (3.1)
q
с заданной функцией 10 (р). Для Toro чтобы рекуррентно
вычислить как функцию дохода, так и функцию страте-
rии, мы поступим следующим образом. Рассмотрим урав-
нение для /1 (р),
/1 (р) == шах [h (р, q) + /0 (Т (р, q»]. (3.2)
q
70
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕНТЫ
Lrл. 111
Для TOrO чтобы подсчитать значения 11 (р), необходи-
мо иметь значения h (р, q), т (р, q) и 10 (р) в запоминаю-
щем устройстве машины или иметь алrоритмы для обра-
зования этих значений. Предположим на минуту, что
МЫ только запомнили эти значения. ВпослеДСТВllИ мы об-
судим более сложный подход.
Так как невозможно запомнить все значения 10 (р),
если р принимает значения из бесконечной последователь-
ности чисел, и весьма трудно это сделать, даже если число
членов этой последовательности конечно, но велико, мы
запомним лишь дискретный набор зна чений {I о (р i) },
i == 1,2,..., М. Друrие значения 10 (р) будут получены
при помощи экстраполяции или интерполяции, как пот-
ребуется. Чтобы найти максимум по q в (3.2), мы анало-
rично оrраничим q конечным набором значений {Qj},
j == 1, 2,..., R, и приступим к непосредственному сравне-
нию значений. Мы вычислим выражения l (Рl' q) +
+ 10 (Т (Рl' q» для q = ql, q2"..' qR И выберем q, назовем
ero Q l' которое максимизирует это выражение. Максими-
зация по дискретной системе значений является арифме-
тической операцией, которая может быть выполнена на
цифровой вычислительной машине. Если несколько зна-
чений дают максимум, мы запоминаем их все.
Вышеизложенная процедура определяет 11 (Рl) И
Ql (Рl). Повторяя эту процедуру для I{аждоrо из состоя-
ний р., i == 1,2,..., М, мы получим функцию дохода 11 (р)
l u
И функцию стратеrии ql (р) для этоrо набора состоянии.
Заменяя (3.2) соотношением
12 (р) == max[h (р, q) + /1 (Т(р, q»], (3.3)
q
получим описанным выше путем 12 (р) и q2 (р) снова для
конечноrо набора р == Рl' Р2'...' Рм. Таким образом, ре-
куррентно мы вычислили последовательности {fn (Р)} и
{qn (р)}.
Прежде Bcero отметим, что вышеизложенная процеду-
ра является итеративной. Мы применяем одну и ту же
процедуру на каждом шаrе, чтобы по заданному fn (Р)
вычислить In+l (Р). Следовательно, система вычислительных
инструкций будет относительно небольшой, и ее можно
леrко записать на одном из новых простых вычислитеЛI)-
4]
ПРИБЛИЖЕНИЯ В ПРОСТРАНСТВЕ Ф"УНRЦИЙ
71
ных языков, таких как ФОРТРАН или Алrол. Эта ите-
ративность или периодическая повторяемость весьма важ-
на для применения цифровой вычислительной машины.
Отметим также, что, как только 11 (р) использована для
определения 12 (р) И q2 (р), соrласно (3.3), ее можно сте-
реть из памяти. Для Toro чтобы определить 1з (р) и qз (р),
мы нуждаемся только в 12 (р). Это чрезвычайно важный
факт, ибо, как мы увидим, в настоящее время при отно-
сительной оrраниченности памяти вычислительных машин
возможность применения запоминающеrо устройства с
малым временем выборки является решающей для успеха
динамическоrо проrраммирования.
Наконец, отметим, что если мы имели оrраничения ви-
да q Е S (р), то число возможных значений q, по которым
на каждом шаrе надо вести поиск, уменьшается. Это
уменьшает время вычислений. Следовательно, чем боль-
ше оrраничений на функцию стратеrии, тем леrче приме-
нить аппарат динамическоrо проrраммирования. Это яв-
ляется важным преимуществом аппарата динамическоrо
проrраммирования по сравнению с классическими спо-
собами учета оrраничений.
4. Прибnижения в пространстве функциЯ
Ряд важных процессов приводит к функциональным
уравнениям вида
f (р) == шах [h (р, q) + f (Т (р, q))],
q
(4.1)
как это было показано в rлаве 11. Чтобы примевить для
численноrо решения уравнений этоrо типа процедуру ре-
шения уравнений peKyppeHTHoro типа, изложенную в раз-
деле 3, обратимся к классическому методу последователь-
ных приближений. Полаrая, что 10 (р) представляет собой
начальное приближение, полученное из математических
или физических соображений, рассмотрим последователь-
ность {fn (р)}, порождаемую соотношением
In+l (р)= шах [h (р, q) + tn (1' (Р,) q))], п == 0,1,2,... (4.2)
q
72
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕИТЫ
[rл. 111
Можно показать, что при определенных предполо-
i-кениях относительно функций h (р, q), т (р, q) и t о (р)
эта последоватеJIЬНОСТЬ сходится к решению уравнения
(4.1). Вообще rоворя, те же самые предположения MoryT
быть использованы для установления единственности ре-
шения.
5. Прибnижение в пространстве стратеrий
Возможностью, :которой обладает динамичеСI{ое проr-
раммирование и которая не имеет места в :классическом
анализе, является приближение в пространстве страте-
rии. Как было подчеркнуто выше, функция дохода опре-
деляется оптимальной стратеrией и, наоборот, оптимальная
стратеrия определяется функцией дохода. В предыду-
щем разделе мы следовали классическим путем в приб-
лижении к функции дохода. Еще раз отметим, что мы
можем также применять приближения в пространстве стра-
теrий. Это было обсуждено в разделе 16 rлавы 11 и ил-
люстрируется в разделе 10 этой rлавы. Аналитическая
и вычислительная действенность здесь зависит от rлубины
проникновения в существо изучаемоrо процесса принятия
решений и изобретательности исследователя.
6. 8ычисnитеnьная осуществимость
Исследуем теперь в некоторых деталях алrоритм, дан-
ный в разделе 3. Осуществима ли описанная вычислитель-
ная процедура в настоящее время и даже в будущем, пос-
кольку речь идет о цифРОВЬ1Х вычислительных машинах?
мыt имеем в виду запоминающее устройство с малым вре-
менем выборки объемом в 105 или, самое большее, 106.
Рассмотрим случай, коrда р есть вектор размерности 2
Р == (x J у), так что f (р) == f (х, у). Предположим, что х и
у изменяются в интервалах О -< х, у -< 1 и что мы запо-
минаем: значения f в 100 точках по х и 100 точках по У,
Bcero в 104 точках. Это находится в пределах наших воз-
можностей. Таким образом, для одномерноrо или двумер-
Horo случаев мы в состоянии применить описанную про-
цедуру получения численноrо решения.
7]
АППРОНСИМАЦИЯ ПОЛИНОМАМИ
73
Если размерность вектора р более высокая, например
4, то обычный метод, описанный выше, требует объема
памяти в 108 значений. Таким объемом памяти мы будем
располаrать, по-видимому, лет через двадцать пять *).
Для изучения таких процессов при современных техни-
ческих средствах требуются более тонкие алrоритмы.
7. Аппроксимация попиномами
в большинстве важных приложений динамичеСI\оrо
проrраммирования набор чисел, связываIОЩИХ функцию
f (р) с набором допустимых векторов состояния, определя-
ется не очень просто. Фукция f (р) является функцией,
обладающей структурой, подразумевающей, прежде все-
ro, «rладкость» функции относительно р. Иными словами,
имеется большая корреляция между значениями f (р) для
различных значений р.
Из этоrо следует, что вместо простоrо запоминания
набора значений {! (P i )}, i === 1,2,..., М, блаrоразумнее
хранить в памяти различные правила или предписания
для воспроизведения значений f (Р). Рассмотрим один из
простейших приемов - метод пОЛU1l0;мuаЛЪ1l0й аппро"К-си-
мации. Ссылка на более изящный способ, такой как дuф-
фереllцuа.лыlяя аппРОJhсuмацuя, будет дана в конце этой
rлавы.
Чтобы сохранить обозначения, применяемые в теории
управления, рассмотрим случай, коrда р - одномерный
вектор, который определен на отрезке [О, 1]. Запишем
f (р) == f (х), rде О < х < 1. Метод, приведенный выше,
в разделе 3, восстанавливает функцию f (х), !{оrда это
необходимо, при помощи интерполяции по набору ее зна-
чений f (k/M), k == О, 1, 2,..., М. Выясним, можно ли
вместо этоrо получить приближенное представление для
f (х) в виде
р
f (х) ak xk .
k=o
(7.1)
*) Мы консервативны: 10 лет, по-видимому, более точная оценка.
Через 25 лет, вероятно, можно ожидать объема памяти в 1010.
74
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕНТЫ
[rл. 111
Если это так, то можно хранить значения f (х) в виде
р + 1 коэффициентов а о , а 1 , ..., ар вместе с указаниями
для вычисления полинома от х с этими коэффициентами.
Если f (х) - rладкая функция, то требуется сравни-
тельно небольmое число коэффициентов. Простейший
способ определения коэффициентов состоит в применении
среднеквадратичной аппроксимации. ы требуем, чтобы
коэффициенты ak минимизировали квадратичную форму
1 Р
(f (х) - а"х")2 dx. (7.2)
о k=o
Для Toro чтобы избежать алrебраических и вычисли-
тельных проблем, возникающих при такой постановке,
можно вместо (7.1) применить аппроксимацию
р
f (х) bkCPk(X), (7.3)
3[=0
rде CPk (х) - ортонормированные полиномы на [О, 1] *).
В этом случае условие среднеквадратичной аппроксима-
ции дает соотношения
1
Ь" = f (х) fJJk (х) ах.
о
(7.4)
Мы теперь столкнемся с трудностями численноrо полу-
чения b/t. Для Toro чтобы преодолеть их, воспользуемся
u u
численнои квадратурои
м
b k = wif (Xi) CPk (Xi).
i=l
(7.5)
Отсюда следует, что требуется запоминать лишь значения
{! (x i )}. Подробное обсуждение вопросов определения и
вычисления CPk (х) и численноrо интеrрирования дано в
конце rлавы.
На первый взrляд мы извлекли большую выrоду, за...
менив хранение f (х) в памяти хранением в памяти зна-
чений {! (x i )}. Мы действите'льно выиrрали, поскольку
*) Точнее, они являются сдвинутыми полиномами Лежавдра.
8]
УСТОйЧИВОСТЬ ВЫЧИСЛИТЕльноrо ПРОЦЕССА
75
речь идет о запоминающем устройстве с малым временем
выборки. НО мы теряем время на запоминание. MHoro
времени расходуется на вычисление коэффициентов b k ,
а затем на вычисление f (х), соrласно (7.3), для друrих
значений х. Это обнаруживается, в частности, на ряде пу-
тей, которыми мы пытаемся обойти указанным способом
проклятие размерности.
Рассмотрим, например, применимость этих способов
аппроксимаI,ИИ к функциям больmоrо числа переменных.
Предположим, что f (р) есть функция четырех переменных,
скажем f (хl, х 2 , хз, Х 4 ). Если мы теперь запишем
р
t (Хl' Х2, хз, Х4) aklrпnCPk (Xl)CPz (Х2) СРт (Х3) <Рn (Х4)'
k, l, т, 11=0
(7.6)
rде aklmn вновь определяются из требований среднеквад-
ратичной аппроксимации, то мы видим, что для запоми-
нания j (р) требуется хранение (Р + 1)4 коэффициентов.
При Р == 4 это будет 54 == 625. Если Р == 9, то это будет
104 == 10 000. Эти цифры указывают на значительное пре-
имущество по сравнению с требованием запоминания
f (р) в узлах четырехмерной решетки.
Можно значительно уменьшить время, требуемое ДJ1Я
вычисления j, используя более низкую степень аппрок-
симации в подобластях. Так, например, можно разделить
область О < Х 1 , х 2 , ХЗ, Х 4 < 1 на 256 областей и применить
аппроксимацию квадратичной формой в каiRДОЙ.
Работа в этой решающей области аппроксимирования
только началась, и имеется MHoro неретенных проблем,
которые досаждают нам. Нашей целью в этом разделе
было указать, что существует некоторое количество пер-
спективных способов и что изобретательность будет воз-
наrраждена сторицей.
8. УСТОЙЧИВОСТЬ вычиспитепьноrо процесса
При при:менении метода, обрисованноrо в разделе 2,
численные поrрещ:пости возникают следующим образом:
При вычислении g (р, q) и Т (р, q) может войти ошибка
окруrления. (8.1а)
76
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕНТЫ
[rл. 111
При вычислении /n-l (Т (р, q)) может потребоваться
интерполяция. (8.1 Ь)
При нахождении максимума по q может быть внесена
ошибка, так как мы учитываем лишь копечный набор
допустимых зна чений q. (8 .1 с)
Из этоrо следует, что численное определение последо-
вательности {tn (р)} порождает новый мноrоmаrовый про-
цесс {СРn (р)}, управляемый соотношением
СРn (р) == тах [g (р, q) + fPn-l (Т (р, q))] + и n (р), (8.2)
q
rде и n (р) изображает пакопление различных упомянутых
выше ошибок. Мы надеемся, что, взяв достаточно MHoro
значений Pi и qj, можно сохранить I и n (Р) I достаточно
малым, а это в свою очередь означает, что I /111 (Р) - СРn (р) ,
мало. Если это так, то наш вычислительный процесс ЯВ-
ляется устойчивым; если это не так, то все результаты,
полученные численно, надо рассмотреть с пристрастием.
Покажем теперь сравнительно просто, что процесс вычис-
ления {fn (р)} устойчив.
Пусть q - максимизирующее значение в исходном
функциональном уравнении
/ n (р) == шах [g (р, q) + / n-l (71 (р, q)) J, (8.3)
q
а Q - максимизирующее значение в (8.2). Тоrда
/n (р) == g (р, q) + f n-l (1' (р, q)) ;> g (р, Q) +
+ t n-l (Т (р,. Q)), (8.4)
СРn (р) == g (р, Q) + CPn-l (Т (р, Q)) + и n (р) >
;> g (р, q) + fPn-l (Т (р, q)) + и n (р).
Следовательно,
fn (р) -<Рn (р) > !n-l (Т (р, Q)) - CPn-l (Т (р, Q)) - и n (р),
< /n-l (Т (Р, Q)) - fPn-l (Т (р, q» - и n (р)
(8.5)
и, таким образом,
!n (р) - СРn (Р) 1< тах[1 !n-l (р, Q) - fPn-l (Т (р, Q» 1,
I !n-l (Т (р, q» - fPn-l (Т (р, q» I ] + I и n (р) 1. (8.6)
10]
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
77
Предположим теперь, что мыI рассматриваем случай, Kor--
да I и n (р) I < 8 для Р Е R. Тоrда
шах I f (р) - <p (р) 1-< шах' In-l (р) - CP -l (р) 1+ в (8.7)
R R
и, таким образом,
шах II n (р) - СРn (р) 1-< пв. (8.8)
R
Линейный порядок роста максимума ошибки означает
устойчивость вычислительноrо процесса.
9. Обсуждение
В это краткое изложение вычислительных аспектов
динамическоrо проrраммирования мы не включИли не-
которые очень интересные и важные вопросы, как, напри-
мер, переформулирование задачи на языке функций мень-
шей размерности, применение множ:ителей Лаrранжа,
методы поиска, стохастическую аппроксимацию, т. е.
вопросы, к ROTOpblM надо обратиться вслед за нашим до-
вольно поверхностным описанием методов аппроксима-
ции. Библиоrраф:ия по этим и родственным вопросам при-
водится в конце rлавы.
Нашей целью в этой rлаве до сих пор являл ось крат-
кое описание основных приемов, встречающихся при чис-
ленном решении функциональных уравнений динамиче-
cKoro проrраммирования. В следующем разделе мы рас-
смотрим некоторые детали.
10. Задача о замене оборудования
MHoro интересных MHoromaroBblX процессов принятия
решений неожиданной математической rлубины возникает
при управлении производственными предприятиями. Сос-
редоточим наше внимание на вопросах замены оборудо-
вания. Предположим, что определенная совокупность
оборудования характеризуется покупательной ценой р
и функцией чистоrо ежеrодпоrо дохода n (t), rде
п (t) === чuстЪLй доход от э сплуатации оборудоваnия
в течение времени от .момента t
до момеnта t + 1, t = О, 1,2,... (10.1)
78
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕRТЫ
[rл. 111
Пусть эта функция будет невозрастаlощей функцие-й от t.
Предположим еще, что рассматриваемое оборудование
является специальным и поэтому не имеет продажной
ценности. В начале каждоrо rода необходимо принять ре-
шение сохранить или заменить оборудование. Нашей
целью является определение политики замены, которая
дает максимальный полный доход в течение N -летнеrо
периода эксплуатации. Более точно, мы хотим решить
задачу управления с обратной связью, т. е. мы хотим
определить, сохранить или заменить оборудование, ко-
торому t лет, коrда оставmееся время процесса составляет
К лет для всех целых чисел К и t. Введем, как обыч-
но, оптимальную функцию дохода fK (t),
fK (t) == чистьtи доход для К-летнеео процесса,
в начале 1f,oтopoeo оборудоваuию уже t лет, при прuмеиеиии
оптu;малъиои полити1f,и замеиьt оборудоваuия, К == 1,
2,...; t == О, 1,2. (10.2)
Из принципа оптимальности непосредственно выте-
кает функциональное уравнение
IK (t) == шах [n (t) + IK-l (t + 1), -р + п (О) + fK-l (1)],
К == 2,3,...; t == О, 1,2,... (10.3)
Кроме Toro, для одноmаrовоrо процесса мы имеем
11 (t) == шах [п (t), - Р + п (О)]. (10.4)
Первый член в скобках в правой части уравнения (10.3)
соответствует непосредственн JMy доходу в результате
решения сохранить оборудование плюс наибольший до-
ход от оставmейся части процесса, начинающеrося с обо-
рудованием rодовой давности. Второй член возникает от
ПОКУПRИ HOBoro оборудования, использования ero в те-
чение одноrо rода и вступления ero в оставшуюся часть
процесса, имея уже rодовую давность.
Сузим теперь ситуацию и составим проrрамму ФОРТ-
РАН, которая даст как оптимальную политику, так и
доход. Предположим, что
п(t)=10-t,
n(t)==O,
t == 0,1,12, ... , 10,}
t == 11,12, ... ,
(10.5)
10]
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
79
и
р == 10.
Уравнения (10.3) и (10.4) принимают вид
11 (t) = шах [п (t), о] == п (t),
fK (t) == шах [n (t) + fK-l (t + 1), fK-l (1)].
(10.6)
(10.7)
(10.8)
Ниже мы воспроизводим nporpaMMy ФОРТРАН IV с вы-
ходом на печать.
Проrрамма подобна тем, которые применяются при
решении мноrих более сложных задач. Утверждения,
обозначенные числом 41, используются для определеных
начальных целей, как, например, выработки функции
п (t), Rоторая запоминается как вектор XN (J), J == 1,2,...
..., 12. Переменная К есть указатель, который содержит
след числа остающихся marOB. «DО-цикл», который на-
чинается с «DO 8 N'f == 1,11», охватывает большую часть
вычислений. Вычисляется доход, который используется
для нахождения решения «сохранить>} или «заменить>}
ХКЕЕР и XRPL дЛЯ оборудования, которому NT лет
при оставшихся К шаrах. Выбирается наибольшее ero
значение, отмечается и называется F (NT, 2). Полученное
решение записывается. Мы положим NQ (NT) == 1, если
правильным решением является «сохранить», О - если
правильное решение есть «заменить» и 2 - если доходы
от обоих решений одинаковы. Состояния
DO 10,1 == 1, 12, 10F (1, 1) == F (1, 2)
сдвиrают уже вычисленные оптимальные значения ФУНК-
цИИ дохода F (1,2) в устройство временной памяти F (1,2),
так что при следующем прохождении цикла мы будем
вычислять оптимальный доход для процесса, продолжи-
тельность KOToporo больше на один rод. Вычисления про-
изводятся для процессов продолжительностью в 25 и
менее лет.
Печатающее устройство записывает оптимальный до-
ход и оптимальное решение. Доходы обозначаются в Е-
системе обозначений. Например, 0,100 Е 0,2 есть 0,1 х
х 102 == 10. Записи в десятой строке ПОRазывают, что
110(0)= 70 И при нулевом возрасте оборудования и остав-
шихся 10 rодах правильным решением будет «сохранить».
80
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕНТЫ
[rл. 111
$JOB 2967, EQUIP, К0160,1 20,20, С
$IB J ОБ EQUIP МАР ,
$IBF те MAIN LIST
С EQUIPMENT REPLACEMENT
DIMENSION F (12,2), NQ (12), XN (12)
D01 Х==1,11
E==J-1
1 XN(J)==10.0-E
XN (12) == 0.0
D03 J = 1,12
2 F (J, 1) == XN ( J )
3 NQ(J)==1
PRINT4, (F (J, 1), NQ (J), J == 1,6)
4 FORMAT (1НО 6 (Е 13.3, 13))
К == 1
41 К === К + 1
DO 8 NT == 1, 11
Х КЕЕР == XN (NT) + F(NT + 1, 1)
XRPL==F(2,1)
IF(XKEEP - XRPL) 7, 6, 5
5 F (NT, 2) == Х КЕЕР
NQ (NT) === 1
GOT08
6 F (NT, 2} == Х КЕЕР
NQ (NT) == 2
GOT08
7 F(NT,2)==XRPL
NQ (NT) == О
8 CONTINUE
F (12, 2) == F (2" 1)
9 NQ (12) == О
PRINT 4, (F (1, 2), NQ (1), 1 == 1, 6)
D010I=1,12
1 О F (1, 1) == F (1, 2)
IF(K-25.) 11,12,12
11 GO ТО41
12 CALLEXIT
13 END
$ENTRY MAIN
$IBSYS END JOB
10]
ЗАДАЧА О ЗАМЕНЕ ОБОРУДОВАНИЯ
81
o o o
O O N
О 0000000000000000000000
оооооооооооооооо оФ оо а
О оФ оФ оФоо
Ф ФФ ООФФ
r
0000000000000000000000000
..
bgg g ggg g 8888 88 8
ооооооосоооооооо Ф
О ОО оо Ф оо
фф ООфф
0000000000000000000000000
o o
0000 000000 0000000000000
оооооооооооооооо Ф
О Ф Ф Ф Ф ФО
ОО ФФ ООООФФ
.
оооооооооооооооооооооосоо
o o M
000000000000 О 0000000000
ооооооооооооооо оо оФ оо оФ
а О о ОО ОФОО N
ф с\1 t:<':' Ф Ф t- ) Ф Ф ...-!
0000000000000000000000000
o o
ooooooooooooo 00000000 О
ООООООоооооооооФ оо оФ оо о
офt- О О ОО Ф
Фt-t- ООФ
ООООООооооооооооооооососо
82
ВЫЧИСЛИТЕЛЬНЫЕ АСПЕНТЫ
[rл. 111
Упражнения
1. Обратитесь к «выходу на печать» для рассмотренной в тексте
задачи. Рассмотрите 10-шаrовый процесс, начинающийся с оборудо-
ванием пятилетней давности.. Определите оптимальный способ за-
мены.
2. Заметим, что для табулированноrо процесса больше чем 11 по
продолжительности, увеличение опримальноrо дохода для каждоrо
прибавленноrо rода есть 6. Прокомментируйте это. Установите тео-
рему, используя это замечание, и докажите ее по индукции.
3. В общих вычислительных проrраммах для решения задачи
динамическоrо проrраммирования имеются три расположенных rнез-
дами цикла. Один относится к решению, друrой - к СОСТО!IНИЮ И
третий - к шаrам. Перепишите приведенпую в тексте nporpaMMY,
чтобы показать это явно.
4. Напишите проrрамм:у для решения друrой какой-либо зада...
чи, рассмотренной в тексте.
&иблиоrрафия и комментарии
1-6. Детальное обсуждение этоrо материала, а также обширные
приложения см. в книrе.
Р. Б е л л м а н и с. Д рей Ф у с, Прикладные задачи
динамическоrо проrраммирования, «Наука», 1965.
7. Дальнейшее обсуждение и приложение этоrо аппарата см. в
цитированных выше книrах и в
R. В е 11т а 11, R.. К а 1 а Ь а and М. Р r е s t r u d, In vari an t
Imbedding and Radiative Transfer in Slabs of Finite Thickness,
American Elsevier Publishing Со., Inc., Ne'N York t 1963.
R. В е 11 m а n, Н. К а g i w а d а, R. К а 1 а Ь а and
М. Р r е s t r u d t Invariant Imbedding and Time-dependent
Processes, American EIsevier Publishing Со., Inc., New York,
1964.
R. В е 11 m а n, S. D r е у f u s and S. А z е n, Some Ар-
plications of Polynomial Approximation to Dynamic Program-
ming, The RAND Corporation, RM-3728-PR, August 1963.
R. В е 11 m а n and S. D r е у f u в, Fuctional Approxima-
tions and Dynamic Programming, Math. Tables and Other Aids
to Computatlon, уоl. 13, 1959, рр. 247-251.
Приложения к численному решению дифференциальных уравнений в
частных производных можно найти в книrе
R. В е 11 m а п, R. К а 1 а Ь а and В. К о t k i n, Оп а
New Approach to the Computational Solution of Partial Diffe-
rential Equations, Proc. Nat. Acad. Sci. USA, vol. 48, 1962,
рр. 1325-1327.
Приложение динамическоrо проrракмирования R задачам прибли-
жения функций при помощи полиrональных функций рассмотрено в
R. В е 11 m а n, Оп the Approximation of Curves Ьу Line Seg-
ments Using Dynamic Programming, Сотт. Assoc. Computinll
Machinery, уоl. 4, 1961, р. 284.
БИБлиоr АФИЛ и RОММЕНТАРИИ
83
8.
R. В е 11 т а n and В. К о t k i n, Оп the Approximatioll
of Curves Ьу Line Segments Using Dynamic Programming,
The RAND Corporation, RM-2978-PR, December 1961.
В. G 1 u s s, Least Squares Fitting of Planes to Surfaces U sing
Dynamic Programming, Соmm. Assoc. Comput. Machinery,
vol. 6, 1963, рр. 172-175.
В. G 1 u s s, Further Remarks оп Line Segment Curve-fitting
Using Dynamic Programming, Соmт. Assoc. Comput. Machi-
nery, vol., 5, 1962, рр. 441-443.
В t G 1 u s s, An Alternative Method for Continuous Line Seg--
ment Curve-fitting, Information and Control, vol. 7, 1964,
рр. 200-206.
В. G 1 u s s, А Line Segment Curve-fitting Algorithm Related
to Optimal Encoding о! Information, Information and Control,
уоl. 5, 1962, рр. 261-267.
Полиномиальная аППРОRсимация является примером аППРОRсимации
функции f (х) при помощи решений линейноrо дифференциальноrо
уравнения вида u(N) + b 1 u(N-l) + ... + Ь:.'{ и == О. Обсуждение и при-
ложение этоrо аппарата привецено в
R. В е 11 m а n and В. К а 1 а Ь а, Quasilinearization and
N onlinear Boundary-value Problems, American Elsevier РиЬ-
lishing Сотрапу, Inc., New York, 1965.
Общие вопросы теории устойчивости рассмотрены в Rниrах
Р. Б е л л м а н, Теория устойчивости решений диффереНЦII-
альных уравнений, ИЛ, 1954.
Р. Б е л л м а н и К. R у н, Дифференциально-разностные
уравнения, «М ир», 1967.
9. Обсуждение некоторых моментов, упомянутых в этом равделе
и друrие ССЫЛRИ УRазаны в Rниrе, упомянутой в разделе 1 и в
R. В е 11 m а n, Оп the Reduction of Djmensionality for
Classes of Dynamic Programming Pt-ocesses, J. Math. Anal.
Appl., vol. 3, 1961, рр. 358-360.
10.
ДальнеЙIПее оБСУiI\дение можно найти в Rниrах:
R. В е 11 m а n, Equipment Replacement Policy, J. Soc.
Ind. Аррl. Math., vol. 3, 1955, рр. 133-136.
R. К а 1 а Ь а and М. J u n с о s а, General Systems Appro-
aches to Telecommunications Optimization ProЫems, 1957,
IRE National Convention Record, Part 8, рр. 203-208.
D. D. М с С r а с k е n, А. Guide to FORTRAN Programming,
J ohn W Неу & Sons, Inc., N БW У ork, 1961.
r л а в а IV
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ В ТЕОРИИ
УПРАВЛЕНИЯ И ТЕОРИИ СВЯЗИ
1. Введение
в первых двух rлавах мы дали абстрактное рассмот-
рение как мноrошаrовых процессов, так и MHoromaroBblX
процессов принятия решения, а в rлаве 111 мы рассмот-
рели, хотя и кратко, вычислительную осуществимость
алrоритмов динамическоrо проrраммирования. В этой
rлаве мы хотим исследовать в деталях процессы, возни-
кающие в управлении и теории связи, структура которых
такова, что как стратеrия, так и функции дохода MoryT
быть получены в простой и явной форме при помощи ме-
тодов функциональных уравнений динамическоrо npor-
раммирования.
Мы рассмотрим как детерминированные, так и стоха-
стичесв:ие процессы для Toro, чтобы подrотовить путь для
изучен:ия адаптивных процессов. Подrотовив фундамент
посредством анализа специальных процессов, мы сможем
тоrда продолжить в следующей rлаве изучение общеrо
вида мноrоmаrовых процессов принятия решений адап-
тивноrо типа.
2. Управnенне с обратной CBJl3bIO
Рассмотрим подробно общий процесс управления де-
терминированноrо типа с обратной связью. Мы принимаем
линейное соотношение
X n -tl == Ах n + Уn,
х о = С,
(2.1)
rде х n И Уn суть N-мерные векторы состояния и страте-
rии соответственно, а А есть матрица типа N х N.
Мы будем иноrда называть Уn ee"fhтopoM управления.
Мы предполаrаем, что вектор Уn выбран так, чтобы
3]
СRАЛЛРНЫЙ СЛУЧАЙ
85
минимизировать квадратичную функцию критерия, на-
пример,
N
RN(x, У) == [(xk, BXk) + (Yl ' Yk)] + (XN, XN). (2.2)
к=о
Это не наиболее общая функция критерия этоrо типа, но
она может служить для иллюстрации общих методов, ко-
торые мы применяем. Если В === О, то мы получим пример
Toro, что обычно называют управленuе поnечnым состоя-
нием (terminal control).
Полученные результаты оказываются весьма интерес-
ными и имеют MHoro непосредственных приложений. Их
наиболее важное значение состоит, однако, в том, что они
MoryT служить отправной точкой при исследовании более
сложных процессов путем аппроксимации как в прост-
ранстве стратеrий, так и в пространстве функций дохода.
3. Скаnярный сnучай
Для Toro чтобы проиллюстрировать особенности полу-
чающихся результатов, не усложняя обозначений и вы-
числений, начнем со скалярноrо случая. Найдя аналити-
ческую структуру решения, нетрудно будет получить
аналоrичные результаты для' векторно-матричноrо случая.
Пусть {и n } - скалярная ПОСJIедовательность, опре-
деляемая соотношением
и n +l === аи n + v n , и о === с,
(3.1)
и пусть v n выбирается так, чтобы минимиэировать с:ка-
лярную функцию
N-l
(и + и ) + u7v.
n=о
(3.2)
Обозначим значение этоrо минимума через tN (с). Тоrда
обычным способом получим рекуррентное соотношение
fN (с) = min [с 2 + v 2 + fN_l (ас + v)] (3.3)
v
86
АНАЛИТИЧЕСНИЕРЕЗУЛЬТАТЫ
[rл. IV
для N > 1, rде 10 (с) = с 2 . ЛеrRО показать по индукции
ИЛИ иным способом, что IN (с) квадратична по с. Так как
IN (с) является, очевидно, четной функцией по с и fN (О) =
== О, то
/N (с) == UNC 2 ,
(3.4)
rде UN есть постоянная, зависящая от N, но не от с. Под-
ставляя (3.4) в (3.3), получим соотношение
UNC 2 == min [с 2 + v 2 + UN_l (ас + V)2] (3.5)
v
или
UN == min [1 + w 2 + UN_l (а + ш)2], (3.6)
w
rде w == v/c. Минимум определяется уравнением
w + UN-l (а + ш) == О,
(3.7)
откуда
U N - 1 а
W==- .
(1 + U N - 1 )
Подставляя это соотношение в (3.6), получим рекуррент-
ное соотношение
(3.8)
2
а uN_l
UN == 1 + (1 + '
U N - 1 )
(3.9)
rде и о == 1. Оптимальная стратеrия описывается уравне-
нием
au N _ 1 c
VN-l = - (1 + UN-l) · (3.10)
Мы получили функции стратеrии и дохода, т. е. полное
решение задачи оптимизации. В упражнениях мы укажем,
как можно пойти далее и получить UN И VN явно В виде
функции от N.
Упражнения
{. Напишите, используя (3.9)
а 2
u N =(1 + а 2 ) - (1 + U N _ 1 ) ,
41
ОБСУЖДЕНИЕ
87
и покажите, что последовательность и n , :монотонно возрастая, стре-
мится к пределу й, определяемому как положительное решение
уравнения
u 2 = 1 + а 2 u.
2. Покажите, что UN может быть выражено явно в виде функции
от решения линейноrо разностноrо уравнения BToporo порядка и
получите аналитическое выражение для U r .
3. Покажите, что ин - и = О (л N ) для HeKoToporo л из интер-
вала О < л, < 1, и определите л при N 00.
4. Рассмотрите случай, коrда функция критерия имеет вид
N-l
{u +V )+Л(UN-Ь)2,
n=о
и изучите зависимость решения от л при л 00.
5. Рассмотрите случай, коrда функция критерия имеет вид
N-l
v; + л (U N - Ь)2.
n=о
Приближается ли при л, 00 оптимальная стратеrия управления к
N-l
оптимальной стратеrии управления в задаче минимизации , v n 2
71=0
при условии на rранице U'V = Ь?
6. Покажите непосредственно из определения (3.3), что fN (с)
монотонна по N для фиксированноrо с.
7. Взяв РО = -с, покажите, что fv (с) 2с 2 , И, следовательно,
используя упражнение 6,ЧТО 'Н (с) сходится при N ОС.
4. Обсуждение
Сделаем несколько замечаний по поводу полученноrо
выше решения. Во-первых, полная стоимость процесса
остается конечной при N -+ 00. Во-вторых, оптимальное
управление линейно, т. е. на каждом mare v пропорцио-
нально и. В-третьих, коэффициент пропорциональноети,
соrласно (3.10), стремится к константе, при N -+ 00, при-
чем достаточно быстро. Все эти свойства имеют место
для мноrошаrовоrо процесса общеrо вида, paccMoTpeHHoro
в разделе 2.
88
АНАЛИТИЧЕСНИЕРЕЗУЛЬТАТЫ
[rЛ.IV
5. Стохастический вариант
Рассм:отрим теперь стохастический вариант рассмот-
реиноrо выше процесса. Вместо (3.1) мы напишем
U nt l == aи + v n + r n ,
r o == С,
(5.1)
rде 1. n - независимые случайные величины с заданной
функцией распределения. Величины V N надо выбрать,
используя управление с обратной связью, которое обсуж-
далось в разделе 13 rлавы 11, так, чтобы минимизировать
математическое ожидание для
N-l
(u + V ) u:V. (5.2)
n=о
Пусть fN (с) обозначает минимум математическоrо ожи-
дания. Как и выше, получим рекуррентное соотношение
fN (с) = m n [(с 2 + v 2 )+ fN-l (ас + v + r) ас (r)], (5.3)
предполаrая для простоты, что dG (r) - общая функция
раСllределения для случайных переменных. Вновь нет-
рудно показать по индукции или друrим способом, что
функция fN (с) квадратична по с. Следовательно, можно
написать
/N (с) == UNC 2 + VNC + WN,
(5.4)
rде UN, VN и WN не зависят от с. Подставляя в (5.3), будем
иметь
UiVc 2 + VNC + WN == min [(с 2 -t- v 2 ) +
v
+ [UN-l (ас + v + r)2 + VN-l (ас + v) + W N-l] dC(r). (5.5)
Мы можем теперь выразить минимизирующее значение
V непосредственно через UN-l и VN-l и: 'rаким образом по-
лучить рекуррентное соотношение для тройки [UN, VN,
WN] В зависимости от [UN-l, VN-l, WN-l]. Мы не будем вхо-
дить в детали, так как вычисления здесь простые и их
лучше предоставить читателю в качестве упражнения.
7]
мноrОМЕРНЫЙ ДЕТЕРМИНИРОВАННЫЙ СЛУЧАЙ
89
Упражнения
1. Rоrда lJN тождественно равно нулю?
2. Получите аналоrи результатов, установленные в упражне-
ниях 2 и 3 в конце раздела 3.
3. Рассмотрите случай, коrда rn не являются независимыми слу-
чайными переменными, начиная со случая, котда функция распре-
деления для r n имеет вид dG (r, rn--l), Т. е. зависит от величины rn-l.
Каково асимптотическое поведение функции управления в этом
случае?
6. Обсуждение
Отметим, что функция распределения для ' n входит
только через ее первый и второй моменты. Следовательно,
любые две функции распределения с одинаковыми двумя
моментами приводят к той же самой функции дохода и
оптимальной стратеrии, хотя обе реализации процессов
MoryT оказаться совершенно различными.
Отсюда ясно, что введение случайных перем.енных не
затраrивает существенно ни функцию стратеrии, ни функ-
цию дохода. Следовательно, стохастическая теория уп-
равления, базирующаяся на линейных уравнениях и
квадратичном критерии, может быть принята лишь с
некоторыми оrоворками. На первый взrляд кажется, что
она сложнее детерминированной теории управления, но
в действительности это не так. Лишь при применении бо-
лее точных методов оценки отклонений, в совокупности
с учетом нелинейности уравнений, стохастические свой.
ства вносят важные и радикальные отличия от детерми-
нированной трактовки.
7. МноrомерныЯ детерминированныЯ сnучаЯ
Используя незначительное количество матричных обоз-
начений, можно теперь обратиться к MHoroMepHoMy ва-
рианту детерминированноrо процесса управления с об-
ратной связью, описанноrо в разделе 2. Пусть Х n и Уn -
М -мерные векторы, а А - матрица типа М хМ. Для
заданноrо преобразованил
X n -tl == Ах n + Уn,
Ха == С,
(7.1)
90
АНАЛИТИЧЕСНИЕРЕ3УЛЬТАТЫ
rrJl. 1\'
rде х п изображает вектор состояния в момент времени п,
Ун - вектор управления, надо выбрать Ун так, чтобы
минимизировать функцию критерия
N
R N == [(Xk, ВХк) + (Ук, YIJJ + (XN, X1V), (7.2)
k=o
rде, !\а!\ обычно, (х, у) обозначает сналярное произведе..
ние, т. е.
м
(х, у) == Xi Yi,
i=]
(7.3)
а X i и У i - соответствующие i-e компоненты х и у. Пола-
rая /N(C) == min R N , получим рекуррентное соотношение
{t/k}
fN (С) == min [(с, Вс) + (У., у) + !N-l (Ас + у)], N> 1, (7.4)
у
rде 10 (С) == (с, с). Заметив, что IN (с) является квадратич-
ной формой относительно с, результат, который получа-
ется интуитивно, по индукции, или непосредственно из
исходной вариационной задачи, мы запишем IN (с) ==
==(с, QNC), Подставляя это равенство в (7.4), получим со-
отношение
(с, QNC) == min [(с, Ве) + (у, у) + (Ас + У, QN-l (Ас + у»],
у
(7.5)
rде Qo == Е. Обычный вариационный подход приводит К
линейному закону управления
у (Е + QN-l) + Q N-1Ac == О
(7.6)
или
У = - (Е + Q N_l)-lQ N-1Ac.
(7.7)
Значение минимума леrко вычислить, если заметить,
что
(у, у) + (Ас + у, QN-l (Ас + у» == (Ас, Q N-1Ac) +
+ (у, у + QN-IY + QN-1Ac) + (у, QN-1Ac). (7.8)
8]
НЕПРЕРЫВНЫЙ СЛУЧАЙ
91
в силу (7.6) и (7.7) это приводится к виду
(с, QNC)== (Ас, QN-1Ас)-((Е+QN-l)-lQN-lАс, QN-J...4c)=
== (Ас, QN-IАс) - ((Е + QN-l)-lX
X(E+QN_1Ac, QN-1Ac)) + ((Е+ QN_l)-lАс, QN-1Ac) =
== ((Е + Q N_l)-l Ас, Q N-1Ac).
Приравнивая коэффициенты, получим из (7.5)
QN==B+A'QN-l(Е+QN-l)-lА, (7.9)
rде Qo == Е. Это позволяет рекурсивно вычислить QN,
Записывая (7.9) в виде
QN == В + А' (Е + QN-l) (Е + QN_l)-l А -
- А' (Е + QN_l)-l А == В + А' А - А' (Е.' + QN_l)-l А,
(7.10)
мы видим, что QN равномерно оrраничена и монотонно
возрастает в том смысле, что матрица QN - QN-l является
положительно опр-еделенной.
Упражнения
1. Покажите, чтп еСJIИ {QN} есть Оl'раниченная последователь-
ность положительно определенных матриц с таким свойством, что
матрица QN - Q N -1 является неотрицательно определенной, то Q '{
сходится при N 00.
2. Покажите, что Q.v , удовлетворяющая (7.10), может быть полу-
чена посредством решения системы разностных уравнений поряд-
ка 2М.
3. Рассмотрите стохастический процесс, порождаемый соотно-
шением
X п + 1 == АХ п + У п + r n'
Хо == С,
тде rn - независимые случайные B KTOpы. Получите аналоrи при-
веденных выше результа'J ов.
8. Непрерывный спучаji
Соответствующие результаты для непрерывноrо про-
цесса управления TaKrRe являются довольно элеrантными.
Рассмотрим задачу минимизации Функционала
т
J (у) = [(х, Вх) :+- (у, у)] dt (8.1)
о
92
АНАЛИТИЧЕСRИЕРЕЗVЛЬТАТЫ
[rл. IV
по всем у, rде векторы х и у связаны соотношением
dx А'
dt = Х + у,
х (О) = с.
(8.2)
Обозначая f (с, Т) == min J су), из тех же рассуждений,
у
что и выше, ПОЛУЧИ I
f (е,Т) == min [[(е, Ее) + (v,v)] + f (с + (Ас + v) , Т -
v
- L\)] + о ( ). (8.3)
в пределе при d -+ О это приводит « дифференциальному
уравнению в частных производных
= (е, Ее) + min [(и, и) + (Ас + и, gradf)], (8.4)
v
rде, ка« обычно,
д!
дс!
grad / == .
.
дем
(8.5)
Здесь через с 1 , С 2 ,...,см обозначены Rо:м:поненты вентора с.
Оптимальное управление в этом случае
grad f
v = - 2 · (8.6)
Обозначая f (с, Т) == (с, Q (Т)с), имеем grad f == 2Q (Т)с.
Следовательно, оптимальное управление является линей-
ным
V == - Q (Т) с
(8.7)
и (8.4) дает уравнение Риккати
Q'(T) = в - ft(T) + A'Q ;QA ,
rде Q (О) = О.
(8.8)
8]
НЕПРЕРЫВНЫЙ СЛУЧАЙ
93
Упражнения
1. Покажите, что (8.8) можно привести R линейному уравнению
при помощи подстаНОВRИ Q = YZ-l, rде у и Z удовлетворяют линей-
ным дифференциальным уравнениям.
2. Покажите двумя способами, что Q (Т) стремится R пределу
при Т 00.
3. BblllIe изложенные методы MoryT быть применены для изуче-
ния изменения функций fрина линейных функциональных уравне-
ний. Начнем с линейноrо дифференциальноrо уравнения BToporo
порядка
и" + q (х)и = v (х), а < х < 1, и (а) = u (1) = О
и оставим последующие mаrи в качестве серии упражнений для чи-
тателя. Покажите, что решение приведенноrо выше уравнения мож-
но записать в виде
1
и (х) = к (х, у, а) о(у) ау,
а
rде К строится из решений однородноrо уравнения. Ядро К (х, у, а)
называется фун,1'i,цией Fpuna, СОQтветствующей определеuным rpa-
ничным условиям.
4. Определите К (х, у, а) в случае, коrда функция q (х) по-
стоянна.
5. Покажите, что уравнение Эйлера, связанное с задачей мини-
мизации функционала
]
J (и) = [q (х) и 2 - (и')2 - 2vи] ах,
а
является линейным дифференциальным уравнением BToporo порядка
и" - q (х)и = v С rраничными условиями, определяемыми из ус-
ловий относительно и.
6. Покажите, что если min J (и) = f (а, с), rде и (а) = с, то
и
д! Сд! /дс)2
да =q(a)c 2 -2v(a)c+ 4
7. Покажите, используя уравнение Эйлера, что
1 1
f (а, с) = к (х, у, а) v (х) v (у) dx dy + 2cL 1 (о) + c 2 g (а),
аа
rде ['1 (v) есть линейный Функционал по и.
8. Подстановкой в уравнение из упражнения 6 получите урав..
нение
дК дК дК
да (х, у, а) = ду (х, а, а) д% (а, у, а).
U4
АНАЛИТИЧЕСНИЕРЕЗУЛЬТАТЫ
[rл, IV
9. Пользуясь уравнением и" + (q (х) + Лr (х))и = v (х), полу-
чите аналоrичную формулу для реЗОJlьnенты и таким образом найдите
формулы, определяющие зависимость характеристических значений
n функций в конечной точке а. (См. R. В е 11 m а 11 and R. s. L е h-
m а n, Functional Equations jn the Theory of Dynamic Programming-
Х: llesolvents, Characte] istic Functions and Values, Duke Math.,
J., vol. 27, 1960, рр. 50 70.)
10. Рассмотрите IIHTer ральное уравнение Ф редrольма
т
и (х) + v (х) + k (х, у) и (у) dy = О,
'"'
а
O а Т,
с единственным решением
т
и (х) = - v (х) + Q (х, у, а) v (у) dy.
а
Пользуясь методами динамичеСI\оrо проrраммирования, минимизи
руйте квадратиqный: фУНRционал
т т
J (и) -= и 2 (х) dx + 2 и (х) v (х) dx +
а а
тт
+ s к (х, у) и (х) и (у) dx dy
аа
и ПОJlучите уравнение
8Q
да (х, у, а) == Q (а, х, а) Q (а, у, а).
(СМ. R. В е ] 1 m а n, Frunctional Equations in the ThE'ory of Dynamic
Programming - V 11: А Partial Differential Eql1ation for the Fred-
holm Resolvent, Proc. Amer. Math. Soc., vo1. 8, 1957, рр. 433-440.
Дальнейшие применения методов динамичеекоrо проrраммироnанил
можно найти в :квиrе н. n е 11т а n апд Н. О s Ь о r n, Dynamje
Programming and the Variation of Green's Funetions, J. Math.
Mech., vol. 7, 1958, рр. 81-86 и в rлаве 9 книrи R. В е l-
1 m а п, Introduction to Marix Analysis, McGraw-Нill Book Со., Inc.,
Ne\v York, 1960).
11. Рассмотрите задачу мииимизации квадратичвоrо фУПI ЦПО-
вала
т
J (и)= (и 2 + и'2) dt
о
9]
ТЕОРИЯ проrНО3ИРОВАНИЯ
95
при условиях u (О) = с, I и' ' т для О -< t Т. Обозначив
f (с, Т) = min J (и), покажите, что
и
f т == min [с'2 + v 2 -t- vj с],
JvJ т
12. Получите аналитический вид f (с, Т) и вид оптимальной стра-
теrии, определяя f (с, Т) сначала для малых Т, а затем увеЛIIчивая
значение Т до тех пор, пока не встретится оrраничевие.
(Для систематическоrо подхода к вариационным задачам с or-
раничениями при помощи леммы Неймапа - Пиреона см. мопоrра-
фИIО Р. Б е л л м а п, И. r л и R С б е р r, О. r р о с с, Некоторые
вопросы математической теории процессов управления, ИЛ, 1962.
Для подхода, использующеrо классические вариационные методы
и их обобщения, полезно прочитать L. D. В е r k о v i t z, Varia-
tional Methods in ProbIems of Control and Programming, 1. Math.
Anal. Appl., vol. 3, 1963, рр. 145-169. Л. С. П о н Т-
ряrин, B.r. Болтянский, Р.В. rамкрелидзе
и Е. Ф. М и Щ е н к о, Математическая теория оптимальных про-
цессов, М., 1961).
13. Рассмотрите задачу минимизации Функциоuала
т
J (и) = (и'2 + g (и» dt, u «) = с.
о
Пусть иn будет п-М приближением и пусть иn+l есть ФУНRЦИЯ, мини-
мизирующая
т
J n (и) = [U'2+ g (U n )+ (и- и n ) g' (ип> + (и 2 иn )2 g"(Un)]dt; u (О)=с.
о
При каких условиях последовательность {иn} схоритсл R функции
U (t), минимизирующей J (и). (СМ. 1\1. А о k i, ОП the Approximation
of Trajectories and its Applications to Control Systems Optjmization
Problems, 1. Math. Anal. and Appl., vol. 9, 1964, рр. 23-41.)
9. Теория проrнозирования
Фундаментальной целью науни является проrнозиро-
вание будущеrо на основе знания прошлоrо и настоящеrо.
Так кан классические методы базируются на дифферен-
циальных уравнениях, требующих большеrо объема све-
дений, чем мы обычно располаrаеl\lf, за последние rоды
получили развитие разные подходы, основанные на веро-
ятностных рассмотрениях.
96
АНАЛИТИЧЕСНИЕ РЕЗУЛЬТАТЫ
[rЛ.IV
Рассмотрим, в частности, задачу получения оценки а n
для всех п > О, задавая последовательность {а n } для
n = О, -1, -2, .". Вообще, пусть даны две после-
довательности: {ак} и {Ь к }; как получить наилучшую
оценку для Ь 10 если ИЗJlестны только а к и различные кор-
реляции?
Один из путей подхода R этой задаче, который выте-
кает из аналитических соображений, а таRже интуитивно
ИЗ электротехнических аналоrий, состоит в ОТЫСRании
третьей последовательности {U k }, обладающей свойством
м
Ь К uLak_l.
[=0
(9.1 )
Следуя Rолмоrорову иВинеру , целесообразно потребо-
вать, чтобы Ul определялись из условия минимизации
квадратичноrо выражения
N м
(b k - Ulak_l)2.
k=o l=o
(9.2)
Леrче исследовать предельную задачу, rде (9.2) принимает
вид
N N
liт (Ь " - и/а,,_д2
N--+co к=о l=o
(9.3)
ИЛИ ВИД
т R
(Ь (t) - а (t - s) и (8) ds)2dt.
о о
(9.4)
Как можно было ожидать из предыдущеrо анализа
вариационные задачи TaKoro рода MoryT быть леrко и
систематически рассмотрены при помощи метода функ-
циональных уравнений динаМИЧЕ.скоrо проrраммирова-
ния, примененноrо в предыдущих разделах. Интересую-
щеrося читателя мы отсылаем н ряд) источников, указан-
ных в конце rлавы.
tt]
ЭФФЕRТИВНЫЙ иrРОR
97
10. Передача информации
Обратимся к друrой интересной области современных
исследований, которая занимает центральное место в тео-
рии передачи информации. Мы можем разложить процесс
на пять частей: (а) образование данных; (Ь) кодирование
данных для их передачи; (с) передача закодированных дан-
ных; (d) декодирование полученноrо в результате пере-
дачи сиrнала; (е) использование декодированноrо сиrнала.
Процесс может быть значительно усложне]I при вве-
дении контура обратной связи для целей проверки.
В прошлом, и в значительной мере в настоящем, име-
лась неудачная, но понятная тенденция изуча'fЬ эти части
порознь, мало зная или вовсе не признавая существова-
ния друrих частей. В лучшем случае эта «ввликолепная»
изоляция приводит к неполным результатам:; в худшем
случае она приводит к полностью ошибочным результа-
там. Таким, в частности, будет случай, коrда результаты,
полученные при идеализированной пропускной способ-
ности канала связи, применяются при недостаточных све-
дениях об основном процесс е и ero целях.
Весьма существенно при изучении этих сложных за-
дач учитывать взаимодействие указанных выше различ-
ных частей систем связи. Для иллюстрации подхода, ко-
торый можно применить, мы обсудим задачу, впервые
поставленную и частично решенную Келли. Применяя
методы динамическоrо проrраммирования, можно решить
исходную задачу и обобщить ее рядом способов. Чтобы
упростить изложение, мы иrнорируем здесь вопросы ко-
дирования и декодирования. Существенный момент сос-
тоит в том, что передача информации используется для
целей принятия решения.
11. ЭффективныJi иrрок
Предположим, что неразборчивый в средствах иrрок
получает априорную информацию относительно результа-
тов спортивных событий по телефону при наличии боль-
moro myMoBoro фона. Так как время весьма оrраничено,
ему передают только слова «выиrрыш» или «проиrрыш»,
и он должен действовать, базируясь на этой информации.
98
АНАЛИТИЧЕСНИЕ РЕЗУЛЬТАТЫ
[rл 1V
Из-за трудностей связи имеется вероятность, что он слы-
шит то или иное слово неправильно. Имея это в виду и
зная вероятность неправильноrо приема, сколько оп дол-
жен ставить в каждом случае?
Ясно, что ero тактика заключения пари должна в зна-
чительной мере зависеть от функции критерия, которым
он пользуется для оценки выrоды. Если, например, он
хочет максимизировать математическое ожидание выиr-
рыта, то он держит пари на полное свое состояние вся-
кий раз, коrда считает, что вероятность получения пра-
пильной информации превышает 1/2. Лсно, что это очень
рискованная политика, так как не исключена возможность
полноrо краха в последовательности ero ставок.
Следовательно, по-видимому, целесообразнее пользо-
ваться более rибким критерием, таким, который предот-
вращает полный крах, независимо от Toro, что произой-
дет . Мы можем обеспечить более осторожное поведение
путем принятия друrих критериев. Например, иrрок мо-
жет решить держать пари так, чтобы максимизировать
матем:атическое ожидаемое лоrарифма полной суммы де-
Her, которая будет в ero распоряжении в конце иrры.
Чтобы увидеть, как это воздеi'tствует на политину зак-
лючения пари, предположим, что р есть вероятность Toro,
что информация является правильной, что иrрок обладает
в начале иrры х долларами и что он хочет сделать ставку
у, которая максимизирует математическое ожидание ло-
rарифма полной суммы денеr, которую он будет иметь
после Toro, как пари будет оплачено, при том или ином
результате иrры. Математическое ожидание имеет вид
Е (у) == р log (х + у) -1-- (1 - р) log (х - у). (11.1)
Как нетрудно видеть, максимум достиrается при у ==
-== (2р - 1)х, если р > 1/2, и при у == о в противном слу-
чае. Рассмотрим теперь наиболее интересный случай,
коrда р > 1/2. Максимальное значение Е (у) будет
E 1nax == log х + log 2 + р log р + q log q, (11.2)
rде q ==- 1 - р. Первые два члена определяют математи-
ческое ожидание при полной информации р == 1. Вторые
два члена, которые являются отрицательными, и будут ме.
12]
ПРИМЕНЕНИЕ МЕТОДА
99
рой потерь от дсзинформаЦИl1 И, таким обраЗОl\I, MoryT
быть использованы для Оl еНI{И llЛПЯПИЛ по:мех передачи.
РаССl\fОТРИ:М теперь мноrошаrовый процесс заключе-
ния пари, в котором иrрОR получает :информацию, делает
ставку, выиrрывает или проиrрывает, получает ВТОрОЙ
сиrнал и Т. д. Какова должна быть теперь ero оптималь-
ная политика?
11. Применение метода динамичеекоrо
проrраммнровання
Следуя обычным путем, обозначим
fN (х) == математuчеС/f;ое ожидание доеарифма О/f;Оllча-
тедъноео /f;aпuтaJla, получеnnое в результате N -и а20вО20
процесса 8а Лl0чеnия пари, отОРЬLЙ nачиnался при ито-
20вой сум.-ме х и cooп вeтcтвoвaд оптимальной полuтU/f;е.
(12.1)
п ринцип оптимальности дает рекуррентное соотно-
шение
fN(X) = шах [p!N-1(х+у)+(1-р)!N-l(Х-У)], (12.2)
O y<x
rде N >= 2, а fl(X), как было показано выше, имеет вид
/1 (х)== logx + К. (12.3)
Здесь
К == (IOg 2+ р log р+(1- р) log (1-р),
О ,
1
Р>т,
1 (12.4)
Р<Т.
Рекуррентное соотношение (12.2) остается тем же са-
мым, несмотря на оrраниченность функции, которой мы
пользуемся. Начальная функция 11 (х) определяет струк-
туру оптимальной политики. До некоторой степени по-
разительное свойство лоrарифма то, что при такой
функции удается получить простое явное решение урав-
нения (12.2) при начальном условии (12.3).
Покажем теперь по индукции, что
f (х) = log х + NK (12.5)
100
АНАЛИТИЧЕСКИЕ РЕЗУЛЬТАТЫ
[rЛ.IV
для N > 1 и что оптимальная политика не зависит от N
и и:м:еет в точности вид, приведенпый выше, а именно,
! (2 Р -1)Х,
У=
о
1
Р>т,
1
Р<Т.
(12.6)
Предположим, что этот результат справедлив дЛЯ N.
Тоrда
IN+l (х) = тах [p(Iog (х + у) + N [{) + (1 - Р) х
o y x .
X[!og(x-у)+NК]]==NК+ тах [plog(x+y)+
o y x
+ (1 - р) log (х - у)] = N К + Iog х + К =
==logx+(N+1)K. (12.7)
Это доказывает оба утверждения.
Упражнения
1. Рассмотрите случай, в нотором свойства передачи изменяются
со временем, так что на k -М шаrе вероятность правильной передачи
есть Pk, rде Pk > 1/2. Покажите, что максимум математичеекоrо
ожидания лоrарифма К" питала по истечении N marOB дается выраже-
нием
N
log х + N log 2 + (Pk log Рк + (1 - Pk) log (1 - Pk»'
k=l
2. Рассмотрите случай, KorAa вероятность правильвой передачи
k-ro сиrнала зависит от Toro, правильно или непрапильно будет
передан (r - 1)-й сиrнал.
3. Рассмотрите ситуацию, коrда М различных сиrналов может
быть передано на любом mare и иrрОR располаrает следующими
данными:
Pij = УС,/tов1tая вероят1tость тоео, что сuznал j uаJtучалсл llС-
тОЧ1luпо.м, если 1tаблюдателем' был прunят сиеиа", i.
qi = вероят1tость тоео, что 1tаблюдатель па любо,м шаее полу-
чuт сиена", i.
ri = доход от 8ыиераппоео пари, отnесеU1lЫЙ " од1l0Й единице
сиенала j.
м
Иrрок получает сиrнал j и заключает пари на величиНу Zi, zi х,
i=l
утверждая, что в действительности наqальвый сиrнал был i.
ВИБлиоrРАФИЯ и Н:ОММЕII Т АРИIf
101
4. Рассмотрите случай континуума сиrналов, -ос < v < ос,
tде задана условная вероятность dG (и, v) Toro, что сиrнал с отметкой
между v и v + dv послан, если был принят сиrнал и И, кроме Toro,
заданы все друrие, относящиеся R делу величины.
(Об этих и друrих результатах можно прочитать в R. В е 1-
1 m а n and R. К а 1 а Ь а, Dynamic Programmjng aHd Statistical
Communication Theory, Proc. Nat. Acad. Sci. USA, vol. 43, 1957, рр.
749-751. Н. В е 11 m а n and Н. К а 1 а Ь а, Оп Communication
Processes Involving Learning and Random Dпrаtiоп, 1958, IRE Na-
tional Convention Record. Part 4, рр. 16-20. Н. В е 11 m а n and
Н. К а 1 а Ь а, Dynamic Programming and Adaptive Proce"ses:
Mathematical FoundatiollS, IRE Trans. Automatic COl1trol, vol. АС-5,
1960, рр. 5-10. Р. Б е л л м а н, Процессы реrулирования с адап-
тацией, Физматrиз, 1964.)
5. Что ДОЛiкен делать иrрок, если р < 1/2!
13. Обсуждение
Весьма важный результат, который непосредственно
вытекает из изложенноrо, состоит в том, что функция
критерия log XN позволяет отделить влияние начальных
ресурсов от влияния помех передачи. При этих усло-
виях мы можем забыть о назначении сиrналов и изучать
свойства канала связи сами по себе. Оказывается также,
что та же самая функция р log р + (1 - р) log (1 - р)
возникает при изучении некоторых специальных задач
кодирования, как результат важноrо cTpyKTypHoro свой-
ства, и в статистической механике в виде энтропии.
Известно несколько интересных применений функции
энтропии в теории передачи информации и, к сожалению,
значительно большее число необдуманных и ведущих к
заблуждению ПОПЫТОI{ ее применения. Вышеприведенный
анализ показывает, как тесно функция энтропии связана
с функцией критерия log XN. При применении иных кри-
териев и дополнительном учете друrих обстоятельств,
мы получим совершенно иную меру для оценки влияния
помех в канале связи, однако не сможем отделить влияния
начальных ресурсов от влияния канала связи.
&и6пиоrрафИJl и комментарии
1-3. См. rл. Х в книr
Р. Б е л л м а н и с. Д рей Ф у с, Прикладные задачи
динамическоrо проrраммирования, «Наука», 1965 и rЛdRУ
IX книrи
102
АНАЛИТИЧЕСНИЕ РЕЗУЛЬТАТЫ
(rJI. IV
Н. в е 11 m а п, Introduction to Matrix Analysis, McGraw-
Hill Book Со., New York, 1960,
rде имеются дополнительные ссылки.
s 4. Реномедуем работы
D. S. А d о r n о, Tlle Asymptotic Theory of Control Systems
- 1: 8tochastic and Deterministic Processes, J et Propulsion
Lab., Technical Release 34-73, June 30, 1960.
R. В е 11 m а n and R. В u с у, Asymptotic Control Theory,
J. SIAM Control, vol. 2, 1964, рр. 11-18.
9 5. О стохастических процессах управл€ния см.
У. Sawaragi, У. Sunahara, Т_ Опо, А Study оп
Dynamic Optimization of Control Systems \vith Gaussian Нап-
dom Outputs, Technical Reports of the El1gineering Research
Institute,l{yoto Univ., vol. 14,1964, Report No.114, рр.
61-87.
J.J. Florentin, J.H.Westcott and J.D.Pear-
s о n, Approximatiol1 Methods in Optimal and Adaptive Соп-
tI'ol, Proc. IF АС Second Congress, Base1, Switzerland,
1963.
J. J. F 1 о r е n t i п, Optimal Control of Continuous Time,
Markoy, Stochastic Systems, J. Еlес. & Control, уоl. 10, 1961,
рр. 473-488.
Н. С о Х, ОП the Estimation of State Variables and Parameters
for Noisy Dynamic Systems, IEEE Trans. оп Automatic Cont-
rol, yol. АС-9, 1964, рр. 5-12.
Н. С о х, Оп Estimation of State Variables and Parameters,
Joint AIAA-IМS-SIАl\I-ОNR Symposium оп Control and Sys-
tem Optimization, u. S. N aval Postgraduate School, Montercy,
California, J аппаrу 27-29, 1964.
J. Т. Т о u and В. V а d h а пар h u t i, Optimum Cont-
rol of N ol1Iinear Discrete-data Systeтs, AIEE Trans., yo1. 80,
1961, рр. 166-171.
J . Т, Т о и, Design of Орtimпm Digital Control Systems via
Dynamic Рrоgrаmmiпg, Proc. Dynamic Programming Works-
hop, J. Е. G i Ь s о п, ed., Purdue University, Lafayette,
Indiana, 1961, рр. 37-66.
J. Е. G i Ь s о п, Optimum Design of Djgital Control Systems,
Academic Press Inc" New York, 1963.
Н. Е. К а 1 m а п, New Methods and Results in Linear Pre-
diction and Filtering Theory, RIAS, Technical Report 61-1,
1960.
7. См.
R. В е с k w i t h, Analytic and Computational Aspects of
Dynamic Programming Processes of High Dimension, J et Pro-
pulsion Lab., 1959.
С, \V. М е r r i а т, 111, An AIgorithm for the Iterative Solu-
tion of а Class of Two-point Boundary Value Problems, J. S IAN[
Control, vol. 2, 1964, рр. 1-10.
БИБлиоrРАФИЛ ИНОММЕНТАРИИ
103
С. '\'. lуI е r r i а т, 111, А Class of Optimum Control Systems,
J. Franklin' Institute, vol. 267, 1959, рр. 267-281.
С. "'. м е r r i а т, 111, Computational Considerations for
а Class of Optimum Control Systf..ms, Proc. First Internat.
Congress of lFAC, J. F. Coales, ed., Butterworth & Со., Ltd.,
London, 1961, vol. 11, рр. 694-701.
С. W . м е r r i а т, 111, Use of а Mathematical Error Criterion
in the Design of Adaptive Contro1 Systems, AIEE Trans., vol.
78, 1960, рр. 506--512.
С. \v. М t r r i а т, 111, Ап Optimization Theory for Feedback
Control System De"ign, lnformation and Control, vol. 3, 1f}60,
рр. 32-59.
Обсуждение процессов с запа3ДЫВ8нием см.
J. D. К r а m е r, Information and Control, уоl. 3, 1960, рр.
299-326.
8. Результаты этоrо вида впервые получены в
R. В е 11 m а п, Оп а Class of Variational Problems, Q. Appl.
Math., vol. 14, 1957, рр. 353-359.
9. См. приложение Н. Левинсова в Rнпrе
N. "V i е n е r, ТЬь Extrapolatiol1, Interpolation and Smoot-
hing of Stationary Time Series and EngineeI'ing Applications,
J ohn vV Неу and Sons, New York, 1942.
См. также rлаву IX книrи«Маtriх Analysis» ,стр.155 и цитированную
выте статье Rалмана. Rалман систематически применял теорию
динамическоrо проrраммирования к задачам проектирования и уп-
равления и получил весьма обстоятельные результаты. Некоторые
ero последующие результаты см. в
Н.Е. К alman and J.E. Bertram, AUnifiedAppro-
ach to the Theory of Sam pling Systems, J. Frank1in Insti-
tute, vo1. 267, 1959, рр. 405-436.
R. Е. К а 1 m а n and J. Е. В е r t r а т, General Synthesis
Procedure for Compllter Control of Single-loop and Multiloop
Linear Systems, AIEE Trans., vol. 77, 1959, рр. 602-609.
R. Е. К а 1 m а n and R. \У. К о е р с k е, The Role of
Digital Compиters in the Dynamic Optimization of Chemical
lleactions, Proc. 'Vesttrl1 J oint Computer Conference, San Fran-
cisco, California, March 1959, рр. 107--116.
10. Исходные результаты Rэлли см. в
J. К е 11 у, А New lnterpretation of Information Rate, Bell
System Tech. J., vol. 35, 1956, рр. 917-926.
Приведенпый в разделе 12 подход был дан в статьях, цитированных в
нонце раздела 12. Дальнейшее обсуждение этих вопросов см. в
J. М а r s h а k, Remarks оп the Economics of Information,
Cowles Foundation Discussion Paper No. 70, April 1959.
Большое внимание было сосредоточено на управляемых процессах,
описываемых линейными дифференциальными уравнениями вида
х' = Ах + у, rде компоненты вектора у удовлетворяют оrраниче-
пиям IYil тi, О < t Т и должны быть выбраны так, чтобы
{О4
АНАЛИТИЧЕСНИЕ РЕЗУЛЬТАТЫ
[rл. IV
минимивировать время, требуемое для переводаzв начало КООрДИНАТ.
МатематичеСRая rлубина этих вопросов весьма поразительна, и
ДЛЯ их изучения был применен ряд мощных математичеСRИХ среАСТВ.
СМ.
R. В е 1 1 m а п, 1. G 1 i С k s Ь е r g and о. G r о s В, ОП
the BaDg-Ьапg Control Problem, Q. Appl. Math., vol. 14,
1956, рр. 11-18.
Р. Б е л JI М а н, и. r л и R С б е р r, о. r р о с с, Некото-
рые вопросы математической теории процессов управления,
ИЛ, 1962.
J. Р. L а S а 1 1 е, Оп Tjme-optimal Contro1 Systems, Proc.
N at. Acad. Sci. USA, vol. 45, 1959, рр. 573-577,
rде MoryT быть найдены дополнительные ссылки.
r л а в а V
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕJit
1. Введение
Перейдем теперь к некоторым более реалистическим и,
естественно, более общим и интриrующим вариантам не-
определенности и соответствующим этим вариантам про-
цессам управления. Процессы, которые мы обсудим,
являются математически совсем новыми. Они, однако, но-
вы в научном отношении лишь в том смысле, что большин-
ство математиков, инженеров и ученых до последнеrо
времени катеrорически отказывались даже допускать
мысль об их существовании. Тем не менее они всеrда,
хотя и будучи незванными rостями, присутствовали за
банкетным столом науки.
В нашем изучении детерминированных процессов уп-
равления мы делали традиционные предположения о том,
что переменные состояния идентифицируемы и наблюдае-
мы, что последовательность возможных решений извест-
на, что исходные причины и взаимные влияния также
известны, а цели изучаемоrо процесса принятия решений
хорошо определены. МатематичеСRие результаты, полу-
ченные таким путем, будут более или менее достоверными
приближениями. Коrда же речь идет оприложениях,
то «риск - за счет потребителя», так как в науке нет
cBoero рода «3акона о пище и лекарствах», требующеrо
ярлыка с указанием содержимоrо.
Первым maroM на пути отказа от полностью детерми-
нистской концепции и шаrом, имеющим существенное
значение, является классическая теория вероятностей с
ее введением случайных переменных. В этой rлаве мы
хотим указать СУlцествование еще более BblcoKoro уровня
неопределепности и показать, что метод функциональных
уравнений теории динамическоrо проrраммировавия
106
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[rл. v
может быть использован для получения аналитических фор-
мулировок даже в этих более сложных условиях.
Чтобы ориентировать читателя в этих новых направ-
лениях, не отпуrивая ero от них насколько это возможно,
МЫ изложим в некоторых деталях сравнительно простые
процессы с адаптацией - аналоrи процессов, рассмот-
ренных выше в детерминированной и стохастической
постановке. Следуя этому, мы перзсмотрим наши методы
и укажем подход к исследованию общеrо вида процессов
управления с адаптацией. Соответствующий мноrошаrо-
вый процесс принятия решений приводит к аналитич
ским трудностям И требует больших усилий для получения
численных решений при помощи вычислительных машин.
Эта область содержит MHoro проблем, заслуживающих
исследования.
2. Линейный процесс управпения с адаптацией
В rлаве IV рассматривалась задача о минимизации
функции критерия
N
,-, 2 2)
R N == L (и n + V n
п=о
(2.1)
по всем V n , rде
и'1+1 == аи n + v n ,
и о = с.
(2.2)
Для определения функции стратеrии и функции дохода
был применен метод функциональных уравнений. Затем
мы обратились к задаче минимизации математическоrо
ОiI идания R N , применяя управление с обратной связью,
rде и n И V N - случайные переменные, связанные соотно-
шением
и n +l == аи n + v n + r n ,
и о = с,
(2.3)
СО случайными переменными r n. Наиболее леr:ким явля-
ется случай, коrда r n - независимые случайные пере-
менные с известной общей функцией распределения; без
чрезмерных трудностей можно изучить и случай наличия
корреляций, коrда функция распределения r 11 зависит от
зна qений r п-l, rn-2,.. . ,r n -l\.
3]
АНАЛИТИЧЕСИАЯ ФОРМVЛИРОDНА
10'
Рискнем теперь отправиться дальше внеизвестность,
полаrая, что существование функции распределения из-
вестно, однако точный вид ее неизвестен. Так как интере-
сующие нас процессы не рассматривались выше, мы долж-
ны вновь точно определить, что мы имеем в виду под
оптимальной стратеrией и математическим ожиданием. На-
шей целью является обеспечить какую-либо единообраз-
ную аналитическую формулировку процессов управле-
ния, возникающих в ситуациях этоrо характера. Заметим,
что мы rоворили... «какую-либо)} единообразную форму-
лировку, а не «единообразную» формулировку. Как мы
укажем впос.ледствии, имеется MHoro путей, ROTOpblM
можно следовать, и каждый из них имеет ряд как привле-
кательных, так и непривлекательных особенностей. Эта
свобода возможно и рассеивает внимание студента, но
это часть платы за риск на пути в незнаемое.
3. Аналитическая формулировка
Мы начнем, как обычно, с упрощения. Вместо Toro
чтобы считать, что функция распределения полностью
неизвестна, предположим, что ее аналитическая струк-
тура известна, но некоторые параметры неизвестны. Так,
например, мы можем использовать rayccoBy функцию рас-
пределения с неизвестными средним значением и дис-
персией, или распределение Пуассона с неизвестным сред-
ним значением, или общее распределение Пирсона с не-
известными параметрами и т. д.
Рассмотрим сперва простейmий, пожалуй, случай,
коrда r имеет биномиальное распределение. Переменная
r принимает значение +1 с вероятностью р и -1 с веро-
ятностью (1 - р). Как указывалось в предыдущем napar-
рафе, мы, однако, не располаrаем какими-либо сведения-
ми о численном значении р, помимо очевидноrо факта,
что 0< р < 1. Мы желаем поэтому оценить р на каждом
mare на основе иоследовательности значений r, которые
появились на предыдущих marax. Это, по-видимому, це-
лесообразная процедура. В процессах этоrо типа мы стал-
Rиваемся с проблемой одновременноrо обучения и функ-
ционирования. Вместо термина «обучение», который пе-
ренасыщен психолоrическ:им содержанием, мы примем
108
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[rл. v
термин «адаптация», так как этот термин пока еще жестко
не фиксирован. Следовательно, процессы этоrо типа бу-
дем мы называть процессами управления с адаптацией.
Упрощая вновь, предположим, что достаточно просто
записать число раз, коrда +1 или -1 появлялись в прош-
лом. То, что здесь принято в качестве математическоrо
предположения, зачастую может оказаться естественным
оrраничением в том смысле, что часто на практике лишь
часть полной информации используется для принятия
решения; сбор более обширной информации может ока-
заться слишком дороrостоящим или требующим чрезмер-
ной затраты времени. С друrой стороны, может оказаться,
что дальнейшая информация относительно процесса уже
не является более необходимой. Мы вернемся ниже к
этому вопросу о «достаточных статистиках».
Соrласимся оценивать р при помощи формулы
т+1
Ртn == т + п + 2 '
(3.1)
если наблюдались т раз +1 и п раз -1. Снова вопрос,
почему принята эта процедура оценки, должен и будет
обсужден. Мы обратим'Ся теперь к вычислению математи-
ческоrо ожидания. Нашим основным предположением
является то, что мы вычисляем математическое ожидание
так, как если бы оценки вероятностей были бы действи-
тельными вероятностями в стохастическом процессе уп-
равления Toro типа, который мы уже рассматривали. Этот
стохастический процесс управления есть один из описан-
ных в (2.3) с известной функцией распределения для r.
Оптимальная стратеrия теперь определяется как страте-
rия, которая минимизирует математическое ожидание
функции критерия.
Наконец, отметим, что концепция переменной состояния
существенно расширяется. В дополнение к текущему фи-
зическому состоянию мы должны также :включать некото-
рую прошлую историю процесса. Одним из преимуществ
метода динамическоrо проrраммирования является то, что
он автоматически распространяется на эти более общие
ситуации. ы остановимся более подробно на этой идее
в последующих разделах.
]
АНАЛИТИЧЕСRИЕ АСПЕНТЫ
109
После этих предварительных указаний вернемся к
аналитическому описанию. Как и ранее, мы возьмем функ-
цию критерия npocToro аналитическоrо вида
N-l
R N =-= (и + V ) + u'fv. (3.2)
n=о
Введем функцию
tN (с, т, n) == .математичеспое ожидаuuе R N , получепuое
при пpu.мeиeпии оптu.:малъnой стратееии, nачииающейся
в состояпии с при иаблюдеиuях т раз + 1 u п раз- 1.
(3.3)
Принцип оптимальности дает функциональное уравнение
!N(C, т, n) = min [(с 2 + v 2 ) + Ртn!N-l(ас + V + 1, т +
v
+ 1, п) + (1 - Ртn) IN-l (ас + V -1" т, n + 1)] (3.4)
для N > 1, rде 10 (с, т, n) = с 2 , а Ртn вычисляется cor-
ласно (3.1). Мы.... таким образом привели изучение процес-
са управления с адаптацией к задаче получения аналити-
ческоrо или численноrо решения функциональноrо урав-
нения.
4. Анапнтичеекие аспекты
Леrко видеть, что, как и выше,
fN (с, т, n) == UN (т, n)с 2 + VN (т, n)с + WN (т, n), (4.1)
rде UN, VN и WN не зависят от с. Подставляя (4.1) в (3.4),
получим уравнение
UN (т, п) с 2 + VN (т, п) с +WN (т, n) == min [(с 2 + v 2 ) +
v
-t- Ртn (UN-l (т + 1, n) с 2 + VN-l (т + 1, п) с +
+ WN-l (т + 1, n)) + (1 - Ртn) (UN-l (т, п + 1) с 2 +
+ VN-l (т, n + 1) с + WN-l (т, n + 1))]. (4.2)
Отсюда мы вновь видим, что оптимальное управление
является линейным, и можем получить рекуррентное
соотношение для тройки [U.7V(т, п), VN (т,п), WN(m,п)J. Мы
110
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[rл. v
предоставляем это читателю для выполнения в качестве
упражнения. 11редостережем ero, однако, указав, что
определение асимптотическоrо поведен:й:я этих величин
при N -+ 00 уже больше, чем упражнение.
5. Обсуждение
Сделав определенное число преДПОJIожений при поста-
новке задачи, хотелось бы провести некоторую проверку,
некоторый контроль в наших математических эксперимен-
тах. Например, следовало бы показать, что с вероятностыо
1 вышеприведенный процесс сходится к стохастическому
процессу управления, для KOToporo р известно. Под схо-
димостью мы здесь понимаем, что оптимальная стратеrия
для одноrо процесса сходится к оптимальной стратеrии
для друrоrо и что сходятся также функции дохода. ХОТЯ
результаты 1'aKoro рода представляются ясными интуи-
тивно, cTpororo ДОI{азательства пока не дано и мы здесь
имеем обширное поле для исследований. Как увидит
читатель, не так просто использовать рекуррентные соот-
ношения, полученные соrласно (4.2), для аналитических
или вычислительных целей.
6. Априорная функция распредепення
Рассмотри:м: теперь более трудный случай, коrда мы
располаrаем априорной функцией распределения dG для
р, т."е. вероятностью для вероятности. Как следует видо-
изменить эту функцию распределения на основе наблю-
дений над процессом? Соrласимся вновь применить ме-
тод Байеса для рассмотрения и обсуждения этоrо вопроса.
Если из наблюдения над r получена величина +1, то мы
заменяем dG новой функцией распределения
dG+ = ac (р) (6.1)
S pdC
о
а если паблюдалась величина -1, то мы пользуемся
следующей функцией распределения:
dG_ = (11 - р) ас (р) . (п .2)
5 (1 - р)ас
о
7]
иrРА с АДАПТАЦИЕЙ
111
Интересно, что здесь вновь достаточно только сохра-
нить след числа плюсов и минусов в значении r. Не обя-
зательно, в частности, указывать зависимость от dG (r).
Если мы возьмем dG (r) == dr, то функциональное урав-
нение в точности совпадает с уравнением (3.3) и правило
для вычисления Ртn сведется к полученному в разделе
3 правилу (3.1).
Имеются различные пути для обоснования преобразо-
ваний (6.1) и (6.2), базирующиеся на теории иrр и ста-
тистических решений. Однако эти обоснования требуют
еще дальнейшеrо обоснования и т. д. Мы лишь предста-
вим наши предположения в более удобном виде.
7. Иrра с адаптацией
Вернемся теперь к задаче об иrроке, использующе"VJ:
несовершенный канал связи, задаче, которой мы уделили
некоторое место в rлаве IV. Предположим теперь, что
иrрок даже не знает вероятности Toro, что сиrнал будет
передан неправильно, но он знает, что вероятность эта
существует и не меняется со временем. Сформулируем за-
дачу оптимальноrо проведения иrры в вышеприведенных
терминах.
Как и выше, мы можем постулировать априорную
функцию распределения dG (р) для р и соrласиться,
в соответствии с формулами раздела 6, преобразовать
dG (р) в
dG тп (р) ===
рт (1 - р)n ас (р)
1
S рт (1 - р)n dC (р)
о
(7.1)
после Toro, как отмечено т успешных иrр и n неуспешных.
Если мы обозначим
/N (х, т, n) = математичеСt;ое ожидание 10gXN при
начальnом t;аnитале х и информации, что до сих пор
и.мелось т успехов и n nеудач, и применении оптимальной
политu и, (7.2)
то мы получим уравнение
/N (.т, 7n, п) === шах [Ртn!N-l (х + у, т + 1, n) +
y x
+(1-Ртn)!N-l(Х-У, т,п+l)], (7.3)
112
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕй
[rл. v
rде
/1 (х, т, n) == шах [Ртn log (х + у) + (1 - Ртn) log (х - у)].
o y<x
(7.4)
Нетрудно, как и выше, по казать по индукции, что
fN (х, т, n) = log х + CN (т, п), (7.5)
rде CN (т, n) удовлетворяет линейному рекуррентному
соотношению довольно сложноrо вида. Тем не менее оп-
тимальная политика имеет еще простой интуитивный вид
{ (2Ртn - 1) х,
У==
О
1
если Ртn >2'
в друrом случае,
(7.6)
1
rде Ртn = pdGmn. Таким образом, структура оптималь-
о
ной политики не изменилась даже в условиях большей
неоnpеделенности.
УпражнеНN.
1. Покажите, что если dG (р) = ра-l(1 - p)h- 1 dp/B (а, Ь),
rде В(а, Ь) есть бета-функция, то
т+а
Ртn == т + а + п + ь '
и что после т выиrрышей и п проиrрыmей ставка иrрока составляет
долю ero капитала, равную
«т + а) - (n + Ь)) / (т + а) + (п + Ь).
2. Если функция критерия есть XN' а > О, то каковы функ-
ция дохода и оптимальная политика?
8. Задача О ДВУРУКОМ бандите
Продолжая в этом направлении, обсудим теперь зада-
чу, которая возникала в работе У. Р. Томпсона при ис-
п танuи новых лекарств. С тех пор она приобрела коло-
а1
ЗАДАЧА О двуруном БАНДИТЕ
113
ритное название, данное позже, и в связи с этим мы вместо
лекарств рассмотрим иrральные автоматы *).
Предположим, что мы имеем два иrральных автомата,
один с известными свойствами и друrой с неизвестными
свойствами. Rоrда рукоятка первоrо автомата включена,
имеется известная вероятность S получения доллара;
коrда иrрает второй автомат, имеется фиксированная, но
неизвестная вероятность р успеха. Предполаrается, что
процесс имеет следующий вид. Мы испытываем второй
автомат несколько раз, чтобы определить результаты,
и тоrда решаем, пользоваться ли нам первым автоматом.
Интуитивно ясно, и это можно леrко показать, что, ре-
шив однажды пользоваться автоматом с известными ха-
рактеристиками, мы никоrда не вернемся к автомату с
неизвестными свойствами. Однако возможно также, что
мы никоrда не обратимся к первому автомату.
Чтобы упростить анализ и проиллюстрировать при-
мепение функции критерия, которой мы до сих пор не
пользовались, предположим, что мы желаем максимизи-
ровать математическое ожиданnе
00
R = anz n ,
n=о
(8.1 )
rде О < а < 1 и zn обозначает доход, полученный в n-м
испытании. Если, как и выше,
fmn = матем,атич,ес ое ожидаиие дохода при оnтuжалъ-
пой политик,е после т успехов и n nеудач, oтopыe
паблюдалuсъ при uере па втором автомате, (8.2)
и dG (р) обозначает априорную функцию распределения
для р, то мы леrко получаем функциональное уравнение
! [ (1 + а!т+l,n) Ртn + а (1 - Ртn) !т'n+l)
тn = шах S / (1 - а) ,
(8.3)
*) Следствие большей близости Лос-Авжелоса к Лас Beracy,
чем к Рочестеру, штат Миннесота. [В обиходной американской
речи иrральные автоматы часто называют «одноруким» и «дву-
руким бандитом», в зависимости от числа рукояток. (При"",. ред.)].
114
ПРОЦЕССЫ УПРАВЛЕНИЯ САПАДАПТАЦИЕЙ
[rл. v
rде вновь
1
S рт+l (1 - р)n dC (р)
о
Рт,n == 1
S рт (1 - p)ndC (р)
()
(8.4)
Соотношение (8.3) может быть использовано для даль-
нейmеrо изучения струнтурных свойств оптимальной по-
литики или для получения численноrо решения. Предос-
тережем читателя, что определение CTpyHTypIJI оптималь-
ной политики является делом нслеrким.
9. Общая формулировка
Теперь, после обсуждения трех частных случаев в раз-
делах 2-8, мы в состоянии дать общую формулировку
процессов управления с адаптацией, которые рассматри-
вались нами. Мы предполаrаем, что
Рl == Т (р, q, ')' (9.1)
rде, :как обычно, р - переменная состояния, q - пере
менная, относительно которой принимается решение, r -
случайная переменная с фиксированной, но неизвестной
функцией распределения. Пусть dG (r) - априорная оцен-
ка дяя этой пеизвестной функции распределения. Физиче...
ским состоянием является р, по состояние управляемоrо
процесса есть пара (р, G).
Нашей целью является применение стратеrии управ-
ления, :которая максимизирует математичесное ожидание
функции критерия
R N = g (р, ql, rl) + g (Рl' Q2, r 2 ) + ...+ g (PN-l, QN, rN).
(9.2)
Для Toro чтобы точно поставить задачу, выразим явно
паши предположения.
Мы Jftожем наблюдать состояиuе cucтeMЪ па аждО.А1J
ша2е. (9.3а)
Н а аждом шаее мы рассматриваем априорпую оцеll1СУ
a uстuuпую фуп цию распределепия. М атематичеС 1J,е
ожидапuя получаются па этой ОС1l0зе. (9.3Ь)
10]
ЗАДАЧА ОЦЕНИВАНИЯ:
115
у пас имеется систе.матичес ая процедура для .моди....
фu ации этой априОрl-l0Й фуп1iции распределепия, по мере
тоео Кta.,., раавертЬLвается процесс; эта процедура сажа по
се-бе .может быть процедурой с адаптацией. (9.3с)
В результате выбора q1 мы имеем: преобразования
Рl = т (р, Q1, r 1 ), "\ (9.4)
dC 1 (r) == S (r; р, Q1, rl, С), (
что l\IOjHHO выразить так: новая функция распределения
нависит от старой функции распределения, от величины
'1, которая получена из наблюдений, от начальноrо сос-
тояния р, HOBoro состояния Р1 И решения ql.
Пусть
JN (р, G) == жатежатичес ое ожидапие R N , получепuое при
оптижальuой стратееии, пачатой в состояпии (р, G). (9.5)
Тоrда принцип оптимальности дает функциональное
уравнение
/N (р, G) = П: Х [ [g (р, Ql, r 1 ) +
+ !N-l (Т (р, Q1, r 1 ), G 1 )] dG (r 1 )), (9.6)
rде G 1 является таной же, нан в (9.4), для N > 2, а для
N == 1 мы и: еем
/1 (р, G) = т x [ g (р, Ql, r1) dG (rl)]' (9.7)
Не очень трудно записать эти соотношения, но боль-
шие трудности представляет получение аналитических
или численных результатов из этих уравнений.
10. Задача оцениваниSl
Подчеркнем, что в силу предположения (9.3с) мы обош-
ли одну из фундаментальных трудностей, связанных с
процессами с адаптацией, именно задачу оценивания.
Существенной частью процесса управления с адаптацией
116
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[rл, v
является процесс обучения, обеспечивающий оптимальное
использование информации по мере ее поступления. Как
следует модифицировать априорные предположения на
основе опыта?
Мы применяли байесову процедуру оценивания по при-
чине ее простоты и интуитивноrо характера. Нет основа-
ний считать, что эта процедура является оптимальной
процедурой оценивания во всех случаях; наоборот, можно
быть уверенным, что это не так. Ссылки на некоторые
работы в этом направлении приводятся в конце rлавы.
11. От функционаnО8 к функциям
Соотношение (9.6) может быть использовано для уста-
новления теорем существования и единственности, для
определения структуры оптимальных стратеrий и изу-
чения их асимптотическоrо поведения. Менее полезно
оно для вычислительных целей вследствие появления
функционалов. Поэтому введем хорошо известную кон-
цепцию «достаточных статистик». Мы предположим, что
G (r) принадлежит к семейству распределений G (r, а),
rде а теперь конечномерный вектор, и что результат вы-
числительной процедуры, подразумеваемой в (9.3с) и
(9.4), состоит в замене а на а 1 , тде а1 зависит от а, '1, р
И qt.
В этом случаff fN(P, G) заменяется на fN(P, а) и (9.6)
принимает вид
/N (р, а) = тах [ [g (р, Ql, rl) +
qt J
+ fN-1 (Т (р, Q1, rl), аl)] dG (r 1 »), (11.1)
rде а 1 = Н(а, р, Q1, '1), а функция Н фиксирована. Этот
метод был нами применен в трех рассмотренных выше
примерах.
12. &onee общие процессы с адаптацией
Мы никоим образом не исчерпали пределов неопреде-
ленности. Во-первых, мы можем рассмотреть случай,
котда преобразование (9.1) содержит фиксированные, но
БИБлиоrРАФИЯ: ИНОММЕНТАРИй
117
неизвестные параметры, скажем,
Рl = Т (р, q, " Ь),
(12.1)
вновь с априорной функцией распределения. Во-вторых,
мы можем предположить, что р само по себе не может
быть точно определено на каждом mare и что известна
лить функция распределения для р. В-третьих, мы мо-
жем предположить, что цель процесса вначале не совсем
ясно определена. Наконец, мы можем поставить задачи
исследования как при наличии, так и при отсутствии
стохастических воздействий, скрытых переменных, а
также при наличии воздействий враждебноrо характера.
Ясно, что имеет большой смысл попытка формулировать
,
на этом уровне теории управления, что мы подразуме-
ваем под оБЩИ 1: видом процесса управления с адапта-
цией. Лсно также, что имеется безrраничная область
ДЛЯ проявления воображения и таланта в этих вопросах
и для каждоrо, кто заинтересуется этими вопросами,
откроется обширное поле деятельности.
6ибпиоrрафиSl и комментарии
1. Дальнейшее обсуждение и ссылки см. в следующих книrах:
Р. Б е л л м а н, Процессы реrулирования с адаптацией.
«Наука», 1964.
А. А. Ф е л ь Д б а у М, Основы теории оптимальных автома-
тических систем, «Наука».. 1й66.
J. Т. Т о u, Optima1 Design of Digital Contro1 Systems,
Academic Press Inc., New York, 1963.
А. В а л ь д, Последовательный анализ, Физматrиз, 1960.
2. Процессы этоrо типа обсуждаются в
М. F r е i m е r, А Dynamic Programming Approach to
Adaptive Control Processes, Linco1n Laboratory, 1959; a1so
published in IRE Trans., vol. АС-4, 1959, рр. 10-15.
7.
Эти результаты получены в
R. В е 11 m а n and R. !{ а 1 а Ь а, Dynamic Programming
and Statistical Communicatiol1 Theory, Proc. N at. Асад. Sci.
USA, vol. 43, 1957, рр. 749-751.
R. В е 11 m а n and R. К а 1 а Ь а, Оп the Role of Dynamic
Programming in Statistical Communication Theory, IRE
Trans. оп Information Theory, vol. IT-3, 1957, рр. 197-203.
118
ПРОЦЕССЫ УПРАВЛЕНИЯ С АДАПТАЦИЕЙ
[rл. v
н. В е 11 m а n and 1(. К а 1 а Ь а, Оп Communication Pro-
cesses Involving Leal'ning апд RaIldom Dиrаtiuп, IRE Natio-
nal Contention Record, Part IV, 1958, рр. 16-20.
8. CML
,v. !{. Т h о m р s о п, Оп the LikelilH)od tllat Опе lTnknown
Probability Exceeds Another in V ie\v of the Evidence of T\vo
Samples, Biometrika, vol. 25, 1933, рр. 285-294.
\у. Н. Т h о m р s о п, ОП the Tlleory of Apportionment,
Amer. J. Math._, vol. 57, 1935, рр. 450-45(1,
В. В е 1 1 m а п, А Problem in tlle SеЧLlепtiаl Design of Ех-
perimel1ts, Sankhya, vol. 16, 1956, рр. 221-229.
РU1Шрд Белл.м.ан
Роберт Iiалаба
Динамическое проrраммирование
и совремзнная теория управлениq
М., 1969 r., 120 стр. с илл.
Peдal\Тo р д. С. фур.м.а1iО]
Техн. редактор и. ш. А1lсельрод
Норректор В. п. COr;Oпu1ia
Сдано в набор 20/111 1969 r. Подписано 1{ печати
9ДХ 1969 r. Бумаrа 84Х1()8 1 / 12 Физ. пе'l. л. 3,7:>
Условн. ПВ!!. п. 6,3 уq.-изд. л 5,73
Тираж 185ЗО экз. Цена Rниrи 42 коп.
Заказ М 2048
Издательство «Наука»
rлавная: редаI<ЦИfI
Физико-матз аТАЧ(СI<ОЙ литературы
l\IocKBa, В-71, Ленинский вроспект, 15.
2-н типоrрафия издательства «Наука»
Моснва, mуБИНСI{ИЙ пер., 10