Математическое моделирование задач распределения ресурсов на основе минимизации риска

В течение последних лет в Российской Федерации возрос научный интерес к задачам математического моделирования экономических систем и процессов [10, 11]. Одним из классов задач математического моделирования в экономике являются задачи оптимального распределения ресурсов.

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

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

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

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

Исторически первой математической двухкритериальной моделью задачи оптимального распределения ресурсов является модель Гарри Марковича [1], который за цикл работ по портфельному инвестированию получил в 1990 г. Нобелевскую премию.

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

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

Математическая модель Марковича задачи оптимального распределения ресурсов в условиях неопределенности принадлежит к классу задач квадратичного программирования. Теория численного решения этого класса задач" получила развитие в работах самого Марковича [2, 3] и в работах других авторов [4−9, 12−15].

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

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

Подход, основанный на рассмотрении задач оптимального распределения ресурсов с использованием вышеуказанных значений р и Л*, получил название УаЯ — подхода (УаЯ — аббревиатура словосочетания УаЫе-а^ШБк).

При постановке задач оптимального распределения ресурсов, основанного на УаЯ — подходе, критерием уровня суммарной эффективности является Я*, а критерием неопределенности (риска) вероятность р*.

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

УаЯ — подход, включая рассмотрение задач оптимизации распределения капитала на основе УаЯподхода, изложены в работах [16−31].

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

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

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

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

При таком подходе необходимо использовать весь современный арсенал методов прогнозирования стохастических временных процессов (временных рядов).

Отметим, что прогнозирование временных процессов в условиях неопределенности является одним из основных направлений исследований современной науки с приложениями практически во всех областях науки, техники, природных и социальных областях [32−42].

В последние годы интенсивно развиваются методы прогнозирования динамических процессов, в том числе в условиях наличия хаотических компонент, основанные на сингулярно-спектральном анализе (SingularSpectrum Analysis — SSA) [43−57]. Отметим, что в Российских научных публикациях вместо «SSA» часто используют термин «Гусеница» [58−62].

Применение SSA — для прогнозирования стационарных временных процессов показало его высокую эффективность и устойчивость при исследовании многих конкретных хаотических временных процессов технического, природного и социально-экономического характеров [63−70].

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

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

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

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

Целью диссертационной работы является:

1. Разработка алгоритмов прогнозирования хаотических нестационарных временных процессов с помощью нестационарного сингулярно-спектрального анализа (К88А);

2. Разработка математических моделей задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯ — подходе;

3. Разработка алгоритмов численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯ — подходе и результатах прогнозирования с помощью нестационарного сингулярно-спектрального анализа;

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

Научная новизна и значимость.

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

2. Предложены новые постановки задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯподходе.

3. Разработаны новые алгоритмы численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯ — подходе, в условиях нормального закона распределения эффективностей.

4. Впервые разработана схема включения результатов прогнозирования на основе нестационарного сингулярно-спектрального анализа в алгоритм решения задачи оптимизации распределения ресурсов на основе УаЯ — подхода.

5. Сконструирован и реализован программный комплекс, включающий в себя все разработанные в диссертации новые алгоритмы прогнозирования хаотических временных процессов и решение задач оптимального распределения ресурсов в условиях неопределенности, основанные на УаИ. — технологии.

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

Краткое содержание диссертации.

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

Нестационарный сингулярно-спектральный анализ хаотических временных рядов ] = 1,., М, / = 1где М — число исследуемых рядов, п — число дискретных фиксаций времени, основан на формировании матрицы наблюдений У размерности (.? х (/? • М+#)).

У," 'У, р У2,1 *" «У2,р „“ 'Ум,'» «Ум, р /, р У 1,2 ~'У, р+ У2,2 •••Уг, р+ Ум, 2 '» «УМ, р+ А, р+ '» «/д, р+1.

У, 1, •" «Ух.п У2,1'» «Уг, п «'Ум, 1 •'•Ум, п.

0.1) где р — параметр N8БА-модели;

Рассматривается задача на собственные значения симметричной неотрицательной матрицы УТУ размерности (р-М + #)х (/?-М + #).

УтГ¥- = мЧ, (0.2) где ,^^)Т, у = 1, р • М + д — ранжированная система собственных значений и соответствующая им ортонормированная система собственных векторов }.

Формулы прогнозирования совокупности исследуемых временных рядов.

Ур* У = 1>—I = 1,.определяются совокупностью собственных векторов Ч? j, а числовые значения ¡-л} определяют информационный вклад соответствующей ей компоненты в исследуемые временные ряды.

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

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

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

Во второй главе дано краткое введение в схему Марковица и VaRсхему при рассмотрении задач распределения ресурсов в условиях неопределенности. Дано сравнение двух систем, включая анализ отличия, недостатков и преимуществ понятия риска в схеме Марковица и VaRсхеме.

