Принцип динамического программирования. Основные рекуррентные соотношения динамического программирования

Метод динамического программирования – один из основных математических методов оптимизации. При его реализации одновременный выбор значений большого числа переменных решаемой экстремальной задачи заменяется поочередным определением каждой из них в зависимости от возможных обстоятельств. Процедуру выбора значений переменных будем трактовать как многоэтапный процесс управления некоторой системой. Далее объект Ω именуем дискретной управляемой системой, если множество его возможных состояний конечно и управления в нем осуществляются в дискретном времени, пошагово; каждое управление заключаются в применении одного из конечного числа возможных воздействий; результатом любого воздействия является изменение состояния системы. С каждым изменением состояния системы связываем платеж (доход или расход); полагаем, что величина платежа на любом шаге зависит от текущего состояния системы и применяемого управляющего воздействия. Начальное состояние системы считается заданным. Определено также множество финальных состояний (достигнув финального состояния, система прекращает функционировать).

Каждая последовательность управлений, переводящая систему из начального в одно из финальных состояний, фактически определяет некоторую полную траекторию движения системы. Требуется найти полную траекторию, оптимальную по значению суммарного платежа, т.е. обеспечивающую максимальный суммарный доход или минимальный суммарный расход. Возможно и другое требование – найти полную траекторию с минимальным значением максимального из пошаговых расходов (максимальным значением минимального из пошаговых доходов).

Формально дискретную управляемую систему определяем как совокупность

Ω = {D; x₀; F; V (x), f (х, v), s(х, v)},

где D – множество состояний системы (множество D конечно);

x₀ – начальное состояние;

F – множество финальных состояний, x₀ Î D, x₀ Ï F, F Ì D;

V(x) – конечное множество возможных в состоянии х управлений, x Î D\F;

f(х, v) – функция переходов (из состояния x под воздействием управления v система переходит в состояние f(х, v)), x Î D\F, v Î V(x), f(х, v) Î D;

s(х, v) – функция платежа, здесь x Î D\F, v Î V(x);

значения функции платежа считаются неотрицательными.

Состояние x системы Ω называем промежуточным, если оно не является ни начальным, ни финальным. Конечную последовательность Т = {x⁰, x¹, x², …, xⁿ} состояний системы Ω именуем траекторией системы, если выполняются условия:

x^t = f(x^{t− 1}, v^t),

где v^t Î V(x^{t− 1}), t = 1, 2, …, n.

Состояние x⁰ – начальное состояние траектории Т, а состояние xⁿ – ее конечное состояние. Состояния x², x³, …, x^{n− 1} из Т являются промежуточными состояниями данной траектории.

Траекторию называем полной, если начальным ее состоянием является начальное состояние системы Ω, а конечным – одно из финальных состояний этой системы. Таким образом, для полной траектории Т = {x⁰, x¹, x², …, xⁿ} имеет место x⁰ = x₀ и xⁿ Î F.

Траекторию Т = {x⁰, x¹, x², …, xⁿ} называем заключительной x-траекторией, если x⁰ = x и xⁿ Î F.

Заключительная x-траектория, имея своим начальным состоянием произвольное состояние x системы Ω, заканчивается в одном из финальных состояний системы.

Траекторию Т = {x⁰, x¹, x², …, xⁿ} называем начальной x-траекторией, если x⁰ = x₀ и xⁿ = x. Начальная x-траектория, имея своим конечным состоянием x, начинается от начального состояния системы.

На множестве состояний системы Ω введем бинарное отношение достижимости Р(х, у): считаем, что произвольные состояния х и у удовлетворяют этому отношению, если существует траектория Т, имеющая своим начальным состоянием х, а конечным – состояние y. Отметим, что введенное бинарное отношение обладает свойствами

рефлексивности (для любого состояния х имеет место Р(х, х))

и транзитивности (для любых x, y, z из того, что имеют место Р(х, у) и Р(y, z) следует, что имеет место и Р(х, z)).

