Содержание к диссертации
Введение
Глава 1. Нестационарный сингулярно-спектральный анализ (nssa) детерминированных и хаотических временных процессов 17
1.1. Одномерный NSSA 17
1.2. Многомерный NSSA 25
Глава 2. Двухкритериальная постановка и решение задачи распределения ресурсов в условиях неопределенности на основе var 37
Глава 3. Алгоритмы и решение задачи оптимального распределения ресурсов в условиях неопределенности на основе var, статистических данных эффективностей и прогнозирования с помощью NSSA 50
Заключение 64
Список литературы
- Одномерный NSSA
- Многомерный NSSA
- Алгоритмы и решение задачи оптимального распределения ресурсов в условиях неопределенности на основе var, статистических данных эффективностей и прогнозирования с помощью NSSA
Введение к работе
В течение последних лет в Российской Федерации возрос научный интерес к задачам математического моделирования экономических систем и процессов [10, 11]. Одним из классов задач математического моделирования в экономике являются задачи оптимального распределения ресурсов.
Задачи оптимального распределения ресурсов возникают в различных областях науки, техники и социальных сферах, причем характер распределяемых ресурсов и смысл оптимальности может быть различным в зависимости от рассматриваемой прикладной области и конкретной задачи.
Наиболее широкий класс задач оптимального распределения ресурсов образуют такого рода задачи в условиях неопределенности. Неопределенность может быть порождена различными причинами, но в абсолютном большинстве случаев причиной неопределенности в задачах распределения ресурсов является неопределенный (случайный) характер величин, количественно описывающих эффективность использования ресурсов в тех объектах, в которые распределяются ресурсы.
В последние годы повысился научный интерес к постановкам и решению задач теории инвестиций, которые связаны с распределением инвестиционных ресурсов и, в частности, формированию инвестиционных портфелей. Решение о распределении инвестиционных ресурсов и формировании инвестиционных портфелей приходится осуществлять в условиях неопределенности и тем самым в условиях наличия риска.
Современный подход постановок задач оптимального распределения ресурсов в условиях неопределенности основан на двухкритериальном рассмотрении такого рода задач, когда одним из критериев является уровень суммарной эффективности использования ресурсов во всей совокупности объектов, в которые распределены ресурсы, а вторым критерием мера неопределенности (риска) эффективного использования ресурсов в
совокупности этих объектов, причем первый критерий подлежит максимизации, а второй - минимизации.
Исторически первой математической двухкритериальной моделью задачи оптимального распределения ресурсов является модель Гарри Марковица [1], который за цикл работ по портфельному инвестированию получил в 1990 г. Нобелевскую премию.
В рамках модели Марковица в качестве критерия уровня суммарной эффективности использования ресурсов (в интерпретации Марковица роль ресурса играет капитал) берется математическое ожидание суммарной эффективности как случайной величины, а в качестве критерия меры неопределенности - дисперсия суммарной эффективности.
Такой выбор математического выражения меры неопределенности позволил реализовать в рамках модели Марковица распределение ресурсов по нескольким объектам (диверсификация ресурсов), что при выполнении некоторых условий должно приводить к уменьшению риска.
Математическая модель Марковица задачи оптимального распределения ресурсов в условиях неопределенности принадлежит к классу задач квадратичного программирования. Теория численного решения этого класса задач" получила развитие в работах самого Марковица [2, 3] и в работах других авторов [4-9, 12-15].
Следует подчеркнуть, что класс задач оптимизации известный под названием задач квадратичного программирования был сформулирован, и была развита теория решений такого класса задач в основном под влиянием модели Марковица.
В последние годы развивается альтернативное направление постановок и решения задач оптимального распределения ресурсов в условиях
неопределенности, основанное на расчете вероятности р* события,
состоящего в том, что суммарная эффективность использования ресурсов,
трактуемая как случайная величина, примет значение меньшее, чем
заданный уровень R*.
Подход, основанный на рассмотрении задач оптимального распределения ресурсов с использованием вышеуказанных значений р и R*, получил название VaR- подхода (VaR- аббревиатура словосочетания Value-at-Risk).
При постановке задач оптимального распределения ресурсов, основанного на VaR - подходе, критерием уровня суммарной эффективности является R*, а критерием неопределенности (риска) вероятность р .
По существу концепция VaR соответствует пониманию риска традиционно используемого в технических областях, где величина риска обычно измеряется величиной вероятности наступления неблагоприятной ситуации (вероятность катастрофы, вероятность аварии, вероятность выхода из строя аппаратуры и т.д.).
VaR — подход, включая рассмотрение задач оптимизации распределения капитала на основе VaR- подхода, изложены в работах [16-31].
Потребность развития и использования VaR - технологии для решения практических задач распределения ресурсов в условиях неопределенности требует разработки эффективных вычислительных алгоритмов и реализации их в компьютерных программах для решения задач оптимального распределения ресурсов в условиях неопределенности.
Более того, современный подход постановки и решения задач оптимального распределения ресурсов требует эффективного использования всей доступной информации об использовании ресурсов в тех объектах, в которые распределяются ресурсы.
Для многих конкретных задач распределения ресурсов исследователю известны реализации эффективностей использования ресурсов, рассматриваемых как временные случайные процессы при непрерывном временном рассмотрении или как случайные временные ряды при дискретном временном рассмотрении.
При наличии такого рода информации естественно требовать ее использования при постановке и решении задач оптимизации распределения ресурсов, прогнозируя рассматриваемые временные процессы, соответствующие эффективностям, на будущий временной промежуток будущего использования ресурсов после их распределения.
При таком подходе необходимо использовать весь современный арсенал методов прогнозирования стохастических временных процессов (временных рядов).
Отметим, что прогнозирование временных процессов в условиях неопределенности является одним из основных направлений исследований современной науки с приложениями практически во всех областях науки, техники, природных и социальных областях [32-42].
В последние годы интенсивно развиваются методы прогнозирования динамических процессов, в том числе в условиях наличия хаотических компонент, основанные на сингулярно-спектральном анализе (Singular-Spectrum Analysis - SSA) [43-57]. Отметим, что в Российских научных публикациях вместо «SSA» часто используют термин «Гусеница» [58-62].
Применение SSA - для прогнозирования стационарных временных процессов показало его высокую эффективность и устойчивость при исследовании многих конкретных хаотических временных процессов технического, природного и социально-экономического характеров [63-70].
Такая высокая эффективность SSA - прогнозирования основана, прежде всего, на возможности с помощью SSA эффективно выделять компоненты исследуемого временного процесса с разным уровнем информации о процессе, в каждой из выделяемых компонент.
В отличие от других методов, использующих разложение исследуемого процесса на составляющие компоненты (например, разложение по системе базовых функций), только SSA не привносит эти компоненты извне, а строит их на основе самого исследуемого временного процесса. Вышеуказанная «самодостаточность» SSA и служит основой его высокой
эффективности при исследовании многих стационарных временных процессов (рядов).
К сожалению, абсолютное большинство хаотических временных процессов, описывающих временное изменение эффективностей использования ресурсов, не обладает свойством стационарности. Поэтому возникает потребность построения такой модификации SSA, которая позволяла бы исследовать, в том числе прогнозировать, нестационарные временные процессы. Одной из целей диссертационной работы и является модификация SSA, позволяющая исследовать и прогнозировать хаотические временные процессы, не обладающие свойством стационарности.
Далее в диссертационной работе рассматриваются в теоретических и прикладных планах постановки, численные методы и компьютерные программы решения актуальных задач оптимального распределения ресурсов в условиях неопределенности, основанные на VaR - технологии и результатах прогнозирования эффективностей как хаотических нестационарных временных процессов.
Целью диссертационной работы является:
Разработка алгоритмов прогнозирования хаотических нестационарных временных процессов с помощью нестационарного сингулярно-спектрального анализа (NSSA);
Разработка математических моделей задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR - подходе;
Разработка алгоритмов численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR - подходе и результатах прогнозирования с помощью нестационарного сингулярно-спектрального анализа;
Реализация решения задач оптимизации распределения ресурсов в виде комплекса компьютерных программ.
Научная новизна и значимость.
Разработаны алгоритмы нового метода прогнозирования хаотических временных процессов на основе нестационарного сингулярно-спектрального анализа.
Предложены новые постановки задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR -подходе.
Разработаны новые алгоритмы численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR - подходе, в условиях нормального закона распределения эффективностей.
Впервые разработана схема включения результатов прогнозирования на основе нестационарного сингулярно-спектрального анализа в алгоритм решения задачи оптимизации распределения ресурсов на основе VaR - подхода.
Сконструирован и реализован программный комплекс, включающий в себя все разработанные в диссертации новые алгоритмы прогнозирования хаотических временных процессов и решение задач оптимального распределения ресурсов в условиях неопределенности, основанные на VaR - технологии.
Предложенные в диссертации постановки задач оптимального распределения ресурсов в условиях неопределенности и разработанные алгоритмы и компьютерные программы их численного решения применяются для построения математических моделей задач оптимизации в экономических областях и могут быть использованы в технических приложениях, например, в задачах оптимального распределения поступающей информации в различных частях компьютерной сети, в задачах трафика различного содержания и др.
Краткое содержание диссертации.
В первой главе изложен нестационарный сингулярно-спектральный метод и алгоритм прогнозирования хаотических нестационарных временных рядов.
Нестационарный сингулярно-спектральный анализ хаотических
временных рядов У jit j = 1,..., М, / = 1,...,и} где М - число исследуемых рядов, п - число дискретных фиксаций времени, основан на формировании матрицы наблюдений Y размерности [Lx(p-M+q))
У\,\"'У\,р Уі,\ " Уг,р "Ум,\'"Ум,р J\,p '"Jq,p
У\,г '--У\,р+\ Уі,і '-У2,р+\ —Ум,2 '"Ум.р+і Ji,p+\ ''Jq,p+\
^Д'і.Л Д'і.і» Уі,1"'Уі,п 'Ум,Ь'"Ум,п J\,n "Jq.n
(0.1)
р - параметр NSSA-модели; fKi,k = \,...,q, і = р,...,п.
Рассматривается задача на собственные значения симметричной неотрицательной матрицы YTY размерности (p-M + q)x(p-M + q).
УтГ = р}, (0.2)
//,>//2>...>/V+?>0, 4J=(4Jlt...,4JtlhK+q)Ttj = l,...,p.M + q
- ранжированная система собственных значений jUj и соответствующая
им ортонормированная система собственных векторов Ч'у.
Формулы прогнозирования совокупности исследуемых временных рядов
[Ур> J = 1,...,-W> / = 1,...,«j определяются совокупностью собственных
векторов *j, а числовые значения /Jj определяют информационный вклад
соответствующей ей компоненты в исследуемые временные ряды.
Показано, что в случае отсутствия хаотических компонент в исследуемых детерминированных временных рядах предлагаемый метод прогнозирования обеспечивает абсолютно точный прогноз (с точностью до вычислительной погрешности при расчете прогнозируемых значений).
В случае присутствия хаотических компонент в исследуемых временных рядах точность прогноза определяется вариацией хаотических компонент.
При практическом использовании прогнозной модели рекомендуется использовать схему предварительного выделения детерминированных компонент исследуемых хаотических временных рядов с помощью систем робастных ортогональных полиномов, либо систем робастных сглаживающих сплайнов первого или третьего порядков [35].
Во второй главе дано краткое введение в схему Марковича и VaR -схему при рассмотрении задач распределения ресурсов в условиях неопределенности. Дано сравнение двух систем, включая анализ отличия, недостатков и преимуществ понятия риска в схеме Марковича и VaR -схеме.
Предлагаемые во второй главе математические модели задач оптимального распределения ресурсов в условиях неопределенности имеют вид:
p(Rp(x)
^-max, (0.3)
р - min, где
хеХ,
X - множество ограничений на искомый вектор долей распределяемого ресурса х, включая естественные ограничения
5Х=1, Xj>0, / = 1,...,М 7=1
R — критерий уровня эффективности,
р - критерий уровня риска.
Двухкритериальная задача (0.3) в отличие от традиционных
многокритериальных задач обладает той особенностью, что критерий R не определяется явным образом через значения управляющих переменных х.
Предлагаются две схемы нахождения решений Парето задачи (0.3), каждая из которой сводит задачу (0.3) к серии однокритериальных задач.
Согласно первой схеме решается серия однокритериальных задач
R* - max,
(0.4) хеХ
при фиксированных значениях уровня риска р є [0,1].
Согласно второй схеме решается серия однокритериальных задач
р* - min,
- (0.5)
при фиксированных допустимых значениях уровня эффективности R*.
Нахождение интервала допустимых значений уровня эффективности R сводится к решению однокритериальных задач
R* - max(min), хеХ. Показано, что решения Парето задачи (0.3) определяются совокупностью функций распределения вероятностей случайных величин Rp(x), хеХ.
Доказано, что в случае нормального закона распределения эффективностей Rj, j = \—,М каждое решение задачи (0.3) является решением задачи Марковича
a* = (Wx,x)-min,
mp=(m,x)-max, (0.7)
xeX, m = (ml,...,mM) - вектор математических ожиданий MR} = ту,
W — ковариационная матрица совокупности случайных величин Щ, j = \,...,M.
В третьей главе конструируются алгоритмы численного решения задачи (0.4).
В условиях нормальности распределения эффективностей
Rj, j = 1,..., М 9 предлагается двухэтапный способ решения задачи (0.4).
На первом этапе находятся решения Парето задачи Марковича (0.7), для численного решения которой предлагается использовать переход к
двойственной задаче с каноническим типом ограничений вида и > 0 и применением к двойственной задаче обобщенного итерационного процесса Некрасова [77].
Доказано, что для нахождения решений Парето исходной задачи (0.4) достаточно на втором этапе построить семейство функций распределения
случайных величин Rp\xj = \m,xjt где х - решение Парето задачи (0.7), и провести огибающую снизу это семейство кривых на плоскости [R ,р ),
p=p(Rp(x)
Практически процедура построения огибающей осуществляется на сетке фиксированных дискретных значений R из интервала допустимых значений.
Конструируются алгоритмы численного решения двухкритериальной задачи (0.4) в общем случае, когда условие нормальности распределения
случайных величин -Ку> j = 1,—,М не выполнено.
Если используется алгоритм, основанный на решении серии однокритериальных задач (0.5), то предлагается численная реализация алгоритма, основанная на методе проекции градиента
х=Рх(хм-а,Ч&(хм;Я-)) (0.8)
»
где Рх - оператор проекции на множество ограничений X, ае > 0 подбирается из условия лучшей скорости сходимости хм к искомому решению х', q>(x',R ) = P{Rp(x) < R ) - целевая функция задачи (0.5).
В третьей главе представлены также разработанные алгоритмы и комплекс программ для численного решения задач оптимального распределения ресурсов в условиях неопределенности на основе VaR и, представлены результаты прогнозирования эффективностей с помощью нестационарного сингулярно-спектрального анализа (NSSA).
Алгоритмы с использованием NSSA для решения задач оптимизации состоят из двух этапов.
На первом этапе с помощью NSSA и с использованием статистических данных по реализации эффективностей осуществляется формирование базы данных распределения прогнозируемых значений эффективностей использования ресурсов.
Итогом первого этапа алгоритма является база
Rj-,> i = \,.,.,N, j = \,...,М распределение прогнозируемых значений эффективностей R = (R{,...,RM)T как случайных величин.
На втором этапе на основе базы данных RJP у = 1,...,М, / = 1,...,JV
используются алгоритмы решения задач, представленных в третьей главе.
Например, при реализации схемы решения серии однокритериальных задач (0.5) для каждого фиксированного вектора х = (х^...,хм)т, хеХ,
формируется статистическое распределение Rpl(x), i = l,...,N для
эффективности Rp(x) = (x,R) как случайной величины согласно формуле м
Rp№)=YjxJRij> t=i->N'.
м Значение целевой функции
формуле (p(x,R*)= , где целое число к определяется из
последовательности ранжированных значений
Разработанный в диссертации комплекс программ решения задач оптимального распределения ресурсов в условиях неопределенности на основе VaR имеет в качестве блоков программные реализации алгоритмов численного решения задач оптимизации по схеме Марковица, включая задачи по нахождению распределения ресурсов с минимальным значением дисперсии суммарной эффективности и задачи линейного программирования по нахождению распределения с максимальным ожидаемым значением эффективности, решаемой с помощью метода прямого и обратного хода [79].
В комплекс программ входят также блоки прогнозирования нестационарных хаотических временных процессов с помощью NSSA и блоки программной реализации алгоритмов численного решения задач оптимизации распределения ресурсов на основе VaR, в том числе блоки формирования статистических данных на основе прогнозирования эффективностей с помощью NSSA и их использования для решения задач оптимизации.
В третьей главе представлены также блок-схемы частей вычислительного комплекса и структурная схема всего комплекса в целом. Представлены также численные результаты оптимального распределения ресурсов в условиях неопределенности и анализ численных результатов.
В диссертации использовались результаты теоретических исследований в различных областях прикладной математики, представленные в работах [86-117].
На защиту выносятся следующие результаты диссертации:
Предложены и обоснованы алгоритмы прогнозирования хаотических временных процессов с помощью нестационарного сингулярно-спектрального анализа (NSSA);
Получены новые постановки задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR-подходе и использующие двухкритериальное рассмотрение задач оптимизации;
Доказано, что в условиях нормальности распределения эффективностей использования ресурсов VaR-оптимальные решения могут быть получены с помощью оптимальных решений схемы Марковича;
Предложены и обоснованы алгоритмы численного решения задач по VaR-оптимизации распределения ресурсов в условиях неопределенности;
Предложены и обоснованы алгоритмы численного решения задач оптимизации распределения ресурсов в условиях неопределенности, основанные на VaR-постановке и результатах прогнозирования с помощью NSSA;
Сконструирован комплекс программ, обеспечивающий численные решения класса задач оптимизации, основанные на VaR-подходе;
Проведены серии численных экспериментов по оптимальному распределению ресурсов.
Все результаты диссертации, выносимые на защиту, получены автором. В работах, отражающих содержание диссертации и выполненных в соавторстве, автору принадлежит равный вклад в разработку
математических моделей, алгоритмов численных решений рассматриваемых задач и их программную реализацию.
Полученные в диссертации результаты были доложены на:
Международной конференции «Обратные и некорректные задачи» (Москва, МГУ, 2003 г.);
Международной конференции «Математическое моделирование социальной и экономической динамики» (Москва, 2004 г.);
Международной научно-практической конференции «Глобальные тенденции в статистике и математических методах в экономике: наука, практика и образование» (Санкт-Петербург, 2004 г.);
Всероссийской конференции «Алгоритмический анализ неустойчивых задач» (Екатеринбург, 2004 г.);
Научных сессиях МИФИ (2001,2002,2003,2004 гг.);
Научном семинаре по рук. профессора Н.Ю. Бакаева (Гос. соц. Университет, Москва);
- Научном семинаре по рук. профессора Н.А. Кудряшова (МИФИ);
Результаты, представленные в диссертации, опубликованы в 16 работах
[37,71-85].
Одномерный NSSA
Рассмотрим сначала случай одномерного (скалярного) временного ряда y„i = \,...,n. (1.1)
Классическая схема сингулярно-спектрального анализа (SSA) временного ряда (1.1) основана на формировании матрицы наблюдений ґУі Уі -УР 7 = Уі Уъ -УР+\ (1.2) КУь Ум-Уп J размерности (Lxp) и рассмотрении задачи на собственные значения симметричной неотрицательной (р х р) матрицы YTY: YTYy = My, (1.3) где //, //2 ... / О - ранжированная система собственных значений Mj, a ,7 = 1,...,/, - ортонормированная система соответствующих им собственных векторов, L - ранг SSA-модели.
На основе системы собственных векторов в рамках SSA строятся система главных компонент и формулы прогнозирования будущих значений Уп+і — Уп+т исследуемого временного ряда [59, 61].
Известно, что, если временной ряд (1.1) является решением конечно-разностного уравнения Уі = Т,акУі-к к (1-4) где / p,L l, то SSA обеспечивает абсолютно точный прогноз на любое число шагов вперед Уп+\ Уп+2»
Если вместо детерминированного уравнения (1.4) рассматривается авторегрессионная модель Уі = ІакУі-к +Єм (1.5) к=ах где м - хаотическая компонента, то SSA обеспечивает прогноз, точность которого определяется степенью вариации хаотической компоненты [59, 61]. Отметим, что непрерывным аналогом конечно-разностного уравнения (1.4) является обыкновенное однородное дифференциальное уравнение с постоянными коэффициентами вида +4 +...+ = 0. (1.6)
Авторегрессионная модель (1.5) определяет (при соответствующих условиях) стационарный хаотический временной ряд и поэтому схема (1.2)-(1.3) SSA не обеспечивает исследование нестационарных временных процессов (рядов) детерминированных или хаотических.
Пусть наряду с исследуемым временным рядом (1.1) известны реализации временных процессов fjn j = \,...,q, / = 1,...,/1, причем каждая реализация / ,/ = 1,..., оказывает аддитивное влияние на значение yt исследуемого ряда, а предыдущие реализации /Р_к,к = \,... влияния на реализацию у, не оказывают.
Для того чтобы учесть влияние нестационарных факторов {/},} j = 1,—»# на исследуемый временной процесс У/, / = 1,...,п образуем матрицу наблюдений У\ Уг — УР J\,p "Jq,p Y = Уі Уъ " Ур-Л J\,p+l- Jq,p+l (1.7) Уь Уь+\ "Уп J\,n "Jqs -18 размерности
Рассмотрим задачу на собственные значения симметричной неотрицательной матрицы YTY размерность (p + q)x(p + Ч) YTYy/j= ijy/ji (1.8) где //, ju2 ... jup+q О - ранжированная система собственных значений и V j=(Vji — l//j,p+q)T J = h— P + q- ортонормированная система собственных векторов матрицы YTY.
Обозначим через И = {у/х,...,у/р ) - (p + q)x(p + q) - ортогональную матрицу системы собственных векторов.
Введем (p + q)x(p + Ч)матрицу главных компонент V = (Vv...,Vp+q) = 4 YT. Имеем p+q y-i Если выделим первые г p + q главных компонент, то равенство Г«.=5»у (1.9) У-1 определяет значение сглаженного временного ряда. Чем меньше в равенстве (1.9) г Р + Я, тем больше степень сглаживания исходного временного ряда.
Поскольку на побочных диагоналях минора ГУ\ Уг -УР у= Уг У, -УР+і Л Ум-Ун J матрицы наблюдений Y должны находиться одинаковые значения исходного временного ряда, рекомендуется значения сглаженного временного ряда Ysmoni получать путем усреднения элементов побочных диагоналей минора YsmoQX матрицы Ysmo0.
Предположим, что исходный временной ряд (1.1) порожден конечно-разностным уравнением у І=Z акУ,-к+ ujfj,i, (їло) к=\ у=1 где ak,Uj, к = 1,...,1, j = \,...,q - постоянные и уравнение (1.10) не может быть сведено к уравнению вида (1.10) с меньшими значениями / и q.
Многомерный NSSA
При исследовании и прогнозировании многих хаотических временных рядов часто есть возможность исследовать не отдельный временной ряд, а несколько временных рядов, оказывающих друг на друга влияние. В этих условиях целесообразно исследовать все семейство рядов вместе с учетом их взаимного влияния. Учет взаимного влияния нескольких хаотических временных рядов дает возможность при исследовании каждого из них использовать информацию, имеющуюся о них в других временных рядах, что, в свою очередь, увеличивает точность результатов исследования и, в частности, точность прогнозирования.
Рассмотрим совокупность временных рядов yjpj = \,...,m, і = 1,...,п. (1.22)
Одна из обычных схем многомерного сингулярно-спектрального анализа совокупности временных рядов (1.22) основана на формировании многомерной матрицы наблюдений У\,\ У 1,2 " У\,р У2,1 У2,1 — Уі,р "Ут,\ Ут,2 " Ут,р _ У\,2 У\,Ъ - У\,р+\ У2,2 2,3 — У2,р+\ "Ут,2 Ут,Ъ — Ут,р+\ У\,Ь У\,Ь+\ "У\,п У2,1 УіМ\ "У2,п " Ут,1 Ут,1+\ "Ут,п ; размерности (Lxm-p) и рассмотрении задачи на собственные значения симметричной неотрицательной (т-рхт-р)-матрицы Y Y. YrY j = j, (1.24) где //, /л ... . jum.p 0 - ранжированная система собственных значений, a y/j,j = \,...,m-p - ортонормированная система соответствующих им собственных векторов, р - ранг многомерной сингулярно-спектральной модели (MSSA).
На основе системы собственных векторов в рамках MSSA строится система главных компонент и формулы прогнозирования будущих значений У\,п+\ — Ут,п+\ У\,п+2 — Ут,п+2 — исследуемых временных рядов [59-62].
Если временные ряды являются решением системы конечно-разностных уравнений т 1 yfl=YLanyyj, (1.25) j =\ к=\ где luL, р 1, / = 1,...,/и, то NSSA обеспечивает абсолютно точный прогноз на любое число временных шагов вперед.
Если вместо системы детерминированных конечно-разностных уравнений (1.25) рассматривается многомерная регрессионная модель т I Ул = ИТ,апУг,і-к+єл ./ = 1.-., , (1.26) где jj - хаотические компоненты, то NSSA обеспечивает прогноз, точность которого определяется степенью изменения хаотической компоненты [59-62]. Непрерывным аналогом системы конечно-разностных уравнений (1.25) является система однородных дифференциальных уравнений с постоянными коэффициентами d1v т d v т +Z - r+-"+S«/ /=0, j = U,m, (1.27)
Регрессионная модель (1.26) определяет стационарный многомерный временной ряд и поэтому схема (1.23)-(1.24) не обеспечивает исследования многомерных нестационарных детерминированных или хаотических временных рядов.
Пусть наряду с исследуемой системой временных рядов (1.22) известны реализации временных нестационарных факторов fkJ, k = \,...,q, / = 1,...,и, причем каждая реализация fki, k = \,...,q, оказывает аддитивные влияния на реализации yJtt, j = 1,...,m - исследуемых временных рядов и не оказывает влияния на последующие реализации для Уу м,У +2 j = \»- т .
Для того чтобы учесть влияние нестационарных факторов {/ ,/ z = ! «} на исследуемую систему временных процессов КУ,/ = 1,--,«} j = \,...,m образуем многомерную матрицу наблюдений У\,\ У\,2 — У\,р Уі,\ — Уі,р "Ут,\ " Ут,р J\,p "Jq,p У\,г У\,г Уі,р+і Уг,2 Уг,Р+\—Ут,г Ут,Р+і J\,p+i "Jq,p+i У = (1.28) У\,Ь Ді+l " У\,п Уі,1 —Уг,п Ут,1 — УЧ,п J\,n "Jq,n размерности (Lx(p-m+q)). Рассмотрим задачу на собственные значения симметричной неотрицательной матрицы Y Y размерности (p-m + q)x(p-m + q) YTYj= jy/j, (1.29) где //, ju2 ... //pm+9 0 - ранжированная система собственных значений, i//j=(i//Jl,...,y/JгР.т+д) , j = 1,2,...,p m + q - ортонормированная система собственных векторов матрицы Y Y.
Пусть система детерминированных временных рядов (1.22) порождена системой конечно-разностных уравнений ml q yjj =11 агІУАі-к+Ти Л,п J = »»m (1.30) У=1 k=\ k=\ где cij\ki ukj - постоянные и система (1.30) не может быть сведена к системе уравнений вида (1.30) с меньшими значениями / и Ц. В этом случае будем говорить, что система временных рядов (1.22) имеет ранг (/,#).
Алгоритмы и решение задачи оптимального распределения ресурсов в условиях неопределенности на основе var, статистических данных эффективностей и прогнозирования с помощью NSSA
Рассмотрим теперь алгоритмы численного решения задач оптимизации распределения ресурсов, предложенные в главе 2.
В целях конкретизации алгоритмов рассмотрим случай, когда априорные ограничения задаются в виде групповых ограничений вида (2.5), причем каждый объект, в который распределяется ресурс, входит в одну и только одну из групп.
Тогда, согласно результатам второй главы каждое решение Парето задачи (3.2) является решение Парето задачи (3.1), причем для нахождения всей совокупности решений Парето задачи (3.2) достаточно для каждого _» решения Парето х задачи (3.1) построить функцию распределения рСО ] случайной величины Rp(x )= 2-ІХІ и провести на плоскости двух критериев (К Р) задачи (3.2) огибающую снизу семейство функций распределения F(i?) кривую, точкам которой и будут на плоскости критериев \R p) соответствовать решения Парето задачи (3.2).
Таким образом, нахождение решений Парето задачи (3.2) в условиях нормальности распределения R можно разбить на два этапа. На первом этапе находятся решения Парето обобщенной задачи Марковича (3.1). Нахождение решений Парето задачи (3.1) сводится к решению серии однокритериальных задач при фиксированном значении тр о =(Wx,x)-mm, (3.3) (т,х) = тре(тртЬ,т ртах), ,m, aj xJl+...+xj J3J, У = 1,. ])Г х, = 1, л:,. 0, / = 1,..., п. где Wpmin и Wpmax вычисляются после решения однокритериальных задач a2 = (Wx, x) - mjn, И X aj xfl + ...+xJnj J3j, j = l,...,m, n x,=l, x, 05 / = 1,...,/1, . =1 m = (m,x)-mjn, X a j хл +... + xjnj pp j = l,...,/w, n ,=1, x; 0, Ї = 1,...,Я, причем w min = m,X j, wPmax = w,x I, где x - единственное решение задачи (3.4), (3.4) (3.5) —» х единственное решение задачи (3.5).
Задача (3.4) - задача квадратичного программирования, которая эффективно решается путем перехода к двойственной задаче —[Си,и)-(а,и)-тт 2 ) \ ) (3.6) и 0, где С-(п + 2т + \)х(п+2т+ї) - симметричная неотрицательная матрица, на главной диагонали которой стоят положительные числа Скк 0, к = \,...,п+2т+\ [86].
Решение двойственной задачи (3.6) находится с помощью эффективной итерационной процедуры обобщенного метода Некрасова к-\ п+2т+1 С, vj/+1) = кк У=і у= +! J (3.7) M /+,)=max{0,v /+,)}, к = 1,...,п+2т+1.
Задача (3.5) - задача линейного программирования, которая эффективно и устойчиво решается с помощью метода прямого и обратного хода, учитывающего специфику задачи линейного программирования (3.5) и требующего значительно меньших вычислительных затрат, чем симплекс-метод [86].
Для реализации второго этапа нахождения решений Парето задачи (3.2) фиксируем значение критерия Rk в точке сетки его дискретных значений _ к = 1,2,..., и для каждого решения Парето х задачи (3.1) подсчитываем значения интеграла вероятностей 1 Г 2 т? . -т-Ц-Je 2а; ds = p(x), (3.8) _ _» __ _ где Jp =(Wx ,x ), mp ={m,x ). — Решением Парето для значения критерия Rk является тот вектор х , для _» — которого =zrgimnp(x), х
Численное решение задачи (3.2), использующее решение обобщенной задачи Марковица (3.1) в условиях нормальности распределения R, в условиях нарушения нормальности закона распределения эффективностей R становится невозможным, поскольку решения Парето задачи (3.2) уже не будут в общем случае являться решениями Парето задачи (3.1).
