1.7. замечания по практическому применению метода динамического программирования

1.7. замечания по практическому применению метода динамического программирования

Принцип оптимальности Беллмана (*) сформулирован с использованием фазовых и управляющих переменных хі и щ и функций /і(хі-і,щ) и Zi(xi-i,Ui). В то же время постановка большинства практических задач не предполагает явного задания каких-либо математических переменных и функций. Следовательно, исходя из экономического содержания решаемых задач, необходимо предварительно должным образом ввести требуемые переменные и функции. Это надлежит сделать в следующем порядке.

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

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

Установить, какой параметр может быть выбран в качестве управляющей переменной и, и выявить налагаемые на нее ограничения.

Составить функцию процесса /, определяющую закон изменения состояния системы.

5. Составить частную целевую функцию z, определяющую экономический эффект на каждом из шагов процесса.

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

Если исходные данные задачи приведены в табличной форме, то при решении задачи методом ДП получаемые результаты расчетов удобно располагать в таблицах следующей структуры:

Вспомогательная таблица

4її

г = 1,2,...,ЛГ г = ЛГ,ЛГ-1,...,2,1

(предварительный этап) (этап условной оптимизации)

с помощью которой и проводится непосредственно расчет функций Беллмана Ві-\{хі-). Вспомогательная и основная таблицы строятся и заполняются для всех і = 1,2,... ,N (т. е. всего строится ./V экземпляров вспомогательных и основных таблиц, отвечающих ./V шагам процесса; содержание таблиц, конечно, меняется от шага к шагу).

Справа от вспомогательной таблицы и снизу под основной таблицей символами «JJ-» и «її» указан порядок заполнения соответствующих фрагментов таблиц, который будет подробно рассмотрен ниже.

Структура основной таблицы строго соответствует структуре функционального уравнения Беллмана (*). Вычисления начинаются с выбора значения аргумента Хі(столбец 1 таблицы) рассчитываемой функции

-Вг-і(Жг-і)При расчете вычисляется максимум по управляющей переменной щ

(столбец 2). Значения и и; в соответствии с формулами

Xi = fi{Xi-,Ui) И Zi = Zi(Xi-l,Ui)

определяют значения х{ и z^ (столбцы 3 и 4). При вычислении максимума по щ используется вычисленное ранее значение Ві(хі) (столбец 5), а максимум вычисляется от суммы

Zi(xi-i,Ui) + Ві(хі)

(столбец 6). Заканчиваются вычисления расчетом значения функции Ві-(хі-і) (столбец 7). Основная таблица может содержать несколько строчных фрагментов, соответствующих различным значениям фазовой переменной. Xi-i, представленной в первом столбце таблицы.

Особое внимание следует обратить на двойную вертикальную черту, разделяющую основную таблицу на две части. Это разделение связано с тем, что заполнение таблиц разнесено по двум этапам: предварительному этапу и этапу условной оптимизации. На предварительном этапе проводится заполнение первой строки вспомогательной таблицы и левой части (четырех столбцов слева от двойной вертикальной черты) основной таблицы, содержащих значения переменных задачи и частных целевых функций и не связанных непосредственно с вычислением функций Беллмана Ві(хі). Заполнение этих фрагментов таблиц проводится в естественном порядке при г = 1,2,..., iV, что и отмечено символом «JJ.». На этапе условной оптимизации проводится заполнение второй строки вспомогательной таблицы и правой части (трех столбцов справа от двойной вертикальной черты) основной таблицы, уже непосредственно связанных с вычислением функций Bi(xi). Заполнение этих фрагментов таблиц проводится, как и предписывает принцип оптимальности Беллмана, е обратном порядке при г — N, N—1,... , 2,1, что и отмечено символом «її». На этом же этапе вычисляются условно-оптимальные управления щ(хі-.і), на которых достигаются промежуточные экстремумы. При заполнении основных таблиц соответствующие условно-оптимальные значения управляющей переменной будут

отмечаться знаком «/» (в отличие от символа «*» для оптимальных значений параметров). Более детальные пояснения будут приведены в следующей главе при рассмотрении конкретных примеров решения методом ДП типовых задач управления многошаговыми процессами.

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

О Контрольные вопросы

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

Дайте понятие многошагового процесса.

Для решения какого класса задач применяется метод ДП?

Что такое фазовая переменная и в чем состоят ее роль и предназначение?

Что такое управляющая переменная и каковы ее роль и предназначение?

Что такое функция процесса и в чем заключаются ее предназначение и экономическое содержание?

Что такое целевая функция и в чем состоят ее предназначение и экономическое содержание?

Сформулируйте понятие допустимого управления и поясните, в чем состоит его смысл.

Сформулируйте понятие оптимального управления и поясните, в чем состоит его смысл.

Дайте понятие траектории и оптимальной траектории.

Дайте понятие оптимального значения задачи.

Сформулируйте и поясните основные допущения метода ДП.

По какой причине оптимизация по нескольким шагам процесса не сводится к независимой оптимизации по отдельным шагам?

Как связаны между собой задачи на поиск максимума и минимума?

Почему классические методы поиска экстремальных значений функций многих переменных, основанные на дифференциальном исчислении, не всегда практически применимы?

Что такое условно-оптимальные значения целевой функции и каково их экономическое содержание?

Поясните принцип оптимальности Беллмана.

Запишите основное функциональное уравнение Беллмана.

Поясните, что означает рекуррентный характер функционального уравнения Беллмана.

В чем заключается принцип инвариантного погружения?

Поясните, что такое условно-оптимальные управления.

Назовите и охарактеризуйте этапы метода ДП.

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

Укажите основные достоинства и недостатки метода ДП.

В чем заключаются сложности, возникающие при практическом применении метода ДП?

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

Опишите структуру и порядок заполнения таблиц, используемых при проведении метода ДП.