Дополнительно предполагаем, что отношение Р(х, у) антисимметрично (из Р(х, у) и Р(у, х) вытекает х = у). Антисимметричность бинарного отношения достижимости означает, что в любой своей траектории система не может реализовывать циклы (возвращаться в состояния, в которых она уже была). Обладая свойствами рефлексивности, транзитивности и антисимметричности, бинарное отношение Р(х, у) является отношением частичного порядка.

Состояние х системы Ω именуем достижимым, если имеет место Р(х₀, х). Отметим, что начальное состояние х0 достижимо по определению. Состояние х системы Ω именуем продуктивным, если для некоторого финального состояния w имеет место Р(х, w). Финальные состояния системы продуктивны по определению. Недостижимые и непродуктивные состояния системы Ω можно изъять из рассмотрения; далее, как правило, будет считаться, что каждое состояние системы достижимо и продуктивно. При реальном исследовании систем, порождаемых конкретными оптимизационными задачами, вопрос выделения состояний, являющихся одновременно достижимыми и продуктивными, заслуживает отдельного анализа. Избавление от недостижимых и непродуктивных состояний способствует сокращению объемов выполняемых вычислений.

Пусть Т = {x⁰, x¹, x², …, xⁿ} – произвольная траектория системы Ω, причем x^t = f (x^{t− 1}, v^t), где v^t Î V (x^{t− 1}), t = 1, 2, …, n.

Стоимость С(Т) траектории Т определяем следующим образом:

Таким образом, стоимость траектории – это сумма пошаговых платежей, имеющих место при реализации траектории.

Центральной является задача построения полной траектории, оптимальной по значению суммарной стоимости, т.е. обеспечивающей максимальный суммарный доход или минимальный суммарный расход. Обе экстремальные задачи по способу решения идентичны. Для определенности проблему формулируем следующим образом.

Задача А. Для системы Ω найти полную траекторию Т минимальной стоимости.

Дополнительно введем в рассмотрение совокупность частных задач А(x), где x принадлежит D\F.

Задача А(x). Для системы Ω и ее состояния x найти заключительную x-траекторию минимальной стоимости.

Решения сформулированных экстремальных задач А и А(x) именуем оптимальной полной траекторией и оптимальной заключительной x-траекторией соответственно.

В основе метода динамического программирования лежит принцип оптимальности, сформулированный американским математиком Ричардом Беллманом следующим образом: «Оптимальное поведение обладает тем свойством, что каковы бы ни были первоначальное состояние и решение в начальный момент, последующие решения должны составлять оптимальное поведение относительно состояния, являющегося результатом первого решения».

Следующая теорема выражает принцип Беллмана в применении к задачам построения оптимальных траекторий.

Теорема 1. Если полная траектория Т= {x⁰, x¹, x², …, xⁿ} оптимальна, то любая ее заключительная часть Т_k = {x^k, x^k+1, …, xⁿ} также оптимальна.

Теорема легко доказывается методом от противного. Предположим, что траектория Т= {x⁰, x¹, x², …, x^k, x^k+1, …, xⁿ} оптимальна, а ее заключительная часть Т_k = {x^k, x^k+1, …, xⁿ} оптимальной не является. Стоимость траектории Т представим как

С(Т) = P + Q, где

Оптимальную заключительную x^k-траекторию запишем в виде

T_k¹ = {у_k, y^k+1, …, у^m}, здесь у^k = x^k; у^k+i = f(у^{k+i− 1}, µⁱ), где µⁱ Î V(у^{k+i− 1}), i=1, 2, …, m − k; у^m Î F.

Пусть

Так как у^k-траектория T_k¹ оптимальна, то R < Q.

Рассмотрим полную траекторию Т* = {x⁰, x¹, x², …, x^k, у^k+1, у^k+2, …, у^m}. Как очевидно, С(Т*) = P + R. Далее имеем С(Т*) = P + R < P + Q = С(Т).

