Формирование оптимального портфеля ценных бумаг

Задача 2. На финансовом рынке имеются три вида ценных бумаг: бумаги первого вида – безрисковые ожидаемой эффективности , а бумаги второго и третьего видов – некоррелированные рисковые ожидаемых эффективностей и с рисками и соответственно.

Требуется решить задачу Тобина о формировании оптимального портфеля ценных бумаг минимального риска заданной эффективности . Как устроена рисковая часть оптимального портфеля? При какой ожидаемой эффективности портфеля возникает необходимость в проведении операции "короткая продажа" ("short sale")?

Решение:

Введем переменные, обозначив через долю капитала, вложенного в безрисковые ценные бумаги, через - долю капитала, вложенного в рисковые ценные бумаги 1-го вида, через - долю капитала, вложенного в рисковые ценные бумаги 2-го вида.

Для удобства записи применяемых при решении задачи формул примем следующие векторно-матричные обозначения:

- вектор-столбец долей рисковых составляющих портфеля;

- вектор-столбец эффективностей рисковых ценных бумаг;

- ковариационная матрица доходностей рисковых ценных бумаг;

.

Так как в данной конкретной задаче доходности рисковых ценных бумаг являются некоррелированными, то ковариационная матрица диагональная и имеет вид:

.

Вектор эффективностей рисковых ценных бумаг .

Оптимальное решение задачи Тобина о формировании портфеля минимального риска выражается формулами ([1], [2]):

, ;

где - матрица, обратная к ковариационной матрице .

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

. Заметим, что в случае диагональной матрицы справедлива формула , и нахождение обратной матрицы существенно упрощается.

Далее находим векторы-столбцы

, ;

вычисляем знаменатель основной формулы

.

Затем применим основную формулу и найдем вектор-столбец оптимальных долей рисковых ценных бумаг

.

Таким образом, в данной конкретной задаче , , т.е. рисковые доли оптимального портфеля должны быть одинаковыми. Здесь - заданная эффективность оптимального портфеля.

Используя долевое соотношение , находим безрисковую долю оптимального портфеля

.

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

2. Задача линейного программирования

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

Ресурсы	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции	Запасы ресурсов
	-
		-
Прибыль от единицы продукции (усл. ден. ед.)

Найти такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Требуется:

1) Составить математическую модель данной задачи.

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

3) Решить задачу симплекс-методом.

Решение:

1) Для составления математической модели поставленной задачи сначала введем переменные:

- количество единиц продукции , планируемое к выпуску;

- количество единиц продукции , планируемое к выпуску.

Затем запишем выражение целевой функции, имеющей смысл суммарной прибыли от реализации, выпущенной продукции: .

Далее составим систему ресурсных ограничений (затраты соответствующего ресурса не должны превышать его запаса):

По смыслу задачи переменные должны быть неотрицательными:

, .

В результате получаем математическую модель стандартной задачи линейного программирования в нормальной форме ([3]):

Найти такие значения переменных и , которые удовлетворяют системе линейных неравенств

и доставляют наибольшее значение целевой функции

.

2) при решении поставленной выше задачи линейного программирования графическим методом будем следовать приведенному в работе [4] алгоритму графического метода.

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

, опорные точки (0; 6) и (18, 0);

, опорные точки (0; 16) и (8, 0);

(горизонтальная прямая);

(вертикальная прямая);

(ось );

(ось ).

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

***

Далее находим вектор-градиент целевой функции и строим его, прикладывая в начале координат. Заметим, что целевая функция возрастает в направлении вектора-градиента. После этого строим нулевую линию уровня целевой функции , которая проходит через начало координат и перпендикулярна вектору-градиенту .

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

Наконец, определяем на пересечении, каких ограничивающих прямых лежит угловая точка : ; находим координаты этой точки, решая соответствующую систему уравнений

имеем (6; 4), т.е. , ; и вычисляем значение целевой функции в этой точке:

.

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

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

;

где .

Краткое описание алгоритма симплекс-метода содержится в работе [5], схему и терминологию которого мы будем использовать ниже.

Включим выражение целевой функции в систему уравнений канонической формы задачи и представим ее в специальном виде:

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

