- •Формальное описание алгоритма 1 задачи “Ближайшая пара”
- •Лекция 2 Задача о битоническом пути
- •Битонический путь
- •Лекция 3 Динамическое программирование и оптимизационная задача перемножения матриц.
- •2. Алгоритмизация описанного процесса на основе (2) и (3).
- •Лекция 4 Оптимальная триангуляция треугольника.
- •Лекция 5
- •Циркуляция.
- •Алгоритм гомори—ху
- •Лекция 6 Многополюсные максимальные потоки
- •Лекция 7 Задача распределения капитала
- •1. Случай запрета коротких позиций.
- •2. Случай разрешения коротких позиций.
- •Случай наличия безрискового актива.
- •Лекция 8 Потоковые алгоритмы.
- •Лекция 9. Алгоритм Гомори.
- •Лекция 10 Многополюсные минимальные потоки.
- •Лекция 11 доминирующие множества и абсолютный центр.
- •Доминирующие множества.
- •Нахождение абсолютного p-центра
- •Ленкция 12 простой (классический) генетический алгоритм.
- •Лекция 13 Стохастическая задача размещения-распределения объектов.
Лекция 7 Задача распределения капитала
Рассматривается задача распределения капитала, который участник рынка хочет потратить на покупку ценных бумаг.
Пусть
переменные xi
-
доли капитала, потраченные на покупку
ценных бумаг i-го
вида (i=1,…,n)
(
).
Доходность бумаг – случайная величина. Значит, и доходность портфеля – случайная величина. Поэтому можем говорить об числовых характеристиках доходностей – математическом ожидании и среднем квадратическом отклонении.
Пусть
- доходность бумаг j-того
вида. Определим эффективность (доходность)
портфеля:
.
Пусть
mj-
математическое ожидание доходности
бумаг j-того
вида: mj
=
.
Тогда формула ожидаемого эффекта
портфеля:
.
В
качестве меры риска взяли квадрат
среднего квадратического отклонения
стоимостей акций, т.е. дисперсию дисперсия
эффективности портфеля (риск):
.
Здесь Vij-ковариация доходностей ценных бумаг i-го и j-го видов, Vii- вариация i-той доходности.
Акциям,
по которым короткие продажи запрещены,
соответствуют ограничения
,
а другим – ограничения вида
,
где
(ограничения, когда по какой-либо акции
инвестор может встать на короткую
позицию, получив средств не более, чем
заданную долю имеющегося капитала.).
Также
возможны дополнительные ограничения
вида
(
)
(ясно, что ограничения любого знака
можно свести к такому виду, чем мы и
воспользовались), необходимые, например,
если суммарная доля некоторых акций не
должна превышать заданной величины,
или
и т.п.
Ставится задача найти множество Парето в плоскости (m,V) и его образ в (m,x) (юго-восточная граница).
Она принимает вид:
Теоретически
доказано, что образ области допустимых
решений в пространстве (m,V)
такой, что верхняя его граница состоит
из конечного числа парабол, а его
юго-восточная граница выпукла и похожа
на параболу:
1. Случай запрета коротких позиций.
Сначала
задачу сведём к однокритериальной,
решая задачу минимизации риска при
различных фиксированных значениях
доходности портфеля
.
В предлагаемом варианте задача будет решаться с помощью метода Вулфа, с введением функции Лагранжа и применением симплекс – метода. Здесь необходимо помнить, что метод Вулфа применим только в случае неотрицательной определённости матрицы V.
Чтобы избавиться от имеющихся равенств, выразим из них две переменные xi* и xk*, соответствующие минимальной (min{mi}) и максимальной (max{mi}) доходностям:
Здесь
- функции, линейно зависящие от параметра
.
Придём к такой функции Лагранжа:
Здесь вектор х’ имеет на 2 элемента меньше, чем вектор х (вычеркнуты элементы с номерами i* и k*).
Функция V’(х) получена из функции V(х) путём подстановки в последнюю выражений для xi* и xk* :
где
матрица
получена из матрицы V
просто путём вычёркивания из последней
строк и столбцов с номерами i*
и k*,
линейна по
,
а
квадратична.
Далее будем использовать обозначение х вместо х’.
Матрицу A и вектор b также необходимо преобразовать:
-
не зависит от mp,
-
линейно зависит от mp.
Кроме того, к матрице А’ добавлены ещё 2 строки, соответствующие условиям неотрицательности переменных xi* и xk*:
Переобозначим:
.
Таким образом, пришли к задаче:
Взяв производные и введя дополнительные переменные, получим систему:
Пользуясь методом Вулфа, получим систему уравнений Куна-Таккера в канонической форме:
Затем
вводим переменные
для первого уравнения и
для второго (в базисные) и используем
метод искусственного базиса, взяв
сначала в качестве искусственных
переменных
,
а потом
.
Задача для :
Задача для :
Дадим формальное описание алгоритма:
Вход: количество акций n, количество ограничений m типа Ах>=b, количество разрешённых коротких продаж, величины li , {mi}, {Vij}.
Выход: доли xi, графики xi(m), V(m).
mp:=min mi
while mp<=max mi do
3. SM( ,v1,x1)
4. if v1 = 0 then
5. SM( ,v2,x2)
6. Count (х*, V*) //2-ая задача всегда разрешима – доказано!
7.
if (m,V*)
Im(П)
then PutPixel (m,V*); PutPixel(m,x*)
8. else return НР1
9. mp:=mp+0.001
Здесь SM(w) означает вызов процедуры симплекс – метода с базисными переменными w.
Пример 1 (без ограничений).
Пример 2 (с ограничениями).
Здесь m уже меняется не от 23.583 до 29, а от 25.404.