Таким образом, С(Т*) < С(Т). Последнее неравенство означает, что траектория Т неоптимальна. Справедливость теоремы вытекает из полученного противоречия.

Стоимость оптимальной в задаче А полной траектории обозначим символом В_А. Стоимость заключительной x-траектории, оптимальной в задаче А(x), обозначим В(х). Функция В(х) называется функцией Беллмана. Отметим, что В_А = В(x₀).

Очевидны следующие равенства:

В(x) = 0, x Î F. (1)

Пусть x − произвольное нефинальное состояние системы. В этом состоянии можно реализовать любое принадлежащее множеству V(x) управление. Предположим, что выбрано управление v, v Î V(x). Данное управление влечет платеж s(х, v), а следующим состоянием системы оказывается f(х, v). Если далее реализуется оптимальная заключительная f(х, v) – траектория, то суммарная величина последующих платежей оказывается равной

В(f(x, v)). Из принципа Беллмана получаем:

(2)

Вычисление значений функции Беллмана по соотношениям (1)–(2) выполняется поэтапно в следующем порядке. На первом этапе фиксируются значения В(x) = 0 для всех x Î F. Далее на каждом следующем этапе вычисление очередного значения функции Беллмана выполняется для произвольного состояния x такого, что В(x) неизвестно, но значения В(y) для всех непосредственно следующих за x состояний y уже найдены (состояние y системы Ω относим к числу непосредственно следующих за состоянием х, если пара {x, y} является траекторией системы Ω). Последним в процессе счета определяется значение В(x₀).

Для синтеза оптимальной полной траектории системы при выполнении определяемой соотношениями (1)–(2) процедуры счета следует дополнительно составить список оптимальных переходов (СОП). Каждая запись этого списка имеет вид [x_i, x_j], где x_i – произвольное нефинальное состояние, а x_j = f(x_i, v*) – состояние, в которое система переходит из xi под воздействием управления v*, возможного в состоянии xi и обращающего в минимум сумму s(x_i, v) + B(f(x_i, v)) в правой части формулы (2); если таких управлений несколько, фиксируется любое из них (нашей целью считаем построение любой из оптимальных траекторий, но не всех таких траекторий). Записи СОП взаимно однозначно соответствуют нефинальным состояниям системы, при этом запись [x_i, f (x_i, v)] считается соответствующей состоянию x_i. Составленный СОП полагаем упорядоченным по возрастанию индексов первых компонент входящих в него записей.

Чтобы построить оптимальную траекторию, из СОП извлекаем последовательность записей W, первым элементом которой является запись, соответствующая состоянию x0; каждая следующая запись последовательности W имеет своей первой компонентой вторую компоненту предыдущей записи этой последовательности. В последней записи последовательности W второй компонентой является некоторое финальное состояние системы Ω. Из составленного СОП последовательность W извлекается однозначно.

Пусть W = {[x₀, y₁], [y₁, y₂], [y₂, y₃], …, [y_{m− 1}, y_m]}, здесь y_m Î F.

Тогда Т = {x₀, y₁, y₂, y₃, …, y_m} – искомая оптимальная траектория.

Уравнения (1)–(2) – рекуррентные соотношения динамического программирования для решения задачи А. Основанный на этих соотношениях метод решения задачи А называется методом динамического программирования.

Пусть N – число состояний системы Ω. Тогда верхняя оценка числа вычисляемых значений функции Беллмана в процессе решения задачи А равна N. Число элементарных операций, выполняемых при определении по формуле (2) каждого конкретного значения этой функции не превышает СN, где С – некоторая не зависящая от N константа. Таким образом, верхней оценкой числа элементарных операций, выполняемых при решении задачи А методом динамического программирования является СN², где N – число состояний системы Ω, а С – не зависящая от N константа. Для запоминания в процессе вычислений всех найденных значений функции Беллмана необходим объем памяти, пропорциональный N; объем памяти такого же порядка нужен для создания списка оптимальных переходов. В итоге получаем, что объем памяти, нужной для решения задачи А методом динамического программирования, линейно зависит от N.

