 |
 |
 |
 |
|
 |
 |
91
На последующих шагах с номером k (k?2:(n-l)) осуществляются аналогичные действия, результатом
которых становятся таблицы значений
?
k
(?),
где
?
?{0, 1,..., b} (см. табл. 5.2).
На последнем n-ом шаге нет необходимости табулировать функцию
?
n
(?),
так как достаточно
определить лишь
?
n
(b) = f(
x
ˆ
n
(b)). Одновременно определяется и оптимальное значение n-й компоненты
оптимального плана x*
n
=
x
ˆ
n
(b). Далее, используя таблицу, сформированную на предыдущем шаге,
определяем оптимальные значения остальных переменных:
и т. д. или, в общем виде,
Подчеркнем одно из преимуществ описанного метода с точки зрения его практической реализации в
рамках программного обеспечения для ЭВМ: на каждом шаге алгоритма непосредственно используется
только таблица, полученная на предыдущем шаге, т. е. нет необходимости сохранять ранее полученные
таблицы. Последнее позволяет существенно экономить ресурсы компьютера.
Выигрыш, который дает применение рассмотренного алгоритма, может также быть оценен с
помощью следующего простого примера. Сравним приблизительно по числу операций (состоящих, в
основном, из вычислений целевой функции) описанный метод с прямым перебором допустимых планов
задачи (5.3)-(5.4) при а1 = a2 = ...а
n
= 1.
Количество допустимых планов такой задачи совпадает с количеством целочисленных решений
уравнения
т. е. равно числу сочетаний с повторениями из n элементов по b. Следовательно, при простом переборе
число возможных вариантов составит
В случае применения метода динамического программирования для вычисления таблицы значений
функции
?
k
(?) при фиксированном ? необходимо выполнить (?+1) операций. Поэтому для заполнения
одной таблицы необходимо проделать
операций, из чего получаем, что для вычисления всех функции
потребуется