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

Изучение метода начнем с простой задачи управления одномерным дискретным ОУ. Одномерность задачи позволяет более четко уяснить принципы метода, а дискретность задачи является, как правило, обязательным спутником метода, который реализуется обычно с помощью ЦВМ.

Описывается уравнением первого порядка

(1.47)

где . Заданы начальное состояние , критерий оптимальности

(1.48)

и область допустимых управлений . Задача соответствует ситуации (1.46), т. е. требуется найти такую последовательность управлений , на которой функционал достигает минимального значения с учетом заданного начального состояния.

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

В соответствии с методом динамического программирования решение обычно осуществляют начиная с правого конца задачи. Предположим, что все управления найдены, а на основании (1.47) и подсчитаны соответствующие состояния . Неизвестно единственное управление ; определим его. Так как от зависит только последнее слагаемое в составе (1.48), то на основании принципа оптимальности его следует искать в соответствии с условием

(1.49)

По предположению известно, поэтому функция зависит от единственного аргумента . Используя какой-либо метод минимизации одномерной функции, найдем в области управление удовлетворяющее (1.49). Очевидно, это управление будет функцией состояния объекта в момент , т. е.

(1.50)

Если это значение управления подставить в выражение , то получим минимальное значение , которое в силу (1.50) будет функцией . Обозначим через минималь­ное значение , достигаемое на оптимальном управлении , т. е.

(1.51)

Осуществить аналитическое решение задачи (1.49), (1.51) удается редко, так как найденное из традиционного условия оптимальное управление , как правило, оказывается за пределами области . На практике его ищут численным путем с помощью ЦВМ, поступая следующим образом. Диапазон возможных значений , регламентируемых ограничениями в области , разбивают на участков длительностью и полагают, что может принимать только дискретные значения с шагом . Значение выбирают достаточно малым, чтобы точность расчетов была приемлемо высокой, и достаточно большим, чтобы величина не оказалась чрезвычайно большой. Пусть ограничения на имеют вид . Разбиение отрезка на уча­стков предполагает, что может принимать только дискретные значения из отрезка . Аналогичным образом поступают с величиной , разбивая диапазон ее возможных значений, который исследователю известен, на участков длительностью . Величина принимает только дискретные значения .

Поиск решения (1.50) проводят следующим образом. Полагают , подставляют эту величину в выражение и вычисляют последовательность. Из этой последователь­ности выбирается наименьший элемент, которому соответствует определенное дискретное значение . Величину найденного элемента обозначим символом , а соответствующее управление . В память ВМ заносят три величины: . Подобные операции проводят для всех последующих значений . По окончании их в памяти машины в момент будут храниться возможные значения состояний , соответствующие им оптимальные управления , и минимальные значения функции на оптимальных управлениях, представленные числами . Утомительность этой процедуры полностью возлагается на ЭВМ. Отметим, что если конечное состояние объекта фиксировано (задано конкретной величиной), то необходимость квантования области возможных состояний объекта в момент отпадает и проводится квантование только области допустимых управлений.

Переходим к следующему этапу решения задачи. Полагаем, что определены все управления и соответствующие им состояния . Найдем оптимальные управления в моменты . На основании принципа оптимальности эти управления зависят только от состояния и цели управления. Последняя заключается в минимизации той части функционала , которая зависит от искомых управлений, т. е. в минимизации двух последних слагаемых из состава (1.48). Следовательно, поиск оптимальных, управлений в моменты осуществляется из условия

(1.52)

Замечаем, что от зависит лишь второе слагаемое в (1.52), но его минимизация уже проведена на первом этапе и найдено значение этого слагаемого при оптимальном управлении в (1.51). Поэтому в (1.52) следует проводить минимизацию только по с учетом резуль­тата первого этапа решения задачи:

(1.53)

Запись (1.53) не означает, что управление ищется из условия минимума только слагаемого, непосредственно от него зависящего. Так как в соответствии с (1.47)

(1.54)

то условие (1.53) приобретает вид

(1.55)

и управление ищут из условия наилучшего качества на всем отрезке .

Задача (1.55) снова содержит единственную неизвестную величину . Ее значение, удовлетворяющее (1.55) и зависящее от , будет

(1.56)

Если это управление подставить в левую часть (1.55), получим минимальное значение левой части, также зависящее от . Обозначим эту величину через

(1.57)

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

Для проведения численной операции (1.55) и (1.57) в области возможных выделяют совокупность дискретных точек и квантуют область значений , в которой регистрируют точки . Затем, положив на основании (1.54), вычисляют возможные состояния при различных , т.е. находят последовательность

Каждую из величин округляют до ближайшего к нему квантованного на первом этапе решения задачи значения состояния , хранящегося в памяти машины, и из памяти машины извлекают соответствующую величину . На основании этих данных формируют систему

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

Отступив на три шага влево от момента , можем провести аналогичные построения для состояния . Они полностью подобны предыдущим, и мы их опускаем. Если отступить на шагов влево, прежняя схема рассуждений приводит к соотношению, подобному (1.57):

(1.58)

На основании соотношения (1.58), снова сопровождаемого минимизацией только по одной переменной , на­ходим в момент оптимальное управление

(1.59)

и величину . Данные , заносим в память машины, стирая предыдущую информацию об .

Придавая возрастающие значения, т. е. все дальше отступая от момента влево, наконец, при получим

(1.60)

Из условия (1.60) находим оптимальное управление как функцию начального состояния объекта

(1.61)

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

После завершения этапа (1.61) начинается движение слева направо с целью отыскания конкретных значений управлений . Зная , на основании уравнения (1.47) находим и округляем его до ближайшего дискретного значения из хранящейся в памяти машины последовательности , которому соответствует также хранящееся в памяти машины управление . Последнее принимается за конкретное оптимальное управление в момент . По и на основании (1.47) вычисляем , после чего весь цикл рассуждений дублируется. Пройдя весь путь слева направо, последовательно восстанавливаем конкретные значения всех оптимальных управлений.

Важно отметить, что метод динамического программирования сводит сложную задачу минимизации функции переменных (1.48) к операциям минимизации функции только одной переменной. Этот метод не является (по крайней мере в дискретном варианте) средством аналитического решения задачи, а формулирует последовательность очень простых правил вычисления, легко реализуемых с помощью ЭВМ. Достоинством метода является его согласование с объемом ограничений: чем их больше и уже область допустимых управлений, тем меньше вычислений.

При изложении вычислительной схемы метода говорилось об округлении вычисленных на различных этапах решения задачи величин до ближайших квантованных значений. В ряде задач это округление целесообразно заменить различными интерполяционными приемами [5].

Изложенный подход к решению задачи легко обобщается на многомерный случай, при котором на вход объекта подается многомерное управление , а в качестве выхода рассматривается вектор состояния . Формально для этого необходимо во всех соотношениях скаляры заменить векторами. Однако теперь на каждом шаге приходится исследовать не одномерную функцию, а функцию переменных в соответствии с размерностью управления. Это резко усложняет схему решения задачи, так как квантование приходится осуществлять в пространстве состояния и пространстве управления, что приводит к необходимости анализировать большое количество точек. Если в одномерном случае дискретизация с шагом приводила, например, к 100 точкам , то в трехмерном пространстве при том же шаге вводится точек, что предъявляет повышенные требования к объему памяти ЭВМ и при больших размерностях задач делает невозможным их решение средствами современной вычислительной техники. Это обстоятельство известно под названием «проклятия размерности», и тогда метод практически малоэффективен. С целью уменьшения требований к памяти прибегают к различным формам аппроксимации [5].