Следует отметить, что в связи с конечностью числа состояний системы Ω число ее траекторий конечно и задача А в принципе может быть решена путем перебора конечного числа вариантов. Метод динамического программирования позволяет определенным образом упорядочить и существенно сократить перебор.

Систему Ω можно представлять конечным взвешенным ориентированным графом G(Ω), вершины которого взаимно однозначно соответствуют состояниям системы, дуги – управлениям, веса дуг – стоимостям соответствующих переходов. Вначале положим, что вершины названы именами соответствующих состояний. Вершину x0 именуем начальной; вершины, соответствующие состояниям подмножества F, называем финальными.

В графе G(Ω) дуга, идущая из произвольной вершины x в вершину y, проводится тогда и только тогда, когда в системе Ω для некоторого возможного в состоянии x управления v* (v*Î V(x)) имеет место y = f(х, v*); вес этой дуги полагаем равным s(х, v*). Вершину х называем непосредственно предшествующей вершине у, если в графе имеется дуга (x, y). В графе G(Ω) путь из произвольной вершины х, х Î D, в вершину у, у Î D, имеется тогда и только тогда, когда выполняется бинарное отношение Р(х, у).

Так как Р(х, у) – отношение частичного порядка, граф G(Ω) – ациклический. Из свойств транзитивности и антисимметричности бинарного отношения Р(х, у) и сделанного предположения о достижимости любого состояния системы Ω вытекает, что в графе G(Ω) нет дуг, входящих в вершину x₀. По определению системы Ω, достигнув финального состояния, она прекращает функционировать; поэтому в графе отсутствуют дуги, исходящие из финальных вершин.

Вершины графа G(Ω) нумеруем целыми неотрицательными числами. Вершине x₀ (начальной вершине) присваиваем номер 0. Далее реализуется многоэтапная процедура, на каждом шаге которой из совокупности пока непронумерованных выбирается какая-либо вершина, для которой все непосредственно предшествующие вершины уже пронумерованы; выбранной вершине присваивается следующий (в порядке возрастания) номер.

Введенные номера далее будем считать новыми наименованиями вершин графа и соответствующих им состояний системы Ω.

Отсюда имеем следующее: если для некоторых состояний i, j и управления v, v Î V(i), имеет место j = f (i, v), то j > i.

При выполненной нумерации в вычислительной процедуре, определяемой соотношениями (1)–(2), значения функции Беллмана для состояний системы Ω вычисляются последовательно, в порядке убывания их номеров. Поэтому в ситуации, когда для состояния i по соотношению (2) определяется значение В(i), все значения В(f(i, v)) при v Î V(i) уже известны. Последней в процедуре вычисляется величина В(0) – оптимальное значение критерия в решаемой задаче А.

Пример 1.1. Имеется дискретно управляемая система Ω ¹, определяющий ее граф G(Ω ¹) представлен на рис. 1.1. Начальным является состояние 0, множество финальных состояний одноэлементно: F = {9}. Требуется найти полную траекторию минимальной стоимости.

Рис. 1.1. Граф G(Ω ¹)

Для состояний системы Ω ¹ (вершин графа G(Ω ¹)) вычисляем значения функции Беллмана. На основании (1) фиксируем В(9) = 0. Далее, пользуясь (2), последовательно получаем:

В(8) = 1;

В(7) = min[3, 1 + В(8)] = 2;

В(6) = 1 + В(7) = 3;

В(5) = min[1 + В(6), 3 + В(7), 7 + В(8)] = min[4, 6, 8] = 4;

В(4) = min[2 + В(5), 3 + В(8), 5 + В(9)] = min[6, 4, 5] = 4;

В(3) = min[3 + В(5), 4 + В(4)] = min[7, 8] = 7;

В(2) = min[1 + В(3), 5 + В(5)] = min[8, 9] = 8;

В(1) = min[9 + В(6), 6 + (2)] = min[12, 14] = 12;