Предлагаемые во второй главе математические модели задач оптимального распределения ресурсов в условиях неопределенности имеют вид: p (Rp (x).

R*- шах, (0.3) р — min, где.

R^^RjXJ, у=1 > xeJ,.

X — множество ограничений на искомый вектор долей распределяемого ресурса х, включая естественные ограничения м l Xj ^ 0, / = 1,., М y=i.

— критерий уровня эффективности, p* - критерий уровня риска.

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

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

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

R* - шах,.

0.4) при фиксированных значениях уровня риска р е [0,1].

Согласно второй схеме решается серия однокритериальных задач р* - min,.

— (0.5) при фиксированных допустимых значениях уровня эффективности R*.

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

R* - max (min),.

— «(°-6) хе X.

Показано, что решения Парето задачи (0.3) определяются совокупностью функций распределения вероятностей случайных величин Rp (x), х е X.

Доказано, что в случае. нормального закона распределения эффективностей Rj> ] — каждое решение задачи (0.3) является решением задачи Марковича о-р = [??х, х^-т}п, тр (т, л:)-т ах, (0.7) хеХ, т = (тх,., тм) Т — вектор математических ожиданий МЯ} = т},.

IV — ковариационная матрица совокупности случайных величин Щ, j = l.

В третьей главе конструируются алгоритмы численного решения задачи (0.4).

В условиях нормальности распределения эффективностей > ] — 1,—> М, предлагается двухэтапный способ решения задачи (0.4).

На первом этапе находятся решения Парето задачи Марковица (0.7), для численного решения которой предлагается использовать переход к двойственной задаче с каноническим типом ограничений вида и > 0 и применением к двойственной задаче обобщенного итерационного процесса Некрасова [77].

Доказано, что для нахождения решений Парето исходной задачи (0.4) достаточно на втором этапе построить семейство функций распределения случайных величин где х — решение Парето задачи (0.7), и провести огибающую снизу это семейство кривых на плоскости р=р (Яр (х)<�Я-).

Практически процедура построения огибающей осуществляется на сетке фиксированных дискретных значений Я* из интервала допустимых значений.

Конструируются алгоритмы численного решения двухкритериальной задачи (0.4) в общем случае, когда условие нормальности распределения случайных величин Яу" у = 1 ,., М не выполнено.

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

0.8) где Рх — оператор проекции на множество ограничений X, ае> 0 подбирается из условия лучшей скорости сходимости х (е) к искомому решению х , — целевая функция задачи (0.5).

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

Алгоритмы с использованием ЫББА для решения задач оптимизации состоят из двух этапов.

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

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

На втором этапе на основе базы данных У = 1,., М, / = 1,., 7А используются алгоритмы решения задач, представленных в третьей главе.

Например, при реализации схемы решения серии однокритериальных задач (0.5) для каждого фиксированного вектора х = (х1,., хм) т, х еХ, формируется статистическое распределение Яр1(х), 1 = 1,.,// для эффективности ЯД-с) = (3с, 7?) как случайной величины согласно формуле м у=1.

Значение целевой функции ^(х, Я*) = Р (Яр (х)<�Я*) подсчитывается по формуле = где целое число к определяется из последовательности ранжированных значений.

V*): * *. * * - *.

Разработанный в диссертации комплекс программ решения задач оптимального распределения ресурсов в условиях неопределенности на основе УаЯ имеет в качестве блоков программные реализации алгоритмов численного решения задач оптимизации по схеме Марковича, включая задачи по нахождению распределения ресурсов с минимальным значением дисперсии суммарной эффективности и задачи линейного программирования по нахождению распределения с максимальным ожидаемым значением эффективности, решаемой с помощью метода прямого и обратного хода [79].

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

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

В диссертации использовались результаты теоретических исследований в различных областях прикладной математики, представленные в работах [86 117].

На защиту выносятся следующие результаты диссертации:

1. Предложены и обоснованы алгоритмы прогнозирования хаотических временных процессов с помощью нестационарного сингулярно-спектрального анализа (ЫЗБА);

2. Получены новые постановки задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯ-подходе и использующие двухкритериальное рассмотрение задач оптимизации;

3. Доказано, что в условиях нормальности распределения эффективностей использования ресурсов УаЯ-оптимальные решения могут быть получены с помощью оптимальных решений схемы Марковича;

4. Предложены и обоснованы алгоритмы численного решения задач по УаЯ-оптимизации распределения ресурсов в условиях неопределенности;

5. Предложены и обоснованы алгоритмы численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на Уа11-постановке и результатах прогнозирования с помощью ЫБЗА;

6. Сконструирован комплекс программ, обеспечивающий численные решения класса задач оптимизации, основанные на УаЯ-подходе;

7. Проведены серии численных экспериментов по оптимальному распределению ресурсов.

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

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

— Международной конференции «Обратные и некорректные задачи» (Москва, МГУ, 2003 г.);

