VladimirDobrovolsky611/Алгоритм SDDP: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
| Строка 12: | Строка 12: | ||
3. матрицы состояний <math>A_i^t, B_i^t, b_i^t, c_i^t</math> | 3. матрицы состояний <math>A_i^t, B_i^t, b_i^t, c_i^t</math> | ||
Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1) | Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1) | ||
[[File:Graph.png]] | [[File:Graph.png|рис.1 Сценарная решетка и выделенный сценарий (синим)]] | ||
== Вычислительное ядро алгоритма== | == Вычислительное ядро алгоритма== | ||
Версия от 10:39, 6 февраля 2017
Свойства и структура алгоритма
Общее описание алгоритма
Стохастическое двойственное динамическое программирование (SDDP) – это метод оптимизации, предназначенный для решения динамических задач в условиях неопределенности, то есть в случае, когда некоторые параметры задачи не являются детерминированными. В силу фундаментальности постановки задачи, данный алгоритм может быть применен в самых различных прикладных областях. Например, на сегодняшний день, стохастическое двойственное динамическое программирование активно используется для управления ГЭС в Норвегии, а также вводится в банках для управления рыночными рисками. На сегодняшний день также широко распространены альтернативные динамические методы поиска решений в условиях неопределенности, например, методы, работающие на принципах построения дерева возможных исходов, или методы, работающие на принципах управляющих правил. Однако, методы, работающие по принципу построения дерева, неизбежно сталкиваются с широко известным «проклятием размерности» (curse of dimensionality), а методы, построенные на принципах управляющих правил, как правило, требуют серьезные ограничения на тип управляющих правил, а также на свойства стохастических параметров задачи. Также, в задачах динамического управления присутствует проблема тайм-консистентности решения (time-consistence solution).
Алгоритм SDDP (Stochastic dual dynamic programming) впервые был предложен в статье M.V.F. Pereira и L.M.V.G. Pinto "Multi-stage stochastic optimization applied to energy planning" в 1991 году. Далее алгоритм претерпел множество модернизаций и спецификаций, описанных в труде Alexander Shapiro, Darinka Dentcheva, Andrzej Ruszczynski "Lectures on Stochastic Programming: Modeling and Theory", Теперь под аббревиатурой SDDP подразумевается целое семейство алгоритмов.
Математическое описание алгоритма
Исходные данные:
1. Количество этапов T, количество состояний на каждом этапе [math]\displaystyle{ N_t }[/math], [math]\displaystyle{ t = 1,...,T }[/math] 2. Вероятности переходов [math]\displaystyle{ p_{nt}; t = 1,...,T; n = 1,...,N_t }[/math] 3. матрицы состояний [math]\displaystyle{ A_i^t, B_i^t, b_i^t, c_i^t }[/math]
Совокупность входных параметров в пунктах 1 - 3 формируют сценарную решетку задачи (см. рис. 1)
