Автоматика и телемеханика, Л- 9, 2006
РАС Б 02.60.Pri
© 2006 г. Л.К. ЛЕВИТ-ГУРЕВИЧ, канд. техн. наук, Д.М. ЯРОШЕВСКИЙ, канд. техн. наук (Институт водных проблем Российской Академии наук, ИБП РАН, Москва)
СХЕМА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С МНОГОМЕРНОЙ ИНДЕКСАЦИЕЙ ШАГОВ
Рассматривается обобщение классической схемы динамического программирования с вычислениями по одной последовательности шагов па те случаи, когда выделено несколько последовательностей, пронумерованных своими индексами. и решение па каждом шаге алгоритма зависит от результатов, полученных па предыдущих шагах каждой из этих последовательностей. Дапы обобщения уравнений Беллмапа, приведены доказательства, оценивается вычислительная сложность алгоритмов, показаны приемы компьютерной реализации, указаны прикладные проблемы, формализация которых приводит к задачам динамического программирования с многомерной индексацией шагов.
1. Введение. Классическая схема
Схема динамического программирования удовлетворяет положениям многоша-говости процесса решения, аддитивности целевой функции и отделимости ограничений [1]. Предполагается, что состояние объекта полностью характеризуется «.-мерным вектором Р = (р1,р2, • • • ,Рп) Пространство век торов Р называется пространством состояний, или фазовым пространством. Многошаговость означает возможность разбить исходную задачу на N этапов (шагов), где на к-м шаге, к = 1, М, осуществляется переход от значения Р(к-1) к Р(к). Вычислительная эффективность такой процедуры выражается в том, что структура задачи позволяет на каждом шаге использовать относительно простое уравнение состояний
(1.1) р(к) = Ек_1 (р(к-1), д£_1) •
Используются также обратные к (1) вектор-функции:
(1.2) р(к-1) = (р(к), , дк- = (р(Ч Р(к-1)) •
Здесь дк-1 = (Я, • • •, Ят)""""" т-мерный вектор управления на к-м шаге при переходе от Р(к-1) к Р( к); Е^^ _ «мерные, ^к-1 ^ т-мерная вектор-функции. Пошаговая оптимизация базируется на том, что Р( к) зависит только от Р( к-1).
"Цена" перехода от Р(к-1) к Р( к) при управлении д 1к-1 на, к-м шаге, к = 1,М, с учетом (1.1) имеет вид
(и) ^-1 (р( к-1), д к-1) = (р( кк-1 (р( к), р( к-1))) = = (р( к-1), р( к)) •
Аддитивность целевой функции С "стоимости всех шагов к = 1, N означает, что
N
(1.4) C(Ф, Ф) = £ Sk-1 (P(fc-1), Qk-J,
к = 1
причем последовательность Ф = {Р(0), Р(1),..., Р(№значений фазовых векторов принято называть фазовой траекторией, а последовательность Ф = {Со, С2,... ..., Ср^— 1} управляющих векторов - управлением. Ограничения на фазовую траекторию и управление имеют вид
(1.5) Р(к) е Пк, к = 1, N - 1; Р(0) е По; Р(№} е ;
(1.6) Ск-1 е вк_1, к = 17ж,
где Пк - заданные подмножества п-мерного пространства фазовых переменных, а вк_^ то-мерного пространства управляющих векторов. При к = 0 и к = N ограничения (1.5) называются соответственно начальными и конечными условиями. Ограничения (1.5) и (1.6) задаются индивидуально для каждого шага и не зависят от других шагов (отделимость).
Классическая формулировка многошаговой задачи оптимизации имеет вид: найти оптимальное управление Ф и оптимальную траекторию Ф, при которых целевая функция (1.4) достигает минимума при условиях (1.1), (1.2), (1.5), (1.6). Согласно принципу оптимальности Беллмана любая завершающая часть
Фк
(P (fc)j = { P (fc), P(fc+1)* , P(fc+2)* p(N Г}
оптимальной траектории Ф, начинающаяся с (к + 1)-го шага, к = 0, N — 1, при достигнутом состоянии Р(к) оптимальна для остающихся шагов. Пусть за к шагов получено состояние Р(к). Рассмотрим аналог задачи (1.1)—(1.6) для оставшихся ^ — к) шагов. Для этого аналога ищется условны оптимальное управленне Ф^ =
= ЫСк—1,..., -1} и траектория Фк (Р(к)*) = ЫР(к)*, Р(к+1)*,..., Р(№ Г }, когда целевая функция
N
C (фй(P(k)), *fc) = £ S^-1 (P(^-1), Q£_i)
Р(к)
ция Беллмана последних N — к шагов
N
(1.7) Bfc(P(k))= min ]Г (P(^-1), Q^-Л
M=fc+1
где минимум берется по всем Фк+1 = {Qk+\ • • •, QM-1}) удовлетворяющим (1.6). Функции Беллмана связаны между собой уравнениями
(1.8) Bn (P(N)) =0; Bn-1 (PN-1, QN-1) = N minn SN- (p(N-1), QN-1);
V } QN-1£0N-1 v }
_>N PflN
1
(1.9) Bfc (P(fc)) = min kfc+1 (P(fc), Qk+Л + Bfc+1 (P(fc+1))
V ) Qk+1eek+1,P(k+i)enfc+J k V k j + V )
k = N - 2,0.
Фактически, в (1.9) функция Bk+1 в соответствии с (1.1) определяется состоянием P(k) и у правлен нем Qfc- :
Bfc+i (P(k+1)) = Bfc+i [ffck+1 (p(k), Qk+1)] = Bfc+i (p(k), Qk+1) , (1.10) Bfc(P(k)) = ^mm^ {St+1 (P(fc), Q^+1) + Bfc+1 (p(k), Q^+1) } ,
N - 1,0.
Функцию Белтмана Вк+1 (Р(к+1)) на к-м шаге оптимизации назовем генератором функции Вк
Р(к)
т)
задачи последовательно находить все функции Вк
Р(к)
и условно оптимальные
управления СС к+1 "ходом паз ад" к = N — 1,0 начиная с Р(№) = П^. Затем на втором этапе па основе функции В0 (Р(0)), начиная с Р(0) = П0 проводится выбор непосредственно оптимальных траектории
Ф о (P(0)) = { P(0), P(1)P(N)}
и управлении
Ф о =
Q01; Q1 ; • • • ; QN-1 }
"ходом вперед", используя рекуррентное уравнение (1.10) и обратные к (1.1) уравнения (1.2).
2. Двумерная индексация шагов
Пусть шаги оптимизации пронумерованы в двух измерениях: к1 = и к2
1, N2. Процесс оптимизации можно отобразить на двумерной сетке
(0,N2) •••
(0,1) (1,1) (0, 0) (1, 0)
(N1,N2)
(N1,0)
в каждом узле (к1; к2) которой состояние объекта характеризуется вектором Р(к1,к2)5 так что состояние объекта во всех узлах сетки описывается фазовой матрицей
Фо.о^0'0))
P(0,N2) p(1,N2)
P(0,1) р(1,1) р(0,0) р(1,0)
p(Ni,N2)
P(Ni,1) p(Ni,0)
а переходы к состояниям Р(к1'к2) в узлах (к1?к2) связаны с заданием соответствующей матрицы управления Ф0,0. На рассматриваемой сетке выделяются клетки (к1 — 1,к2) (кьк2) )' (к1 — 1, к2 — 1) (к1, к2 — 1) стоянию Р(к1,к2) на (к1,к2)-м шаге в соответствующей клетке осуществляется из совокупности состояний Р(к1-1,к2) и Р(к1,к2-1)#
Уравнения состояний и обратные к ним уравнения принимают вид системы усло-(2-1)
р(к1,к2) — рк1 ,к2 ^р(к1—1,к2) 0к1,к2 ^ р(к1 ,к2) — Рк1,к2 (р(к1,к2 — 1) 0к1 ,к2 ^
р(к1-1,к2) _ /р(к1-1,к2-1) 0к1-1,к2 \ р(к1 ,^2 —1) — рк1,к2-1 /р (к1—1 ,к2 — 1) 0к1,к2-1 V
(
р(&1- 1,Й2- 1) _ 1,^2 /р(к1-1,^2) 0к1 —1,^2 \ р(^1-1,^2-1) — —1 /р^,^—1) 0к1,к2 —1 ^ к1— 1 ,к2— ^\ ' 1^2-1) ' к1—1,&2—1\ ' 0&1— 1,к2—1/'
р(к1—1,к2) — А ,к2 /р(к1,к2) 0к1,к2 \ р(к1,к2 —1) — *к1,к2 —1 /р(к1,к2) 0к1,к2 V
к1—1,к2 \ >0к1 —1,&2/ ' к1,к2 —1 \ '0к1,к2 —V '
(
1,к2 _ „к1 —1,^2 \р 'р 0к1,к2 — 1 _ ^1— 1,к2 \р 'р
0^:1—1^2 _ „^1—1,^2 /р(к1-1,^2) р(^1-1,^2- 1А 0^1,^2 — 1 _ „к1,к2 —1 /р(к1,к2-1) р(к1—1,к2—1)^ 1,^2-1 „к1—1,&2—1\ ' /'0к1—1,^2—1 „к1-1,к2-1\ ' /'
где дк1-к2 к2, дк1'к2-1 - т~мериые вектора управления на (к1? к2)-м шаге, Е^ — к2,
Ек1 ; к2 Ек 1-1, к2 Ек1;к2-1 ок 1-1, к2 о к1, к2-1 о к1, к2-1 г к1 ,к2 _«.мрП„ьТр
Е к1, к 2-1' Е к 1 — 1, к 2 — 1' Е к1-1, к2-1> 1 к1-1, к2-1> 1 к1-1, к2-1> 1 к1, к 2-1' ^ к1-1, к2 «мерные,
к 1, к2 к 1, к2 к1, к2-1 к1 — 1, к2 1
^к 1, к 2 — 1' ^к 1-1, к^ ^к1-1, к2 — 1' ^к1-1, к 2 — 1 «-мерные вектор-функции.
Для компактности изложения всю совокупность параметров состояния Р( к1'к2)
Г (к1 — 1,к2) (к15к2) 1 ,, _к! к2
в пределах клетки < — 1 к2 — 1) (к1 к'2 — 1) | 0"03начим чеРез ^к1-1 к2-1,
совокупность управлении через ^к1—1к2-1, а совокупность уравнении системы (2.1) (2.3) как
(2.4) Ек1 -к?,к2-1 (ок1—к2,к2-1, Ск1—к2,к2-0 = ° ( к1 , к2 )
ск1,к2 = ок1,к2 (р(к1 — 1,к2) дк1,к2 \ , ок1;к2 /'р(к1,к2-1) дк1,к2
= °к1-1,к2 , дк1-1,к^ + °к1-1,к2 , дк1,к2-1
Учитывая двумерную отделимость ограничений, задача с двумерной индексацией шагов формулируется следующим образом:
(2.5) с(ф, *) = £ ]Г ок1—^ (р(к1—1-к2), дк1—к2,к^ + к1 = 1 к2=0
N1 N2
+ Е Е (р(к1-к2—1), дк1;к2-0 - т1П'
к1 =0 к2 = 1 к1 ;к2 / Т~»к1;к2 г-1к1;к2
(2.6) Ек1 —1;к2-1 (Вк1— 1;к2-1, Ск1—1;к2-0 =°; к1 = 1,М1, к2 = 1,М2,
(2.7) Р(0;0) е П0;0, Р(к1;к2) е Пк1;к2, к1 = 17Ж, к2 = 17М2, р(Nl;N2) е ПNl;N2,
(2.8) дк1—2;к2 е ©к1—к2;к2, дк1—2;к2 е ©к1—к2;к2, к1 к2 = т
Принцип оптимальности Беллмана для задачи с двумерной индексацией шагов формулируется следующим образом: для прямого хода оптимизации, описываемого
оптимальной фазовой матрицей Фо,о (Р(0;0)), любой завершающий процесс при достигнутом состоянии объекта Р (к1;к2) в узле (к1? к2), начинающийся с (^ + 1, к2)-го и (&1, к2 + 1)-го шагов, т.е. шагов (к1? к2) ^ (к1 + 1, к2) и (к1? к2) ^ (к1? к2 + 1), оптимален для остающихся шагов, т.е., если на шаге (к1, к2) получено значение Р (к1;к2), то правый верхний блок пересечения строк к2, к2 + 1,..., N2 и столбцов к1 ,к1 + 1,..., N1 матрицы Ф0;0 (Р(0;0)) является оптимальной матрицей Фк1;к2 ^Р (к1,к2)^ с образующим узлом (^1, к2):
р (0,N2) р (к 1,) р(Nl;N2)
Ф 0,0(Р(0,0) ) = р (към р ^к)
Р(0,0) . . . р (N1,0)
Ф к1;к2 (Р (к1;к2) = Р ( к 1, ) Р(Й1,Й2) р(Nl;N2) Р
Назовем этот блок условно оптимальным блоком Фк1 ;к2 (р(к1,к2)) для обратного хода оптимизации, зависящим от р(к1,к2). Сформулированный принцип оптимальности для задачи с двумерной индексацией шагов не так очевиден, как в классическом случае: доказательство его вынесено в Приложение 1. Важно следствие сформулированного принципа оптимальности: если у двух условно оптимальных блоков
Фк1 ,/Ц (Р^1 ;к2^ и Фк1',к2' ^Р^1 ;к2)^, появившихся при обратном ходе оптимизации,
существует общее значение Р(к1,к2) в общем для них узле {к1, к2}, то в оба эти блока полностью входит условно оптимальный блок Фд^,^ (Р(к1;к2)). Заметим, что не все условно оптимальные блоки обратного хода оптимизации имеют подобное условно оптимальное "пересечение" в общих узлах из-за несовпадения значения фазовых состояний в этих узлах, за исключением разве значения р(№^2) узла {N.,N2}, с которого начинается обратный ход.
Итак, пусть на первом этапе расчетов пошаговый процесс оптимизации выполняется "ходом назад" от конечного состояния р№^2). Тогда функцию Беллмана последних (N1 — к1 + 1) х (N2 — к2 + 1) — 1 шагов, пройденных уже "ходом назад" по двум измерениям (в любой последовательности), можно определить как
(2.9) Вк1М (Р(к1-*2)) =шш
N1-1 N2
Е^ <?М1 + 1,М2 (р(м1 + 1,м2) ПМ1 + 1.М2
М1 = к1 М2 = ^2
N1 N2-1
+ Е Е «2+1 (Р(—+1),
М1=к1 М2 =^2
где миним
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.