Здесь приводится общий математический аппарат, рассмотренный ранее на отдельных частных примерах, и выводится функциональное уравнение Беллмана. Так же как и в непрерывном случае, оно справедливо при выполнении принципа оптимальности, который аналогичен принципу оптимальности в непрерывном случае, но имеет свои особенности.
Предположим, что при распределении х средств между N отраслями необходимо добиться максимального дохода I(x1, x2,...,xN). Считается, что
I(x1, x2,..., xN)=g1(x1)+g2(x2)+...+gN(xN)(14-14)
Ресурсы xi имеют общую меру и удовлетворяют условию
Такие нелинейные функции носят название сепарабельных. Они типичны для динамического программирования и будут встречаться и дальше. Для таких функций можно построить динамический процесс, для которого заведомо справедлив принцип оптимальности Беллмана, аналогично тому, как это было сделано в задаче о распределении ресурсов.
Требуется найти
Функция (14-14) обладает свойством аддитивности доходов по всем отраслям. Оно обеспечивает выполнение принципа оптимальности Беллмана, который для дискретных процессов управления может быть сформулирован следующим образом: последующие решения должны составлять оптимальное поведение относительно предыдущего состояния, полученного в результате решения на предыдущем этапе, независимо от того, какими бы эти состояние и решение ни были. Дискретное динамическое программирование применимо только к таким много шаговым процессам управления. Для функции (14-14) этот принцип заведомо выполнен, так как доход от вложения ресурсов в данную отрасль зависит только от количества ресурсов, вложенных в эту отрасль, и не зависит от количества ресурсов, вложенных в другие отрасли. Именно это обстоятельство позволяет построить много шаговый процесс типа "первый шаг - вклад в первую отрасль, второй шаг - вклад в первые две отрасли и т. д.", для которого справедлив принцип оптимальности. Иначе смысл принципа оптимальности можно сформулировать так: много шаговый процесс удовлетворяет принципу оптимальности Беллмана, если функция цели, принимающая на k-м шаге оптимальное значение при х=xk, принимает, также оптимальное значение для оставшихся k=1 шагов при том же х=xk. Если функция суммарного дохода является не сепарабельной, то нельзя построить много шаговый процесс, для которого удовлетворяется принцип оптимальности.
Имеется много приемов преобразования исходной задачи для удовлетворения принципа оптимальности, которые в основном разделяются на две группы. В первом случае сводят не сепарабельную функцию цели к сепарабельной. Во втором случае преобразуют уже сам много шаговый процесс. В обоих случаях для удовлетворения принципа оптимальности приходится усложнять задачу введением дополнительных ограничений на область изменения переменных, что не очень сильно усложняет вычислительную процедуру, или введением дополнительных переменных, что фактически приводит к увеличению размерности решаемой задачи и к практически не реализуемым по сложности вычислительным процедурам. Поэтому во многих случаях этот второй прием вряд ли можно расценивать как решение задачи. В качестве примера рассмотрим два варианта сведения функций к сепарабельным. Так, если в функции цели встречаются слагаемые вида xixj, то введением двух новых переменных
и
можно преобразовать их к сепарабельной форме
xixj=y2i-y2j
Сепарабельная форма здесь достигается введением новых переменных, не увеличивающих размерность задачи (увеличивается число отраслей), и добавлением ограничений по два на каждый член вида xixj.
Если в функции цели I встречаются члены вида gi(xi,xi-1), то доход в данной отрасли будет зависеть от величины вложений в эту и соседнюю (i-1)-ю отрасли. Введением дополнительной переменной yi=xi-1 получаем для такого случая зависимость функции дохода от двух переменных gi(xi, yi). Здесь возникает трудность, связанная с увеличением размерности задачи, так как функция цели I зависит уже от двух видов ресурсов xi и yi которые в данном случае связаны ограничением, а в общем случае двумерной задачи о распределении они могут быть друг от друга независимы. Характерной особенностью много шаговых процессов, которые оптимизируются с помощью динамического программирования, является зависимость текущего состояния только от предыдущего и независимость от состояний, предшествующих этому предыдущему (отсутствие последействия). Только в этом случае удается составить функциональное уравнение Беллмана. Ранее рассмотренный вариант, в котором функция gi(xi, xi-1) зависела от двух переменных без их замены, приводит к много шаговому процессу, не удовлетворяющему этому условию. Однако с помощью только что проделанной замены yj=xi-1 - много шаговый процесс становится процессом без последействия.
Если доходы в разных отраслях связаны между собой, то принцип оптимальности Беллмана также несправедлив.
При условии (14-14) функциональное уравнение Беллмана имеет вид:
причем x - общее число ресурсов; xi - количество ресурсов, вкладываемое в i-ю отрасль, причем gk(xk)- доход от вложения x средств в k-ю отрасль (k=1, 2,..., N). Благодаря этому соотношению имеется N этапов, где N - число отраслей. Формально можно получить уравнение (14-15), используя следующее соотношение, основанное на принципе оптимальности:
Это равенство означает, что доход в k-и отрасли не зависит от дохода в остальных -k1 отраслях и благодаря этому максимальный доход по всем отраслям равен сумме максимального дохода по всем -k1 отраслям и по k-й отрасли. С помощью формулы (14-16) напишем цепочку равенств:
Тем самым получено функциональное уравнение с использованием свойства аддитивности функционала (14-15), обеспечивающего выполнение принципа оптимальности Беллмана. Согласно этому уравнению динамическое программирование заменяет прямой перебор направленным, поэтапным [на каждом k-м шаге используется результат перебора на предыдущем (k-1)-м шаге], который существенно сокращает число вариантов.
Если в задаче распределения имеется несколько видов ресурсов, не имеющих общей меры, то она становится многомерной. Так, в случае с. двумя ресурсами суммарный доход равен:
где
Функция Беллмана определяется как
SN(x,y)=maxIN(x1, x2,...,xN; y1, y2,...,yN)
причем для N=1
S1(x,y)=g1(x,y)
для N≥2
Такой вид имеет функциональное уравнение Беллмана для двумерного случая.