WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 41 |

Если банк не имеет лицензии на операции с драгоценными металлами, что характерно для большинства отечественных кредитных организаций, то из задачи (45) исключается норматив Н14, и она преобразуется к виду:

НJ (x0) = max НJ (x ); J = 2, 3;

x = S ; i =1, n;

xi (46) i R3(x0) r;

Н1(x0) Н1min.

Задача (42) для нормативов ликвидности Н2, Н3 и критерия доходности R3 будет иметь вид:

НJ (x0) = max НJ (x ); J = 2, 3;

x R3 (x0 ) = max R3 (x );

x (47) = S ; I =1, n;

xi i Н1(x0 ) Н1min.

Для критериев доходности R3 и надежности по Кромонову N (x ) задача (42) записывается следующим образом:

R3 (x0) = max R3 (x );

x N (x0) = max N (x );

x = S ;i =1, n; (48) xi i НJ (x0 ) НJ ; J =1, 2, 3, 5,14;

min Н4 (x0 ) 120 %.

2.6.2.5 АЛГОРИТМЫ СКАЛЯРНОЙ ОПТИМИЗАЦИИ Для применения различных методик оптимизации структуры активов была построена модель в программной среде Excel 7.0.

Задача скалярной оптимизации решалась в программной среде Excel 7.0 средствами модуля Solver.xla.

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

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

Чтобы найти оптимум (для определенности – максимум) критерия F(X), нужно выбрать последовательность точек Хi (i = 1,..., n), для которых будут выполнены условия:

F(Х1) < F(Х2) < … < F(Хi) < F(Хn). (49) Как только в этой последовательности появится вектор Xn + 1, такой, что F(Xn) > F(Xn + 1), это будет означать, что при Xn < X* < Xn + 1, функция F(A*) достигает максимума. Способ нахождения последовательности Х1, Х2,... Хn определяет стратегию поиска. В Excel реализована одна из стратегий, относящаяся к группе методов, именуемых градиентными (метод сопряженных градиентов). В этих стратегиях точки Хi вычисляют по формуле:

Хi + 1 = Хi + aiPi. (50) где ai – скаляр, определяющий длину шага вдоль этого направления (при поиске минимума в формуле – минус); Рi – вектор, задающий направление поиска.

Для определения вектора Рi используется понятие градиента. Градиент F (Хi) скалярной функции векторного аргумента F(X) в точке Хi – вектор, направленный в сторону наискорейшего возрастания функции и ортогональной поверхности уровня [поверхности постоянного значения функции F(X)], проходящей через точку Хk. Выражение (52) можно записать в координатной форме:

xji + 1 = xji + aiGj(Xi); j = 1, 2, …, k, (51) где Gj – j-я компонента вектора градиента. Графическая интерпретация градиентного метода представлена на рис. 1.

Поскольку явный вид функции F(Х) неизвестен, вычислительный процесс градиентного поиска строят следующим образом. Произвольно выбирают начальную точку Х1 и в этой точке вычисляют значение функции F(Х1). Всем компонентам вектора Х1 дают малые приращения Dхj (j = 1, 2,..., k) и формируют вектор Х2 = Х1 + DX. Затем выполняют пробный шаг, т.е.

вычисляют значение функции F(Х2). Если F(Х1) < F(Х2), то пробный шаг признается удачным и вычисляются компоненты вектора градиента:

F (X ) - F (X1) Gj = ; j =1, 2,..., k. (52) x j Если F(Х1) > F(Х2), то пробный шаг неудачен. Поэтому знаки всех приращений Dxj меняются на противоположные, меняется и направление вектора градиента. Найдя нужное направление, выбирают величину шага ai и продолжают процесс, выстраивая последовательность векторов {X}, удовлетворяющую условию (49).

Проблема выбора шага – важнейшая во всей процедуре. Именно способом выбора шага отличаются друг от друга различные градиентные методы. Дело в том, что при малом шаге поиск будет почти наверняка успешным, т.е. сходящимся к искомому оптимуму, но потребует много времени на вычисления. Большой шаг, экономя время, не гарантирует сходимости, поскольку оптимум можно «проскочить». Наконец, бывают ситуации, когда процесс поиска зацикливается. Пусть нужно найти минимум функции F(x) = bx2, где b – положительное число. Для этой функции формула (50) имеет вид:

x = (1- 2ak b)x. (53) k +1 k Рис. 1 Градиентный метод оптимизации При определенных обстоятельствах возможна следующая ситуация: x1 = -x0; x2 = x0; x3 = -x0..., т.е. вычислительный процесс зацикливается (рис. 2).

При использовании градиентных методов помимо несходимости и зацикливания имеется еще одна проблема (рис. 3).

Если искать оптимум функции F(x) градиентным методом и выбрать стартовую точку в интервале [xmin, x0], то поиск приведет нас в вершину, обозначенную как max.

найденная истинная вершина вершина погрешность начало поиска Рис. 2 Проблема зацикливания алгоритма оптимизации Рис. 3 Проблема подмены глобального оптимума локальным Однако из графика видно, что оптимальная точка есть правая граница интервала, которую в такой ситуации называют глобальным (или истинным) оптимумом, в то время как найденная вершина – локальный оптимум. При поиске оптимума на многомерных поверхностях со сложной топологией всегда существует опасность «застрять» на локальном оптимуме и никогда не добраться до глобального. Способ избежать этого состоит в повторении поиска из различных стартовых точек.

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

Следует заметить, что, несмотря на относительную простоту используемых в финансовой модели функций, в ходе вычислений возникли проблемы с критерием останова, которые были решены уменьшением параметра в диалоговом окне «сходимость» до 0,000000005.

