УСТОЙЧИВОСТЬ ДИСКРЕТНЫХ ЗАДАЧ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ: ЗАДАЧА ФОРМИРОВАНИЯ ИНВЕСТИЦИОННОГО ПОРТФЕЛЯ
Авторы:
1.
Российский государственный университет нефти и газа им. И. М. Губкина
Тип:
Статья
Страницы:
с 112
по 120
Статус:
Опубликован
Получено:
05.04.2013
Одобрено:
25.04.2013
Опубликовано:
25.04.2013
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 336.76:004.382
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 65.263.12с515
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 336.76:004.382
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ББК 65.263.12с515
Язык материала:
русский
Ключевые слова:
паретовское множество, инвестиционный финансовый портфель, целевая функция, паретовский оптимум, векторная целевая функция, интервальная весовая функция, возмущающее множество, интервальная задача, радиус устойчивости
Аннотация (русский):
Для практического применения в экономике в качестве математической модели задачи оптимизации инвестиционного финансового портфеля рассмотрена известная задача с интервальной весовой функцией. В качестве главных показателей эффективности введены две целевые функции: величина ожидаемой прибыли и величина риска. В виде интервала задаётся ожидаемая прибыль от объектов инвестирования. Вводятся два типа возмущения исходных данных, которые не выводят исходную задачу из класса интервальных: интервальное сложение исходных весов с возмущающим весом и одновременное возмущение границ интервала. Для каждого типа возмущения получены количественные характеристики устойчивости в виде радиуса устойчивости, означающего, например, оценку инфляции.
Для практического применения в экономике в качестве математической модели задачи оптимизации инвестиционного финансового портфеля рассмотрена известная задача с интервальной весовой функцией. В качестве главных показателей эффективности введены две целевые функции: величина ожидаемой прибыли и величина риска. В виде интервала задаётся ожидаемая прибыль от объектов инвестирования. Вводятся два типа возмущения исходных данных, которые не выводят исходную задачу из класса интервальных: интервальное сложение исходных весов с возмущающим весом и одновременное возмущение границ интервала. Для каждого типа возмущения получены количественные характеристики устойчивости в виде радиуса устойчивости, означающего, например, оценку инфляции.
Ключевые слова:
паретовское множество, инвестиционный финансовый портфель, целевая функция, паретовский оптимум, векторная целевая функция, интервальная весовая функция, возмущающее множество, интервальная задача, радиус устойчивости
паретовское множество, инвестиционный финансовый портфель, целевая функция, паретовский оптимум, векторная целевая функция, интервальная весовая функция, возмущающее множество, интервальная задача, радиус устойчивости
Для описания факторов неопределенности могут быть использованы различные модели [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).
1. Вощинин А. П. Построение аналитических моделей по данным вычислительного эксперимента в задачах анализа чувствительности и оценки экономических рисков / А. П. Вощинин, П. В. Бронз // Заводская лаборатория. - 2007. - Т. 72, № 1. - С. 101-105.
2. Перепелица В. А. Дискретная оптимизация и моделирование в условиях неопределенности данных: монография / В. А. Перепелица, Ф. Б. - М.: Акад. естествознания, 2007. - 152 с.
3. Вощинин А. П. Интервальный анализ данных: развитие и перспективы // Заводская лаборатория. - 2002. - Т. 68, № 1. - С. 118-126.
4. Тебуева Ф. Б. Принятие решений в дискретных задачах оптимизации на графах с нечеткими весами / Ф. Б. Тебуева // Горный информационно-аналитический бюллетень. - 2008. - № 6. - С. 381-392.
5. Шапкин А. С. Экономические и финансовые риски. Оценка, управление, портфель инвестиций / А. С. Шапкин. - М.: Изд.-торг. корпорация «Дашков и Кº», 2004. - 544 с.
6. Мищенко А. В. Двухкритериальная задача оптимизации инвестиционного портфеля / А. В. Мищенко, А. А. Попов // Менеджмент в России и за рубежом. - 2001. - № 1. - С. 106-116.
7. Зыков А. А. Основы теории графов / А. А. Зыков. - М.: Наука, 1987. - 384 с.
8. Леонтьев В. К. Стойкость в линейных дискретных задачах / В. К. Леонтьев // Проблемы кибернетики. - 1979. - Вып. 35. - С. 169-184.
9. Бакурова А. В. О стойкости многокритериальных задач на системах подмножеств / А. В. Бакурова, В. А. Емеличев, В. А. Перепелица // Докл. акад. наук Беларуси. - 1995. - № 2. - С. 6-12.
10. Кравцов М. К. Полиэдральные аспекты транспортных задач и сложность многокритериальных задач дискретной оптимизации / М. К. Кравцов: дис. … д-ра физ.-мат. наук. - Минск: Белорус. гос. ун-т, 1994. - 303 с.
