 |
 |
 |
 |
|
 |
 |
90
Таким образом, динамическое программирование представляет собой целенаправленный перебор
вариантов, который приводит к нахождению глобального максимума. Уравнение (5.11), выражающее
оптимальное решение на
k-м шаге через решения, принятые на предыдущих шагах, называется
основным рекуррентным соотношением динамического программирования. В то же время следует
заметить, что описанная схема решения при столь общей постановке задачи имеет чисто теоретическое
значение, так как замыкает вычислительный процесс на построение функций
?
k
(?) (k?1:n), т. е. сводит
исходную задачу (5.3)—(5.4) к другой весьма сложной проблеме. Однако при определенных условиях
применение рекуррентных соотношений может оказаться весьма плодотворным. В первую очередь это
относится к задачам, которые допускают табличное задание функций
?
k
(?).
5.1.2. Задачи динамического программирования, допускающие табличное задание
рекуррентных соотношений. Рассмотрим процесс решения модифицированного варианта задачи (5.3)-
(5.4), в котором переменные х
j
и параметры a
j
, b могут принимать только целочисленные значения, а
ограничение (5.4) имеет вид равенства. В рамках предложенной в п. 5.1.1 интерпретации о вложении
средств в активы данные предпосылки вполне реалистичны и, более того, могут быть даже усилены
требованием о кратности значений х
j
, например, 1000 единицам.
Чтобы не усложнять обозначения, условимся операции целочисленной арифметики записывать
стандартным образом, полагая, что промежуточные результаты подвергаются правильному
округлению. Так, например, будем считать, что 12/5=2.
В соответствии с общей схемой вычислительного алгоритма на первом шаге мы должны построить
функцию
Поскольку
??
b, x1 принимает конечное число целых значений от 0 до b/a1. Это позволяет, например,
путем перебора значений f1(x1) найти функцию
?
1
(?)
и задать ее в форме таблицы следующей структуры
(табл. 5.1).
Последняя колонка табл. 5.1 (
x
ˆ1
(?))
содержит значение
x1 , на котором достигается оптимальное
решение первого шага. Его необходимо запоминать для того, чтобы к последнему шагу иметь значения
всех компонент оптимального плана.
На следующем (втором) шаге можно приступить к вычислению функции
?
2
(?),
значения которой для
каждого отдельно взятого
?
? 0: b находятся как
где значения
берутся из табл. 5.1. В результате вычислений формируется таблица значений ?2(?), содержащая на
одну колонку больше по сравнению с табл. 5.1, так как теперь необходимо запомнить оптимальные
решения первого (
x
ˆ1
(?)) и второго шагов (
x
ˆ2
(?)).