ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
— методы, непосредственно использующие рекуррентное соотношение Веллмана для построения оптимального поведения в многоэтапных задачах.
Рекуррентное соотношение Веллмана имеет вид
где 
— состояние процесса, D — мн-во состояний, q — управление, 
мн-во возможных управлений в состоянии 
оператор перехода при применении управления 
— ф-ция дохода за один шаг, N — число шагов, 
значение ф-ции критерия, определяемое при осуществлении оптим. поведения на m шагов процесса, если его начальное состояние 
. Из рекуррентных соотношений следует, что точное решение задачи программирования динамического можно получить лишь в том случае, если мн-во D является конечным. Пусть число элементов мн-ва D равно 
, число элементов в каждом из 
не превышает I. Тогда на каждом шаге процесса динамического программирования мы должны использовать соотношение (1) не более 
раз. Однократное использование этого соотношения требует вычисления сумм вида
не более I раз. Пусть с — верхняя граница числа операций для вычисления выражения (3). Тогда общее число операций можно приближенно оценить сверху величиной 
при этом требуется память порядка 
ячеек. Если мн-ва 
и (или) мн-во D являются бесконечными, то эти мн-ва аппроксимируются некоторыми мн-вами с конечным числом элементов. Если мн-во D представляет собой некоторое компактное подмн-во эвклидова пространства, то для получения дискретной аппроксимации этого подмножества можно ввести в этом пространстве некоторую дискретную сетку, узлы которой, принадлежащие D, образуют аппроксимирующее мн-во. Однако этот способ эффективен лишь для задач, в которых размерность мн-ва D не превышает трех, т. к. при большей размерности для получения приемлемой точности решения аппроксимирующее мн-во должно содержать слишком большое число узлов. Эти трудности частично преодолеваются с помощью метода множителей Лагранжа, когда удается путем включения части ограничений аддитивного типа в функционал с неопределенными множителями уменьшить размерность пространства состояний. Если ф-ции g (р, q) вогнуты по р, q, то удается уменьшить время счета путем более эффективного поиска максимума в соотношениях (1), (2).
Лит. см. к ст. Программирование динамическое.
Н. З. Шор