В(0) = min[1+ В(1), 5 + В(2), 4 + В(3)] = min[13, 13, 11] = 11.

Таким образом, минимальная из стоимостей полных траекторий в рассматриваемой задаче равна 11.

При подсчетах значений функции Беллмана в графе G(Ω ¹) для каждой нефинальной вершины специально выделяем (рисуем жирной линией) дугу, соответствующую управлению, в ней принимаемому (т.е. обращающему в минимум правую часть (2)). Получаемый результат представлен на рис. 1.2.

Рис. 1.2. Граф G(Ω ¹) с выделенными дугами

Как показывают выделенные дуги, на первом такте процесса управления следует выполнить переход из вершины 0 в вершину 3, на втором такте – из вершины 3 в вершину 5, на третьем такте – из вершины 5 в вершину 6, на четвертом такте – из вершины 6 в вершину 7, на пятом такте – из вершины 7 в вершину 8, на шестом, заключительном такте – из вершины 8 в вершину 9. Таким образом, оптимальной по критерию суммарной стоимости полной траекторией является Т = {0, 3, 5, 6, 7, 8, 9}.

Далее введем совокупность частных задач следующего вида.

Задача А*(x). Для системы Ω и ее состояния x найти начальную x-траекторию минимальной стоимости. Оптимальное решение задачи А*(x) именуем оптимальной начальной x-траекторией системы Ω.

Имеет место следующий факт.

Теорема 1.2. Если полная траектория Т = {x⁰, x¹, x², …, xⁿ} оптимальна, то любая ее начальная часть также оптимальна.

Доказательство данной теоремы идентично доказательству теоремы 1.1.

Стоимость начальной х-траектории, оптимальной в задаче А*(x), обозначим В*(х). Очевидно, что

В*(x₀) = 0 (3)

В системе Ω произвольное состояние х непосредственно предшествует состоянию у, если пара {x, y} является траекторией системы Ω. Управление, переводящее систему Ω из состояния х непосредственно в состояние у, обозначим v[х, у]. Множество состояний системы, непосредственно предшествующих состоянию у, обозначим Г(у). Основываясь на теореме 1.2, запишем соотношение, позволяющее организовать процесс вычислений значений функции В*(у) для всех состояний у, отличных от начального:

(4)

Отметим, что

(5)

Вычисление значений функции В*(у) на основе рекуррентных соотношений (3)–(4) выполняется поэтапно в следующем порядке. На первом этапе фиксируется значение В*(x₀) = 0.

Далее на каждом следующем этапе вычисление очередного значения функции В* выполняется для произвольного состояния у такого, что В*(у) неизвестно, но значения В*(х) для всех со

стояний x, непосредственно предшествующих состоянию y, уже найдены.

Метод решения задачи А, основанный на соотношениях (3)–(5), – прямой метод Беллмана. В отличие от него, метод, основанный на соотношениях (1)–(2), носит название обратного метода Беллмана. Функции В*(x) и В(x) будем именовать функциями Беллмана для прямого и обратного счета соответственно. Реализация как обратного, так и прямого метода Беллмана для решения задачи А требует по верхней оценке квадратично зависящего от числа состояний системы Ω количества элементарных операций. Иногда прямой и обратный метод Беллмана, подразумевая, что задача решается с использованием соотношений динамического программирования, называют методами прямого и обратного счета соответственно.

Пример 1.2. Имеется дискретно управляемая система Ω ¹, определяющий ее граф G(Ω ¹) представлен на рис. 1.1. Начальным является состояние 0, множество финальных состояний одноэлементно: F = {9}. Методом прямого счета требуется найти полную траекторию минимальной стоимости.

Для состояний системы Ω ¹ (вершин графа G(Ω ¹)) вычисляем значения прямой функции Беллмана. На основании (3) фиксируем В*(0) = 0. Далее, пользуясь (4), последовательно получаем:

В*(1) = 1;

В*(2) = min[5, В*(1) + 6] = 5;

В*(3) = min[4, В*(2)+1] = 4;