2.6.2.6 МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ВЕКТОРНОЙ ОПТИМИЗАЦИИ Нормализация критериев Как правило, в большинстве задач многокритериальной оптимизации критерии имеют существенно различный физический (экономический) смысл, разные единицы измерения, поэтому сравнение критериев по численному значению невозможно, что в значительной степени затрудняет применение всех методик многокритериальной оптимизации.

Поэтому в большинстве случаев в решение многокритериальной задачи требуется включение предварительного этапа – нормализации критериев.

N N Нормализация критериев представляет собой однозначное отображение функции fk (X ),k K, из R в R. Для нормализации критериев в векторных задачах используется линейное преобразование:

fk (X ) = afk (X ) + c,k K (54) или fk (X ) = ( fk (X ) + c) / a,k K, (55) где fk (X ),k K – первоначальное значение критерия; fk (X ),k K – нормализованное значение.

Такая нормализация критериев в оптимизационной задаче не влияет на результат решения. В случае, если решается выпуклая оптимизационная задача:

max F (X ), X S, (56) X то в точке оптимума * * X S,dF (X ) / dX = 0. (57) Если же решается оптимизационная задача:

max(aF (X ) + c), X S, (58) X то в точке оптимума * * X S,d(aF (X ) + c) / dX = 0, (59) т.е. результат идентичен.

К нормализации критериев в векторных задачах предъявляются два основных требования:

• нормализованные критерии должны быть измерены в одних и тех же величинах;

* • в точках оптимума X,k K величины всех критериев должны иметь одинаковую величину.

k При выполнении этих требований представляется возможным сравнить критерии по их численному значению.

В нашем случае – решении задачи многокритериальной оптимизации с максимумом векторной целевой функции применяется следующая нормализация критериев:

k (X ) = ( fk (X ) - fkmin ) /( fk* - fkmin ). (60) При этом относительная оценка k (X ),k =1, K на всем множестве допустимых точек лежит в пределах 0 k (X ) 1, k =1, K, X S. (61) При этом величины 1 – k ( X ) называются относительными отклонениями k (X ).

Следует заметить, что при всех достоинствах предварительной нормализации критериев у нее имеется важный недостаток (общий для всех относительных величин) – нормализованный критерий не всегда имеет столь однозначную экономическую интерпретацию, как обычный. Например, если относительная оценка критерия f9 – норматив текущей ликвидности – равна 0,9 (т.е. 90 % от максимально возможной), то трудно сказать, достаточный ли это показатель для банка.

Если же знать, что в абсолютных величинах данная величина составляет 94 % (при максимуме в 106 %), а требуемое инструкцией минимальное значение составляет 70 %, то на основании этого можно сделать более определенные выводы.

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

Методика построения множества Парето-оптимальных решений Выделение Парето-оптимального подмножества – достаточно трудная задача, для которой пока не известен универсальный алгоритм. Однако для некоторых частных случаев такие алгоритмы известны, например, для случая линейной задачи векторной оптимизации существует обобщенный вариант симплекс-метода, который позволяет выделить все Парето-оптимальные крайние точки и неограниченные эффективные ребра. Однако в нашем случае он не подходит, так как некоторые из целевых функций являются нелинейными. В этом случае напрашивается решение, использующее идею полного просмотра всех возможных вариантов решений и выбора из них лучшего. Однако, естественно, что такой полный просмотр невозможен, так как количество точек просмотра бесконечно. Для того, чтобы уменьшить количество просматриваемых точек можно (конечно, в ущерб получаемого объема информации) каким-либо разумным способом организовать процедуру просмотра. На этой идее и основан метод решения проектно-конструкторских задач с противоречивыми критериями, предложенный И. М. Соболем и Р. Б. Статниковым и основанный на утверждении, что максимальное число просматриваемых точек при минимуме вычислений достигается, если точки выбираются из так называемой ЛП-последовательности. Название ЛП-последовательность появилось как сокращение фразы "бесконечные последовательности точек, любой двоичный участок которых есть П-сетка". Таким образом, просматривая варианты в точках, соответствующих ЛП-последовательности и, вычисляя значения критериев в этих точках, можно принимать обоснованные решения. Для выделения среди полученных точек Парето-оптимальных используется метод, основанный на применении алгоритмов сортировки. Достоинством данного метода является отсутствие необходимости решения скалярных задач оптимизации, которые в некоторых случаях (сложные нелинейные функции с обилием разрывов и т.д.) требуют значительных затрат машинного времени. В нашем случае это не столь актуально, как в инженерных задачах, так как экстремумы всех использованных функций легко вычисляются.

Поэтому в качестве метода построения множества Парето был выбран приближенный графоаналитический метод Н. Н.

Моисеева, который заключается в последовательном итеративном процессе решения простейших оптимизационных задач. В случае двух критериев он применяется следующим образом: сначала задаются начальными произвольными значениями критериев: f1 = c1; f2 = c2. Затем решаются две оптимизационные задач:

1) max f1, f2 = c2; 2) max f2, f1 = c1. (62) Решив эти две задачи находят точки a и b. Прямая, соединяющая эти две точки является областью Парето в первом приближении. Далее решаются две аналогичные задачи. При этом задаются значениями критериев: f1 = c3; f2 = c4. Затем решаются две оптимизационные задачи:

1) max f1, f2 = c4; 2) max f2, f1 = c3. (63) Через полученные точки снова проводят прямые. После соединения точек c и d получают ломаную acdb, которая является областью Парето второго приближения. В большинстве случаев второе приближение является достаточным.

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

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

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

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

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 41 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.