СТ-0

Все переменные специальной системы оказались разбитыми на две группы:

- базисные переменные , , , ( в СТ-0 им соответствуют "единичные" столбцы) и

- свободные переменные , (им соответствуют не "единичные" столбцы в СТ-0).

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

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

Опишем подробно первый шаг применения симплекс-метода, т.е. процедуру однократного замещения.

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

Далее находим отношения свободных членов СТ-0 к соответствующим положительным коэффициентам выделенного разрешающего столбца:

; ;

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

Далее вычисления организуются в следующем порядке:

- разрешающая строка делится на разрешающий элемент и переписывается в новую симплекс-таблицу СТ-1;

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

Этим заканчивается процедура однократного замещения, и в результате получаем новую симплекс-таблицу

СТ-1

						-3	-15
						-3
						-1

Новое опорное решение: , , , , , , а соответствующее ему базисное значение целевой функции .

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

Приведем последующие шаги табличной реализации симплекс-метода решения поставленной задачи:

СТ-2

			-2				-21
						-3
			-2
			-1

СТ-3

							-24

Таким образом, оптимальное решение рассматриваемой задачи линейного программирования выражается равенствами

, , , , , , а соответствующее ему оптимальное значение целевой функции .

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

,

то для приведения задачи к канонической форме следует заменить каждое такое неравенств равносильной ему системой соотношений:

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

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

3. Транспортная задача

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

Требуется:

1) Составить математическую модель транспортной задачи, заданной таблицей.

2) Найти оптимальный план перевозок груза, минимизирующий общую стоимость всех перевозок.

Решение:

1) Для составления математической модели данной транспортной задачи сначала введем переменные:

- количество единиц (тонн) груза, планируемое к перевозке из пункта отправления в пункт назначения ( ).

Затем запишем выражение целевой функции, имеющей смысл суммарной стоимости всех перевозок:

.

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

- все запасы груза должны быть вывезены;

- все потребности в грузе должны быть удовлетворены. Получаем следующую систему уравнений:

По смыслу задачи все переменные должны быть неотрицательными:

( )

Таким образом, приходим к следующей математической формулировке данной транспортной задачи:

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

Задача имеет решение, так как выполнено условие баланса: суммарные запасы груза равны суммарным потребностям.

2) Основными этапами решения поставленной транспортной задачи являются следующие:

- определение начального опорного плана;

- проверка полученного начального опорного плана на оптимальность;

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

Для нахождения начального опорного плана применим метод Фогеля. Приведем алгоритм метода Фогеля, следуя работе [4].

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

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

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

Обычно начальный опорный план, полученный методом Фогеля. Будет оптимальным, или близким к оптимальному.

Используя описанный алгоритм, получим следующий начальный опорный план:

				-				-
				-		-		-
						-

***

В результате реализации метода Фогеля все переменные оказываются разбитыми на 2 группы:

- базисные переменные : , , , , , , которые соответствуют ненулевым (загруженным) клеткам;

- свободные переменные : , , , , , , которые соответствуют нулевым (прочеркнутым) клеткам.

Проверим полученный методом Фогеля начальный опорный план на оптимальность. Для этого применим метод потенциалов, краткое изложение которого содержится, например, в работе [5].

Введем так называемые потенциалы пунктов отправления ( ) и потенциалы пунктов назначения ( ). Потенциалы найдем, решая систему линейных уравнений

,

где индексы и соответствуют группе базисных переменных .

В данном случае система уравнений для потенциалов имеет вид:

Составленная система содержит 6 уравнений и 7 неизвестных. Ранг системы равен . Следовательно, одна из неизвестных является свободной. Выберем в качестве этой переменной и примем ее равной нулю: .

Последовательно решая систему, найдем потенциалы всех поставщиков и потребителей:

, , , , , , .

Далее найдем так называемые косвенные стоимости в соответствии с формулой

,

где индексы и соответствуют группе свободных переменных :

, , ,

, , .

Затем вычисляем разности стоимостей (оценки свободных клеток) по формуле

.

Получим следующие значения оценок6

, ,

, ,