В*(4) = В*(3) + 4 = 8;

В*(5) = min[В*(2) + 5, В*(3) + 3, В*(4)+2] = 7;

В*(6) = min[В*(1) + 9, В*(5) + 1] = 8;

В*(7) = min[В*(6) + 1, В*(5) + 3] = 9;

В*(8) = min[В*(5) + 7, В*(7) + 1] =10;

В*(9) = min[В*(7) + 3, В*(8) + 1, В*(4) + 5] = 11.

При вычислении значений функции Беллмана в графе G(Ω ¹) для каждой вершины у, отличной от начальной, специально выделяем (рисуем жирной линией) дугу (x, y), где x – вершина для которой значение правой части (4) при подсчете В*(у) оказывается минимальным (этот способ выделения дуг с учетом используемого метода счета называем прямым; способ выделения, использованный в решении предыдущего примера, именуем обратным). Полученный результат представлен на рис. 1.3. Как показывают выделенные дуги, на последнем такте процесса управления следует выполнить переход из вершины 8 в вершину 9, переход в вершину 8 реализуется из вершины 7, в вершину 7 – из вершины 6, в вершину 6 – из вершины 5, в вершину 5 – из вершины 3, в вершину 3 – из вершины 0. Оптимальной является траектория {0, 3, 5, 6, 7, 8, 9}.

Полученные в результате решения примеров 1.1 и 1.2 оптимальные в системе Ω ¹ траектории совпали.

Рис. 1.3. Граф G(Ω ¹) с выделенными дугами (способ выделения дуг – прямой)

Отметим следующее обстоятельство. Пусть в процессе вычислений по соотношениям (3)–(4) для некоторого финального состояния x* оказалось найденным значение В*(x*); полную траекторию стоимости В*(x*), имеющую своим конечным состоянием x*, обозначим Т *. Если каждая из остальных траекторий имеет в своем составе как минимум одно состояние из некоторого подмножества состояний Q, причем все значения В*(x) при x Î Q уже вычислены и оказались не меньше В*(x*), то Т*.– полная оптимальная траектория. Сделанное утверждение нередко дает возможность ограничить объем требуемых вычислений.

Подмножество промежуточных состояний М системы Ω назовем разрезающим, если каждая полная траектория T этой системы имеет в своем составе состояния из М. Разрезающее подмножество М* назовем минимальным разрезающим, если среди его собственных подмножеств нет разрезающих. Минимальная из стоимостей полных траекторий системы Ω равна

(6)

здесь М* – любое минимальное разрезающее подмножество состояний системы Ω.

Основанный на данном факте метод решения задачи синтеза полной траектории минимальной стоимости называется методом встречного счета.

Для системы Ω ¹, определяемой представленным на рис. 1.1 графом G(Ω ¹), минимальным разрезающим является, в частности, подмножество вершин-состояний М* = {4, 5, 6}. При решении задачи синтеза оптимальной по стоимости полной траектории методом встречного счета выполняем следующие действия.

Прямым счетом последовательно определяем:

В*(1) = 1;

В*(2) = 5;

В*(3) = 4;

В*(4) = 8;

В*(5) = 7;

В*(6) = 8.

Обратным счетом находим: В(8) = 1; В(7) = 2; В(6) = 3; В(5) = 4; В(4) = 4. Для принадлежащих подмножеству М* состояний находим: В*(4) + В(4) = 12; В*(5) + В(5) = 11; В*(6) + В(6) = 11. Получаем, что минимальная из стоимостей полных траекторий системы Ω ¹ равна 11.

Оптимальные полные траектории системы Ω ¹ (их, в принципе, может быть несколько) проходят через вершины 5 и 6. При выполненном подсчете значений функции В*(х), см. решение примера 1.2, определено, что оптимальной начальной 5-траекторией системы Ω ¹ является Т*(5) = {0, 3, 5}, а оптимальной начальной 6-траекторией этой системы является Т*(6) = {0, 3, 5, 6}.

