Динамическое программирование. 
Динамическое программирование. 
Уравнение Беллмана

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

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

Одной из особенностей метода динамического программирования является то, что принятие решения по отношению к многошаговым процессам рассматривается не как единичный акт, а как целый комплекс взаимосвязанных решений. Эта последовательность взаимосвязанных решений называется стратегией. Цель оптимального планирования — выбрать такую стратегию, которая обеспечивала бы получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной. Если, например, рассматривается работа станции с точки зрения её рентабельности, то критерием оптимальности будет прибыль, получаемая станцией за хозяйственный год, а оптимальной будет стратегия, состоящая из всех тех решений, которые приведут к получению максимальной прибыли.

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

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

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

Математически это можно записать следующим образом:

.

где Fk (uk) — значение искомой целевой функции на k-м этапе; Fk+1(uk+1) — значение целевой функции на k+1 этапе; Z (xk, uk) — оценочная функция данного k-го этапа; x, u — выбранные параметры функции.

Выражение (29) представляет собой математическую запись принципа оптимальности. Его называют основным функциональным уравнением динамического программирования или функциональным уравнением Беллмана.

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

Исключением является последний шаг, которым процесс заканчивается. Здесь процесс можно планировать таким образом, чтобы последний шаг сам по себе приносил максимальный эффект. Спланировав оптимальным образом последний шаг, можно к нему «пристраивать» предпоследний шаг так, чтобы результат этих двух шагов был оптимальным и т. д. Именно так — от конца к началу — и можно развернуть всю процедуру принятия решений. Но, чтобы принять оптимальное решение на последнем шаге, надо знать, чем мог закончиться предпоследний шаг. Значит, надо сделать разные предположения о том, чем мог закончиться предпоследний шаг и для каждого из предположений найти решение, при котором эффект последнего шага был бы наибольшим. Такое оптимальное решение, найденное при условии, что предыдущий шаг закончился определенным образом, называют условно-оптимальным.

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

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

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