интересно
Предыдущая | Содержание | Следующая

Стандартные методы решения задач стохастического программирования

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

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

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

Приведем подробное описание для первого представления.

. Эти допущения позволяют сформулировать детерминированный эквивалент исходной задачи в виде

здесь вектор переменных решения соответствует каждой вершине дерева решений.

В матричных обозначениях многошаговая линейная задача записывается следующим образом:

где

что порождает в конечном счете задачи весьма большой размерности по мере нарастания числа сценариев.

Прямая задача линейного программирования:

Двойственная задача линейного программирования:

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