, .

Так как все оценки свободных клеток являются неотрицательными, то начальный опорный план, полученный методом Фогеля, является оптимальным.

Таким образом, искомый оптимальный план перевозок выражается равенствами

, , , ,

, , , ,

, , , .

Наименьшая суммарная стоимость всех перевозок, соответствующая найденному оптимальному плану, равна

(усл. ден. ед.)

5. Условный экстремум. Метод Лагранжа

Задача 5.

На развитие двух предприятий, входящих в производственное объединение, выделено2 млн.долл. Если первому предприятию выделить млн.долл, то прибыль, полученная от этого предприятия, будет равна млн.долл; если млн.долл. выделить ворому предприятию, по прибыль от него будет равна млн.долл.

Как следует распределить денежные средства между предприятиями, чтобы суммарная прибыль была максимальной?

Решить задачу методом множителей Лагранжа.

Решение.

Составим математическую модель данной задачи. Для этого сначала введем переменные:

(млн.долл.) – количество денежных средств, выделяемых первому предприятию;

(млн.долл.) – количество денежных средств, выделяемых второму предприятию.

Затем запишем выражение целевой функции, имеющей смысл суммарной прибыли производственного объединения:

.

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

В результате получаем задачу условного максимума функции двух переменных при ограничении типа равенства. Для решения этой задачи применим метод Лагранжа ([4], [5]).

Составим функцию Лагранжа

,

где - числовой параметр, называемый множитель Лагранжа.

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

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

, , ;

, , , .

Корень является посторонним; поэтому , , .

Получаем единственную стационарную точку функции Лагранжа .

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

Находим: , ;

; ;

;

, , , , ;

.

Так как дискриминант функции Лагранжа в стационарной точке отрицателен, то в соответствии с достаточным условием условного максимума функция имеет при , условный максимум. Значение целевой функции в точке условного максимума

.

Таким образом, наибольшая суммарная прибыль производственного объединения (млн.долл.) достигается при следующем распределении денежных средств между предприятиями:

млн.долл. и млн.долл.

6. Оптимальное распределение капиталовложений. Метод динамического программирования

Задача 6. В производственное объединение входят при предприятия. Прирост продукции каждого из них в зависимости от величины выделенных предприятию капиталовложений указан в приведенной ниже таблице.

предпр. 1	предпр. 2	предпр. 3

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

Капиталовложения (в усл.ден.ед.) каждому предприятию могут быть выделены только в размерах кратных 20 (усл.ден.ед.), и общий объем капиталовложений составляет (усл.ден.ед.).

Решить задачу о распределении денежных ресурсов методом динамического программирования

Решение.

Составим математическую модель данной задачи оптимального распределения ресурсов. Для этого сначала введем переменные:

- количество денежных средств, выделяемых -му предприятию ;

- соответствующий прирост выпуска продукции -го предприятия .

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

(1)

Далее запишем ресурсное ограничение

(2)

по смыслу задачи переменные должны быть неотрицательными:

, , . (3)

В результате получаем математическую формулировку задачи:

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

Решение поставленной задачи методом динамического программирования Беллмана содержит следующие основные этапы ([6]):

1) Вложение данной конкретной задачи в семейство подобных задач (инвариантное погружение задачи);

2) составление уравнения Беллмана, исходя из принципа оптимальности Беллмана;

3) Решение уравнения Беллмана4

4) Выделение решения исходной задачи из найденной функции Беллмана.

Перейдем к реализации указанных этапов.

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

, (4)

, (5)

. (6)

Введем функцию 2-х переменных - функцию Беллмана

,

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

2) Принцип оптимальности многошагового процесса впервые был сформулирован Р. Беллманом и заключается в следующем: завершающая часть процесса должна быть оптимальной относительно текущего реализовавшегося состояния. Математическим выражением для данной задачи является уравнения Беллмана ([6]):

, (8)

где , .

3) Уравнение Беллмана имеет очевидное краевое условие

(9)

Зная , из уравнения (8) последовательно находим:

,

где в силу краевого условия (9);

.

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

Приведем табличную реализацию изложенного выше решения уравнения Беллмана.