— Международной конференции «Математическое моделирование социальной и экономической динамики» (Москва, 2004 г.);

— Международной научно-практической конференции «Глобальные тенденции в статистике и математических методах в экономике: наука, практика и образование» (Санкт-Петербург, 2004 г.);

— Всероссийской конференции «Алгоритмический анализ неустойчивых задач» (Екатеринбург, 2004 г.);

— Научных сессиях МИФИ (2001, 2002, 2003, 2004 гг.);

— Научном семинаре по рук. профессора Н. Ю. Бакаева (Гос. соц. Университет, Москва);

— Научном семинаре по рук. профессора H.A. Кудряшова (МИФИ) — Результаты, представленные в диссертации, опубликованы в 16 работах.

37, 71−85].

ЗАКЛЮЧЕНИЕ

.

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

1. Разработан и обоснован алгоритм прогнозирования детерминированных нестационарных одномерных временных рядов с помощью ЫЗБА.

2. Разработан алгоритм прогнозирования хаотических нестационарных одномерных временных рядов с помощью N8 Б А.

3. Разработан и обоснован алгоритм прогнозирования систем детерминированных взаимосвязанных временных рядов с помощью многомерного № 8А.

4. Разработан алгоритм прогнозирования систем хаотических взаимосвязанных временных рядов с помощью многомерного № 8А.

5. Проведены серии численных экспериментов по исследованию эффективности разработанного ШБА и алгоритмов прогнозирования детерминированных и хаотических временных процессов.

6. Предложена двухкритериальная УаЯ-постановка задачи оптимизации распределения ресурсов, соответствующая классической задаче Марковича.

7. Проведено сравнение понятий риска в схеме Марковича и УаЯ-схеме.

8. Установлена взаимосвязь решений Парето задачи Марковича и решений Парето задачи оптимизации в УаЯ-постановке в условиях нормальности распределения эффективностей как случайных величин.

9. Предложены обобщенные постановки задачи Марковича и соответствующей ей задачи в УаЯ-постановке.

10. Разработан и реализован алгоритм численного решения нахождения решений Парето задачи оптимального распределения ресурсов в обобщенной УаК-постановке в условиях нормального закона распределения вероятностей для эффективностей как случайных величин. Алгоритм состоит из двух этапов, на первом из которых решается обобщенная задача Марковича с тем же множеством ограничений на искомый вектор долей распределенного ресурса х, что и в обобщенной УаК-постановке.

11. Разработан и реализован алгоритм численного нахождения решений Парето задачи оптимального распределения ресурсов в обобщенной УаК-постановке в условиях общего закона распределения вероятностей для эффективностей как случайных величин. Алгоритм использует статистические данные реализованных значений эффективностей и основан на эмпирическом расчете УаЯя вероятности Р (Яр (х)<�Я.), где Кр (х) — - суммарная 1 эффективность использования распределенного ресурса.

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

13. Разработан и реализован алгоритм построения эмпирических распределений эффективностей как случайных величин на основе результатов прогнозирования эффективностей с помощью многомерного ЫЗБА.

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

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

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

На защиту выносятся следующие положения и результаты:

1. предложен и обоснован алгоритм прогнозирования детерминированных и хаотических временных процессов с помощью ИББА;

2. получены новые постановки задач оптимизации распределения ресурсов в условиях неопределенности, основанные на УаЯ-подходе и использующие двухкритериальное рассмотрение задач оптимизации;

3. доказано, что в условиях нормальности распределения вероятностей для эффективностей использования ресурсов как случайных величин УаЯ-оптимальные решения могут быть получены с помощью оптимальных решений в смысле Марковича;

4. предложены и обоснованы алгоритмы численного решения задач УаЯ-оптимизации распределения ресурсов в условиях неопределенности и нормального закона распределения эффективностей;

5. предложены и обоснованы алгоритмы численного решения задач оптимального распределения ресурсов в условиях неопределенности, основанные на УаЯ-постановке и результатах прогнозирования с помощью № 8А;

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

7. проведены серии численных экспериментов по прогнозированию и оптимальному распределению ресурсов.

Автор благодарен коллективу кафедры Прикладной математики (каф.31) МИФИ и персонально заведующему кафедрой профессору Николаю Алексеевичу Кудряшову за благожелательную обстановку во время учебы в аспирантуре и работы над диссертацией.

Автор искренне благодарен профессору кафедры Прикладной математики МИФИ Татьяне Ивановне Савеловой за оказанное положительное влияние на формирование профессиональных навыков автора.

Автор также благодарен сотрудникам ООО «Лаборатория 3 ИТ» и персонально Елене Владимировне Шелястиной за помощь в программной реализации разработанных в диссертации алгоритмов, включая реализацию вычислительного комплекса и проведение на их основе численных экспериментов.

Особую благодарность и признательность выражаю своему научному руководителю профессору Александру Витальевичу Кряневу.

<"