При подсчете значений функции В(х), см. решение примера 1.1, установлено, что оптимальной заключительной 5-траекторией системы Ω ¹ является Т(5) = {5, 6, 7, 8, 9}, а оптимальной заключительной 6-траекторией этой системы является Т(6) = {6, 7, 8, 9}. Получаем, что единственной оптимальной полной траекторией системы Ω ¹ является Т = {0, 3, 5, 6, 7, 8, 9}.

Метод встречного счета оказывается эффективным, в частности, при решении задач в вычислительных системах с несколькими процессорами.

Выше траектории системы Ω оценивались по показателю суммарной стоимости. В некоторых задачах целесообразной оценкой каждой траектории Т = {x⁰, x¹, x², …, xⁿ} является величина максимального из пошаговых платежей в ходе реализации этой траектории. Введем показатель

и рассмотрим задачу синтеза полной траектории с минимальным значением этого показателя. Обозначим через Т (Ω) совокупность всех полных траекторий системы Ω. Сформулированная задача записывается в виде

(7)

Оптимальную в задаче (7) траекторию будем именовать минимаксной полной траекторией системы Ω. Идентичным образом вводится понятие минимаксной заключительной x-траектории системы Ω. Имеет место следующий факт.

Теорема 1.3. Если Т = {x⁰, x¹, x², …, x^k, x^k+1, …, хⁿ} – минимаксная полная траектория, а Т' = {у¹, у², …, у^m} – минимаксная заключительная x^k-траектория, здесь у¹ = x^k, то траектория {x⁰, x¹, x², …, x^k, у², …, у^m} – минимаксная полная траектория.

Доказательство данной теоремы легко выполняется методом от противного.

Из теоремы 1.3 вытекает Следствие 1.1. В системе Ω имеется минимаксная полная траектория, любая заключительная часть которой также минимаксна.

Максимальный из пошаговых платежей при реализации минимаксной полной траектории Т системы Ω обозначим В'. Максимальный из пошаговых платежей при реализации минимаксной заключительной х-траектории системы Ω обозначим В'(х).

Функция В'(х) – функция Беллмана для рассматриваемой минимаксной задачи. Очевидны следующие равенства:

В'(x_k) = 0, x_k Î F (8)

Пользуясь следствием из теоремы 3, запишем общее уравнение

(9)

Формулы (8)–(9) – рекуррентные соотношения динамического программирования для задачи синтеза минимаксной полной траектории в системе Ω. В вычислительной процедуре, определяемой этими соотношениями, значения функции Беллмана для нефинальных состояний системы Ω вычисляются последовательно, в порядке убывания их номеров. В ситуации, когда для состояния xi по формуле (9) определяется значение В'(x_i), все значения В'(f(x_i, v)) при v Î V(x_i) уже известны. Последней в реализации процедуры вычисляется величина В'(x₀) – оптимальное значение критерия в решаемой задаче (7). Синтезируемая с использованием рекуррентных соотношений (8)-(9) минимаксная полная траектория такова, что любая ее заключительная часть также минимаксна. Количество элементарных операций, необходимых для решения изложенным способом задачи (7) по верхней оценке квадратично зависит от числа состояний системы Ω.

Идентичным образом вводится понятие максиминной полной траектории и записываются соотношения динамического программирования для ее синтеза.

В рамках моделей управления системами описанного вида формулируются и решаются многие типы задач дискретной оптимизации. Число состояний системы Ω, конструируемой по исходным данным решаемой оптимизационной задачи, от размерности этой задачи очень часто зависит экспоненциально.

Данное обстоятельство является причиной значительных затрат на время вычислений уже при средних размерностях решаемых задач. При изучении каждого конкретного класса оптимизационных задач актуальны проблемы построения моделирующих систем с возможно меньшим числом состояний и синтеза алгоритмов, которые экономят время вычислений и объем используемой памяти за счет отыскания только тех значений функции Беллмана, которые действительно оказываются необходимыми.