11. БЕСКОНЕЧНОШАГОВЫЙ ПРОЦЕСС ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Все задачи динамического программирования, которые мы рассматривали до сих пор, относились к процессам, разделяющимся на конечное число шагов. Разумеется, все практические задачи, связанные с планированием экономических и подобных им операций, относятся к этому классу — планировать имеет смысл только на конечный (пусть даже очень большой) участок времени вперед. Однако, есть задачи, в которых этот участок времени представляется заранее не вполне определенным, и нас может интересовать решение задачи оптимального планирования безотносительно к тому, на каком именно шаге операция закончится. В таких случаях иногда бывает целесообразно рассмотреть в качестве модели явления некоторый идеализированный бесконечношаговый управляемый процесс, который получится из реального при Эта модель удобна тем, что в ней не существует исключительного по своей роли «последнего шага» — все шаги между собой равноправны, процесс известном смысле однороден. Условное оптимальное управление в таком процессе оказывается не зависящим от номера шага, а зависящим только от состояния S системы S перед началом шага. Разумеется, для этого нужно, чтобы шаги были однородными, т. е. функции, определяющие доход и изменение состояния системы под действием управления, были для всех шагов одинаковыми.

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

Заметим, что в отличие от конечношаговых задач, для которых оптимальное управление всегда существует, бесконечношаговые задачи могут и не иметь решения. Чтобы убедиться в этом, рассмотрим элементарный пример.

Пусть имеется задача распределения ресурсов с резервированием (см. § 6), но с бесконечным числом шагов. Средства X, вложенные в производство, дают за год доход и расходуются до конца.

Рис. 3.40

Рис. 3.41

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

Существование и вид решения зависит от того, каков вид функции

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

Предположим теперь, что функция выпукла вверх (рис. 3.41).

Очевидно, что в этом случае выгодно не вкладывать в производство все средства сразу, а «растянуть» их. Например, если мы, вместо того, чтобы вкладывать в производство все средства на первом же шаге, распределим их на два шага, то получим больший доход:

на три шага — еще больший, и т. д. При увеличении числа шагов, на которые распределяются средства, доход только возрастает.

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

а затем устремим к бесконечности, а — к нулю. Из рис. 3.42 видно, что при достаточно малом можно заменить участок кривой участком касательной в начале координат. Тогда доход, получаемый за год, будет приближенно равен

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

Рис. 3.42

При приближенное равенство (11.1) превращается в точное.

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

Это пример бесконечношаговой задачи, где оптимального решения не существует. При любом конечном оно существует и состоит в том, чтобы вкладывать средства во все этапы поровну, а при бесконечном числе шагов перестает существовать.

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

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

Запишем это единственное функциональное уравнение. Пусть бесконечношаговый управляемый процесс происходит в физической системе S; обозначим S — состояние этой системы после какого-то (любого) шага.

Под влиянием управления U система S за следующий шаг переходит в новое состояние S, зависящее от предыдущего состояния S и примененного управления

За этот шаг мы получаем выигрыш (доход) w, также зависящий от S и

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

где — условный максимальный выигрыш, который можно получить, управляя системой, находящейся в состоянии S. В уравнении — единственная неизвестная функция; остальные функции являются заданными. Условное оптимальное управление — то управление, при котором достигается максимум (11.2).

В некоторых простейших задачах удается подобрать функцию так, чтобы она удовлетворяла уравнению (11.2). Общих методов аналитического решения функциональных уравнений не существует. В случаях, когда подобрать функцию удовлетворяющую уравнению (11-2), не удается, прибегают к приближенному решению этого уравнения. Для этого может быть применен метод последовательных приближений, состоящий в следующем: решается задача динамического программирования для конечного, все возрастающего числа шагов ; если решение существует, то при возрастании функции определяющие условный оптимальный выигрыш и условное оптимальное управление для шагов, достаточно удаленных от конца, стабилизируются, приближаясь к соответствующим функциями для бесконечношагового процесса, в качестве которых они и могут быть приближенно взяты.

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