Применение динамического программирования для решения задач управления

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

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

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

Вид и форма целевой функции не оговариваются, она может быть и линейной и нелинейной. Математически она представляется рекуррентным выражением вида

W^*_1,2,…,i(S_i)=exrt[W_i(S_i;P_i)+W^*_{1,2,…,(i-1)}(S_i-1)]

W^*_n,n-1,…,i(S_i-1)=exrt[W_i(S_i-1;P_i)+ W^*_{n,n-1,…,(i+1)}(S_i-1)]

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