STABILITY OF THE DISCRETE PROBLEMS UNDER UNCERTAINTY: PROBLEM OF FORMATION OF A FINANCIAL INVESTMENT PORTFOLIO
Abstract and keywords
Abstract (English):
The well-known problem with interval weight function is considered as a mathematical model of the optimization problem of the financial investment portfolio for practical use in the economy. Two objective functions are introduced as the main performance indicators: the value of the expected profit and the risk value. The expected profit of investment objects is defined as an interval. Two types of disturbance of initial data such as interval addition of the initial disturbance weight and simultaneous perturbation interval boundaries, which cannot derive the original problem from the class of interval problems, are introduced. For each type of disturbance quantitative characteristics of stability as a stability radius that means, for example, an assessment of inflation, are obtained.

Keywords:
Pareto set, financial investment portfolio, objective function, Pareto optimum, vector objective function, interval weight function, perturbation set, interval problem, radius of the stability
Text
Для описания факторов неопределенности могут быть использованы различные модели [1, 2], в том числе интервальное описание, которое привлекает большое внимание исследователей [3], т. к. в большинстве случаев какие-либо стохастические характеристики просто отсутствуют, а для неопределенностей известны лишь границы изменения [4]. Методы многокритериальной оптимизации в условиях неопределенности можно разделить на несколько подходов в зависимости от того, на каком этапе формируются предпочтения лица, принимающего решение [2]. В настоящей работе рассматривается следующий подход: предполагается, что все эффективные решения найдены, после чего осуществляется выбор наилучшего из них. Так как нахождение паретовского множества (ПМ) позволяет сузить неопределенность при выборе принятия решения, то нами под оптимальным решением понимается именно ПМ. Проблеме исследования условий неизменности оптимального решения и посвящена данная работа. Решение задачи формирования инвестиционного финансового портфеля (ИФП) [5, 6] является очень трудоёмким и требует использования ЭВМ. Вычисление радиуса устойчивости таких задач по разработанным формулам на ПЭВМ позволяет получить ответы не для одной индивидуальной задачи, а целого ряда задач, близких к данной. Следует отметить, что исходные данные в задачах всегда известны только с определённой погрешностью, природа которой зависит от специфики задачи и обусловливается рядом физических и экономических факторов. Непредсказуемость поведения решения задач дискретной оптимизации при возмущении исходных данных требует особой внимательности на этапе подготовки к численному решению. При таких условиях наилучшей природной моделью описания данных является их представление в интервальной форме, когда задают диапазон возможных значений переменных или зависимостей, например, в виде , где и – нижняя и верхняя границы неопределённого -го фактора (параметра). Приведенное неравенство означает, что параметр может приобретать какое-либо значение из интервала и ему нельзя задать никакой вероятностной величины. Именно поэтому появилась необходимость использовать в математических моделях сразу несколько методов учёта неопределённости в исходных данных. Примером такой модели является задача формирования ИФП. В качестве главных показателей эффективности часто фигурируют две целевые функции (ЦФ): 1) величина ожидаемой прибыли; 2) величина риска. Укажем, что первая из этих ЦФ является максимизируемой, а вторая – минимизируемой. Кроме того, математическим выражением для первой из них является математическое ожидание, а для другой – среднеквадратическое отклонение. Предположим, что есть инвестор, который желает вложить капитал в некоторые ценные бумаги (например, акции различных предприятий). Как известно, существует важный для инвестора закон диверсификации вкладов, т. е. некоторый рассудительный инвестор не будет вкладывать весь капитал в акции одного предприятия, а попытается распределить их наилучшим способом между различными предприятиями. Такое суждение подтверждается законом больших чисел, т. к. при распределении инвестиций между предприятиями уменьшается величина дисперсии. Поэтому возникает вопрос: что такое «наилучший способ»? Приобретая ценные бумаги, необходимо иметь в виду два момента: будущий доход (т. е. цену возможной продажи акции) и риск (например, риск недополучения прибыли, потеря части дохода или в крайнем случае риск банкротства). Инвестор стремится сформировать такой портфель ценных бумаг, который приносил бы ему наибольшую прибыль при минимальном риске. В реальных задачах формирования ИФП объекты инвестирования фактически не имеют статистических данных, которые позволяют вычислять математическое ожидание и дисперсию. Единственно возможной становится интервальная постановка задачи определения наиболее целесообразного ИФП. Постановка исследуемой задачи. В общем виде постановка формулируется следующим образом. Дано множество объектов инвестирования, связанных между собой конкретной топологической структурой (например, такими объектами могут быть различного вида и назначения сети). Эта топологическая структура может быть описана n-вершинным графом [7], в котором каждому ребру приписан интервальный вес . Допустимым множеством задачи является подграф вида , где . Всё множество допустимых решений обозначим через . В виде интервала задаётся ожидаемая прибыль от объекта , где минимально (максимально) возможный размер дохода от инвестирования объекта . В этой ситуации эффективность (полезность) того или иного портфеля целесообразно оценивать с помощью таких критериев: (1) (2) (3) где критерии (1), (2) представляют собой математическое выражение оценки ожидаемой прибыли, а критерий (3) отображает некоторую оценку величины риска инвестиций в данных ценных бумагах. Решением задачи является ПМ . Векторная целевая функция (ВЦФ) (1)–(3) определяет ПМ , которая содержит все паретовские оптимумы (ПО). Элемент называется ПО, если не существует такой траектории , доминирующей траекторию , что , где хотя бы одно неравенство строгое. Для формирования ВЦФ из критериев (1)–(3) желательно совершить такое их преобразование, чтобы имел место экстремум одного и того же вида (либо все максимальные, либо все минимальные) для каждого из них. Преобразуем критерий (3) к максимизируемому с помощью следующего линейного преобразования исходных данных , : (4) Отметим, что это преобразование оставляет неизменными границы (верхнюю и нижнюю) области значений интервалов , . В обозначениях (4) вместо критерия (3) используем следующий максимизируемый критерий: (5) Таким образом, на множестве определена ВЦФ: , (6) состоящая только из максимизируемых критериев (1), (2), (5). Занумеруем все элементы множества . Тогда векторную весовую функцию (ВВФ) удобно трактовать как интервальную матрицу-столбец в пространстве замкнутых интервалов . Таким образом, элементами матрицы-столбца будут интервалы вида . Изменяя матрицу , будем получать различные интервальные задачи . Формулировка проблемы локальной устойчивости [8]. В пространстве матриц-столбцов зададим норму [8]: Через обозначим множество всех таких матриц-столбцов , что Задачу , полученную из исходной задачи , при сложении матриц и , будем называть возмущённой, а матрицу возмущающей. Для интервальной задачи введём два типа возмущения исходных данных, которые не выводят исходную задачу из класса интервальных: 1) интервальное сложение исходных весов с возмущающим весом . При этом возмущающее множество можно представить в виде (7) 2) одновременное возмущение границ интервала: (8) где ширина интервала. Определение. Задача называется -устойчивой к I (II) типу возмущения, если выполняются такие включения: Очевидно [9], что задача является при любом , если . В дальнейшем этот случай будем исключать. Задачу назовем нетривиальной, если разность Для пары решений введём число где число элементов, которые являются общими для решений . Очевидно, что при . Для какого-либо решения определим множество: где За количественную меру устойчивости будем принимать число , которое назовём радиусом устойчивости. Задача нахождения радиуса устойчивости является обратной проблеме локальной устойчивости. Радиус устойчивости задачи определяется такой границей возмущений элементов матрицы , при которых не возникает новых ПО. Содержательно, он, например, может означать оценку инфляции, при которой множество не пополняется новым ПО. Исследование интервальной задачи . Из возмущений и вида (7) и (8) для интервальной задачи выделим два следующих подмножества: а) возмущения, которые не влияют на величины и , т. е. , и ширина интервала : (9) б) возмущения, при которых , а . Для описания вида возмущения в случае б) введём следующие обозначения: – ширина интервала возмущения; , где – число вхождений ребер и в траектории ; где число вхождений ребер и в траекторию и число вхождений ребер и в траекторию . С учетом этих обозначений имеем: Учитывая, что , имеем . Тогда возмущение, описываемое в случае б) имеет следующий вид: (10) Следующая теорема описывает условия -устойчивости к возмущению вида (9). Теорема. Для интервальной задачи следующие утверждения эквивалентны: (1) задача -устойчива к возмущению вида (9); (2) для всякой траектории существует число и траектория такие, что справедливы неравенства (среди которых хотя бы одно строгое) (11) (3) , где – множество слабоэффективных траекторий . Доказательство проведем по схеме: (1)(2)(3)(1). Так как возмущения вида (9) не изменяют ширины интервала , то критерий вида (5) остается неизменным. Рассмотрим вспомогательную задачу , которая получается из исходной интервальной задачи удалением критерия . Тогда вспомогательная задача представляет собой 2-критериальную задачу, под «решением» которой будем понимать ПМ исходной задачи . (1)(2). Предположим противное. Пусть при любом для траектории не существует такой траектории , что выполняются условия (11), т. е. для каждой траектории существует хотя бы один индекс , для которого справедливо равенство . Тогда, если в качестве возмущающей матрицы выбрать матрицу с элементами получим . Поэтому в возмущенной задаче никакая траектория не доминирует траекторию . Кроме того, в задаче никакая траектория не доминирует траекторию , поскольку это верно для задачи . Следовательно, , т. е. задача не является устойчивой, т. к. . Полученное противоречие доказывает (1)(2). (2)(3). Поскольку для всякой траектории существует число и траектория такие, что справедливы неравенства (11), то учитывая неравенство при , получаем, что , а следовательно . Так как , то справедливо равенство . (3)(1). Пусть . Тогда для всякой траектории существует число и траектория такие, что . Поэтому найдется такое число , для которого выполняются соотношения (11). В силу леммы 9.1 [10] верны неравенства . С учетом леммы 9.2 [10] получаем , т. е. задача -устойчива. Теорема доказана. Приведенная теорема, описывающая необходимые и достаточные условия -устойчивости интервальной задачи к возмущению вида (9), позволяет получить формулу для вычисления радиуса устойчивости этой задачи. Утверждение 1. Радиус устойчивости в случае возмущения вида (9) определяется следующей формулой: Для возмущений вида (10) и (8) приведем только формулы вычисления радиуса устойчивости. Утверждение 2. Радиус устойчивости в случае возмущения вида (10) определяется следующей формулой: Утверждение 3. Радиус устойчивости в случае возмущения вида (8) определяется следующей формулой: Вычисление радиуса устойчивости задач с интервальной весовой функцией. Рассмотрим задачу коммивояжера на интервально взвешенном графе , изображенном на рисунке, где ВЦФ (6) представлена критериями вида (1), (2), (5), а интервальная весовая функция (ИВФ) – матрицей (табл. 1). Интервально взвешенный граф Таблица 1 Весовая матрица * 3 1 3 8 2 4 5 5 7 5 4 8 9 4 8 11 6 10 2 3 5 1 2 4 6 1 3 5 4 2 6 5 3 1 6 4 ∆*s 4 3 1 5 4 2 – – 3 * ∆*s∆*s Так как значение не является единственным то возможны следующие комбинации выбора и Таким образом, для каждой из этих комбинаций подсчитывается число рассматривается различное возмущающее множество и определяется радиус устойчивости . Множество допустимых решений : Вычислим радиус устойчивости для случая . Если значения то исключаем их из рассмотрения. Исключенные значения обозначены знаком « – » (табл. 2). Таблица 2 Вычисление радиуса устойчивости min max min 21 38 2 4 9/4 8/4 1 1 1 1 26 43 1 5,4 4/5, 4/4 3/5, 5/4 –, 2 3/5, 1 1 1 –, 1 30 46 2 * 25 44 1 2,5 5/2, 5/5 2/2, 4/5 –, – 1, 4/5 1 –, 1 20 41 1 4,3 10/4, 10/3 5/4, 7/3 –, – 5/4, 3/2 3/2 –, 3/2 30 48 1 * Радиус устойчивости Проведем возмущение вида . Пусть возмущающая матрица имеет вид Далее проведем расчет паретовских множеств возмущенной задачи (табл. 3). Таблица 3 Паретовские множества возмущенной задачи t F1 F2 F3 (t, W + B) 21 39 2 ** 25 45,1 1 – 29 48,1 1,9 * 24 45,1 1 – 20 41 1 – 29 50,1 1 * В результате проведенного возмущения получаем: при возмущении матрицей появился новый паретовский оптимум . Таким образом, исследованная задача неустойчива, если Проведенное исследование устойчивости векторных задач на системах подмножеств с ИВФ показало, что значение радиуса устойчивости изменяется при различных типах возмущений исходных данных, которые не выводят рассматриваемую задачу из класса интервальных. Приведено практическое применение конкретной задачи в области экономики. Для каждого возмущения получены количественные характеристики устойчивости. Сформулирован и доказан критерий устойчивости интервальной задачи к возмущению вида (9).
References

