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

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

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

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

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

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

Методы активной группы - это методы поиска, в которых при каждой итерации подгруппа ограничений в виде неравенств вместе со всеми ограничениями в виде равенств являются активными (действующими). В этом случае итерация состоит в попытке

движения из текущей точки, которая удовлетворяет всем активным ограничениям как равенствам, в наилучшую точку, которая удовлетворяет всем активным ограничениям как равенствам.

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

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

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

УПРАЖНЕНИЯ

1. Что вы понимаете под терминами целевая функция , ограничения , математическое программирование , линейное программирование и квадратическое программирование ?

2. Представьте графическое решение для следующей задачи линейного программирования.

Максимизировать (доход): 0,10% + 0,18% + 0,07% при:

(а) 0,8%+ 1,3%+ 1,1 %< 1

(б) 0<%<;1 0 <> % <> 1

0<;%<;1

(в) %+%+%=!

3. Как вы понимаете термины базисная и небазисная в отношении линейного программирования?

4. Используйте симплексный метод для решения задачи из вопроса 2.

5. Рассмотрите три актива А, В и С с ожидаемыми доходами 8%, 18% и 7%. Дисперсионно-ковариационная матрица выглядит как

0,00013 0,00004 -0,00008 П= 0,ООЪ04 0,00022 -0,00002 -0,00008 - 0,00002 0,00009

Поставьте оптимизационную задачу, которая минимизирует дисперсию портфеля при условии достижения минимального дохода 12%. Замечание: вам не нужно решать эту задачу, определите только целевую функцию и ограничения.

6. Определите лагранжиан, применимый к указанной выше задаче.

7. Что вы понимаете под условиями Кюна-Такера ? Определите условия Кюна-Такера, соответствующие задачам из вопросов 5 и 6.

ОТВЕТЫ

К ИЗБРАННЫМ

УПРАЖНЕНИЯМ

2. Используйте Wa + Wb + Wc = 1, чтобы выразить Wc как 1- Wa- Wb. Подстановка дает:

максимизировать 0,10Wo > Q,lSWb + 0,07(1-И-й) = 0,03+ 0,11 W4 + 0,07

при 0,8ЖЙ + 1.3И4+ 1,1(1-И/-Жй)5 1,

что упрощается до Wb < 1,5 Wa 0 5 Wa< 1 0 5 Wb< 1

Решение: Wa = 0,4; Wb = 0,6; Wc = 0; доход = 0,148.

4. Использование преобразованной задачи с двумя переменными как в вопросе 2.

(Заметьте, что вторая строка показывает -3Wa + 2И4<0, что то же самое, что и lV/l,SWa).