Математические методы исследования операций в экономике (стр. 30 из 37)

и т. д. или, в общем виде,

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

Выигрыш, который дает применение рассмотренного алгоритма, может также быть оценен с помощью следующего простого примера. Сравним приблизительно по числу операций (состоящих, в основном, из вычислений целевой функции) описанный метод с прямым перебором допустимых планов задачи (5.3)-(5.4) при а₁=a₂ = ...а_n=1.

Количество допустимых планов такой задачи совпадает с количеством целочисленных решений уравнения

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

В случае применения метода динамического программирования для вычисления таблицы значений функции Λ_k(ξ) при фиксированном ξ необходимо выполнить (ξ+1) операций. Поэтому для заполнения одной таблицы необходимо проделать

операций, из чего получаем, что для вычисления всех функции

потребуется

операций, что при больших n и b существенно меньше, чем в первом случае. Например, если п = 6 и b = 30, то непосредственный перебор потребует выполнения 324 632 операций, а метод динамического программирования — только 2511.

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

Перечислим основные требования к задачам, выполнение которых позволяет применить данный подход:

- объектом исследования должна служить управляемая система (объект) с заданными допустимыми состояниями и допустимыми управлениями;

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

- задача не должна зависеть от количества шагов и быть определенной на каждом из них;

- состояние системы на каждом шаге должно описываться одинаковым (по составу) набором параметров;

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

Рассмотрим вопросы применения модели динамического программирования в обобщенном виде. Пусть стоит задача управления некоторым абстрактным объектом, который может пребывать в различных состояниях. Текущее состояние объекта отождествляется с некоторым набором параметров, обозначаемым в дальнейшем ξ и именуемый вектором состояния. Предполагается, что задано множество Ξ всех возможных состояний. Для объекта определено также множество допустимых управлений (управляющих воздействий) X, которое, не умаляя общности, можно считать числовым множеством. Управляющие воздействия могут осуществляться в дискретные моменты времениk(k∊1:n), причем управленческое решение заключается в выборе одного из управлений x_k∊Х. Планом задачи или стратегией управления называется вектор х=(х₁, х₂, .., x_n-1), компонентами которого служат управления, выбранные на каждом шаге процесса. Ввиду предполагаемого отсутствия последействия между каждыми двумя последовательными состояниями объекта ξ_k и ξ_k+1 существует известная функциональная зависимость, включающая также выбранное управление:ξ_k+1 = φ_k(x_k , ξ_k),k∊1:п-1. Тем самым задание начального состояния объекта ξ₁∊Ξ и выбор плана х однозначно определяют траекторию поведения объекта, как это показано на рис. 5.1.

Эффективность управления на каждом шаге k зависит от текущего состояния ξ_k , выбранного управления x_k и количественно оценивается с помощью функций f_k(х_k, ξ_k), являющихся слагаемыми аддитивной целевой функции, характеризующей общую эффективность управления объектом. (Отметим, что в определение функции f_k(х_k, ξ_k) включается область допустимых значений х_k , и эта область, как правило, зависит от текущего состояния ξ_k .) Оптимальное управление, при заданном начальном состоянии ξ₁ , сводится к выбору такого оптимального плана х*, при котором достигается максимум суммы значений f_k на соответствующей траектории.

Основной принцип динамического программирования заключается в том, что на каждом шаге следует стремиться не к изолированной оптимизации функции f_k(х_k, ξ_k), а выбирать

оптимальное управление х_k* в предположении об оптимальности всех последующих шагов. Формально указанный принцип реализуется путем отыскания на каждом шагеk условных оптимальных управлений

_k(ξ), ξ∊Ξ, обеспечивающих наибольшую суммарную эффективность начиная с этого шага, в предположении, что текущим является состояние ξ.

Обозначим Λ_k(ξ) максимальное значение суммы функций f_k на протяжении шагов от k до п (получаемое при оптимальном управлении на данном отрезке процесса), при условии, что объект в начале шага k находится в состоянии ξ . Тогда функции Λ_k(ξ) должны удовлетворять рекуррентному соотношению:

где ξ_k+1 = φ_k(x_k, ξ)

Соотношение (5.14) называют основным рекуррентным соотношением динамического программирования. Оно реализует базовый принцип динамического программирования, известный также как принцип оптимальности Беллмана:

- Оптимальная стратегия управления должна удовлетворять следующему условию: каково бы ни было

начальное состояние ξ_k на k-м шаге и выбранное на этом шаге управление х_k,, последующие управления (управленческие решения) должны быть оптимальными по отношению к состояниюξ_k+1 = φ_k(x_k, ξ_k), получающемуся в результате решения, принятого на шаге k.

Основное соотношение (5.14) позволяет найти функции Λ_k(ξ) только в сочетании с начальным условием, каковым в нашем случае является равенство

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

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

В то же время, говоря о динамическом программировании как о методе решения оптимизационных задач, необходимо отметить и его слабые стороны. Так, в предложенной схеме решения задачи (5.3)-(5.4) существенным образом используется тот факт, что система ограничений содержит только одно неравенство, и, как следствие, ее состояние задается одним числом — нераспределенным ресурсом ξ . При наличии нескольких ограничений состояние управляемого объекта на каждом шаге характеризуется уже набором параметров ξ₁, ξ₂,..., ξ_m, и табулировать значения функций Λ_k (ξ₁, ξ₂,..., ξ_m) необходимо для многократно большего количества точек. Последнее обстоятельство делает применение метода динамического программирования явно нерациональным или даже просто невозможным. Данную проблему его основоположник Р. Беллман эффектно назвал «проклятием многомерности». В настоящее время разработаны определенные пути преодоления указанных трудностей. Подробную информацию о них можно найти в специальной литературе [4, 5].