1. Voschinin A. P. Postroenie analiticheskih modeley po dannym vychislitel'nogo eksperimenta v zadachah analiza chuvstvitel'nosti i ocenki ekonomicheskih riskov / A. P. Voschinin, P. V. Bronz // Zavodskaya laboratoriya. – 2007. – T. 72, № 1. – S. 101–105.

2. Perepelica V. A. Diskretnaya optimizaciya i modelirovanie v usloviyah neopredelennosti dannyh: monografiya / V. A. Perepelica, F. B. – M.: Akad. estestvoznaniya, 2007. – 152 s.

3. Voschinin A. P. Interval'nyy analiz dannyh: razvitie i perspektivy // Zavodskaya laboratoriya. – 2002. – T. 68, № 1. – S. 118–126.

4. Tebueva F. B. Prinyatie resheniy v diskretnyh zadachah optimizacii na grafah s nechetkimi vesami / F. B. Tebueva // Gornyy informacionno-analiticheskiy byulleten'. – 2008. – № 6. – S. 381–392.

5. Shapkin A. S. Ekonomicheskie i finansovye riski. Ocenka, upravlenie, portfel' investiciy / A. S. Shapkin. – M.: Izd.-torg. korporaciya «Dashkov i Kº», 2004. – 544 s.

6. Mischenko A. V. Dvuhkriterial'naya zadacha optimizacii investicionnogo portfelya / A. V. Mischenko, A. A. Popov // Menedzhment v Rossii i za rubezhom. – 2001. – № 1. – S. 106–116.

7. Zykov A. A. Osnovy teorii grafov / A. A. Zykov. – M.: Nauka, 1987. – 384 s.

8. Leont'ev V. K. Stoykost' v lineynyh diskretnyh zadachah / V. K. Leont'ev // Problemy kibernetiki. – 1979. – Vyp. 35. – S. 169–184.

9. Bakurova A. V. O stoykosti mnogokriterial'nyh zadach na sistemah podmnozhestv / A. V. Bakurova, V. A. Emelichev, V. A. Perepelica // Dokl. akad. nauk Belarusi. – 1995. – № 2. – S. 6–12.

10. Kravcov M. K. Poliedral'nye aspekty transportnyh zadach i slozhnost' mnogokriterial'nyh zadach diskretnoy optimizacii / M. K. Kravcov: dis. … d-ra fiz.-mat. nauk. – Minsk: Belorus. gos. un-t, 1994. – 303 s.