Математические методы исследования операций в экономике (стр. 29 из 37)
Поскольку логарифм функции типа (5.2) является аддитивной функцией, достаточно ограничиться рассмотрением функций вида (5.1).
Изложим сущность вычислительного метода динамического программирования на примере задачи оптимизации
при ограниченияx
Отметим, что в отличие от задач, рассмотренных в предыдущих главах, о линейности и дифференцируемости функций fj(xj) не делается никаких предположений, поэтому применение классических методов оптимизации (например, метода Лагранжа) для решения задачи (5.3)-(5.4) либо проблематично, либо просто невозможно.
Содержательно задача (5.3)-(5.4) может быть интерпретирована как проблема оптимального вложения некоторых ресурсов j, приводимых к единой размерности (например, денег) с помощью коэффициентов aj, в различные активы (инвестиционные проекты, предприятия и т. п.), характеризующиеся функциями прибылиfj, т. е. такого распределения ограниченного объема ресурса (b), которое максимизирует суммарную прибыль. Представим ситуацию, когда она решается последовательно для каждого актива. Если на первом шаге принято решение о вложении в n-й актив xn единиц, то на остальных шагах мы сможем распределить b-anxn единиц ресурса. Абстрагируясь от соображений, на основе которых принималось решение на первом шаге (допустим, мы по каким-либо причинам не могли на него повлиять), будет вполне естественным поступить так, чтобы на оставшихсяшагахраспределениетекущегообъема ресурса произошло оптимально, что равнозначно решению задачи
при ограничениях
Очевидно, что максимальное значение (5.5) зависит от размера распределяемого остатка, и если оставшееся количество ресурса обозначить через ξ, то величину (5.5) можно выразить как функцию от ξ:
где индекс п-1 указывает на оставшееся количество шагов. Тогда суммарный доход, получаемый как следствие решения, принятого на первом шаге, и оптимальных решений, принятых на остальных шагах, будет
Если бы имелась возможность влиять наxn , то мы для получения максимальной прибыли должны были бы максимизировать Ωn по переменной xn , т. е. найти Λn(b) и фактически решить задачу:
В результате мы получаем выражение для значения целевой функции задачи при оптимальном поэтапном процессе принятия решений о распределении ресурса. Оно в силу построения данного процесса равно глобальному оптимуму целевой функции
т. е. значению целевой функции при одномоментном распределении ресурса.
Если в выражении (5.9) заменить значения b на ξ, и п наk, то его можно рассматривать как рекуррентную формулу, позволяющую последовательно вычислять оптимальные значения целевой функции при распределении объема ресурса ξ за k шагов:
Значение переменной xk, при котором достигается рассматриваемый максимум, обозначим 
k (ξ).
При k = 1 формула (5.11) принимает вид
т. е. допускает непосредственное вычисление функций Λ1(ξ) и 1(ξ).
Воспользовавшись (5.12) как базой рекурсии, можно с помощью (5.11) последовательно вычислить Λk(ξ) и k(ξ),k∊2:n. Положив на последнем шаге ξ =b, в силу (5.9), найдем глобальный максимум функции (5.3), равный Λn(b), и компоненту оптимального плана хn* = n(b). Полученная компонента позволяет вычислить нераспределенный остаток на следующем шаге приоптимальном планировании: ξ= b –аnх*n, и, в свою очередь, найти х*n-1= n-1(ξn-1). В результате подобных вычислений последовательно будут найдены все компоненты оптимального плана.
Таким образом, динамическое программирование представляет собой целенаправленный перебор вариантов, который приводит к нахождению глобального максимума. Уравнение (5.11), выражающее оптимальное решение наk-м шаге через решения, принятые на предыдущих шагах, называется основным рекуррентным соотношением динамического программирования. В то же время следует заметить, что описанная схема решения при столь общей постановке задачи имеет чисто теоретическое значение, так как замыкает вычислительный процесс на построение функций Λk(ξ) (k∊1:n), т. е. сводит исходную задачу (5.3)—(5.4) к другой весьма сложной проблеме. Однако при определенных условиях применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это относится к задачам, которые допускают табличное задание функций Λk(ξ).
5.1.2. Задачи динамического программирования, допускающие табличное задание рекуррентных соотношений. Рассмотрим процесс решения модифицированного варианта задачи (5.3)-(5.4), в котором переменные хj и параметры aj, b могут принимать только целочисленные значения, а ограничение (5.4) имеет вид равенства. В рамках предложенной в п. 5.1.1 интерпретации о вложении средств в активы данные предпосылки вполне реалистичны и, более того, могут быть даже усилены требованием о кратности значений хj , например, 1000 единицам.
Чтобы не усложнять обозначения, условимся операции целочисленной арифметики записывать стандартным образом, полагая, что промежуточные результаты подвергаются правильному округлению. Так, например, будем считать, что 12/5=2.
В соответствии с общей схемой вычислительного алгоритма на первом шаге мы должны построить функцию
Поскольку ξ≤b,x1 принимает конечное число целых значений от 0 до b/a1. Это позволяет, например, путем перебора значений f1(x1) найти функцию Λ1(ξ) и задать ее в форме таблицы следующей структуры (табл. 5.1).
Последняя колонка табл. 5.1 ( 1(ξ)) содержит значениеx1 , на котором достигается оптимальное решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения всех компонент оптимального плана.
На следующем (втором) шаге можно приступить к вычислению функции Λ2(ξ), значения которой для каждого отдельно взятого ξ∊ 0: b находятся как
где значения
берутся из табл. 5.1. В результате вычислений формируется таблица значенийΛ2(ξ), содержащая на одну колонку больше по сравнению с табл. 5.1, так как теперь необходимо запомнить оптимальные решения первого ( 1(ξ)) и второго шагов ( 2(ξ)).
На последующих шагах с номеромk (k∊2:(n-l)) осуществляются аналогичные действия, результатом которых становятся таблицы значений Λk(ξ), где ξ ∊{0, 1,..., b} (см. табл. 5.2).
На последнем n-ом шаге нет необходимости табулировать функцию Λn(ξ), так как достаточно определить лишь Λn(b)=f( n(b)). Одновременно определяется и оптимальное значение n-й компоненты оптимального плана x*n = n(b). Далее, используя таблицу, сформированную на предыдущем шаге, определяем оптимальные значения остальных переменных:
