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

МАТЕМАТИЧЕСКИЕ ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ, КОТОРЫЕ ОСНОВАНЫ НА НЕЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

• Введение
• 1. Условия оптимальности. Теорема Куна-Таккера
• 2. Методы условной оптимизации. Метод Вульфа
• 3. Метод проектирования градиента
• 4. Метод штрафных функций
• 5. Метод барьерных функций
• 6. Другие методы условной оптимизации
• 7. Примеры методов нелинейного программирования
• 8. Примеры методов нелинейного программирования
• Вывод
• Литература
• Введение
• Реферат посвящен решению задач исследования операций с помощью нелинейного программирования.
• Методы нелинейного программирования применяются для решения задач с нелинейными функциями переменных.
• Как известно, в общем случае задача математического программирования записывается в виде:
• (1.1)
• Если хотя бы одна функция в модели (1.1) нелинейная, имеем задачу нелинейного программирования (НП). Размерность задачи характеризуется размерностью вектора переменных n и числом условий m₁+m₂. Однако сложность задачи определяется не столько размерностью, сколько свойствами функций цели и ограничений.

Разнообразие задач НП очень велико. Универсальных методов решения таких задач не существует. Имеется весьма ограниченное число точных методов и намного больше приближенных.

Наиболее развиты методы решения задач выпуклого программирования. К этому классу относятся задачи НП с выпуклым допустимым множеством и выпуклой целевой функцией при минимизации или вогнутой при максимизации. Допустимое множество выпуклое, если все функции линейные и выпуклы при неравенстве или вогнуты при. Например, условие x₁²+x₂² r² порождает выпуклое множество, пересечение которого с прямой x₁+x₂=0 дает тоже выпуклое множество. Очевидно, что задачи НП относятся к этому классу. Главная особенность задач выпуклого программирования в том, что они унимодальные, то есть любой их локальный оптимум является глобальным. Для ряда задач выпуклого программирования с дифференцируемыми функциями разработаны точные методы. Наибольшие сложности возникают при решении многоэкстремальных задач, которые по определению не относятся к классу выпуклых.

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

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

Кусочно-линейное программирование включает специальные методы решения задач с кусочно-линейными функциями. В частности, такими являются функции и если все f_i(x) — линейные функции. Первая из них — выпуклая (рис. 1.1), вторая — вогнутая. Задачи с такими функциями могут входить в класс задач выпуклого программирования. Их решение строится на преобразовании модели к линейному виду с последующим применением методов ЛП.

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

1. Условия оптимальности. Теорема Куна-Таккера

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

Пусть дана задача в виде

(1.2)

Обобщенный метод множителей Лагранжа применим и к условиям-неравенствам. Запишем функцию Лагранжа (регулярную) для задачи (1.2)

. (1.3)

В теории НП показано, что эта функция имеет седловую точку (X*,*) c максимумом по X и минимумом по :

F(X, *) F(X*, *) F(x*,). (1.4)

Поэтому задача (1.2) сводится к отысканию седловой точки функции (1.3).

Теорема. Пусть f, _i и _k — дифференцируемые функции и справедливо свойство Слейтера (то есть найдутся такие XD, что неравенства _i будут строгими). F(X,) — соответствующая функция Лагранжа. Тогда для того чтобы вектор X* являлся решением общей задачи максимизации (1.2) необходимо выполнение условий

1) по X:

(1.5)

(1.6)

X_j^* 0;

2) по :

(1.7)

(1.8)

(1.9)

Приведенные условия оптимальности называются условиями Куна-Таккера. Опуская строгое доказательство, приведем логическое обоснование выражений (1.5)-(1.9).

По существу они являются обобщением классических условий экстремума, определяющих стационарные точки. Условие (1.5) содержит неравенство, так как неотрицательность вектора X означает, что максимум может быть либо при положительном X и тогда производная F по X обязательно равна нулю (случай 1 на рис. 1.2), либо при X=0 и тогда эта производная может быть как равной нулю, так и отрицательной (случаи 2 и 3 на рис. 1.2). Этим же объясняются условия дополняющей нежесткости (1.6): в точке максимума равны нулю либо x, либо производная, либо вместе.

Выражения (1.7)-(1.9) можно обосновать аналогично, если учесть, что по рассматривается минимум F и .

Применив условия Куна-Таккера к задаче НП, получим равенства второй основной теоремы двойственности как частный случай условий дополняющей нежесткости, а двойственные переменные — как частный случай .

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

2. Методы условной оптимизации. Метод Вульфа

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

Из большого числа методов условной оптимизации можно выделить 3 основные группы:

· методы возможных направлений: метод проектирования градиента, методы Зойтендейка, Вулфа и др.;

· методы штрафных и барьерных функций;

· модификации методов безусловной оптимизации.

Методы первой группы отличаются способом определения возможных направлений. Направление d в точке x^kD называется возможным направлением, если существует 0, при котором

Эти условия означают, что на направлении d найдутся допустимые точки, в которых значение функции лучше, чем в точке x^k.

Ниже рассматривается один из методов возможных направлений.

3. Метод проектирования градиента

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

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

Пусть ограничения заданы в виде

(1.10)

Найдем возможное направление l, на котором скорость изменения целевой функции максимальна:

(1.11)

В допустимой области D функции _j постоянны. Поэтому искомое направление должно удовлетворять системе равенств

(1.12)

Из связи направления с координатами следует:

что перепишем в виде (1.13)

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

Запишем функцию Лагранжа:

. (1.14)

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

Отсюда выразим компоненты искомого вектора:

(1.15)

Подставив (1.15) в (1.13), находим:

С учетом этого выражения формула (1.15) принимает вид

(1.16)

Для определения неизвестных множителей _j воспользуемся системой (1.12). Подставив в нее (1.16), получаем:

После раскрытия скобок окончательно имеем:

(1.17)

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

Аналогично градиентному методу новая точка вычисляется по формуле

. (1.18)

Алгоритм метода проектирования градиента.

1. Задать начальную точку, удовлетворяющую системе (1.10), начальное значение h⁰ и точность по величине проекции градиента .

2. В текущей точке вычислить градиенты всех функций (f и _j) и решить систему (1.17).

3. Вычислить проекцию градиента по формуле (1.16).

4. Проверить: если завершить поиск.

5. Вычислить новую точку по формуле (1.18).

6. Проверить: если значение целевой функции улучшилось, перейти на шаг 2, иначе уменьшить h^k в два раза и перейти на шаг 5.

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

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

Если, то включается процедура коррекции, заключающаяся в минимизации невязки:

(1.19)

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

Теперь рассмотрим случай, когда ограничения заданы в виде неравенств _j(x)0. Поиск начинается из точки, в которой удовлетворяются все ограничения. Пока они выполняются как строгие, движение осуществляется по градиентному методу. Когда достигается граница допустимого множества, одно или несколько ограничений обращаются в равенства. Такие ограничения называют активными.

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

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

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

4. Метод штрафных функций

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

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

f(x) > min; (1.20)

_i(x) 0,; (1.21)

_i(x) = 0,. (1.22)

Тогда можно построить вспомогательную функцию

(x) = f(x) + H(x), (1.23)

где H(x) -функция штрафа, — параметр штрафа.

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

(1.24)

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

Примеры

Пример 1: f(x) = x > min; (x)=3 — x 0.

Ответ очевиден: x^*=3. Теперь сведем эту задачу к определению безусловного экстремума вспомогательной функции. Построим штрафную функцию в соответствии с (1.24): H = [max (0, 3-x)]². Тогда приходим к задаче =x+[max (0, 3-x)]² min.

На рис. 1.6 и 5.6 показаны соответственно функции H и для двух значений. Видно, что точки минимума вспомогательной функции с увеличением приближаются к точке условного минимума исходной задачи. Такой же вывод следует из аналитического решения. Действительно, при x<3 вспомогательная функция имеет вид: = x + (3 — x)².

Находим минимум этой функции:

Отсюда получаем

Пример 2: Рассмотрим влияние параметра шага в задаче Здесь и

На рис. 1.7 построены линии уровня функции для разных значений и линия ограничения .

При =0 имеем =f, и минимум достигается в точке безусловного минимума f: x₁=x₂=1. С увеличением меняется форма линий уровня и положение минимума. При =1 минимум смещается к линии ограничения, а при =1000 он практически точно совпадает с условным минимумом задачи.

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

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

Алгоритм.

1. Задать: начальную точку x⁰, точность, начальное значение ₀ и число >1.

2. Минимизировать (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если, то остановиться, приняв за оптимальное решение задачи.

Положить, за начальную точку принять и вернуться на шаг 2.

Рекомендуется выбирать значения параметров алгоритма из диапазонов: ₀(0,1], (1,10]. Начальную точку следует задавать в недопустимой области.

Пример 3: Алгоритмом штрафных функций решить задачу Возьмем начальную точку x⁰=(-5;5), ₀=0,21, =5 и =0,0001. Применяя для минимизации метод Ньютона, получаем результаты, представленные в табл. 1.1.

Как следует из табл. 1.1, решение с заданной высокой точностью получено за 11 итераций алгоритма. Заметим, что несмотря на увеличение значение H сходится к нулю, обеспечивая сходимость алго-ритма.

Траектория поиска и линии уровня функции f изображены на рис. 1.8.

Таблица 1.1 Минимизация функции методом Ньютона

Пример 4: Алгоритмом штрафных функций решить задачу Этот пример показан на рис. 1.9. Поиск проводится из начальной точки (-2;-7) с параметрами ₀=0,1 и =2.

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

Пример 5: Алгоритмом штрафных функций решить задачу Этот пример приведен на рис. 1.10. Поиск производился при ₀=1 и =10. Такие параметры обусловили другой характер движения к условному минимуму: первая итерация уже не приводит в окрестность безусловного экстремума и траектория не имеет резких изменений направ-ления поиска.

Таким образом, выбор параметров поиска имеет существенное влияние на эффективность алгоритма.

5. Метод барьерных функций

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

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

Исходная задача на условный экстремум задается в виде

f(x) > min; (1.25)

_i(x) 0,. (1.26)

Она преобразуется в задачу безусловной минимизации вспомогательной функции

(x) = f(x) + B(x),

где B(x) — барьерная функция, — параметр барьера.

Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых _i (x) < 0).

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

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

(1.27)

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

Примеры

Пример 1: f(x) = x > min; (x)=3 — x 0.

Барьерную функцию строим согласно (1.27). Тогда вспомогательная функция имеет вид Находим точку минимума: Отсюда

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

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

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

Алгоритм.

1. Выбрать начальную точку x⁰ так, чтобы _i(x⁰)<0; задать точность, начальное значение ₀ и число (0, 1).

2. Минимизировать (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если, то остановиться, приняв за оптимальное решение задачи.

4. Положить, за начальную точку принять и вернуться к шагу 2.

Значение ₀ можно брать из интервала [2, 10]. Важное замечание касается пункта 2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации .

Пример 2: f(x) = (x₁-2)⁴+(x₁-2x₂)² min; (x)=x₂ 0.

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

=(x₁-2)⁴+(x₁-2 x₂)² — 

За начальную точку возьмем допустимую точку (0;1), значения и принимаем равными 10. Результаты поиска алгоритмом барьерных функций представлены в табл. 1.2 и на рис. 1.12.

Таблица 1.2

Результаты поиска алгоритмом барьерных функций

Как и следовало ожидать, с уменьшением значение B стремится к нулю.

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

(x) = f(x) + B(x) +

где барьерная функция B(x) применяется к неравенствам, а штрафная функция Н(х) — к ограничениям-равенствам. Последовательность задач минимизации решается с уменьшающимися значениями параметра .

6. Другие методы условной оптимизации

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

Аналогичное дополнение алгоритма Хука-Дживса делает его пригодным для поиска условного минимума. Генетические алгоритмы также могут использоваться для условной оптимизации. Для этого в них вводится детерминированный оператор жизнеспособности: если особь не удовлетворяет условиям «жизни», она погибает. Такой оператор должен применяться к каждой особи.

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

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

7. Примеры методов нелинейного программирования при формировании оптимального портфеля ценных бумаг по модели Марковица

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

На финансовом рынке обращается, как правило, несколько типов ценных бумаг: государственные ценные бумаги, муниципальные облигации, корпоративные акции и т. п. Если у участника рынка есть свободные деньги, то их можно отнести в банк и получать проценты или купить на них ценные бумаги и получать дополнительный доход. Но в какой банк отнести? Какие ценные бумаги купить? Ценные бумаги с низкими рисками, как правило, и малоэффективны, высокоэффективные, как правило, более рискованны.

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

Набор ценных бумаг, находящихся у участника рынка, называется его портфелем. Стоимость портфеля — это суммарная стоимость всех составляющих его бумаг. Если сегодня его стоимость есть Р, а через год она окажется равной Р^/, то (Р^/— Р)/Р естественно назвать доходностью портфеля в процентах годовых. Т. е. доходность портфеля — это доходность на единицу его стоимости.

Пусть x_i — доля капитала, потраченная на покупку ценных бумаг i-го вида. Весь выделенный капитал принимается за единицу. Пусть d_i — доходность в долях годовых бумаг i-го вида в расчете на одну денежную единицу.

Найдем доходность всего портфеля d_p. С одной стороны, через год капитал портфеля будет равен 1+d_p, с другой — стоимость бумаг i-го вида увеличится с х_i до х_i+d_ix_i, так что суммарная стоимость портфеля будет. Приравнивая оба выражения для стоимости портфеля, получаем:. Отсюда:

. (1.28)

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

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

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

Математическое ожидание доходности портфеля обозначим через :

.

Дисперсию доходности портфеля обозначим через :

.

Назовем — эффективностью портфеля, а величину — риском портфеля.

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

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

(1.29)

Оптимальный портфель Марковица максимальной эффективности и заданного (приемлемого) риска можно представить в виде:

(1.30)

Необходимо определить доли капитала, потраченные на покупку каждого вида ценных бумаг: x₁, x₂ ,…, x_n.

Исходными данными для расчета является табл. 1.3.

Таблица 1.3

Таблица доходностей ценных бумаг

Для вычисления используются нижеследующие расчетные формулы.

Среднее арифметическое доходности i-ой ценной бумаги:

(1.31)

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

(1.32)

где и — отклонения доходностей i-ой и j-ой бумаг от средней арифметической доходности.

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

(1.33)

где — вариация прибыльности ценных бумаг i-го вида, — ковариация прибыльности ценных бумаг i-го и j-го видов.

Работоспособность предложенной сверстки обоих критериев доказана путем числовых экспериментов методом «Монте-Карло».

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

Пример

Задана эффективность портфеля ценных бумаг и риск портфеля. Ценные бумаги заданы табл. 1.4.

Таблица 1.4

Таблица доходностей ценных бумаг

Необходимо с использованием программы Maxima определить доли капитала, потраченные на покупку каждого вида ценных бумаг при:

а) минимальном риске и заданной эффективности;

б) максимальной эффективности и заданном риске;

в) рискованно-эффективной модели.

< Введем обозначения: матрица X={x₁, x₂ ,…, x₆} - доли капитала, потраченные на покупку каждого вида ценных бумаг; матрица A — таблица доходностей ценных бумаг, заданная в условии.

а) при минимальном риске и заданной эффективности модель оптимального портфеля Марковица задается выражением (1.29). В данной модели целевая функция r нелинейна, а ограничения линейные функции.

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

(%i1) X: matrix ([x1, x2, x3, x4, x5, x6])$

(%i2) A: matrix ([11.293, 11.493, 13.753, 12.936, 12.881, 13.820],

[12.112, 12.919, 12.415, 14.048, 14.770, 14.310],

[11.429, 13.098, 14.277, 14.551, 11.639, 13.524],

[10.526, 11.988, 11.705, 12.466, 11.825, 10.864],

[11.467, 13.364, 12.171, 11.631, 11.923, 13.764],

[11.467, 13.334, 12.338, 14.208, 12.271, 13.324])$

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

Целевая функция в выражении (1.29) есть не что иное как квадратичная форма, которая в матричной форме запишется как, где X — матрица-столбец переменных, а X^T— матрица-строка переменных, которую получим при помощи функции transpose. Матрицу ковариаций доходностей ценных бумаг найдем с помощью функции cov, перед применением которой необходимо обязательно загрузить пакеты descriptive и numericalio.

Для получения результатов в удобном для просмотра виде нужно задать точность вычислений с помощью опции fpprec:7 (будет показано 7 значащих цифр, вместо 16 по умолчанию).

(%i3) load (descriptive)$

(%i4) load (numericalio)$

(%i5) fpprec: 7 $

Теперь целевую функцию можно записать в Maxima как:

(%i6) r: transpose (X).cov (A).X$

Ограничение в матричном виде можно записать как, где — средние значения доходностей матрицы A. Для матрицы используем команду mean(A). Тогда ограничение примет вид в виде X.mean(A).

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

где , — ограничения в выражении 5.29.

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

В программе Maxima функцию Лагранжа запишем как:

(%i7) L: r+g1*(X.mean (A)-12)+g2*(x1+x2+x3+x4+x5+x6−1)$

С помощью функции linsolve решим систему из 8-ми уравнений с 8-ми неизвестными:

(%i8) linsolve ([diff (L, x1), diff (L, x2), diff (L, x3), diff (L, x4), diff (L, x5), diff (L, x6), diff (L, g1), diff (L, g2)], [x1,x2,x3,x4,x5,x6,g1,g2]), numer;

(%o8) [x1=0.15 798, x2=0.62 034, x3=0.60 815, x4=-0.29 938, x5=0.4285,

x6=-0.5156, g1=-0.16 695,g2=0.11 864]

Решение задачи нам не подходит поскольку инвестор еще не вкладывал деньги в акции, и, следовательно, отрицательные значения переменных невозможны. Для устранения этой проблемы присвоим отрицательным переменным значение равное нулю (x4=x6=0) и заново повторим расчет:

(%i9) linsolve ([diff (L, x1), diff (L, x2), diff (L, x3), x4, diff (L, x5), x6, diff (L, g1),

diff (L, g2)], [x1,x2,x3,x4,x5,x6,g1,g2]), numer;

(%o9) [x1=0.53 933, x2=0.23 621, x3=0.19 622, x4=0, x5=0.2 824, x6=0,

g1=-0.77 851, g2=-0.27 808]

Решение найдено. Сделаем проверку и вычислим минимальный риск портфеля ценных бумаг:

(%i10) x1:0.53 933 $ x2:0.23 621 $ x3:0.19 622 $ x4:0 $ x5:0.2 824 $ x6:0 $

(%i16) ev (x1+x2+x3+x4+x5+x6);

(%o16) 1.0

(%i17) ev®;

(%o17) 0.18 575

Таким образом, при минимальном риске и заданной эффективности инвестору следует вложить деньги в следующем соотношении:

· 53,9% в акции № 1;

· 23,6% в акции № 2;

· 19,6% в акции № 3;

· 2,9% в акции № 5.

При этом минимальный риск портфеля .

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

Введение

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

В новом рабочем листе программы Maxima заново введем первые шесть строк из модели минимального риска. Поэтому ввод начнем с ячейки (%i7):

Введем целевую функцию и функцию Лагранжа:

(%i7) L: r+g1*(X.mean (A)-12-y)+g2*(x1+x2+x3+x4+x5+x6−1)$

Решим систему из 8-ми уравнений с 8-ми неизвестными с помощью функции linsolve. Кроме того, используем для упрощения результатов функции ratsimp и float:

(%i8) ratsimp (float (linsolve ([diff (L, x1), diff (L, x2), diff (L, x3), diff (L, x4), diff (L, x5), diff (L, x6), diff (L, g1), diff (L, g2)], [x1,x2,x3,x4,x5,x6,g1,g2])));

(%o8) [x1=-(22 795 378 539 428 444*y-4 537 670 339 779 197)/28 722 781 234 937 848,

x2=(2 042 987 868 973 048*y+3 563 561 400 232 913)/5 744 556 246 987 570,

x3=(663 161 266 743 035*y+2 183 481 844 408 430)/3 590 347 654 367 231,

x4=-(3 687 740 930 219 273*y+17 198 034 751 936 498)/57 445 562 469 875 696,

x5=(8 251 473 140 996 895*y+12 603 202 586 464 272)/29 412 127 984 576 352,

x6=(530 470 143 236 891*y-7 404 674 255 574 559)/14 361 390 617 468 924,

g1=-(4 013 841 060 378 303*y+19 640 954 047 503 052)/1 176 485 119 383 054 336,

g2=(870 518 148 102 923*y+4 259 714 641 710 461)/35 903 476 543 672 312]

В результате получаем выражения для нахождения искомых переменных через новую переменную y. Решение задачи нам не подходит поскольку инвестор еще не вкладывал деньги в акции, и, следовательно, отрицательные значения переменных невозможны. Для устранения этой проблемы присвоим первой отрицательной переменной значение равное нулю (x1=0) и заново повторим расчет.

(%i9) ratsimp (float (linsolve ([x1, diff (L, x2), diff (L, x3), diff (L, x4), diff (L, x5), diff (L, x6), diff (L, g1), diff (L, g2)], [x1,x2,x3,x4,x5,x6,g1,g2])));

Зададим явно полученные выражения для переменных:

(%i10) x1:0 $ x2:-(2 349 544 658 492 416*y-4 197 451 106 211 809)/5 396 587 288 453 469 $

x3:-(3 448 036 661 085 509*y-4 166 743 184 483 998)/5 396 587 288 453 469 $

x4:(8 362 865 560 794 453*y-5 033 901 278 897 518)/10 793 174 576 906 938 $

x5:-(6 156 740 579 208 624*y-6 453 235 294 153 811)/10 793 174 576 906 938 $

x6:(9 389 037 657 570 022*y-7 354 548 019 740 969)/10 793 174 576 906 938 $

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

(%i16) ev (find_root (r-0.3, y, 0, 1));

(%o16) 0.87 133 341 353 558

Зададим явно переменную y:

(%i17) y:0.87 133 341 353 558 $

Вычислим искомые переменные:

(%i18) ev (x2);

(%o18) 0.39 843 964 782 594

(%i19) ev (x3);

(%o19) 0.21 538 679 325 571

(%i20) ev (x4);

(%o20) 0.2 087 377 444 954

(%i21) ev (x5);

(%o21) 0.10 086 573 706 945

(%i22) ev (x6);

(%o22) 0.76 570 077 353 503

Решение найдено. Сделаем проверку и вычислим максимальную эффективность портфеля ценных бумаг:

(%i23) ev (x1+x2+x3+x4+x5+x6);

(%o23) 1.0

(%i24) ev (12+y);

(%o24) 12.87 133 341 353 558

Таким образом, при максимальной эффективности и заданном (приемлемом) риске инвестору следует вложить деньги в следующем соотношении:

· 39,9% в акции № 2;

· 21,5% в акции № 3;

· 20,9% в акции № 4;

· 10,0% в акции № 5;

· 7,7% в акции № 6.

При этом максимальная эффективность .>

в) Для вычисления по рискованно-эффективной модели оптимальный портфель Марковица задается выражением (1.33). Целевая функция в матричной форме запишется как, где — матрица вариаций доходностей ценных бумаг, которую найдем с помощью функции var (matrix), перед применением которых необходимо обязательно загрузить пакеты descriptive и numericalio. Остальные обозначения и функции те же, что и в предыдущих моделях.

В новом рабочем листе программы Maxima заново введем первые шесть строк из модели минимального риска. Теперь ввод начнем с ячейки (%i7):

Теперь целевую функцию запишем в Maxima как:

(%i7) f: ((sqrt ((X²).(var (A))^2)+r)/(X.mean (A)))$

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

где — ограничение в выражении (1.33).

В данном случае функция Лагранжа имеет вид:

(%i8) L: f+g1*(x1+x2+x3+x4+x5+x6−1)$

Для решения 7-ми уравнений с 7-ми неизвестными используем функцию mnewton, которая решает нелинейные системы уравнений, с использованием метода Ньютона. Аргументами функции служат список функций для решения, список имен переменных, список начальных приближений. В данном случае зададимся начальным приближением. Для использования функции mnewton необходимо предварительно загрузить оператор load («mnewton»).

(%i9) load («mnewton»)$

(%i10) mnewton ([diff (L, x1), diff (L, x2), diff (L, x3), diff (L, x4), diff (L, x5), diff (L, x6),

diff (L, g1)], [x1,x2,x3,x4,x5,x6,g1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1]), numer;

(%o10) [[x1=0.73 152,x2=0.16 617,x3=0.97 063,x4=0.18 938,x5=0.15 683,

x6=-0.2 938, g1=-0.15 248]]

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

(%i11) mnewton ([diff (L, x1), diff (L, x2), diff (L, x3), diff (L, x4), diff (L, x5), x6,

diff (L, g1)], [x1,x2,x3,x4,x5,x6,g1], [0.1,0.1,0.1,0.1,0.1,0.1,0.1]), numer;

(%o11) [[x1=0.70 668,x2=0.16 554,x3=0.93 007,x4=0.19 819,x5=0.14 955,x6=0.0,

g1=-0.16 404]]

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

(%i12) x1:0.70 668 $ x2:0.16 554 $ x3:0.93 007 $ x4:0.19 819 $ x5:0.14 955 $ x6:0 $

(%i18) ev (x1+x2+x3+x4+x5+x6);

(%o18) 1.0

(%i19) ev®;

(%o19) 0.19 333

(%i20) ev (X.mean (A));

(%o20) 11.78 565

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

· 70,7% в акции № 1;

· 16,5% в акции № 2;

· 9,3% в акции № 3;

· 2% в акции № 4;

· 1,5% в акции № 5.

При этом риск портфеля и эффективность .

Как следует из результатов этого примера рискованно-эффективная модель полность удовлетворяет требованиям игрока рынка ценных бумаг. Риск при этой модели несколько больше чем в модели с минимальным риском, где это значение составляет 0,18 575. Эффективность при этой модели несколько ниже чем в модели с максимальной эффективностью, где это значение составляет 12,871. Но в целом, игрок имеет определенность действий по распределению ценных бумаг и эти действия приносят приемлемый доход при приемлемом риске.

8. Примеры методов нелинейного программирования при формировании оптимального портфеля ценных бумаг по модели Тобина

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

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

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

(1.34)

где m₀ — эффективность безрисковых бумаг;

x₀ — доля капитала вложенная в безрисковые бумаги;

x_i, x_j — доля капитала вложенная в ценные бумаги i-го и j-го видов;

d_i — математическое ожидание (среднее арифметическое) доходности i-ой ценной бумаги;

V_ij - корреляционный момент между эффективностью бумаг i-го и j-го видов.

Оптимальный портфель Тобина максимальной эффективности и заданного (приемлемого) риска можно представить в виде:

(1.35)

где r_p — заданный риск портфеля.

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

Вывод

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

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

1. Таха Х.

Введение

в исследование операций. В 2-х книгах. Кн. 1. Пер. с англ. — М.: Мир, 1985.

2. Исследование операций. Методологические аспекты. — М.: Наука, 1972.-136с.

3. Исследование операций / Под ред. Дж. Моудера, С.Элмаграби. — Т. 1,2. — М.: Мир, 1981.-712 с.

4. Пістунов І.М., Ситников О. А. Дослідження межі існування оптимальних рішень для портфеля Марковіца // Економічний вісник НГУ. — Д.: НГУ, 2003. — № 4. — С.114−119.

5. Пістунов І.М., Полінський О. М. Визначення оптимальності ризиково-прибуткової моделі портфеля інвестицій Марковіца // Економіка: проблеми теорії та практики: Зб. наук. праць ДНУ. — Д.: ДНУ, 2008. — Вип. № 238. — том I. — С.156−162.