Методы стабилизации решений в задачах распределения ресурсов

УДК 519.21

МЕТОДЫ СТАБИЛИЗАЦИИ РЕШЕНИЙ В ЗАДАЧАХ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

ГИБКИНА Н. ВПАРШИН О.В._________________

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

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

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

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

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

Описанному графу можно поставить в соответствие матрицу 40, которая отображает числовую информацию о связях между объектами. Каждый элемент фДг) этой матрицы представляет собой интенсивность перехода ресурсов с течением времени от i -го объекта к j -му; если между объектами i и j нет связи, т.е. i -я и j -я вершины графа не соединены ребром, то % (г) = 0 , в противном случае aj{t)^ 0 . Знак “-” перед элементом ai^t) говорит об обратной связи, т.е. о том, что на самом деле

средства переходят не от i -го предприятия к j -му, а наоборот. Матрица 40 удовлетворяет следующему свойству: в любой момент времени сумма элементов каждой ее строки равна нулю, т.е.

П

^a^it) = 0 , i = 1, 2,..., n . Это означает, что суммарные ресурсы, скажем банка, распределены между всеми его партнерами.

Зависимость перераспределения ресурсов между рассматриваемыми объектами с течением времени может быть получена как решение на интервале [s0, г0) системы дифференциальных уравнений колмогоровского вида:

d-p

Распределение ресурсов в начальный момент времени s0 задается вектором начальных условий

p0 = jpj0, p0, •••, рП}, причем величины p0 ,

j = 1, 2,..., n могут быть как положительными, так и отрицательными, например, в случае имеющихся в наличии финансовых средств или задолженностей у каждого из n объектов.

На практике часто встречаются такие ситуации, когда система функционирует под воздействием сильных, быстро изменяющихся внешних возмущений. Такая ситуация имеет место в случае, когда финансовая система испытывает сильные возмущения, которые вызывают резкие колебания курса валют, акций и курса вторичных финансовых инструментов (опционов, свопов, фьючерских контрактов). Резкие колебания курсов можно в нашей модели отразить добавкой возмущенной матрицы с быстро изменяющимися коэффициентами. В этом случае коэффициенты системы дифференциальных уравнений (1) возмущаются на заданном интервале элементами матрицы Л 0. Эта матрица обладает следующим свойством: сумма элементов каждой ее строки равна нулю, однако, в отличие от матрицы 40, у матрицы А(t) все элементы, расположенные на главной диагонали, должны быть отрицательными. Воздействие возмущений задается таким образом, что возмущенная матрица может быть представлена в виде

40 = 40 +40.

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

40 и Л (0.

Рассмотрим теперь возмущенную систему дифференциальных уравнений с матрицей 40:

d-p

при заданных начальных условиях p(s0) = p0.

36

РИ, 2002, № 1

Имеет место следующее утверждение.

Утверждение 1. Рассмотрим систему дифференциальных уравнений вида

d-p

при заданных начальных условиях p(s0) = p0. Пусть матрица А(^ этой системы обладает следующим

П

свойством: Z і)= 0 , i = 1, 2, ..., п . Тогда для

j=i

любого t є [s0, t0) вектор p(t) решения системы удовлетворяет соотношению

Z рЛО=z pj

30 ^Р° .

j=1 j=1

Доказательство. Рассмотрим систему дифференциальных уравнений

d

dt

р( 0=р( МО,

dp j (t) « мм

“df" = Z WPilO, j = 1,2,..., П

при начальных условиях p(s0) = p0. Матрица A(t) этой системы удовлетворяет свойству: Z atj (t) = 0

j

для всех i .

Проинтегрировав каждое из уравнений системы

s0 до t є [s0> t0)

t

^ SjAWM Ъ , j = 1,2, ..., П ,

от s0 до t є [s0, t0), получим выражения вида Pj(0- Р0 = JZajfeK , j = 1,2,...,

s0

Pj

s0 i=1

Если все aij (§)Pi (|) интегрируемы на интервале

ад

[s0, t] и в случае, когда п м-да , ряд Z aij fe)pД^)

i=1

сходится равномерно на [s0, t], то

j Z av feta feK = Z j av feta feta.

S0 i i S0

Тогда выражение (5) можно переписать в виде

Pj

г s0

Далее, просуммировав последнее выражение по всем j, получим

X PjW=Х P +ХХ1 at ИP, fed.

jj

В случае, когда ряд

j i S0

ZZ

j=1 i =1

Іa fe) Pi fed

XXII aj fell Pi fcl *

j =1 i =1 s0

сходится, возможно изменение порядка суммирования, т.е.

ад ад t ад ад t

ZZl aij feta feta=Z Z} aij feta feta.

j =1 i=1 S0 i=1 j=1 S0

Тогда выражение (7) можно записать в виде

X j)=Х p° +ХХ1 «А«.

j І i І S0

На основании свойства, описанного выше,

X PjW=Х р°, +Х1Х a fe)p,№,

j j i S0 j

X PjW=X p 0+Xf PiO)-

j j i S0

X a fe)

Поскольку Z aij fe) = 0 для всех i, то второе слага-

j

емое в выражении (8) обращается в нуль. Таким образом, получаем Z j)=z P j , что и требова-

jj

лось доказать.

Полученный результат говорит о том, что при описанной выше особенности матриц А(^ и A(t) в любой момент времени совокупное количество ресурсов, распределенных между п объектами, остается постоянным и совпадает с их исходным количеством при t = s0.

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

Утверждение 2. Пусть на интервале [s0, t0) задана система (1) с конечным числом уравнений п ( п<ж ). Предположим, что возмущенная матрица системы A(t), которая определяется выражением (2), удовлетворяет следующим условиям:

1) матрица A(t) непрерывна в некоторой левой полуокрестности q точки t0;

2) существует столбец j0, элементы которого удовлетворяют условию:

t0

К (Odt

s0

3) левый собственный вектор

p (0 = {p^(t)> P2 fe), Pn(t)}

матрицы A(t), отвечающий ее нулевому собственному значению, удовлетворяет условию:

to pW = pi, i = 1,2.п .

Тогда при любых начальных условиях p0, заданных в точке s0, limpi (s0, t) = pi , i = 1, 2,п , где ttt0

s0 ей , i = 1, 2,

П

РИ, 2002, № 1

37

p(s0,t) — вектор решения возмущенной системы с матрицей A(t).

Доказательство. Выберем в столбце j0 матрицы A(t) элемент ^ij0 (0 такой, что

Кс №1

Щ №

для любого t < t0

Вынесем данный элемент из матрицы A(t), тогда

получим матрицу Л*(Л = —^ л(t).

^j-0 (О

Матрица A*(t) обладает следующим свойством: lim Л*( t) = Л*

t^to ’

где л* имеет следующую структуру: все ее элементы равны нулю, за исключением тех, скорость роста которых в точке t0 такая же, как и у элемента ^ щ (t). Нулевой собственный вектор числовой матрицы А* совпадает с р*= jp*, р*,р*}.

t0

Отметим, что в случае, когда величины щ ^dt

s0

имеют достаточно большое, но конечное значение, решение системы будет не точно принимать заданные теоретические значения, а локализоваться в их окрестности [3].

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

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

Рис. 1. Возмущающая функция f{t)

Pi

Рз

t

t

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

Рис. 2. Поведение компонент решения Pj (О (а) и

Рз

Для эксперимента была выбрана матрица

40=

( з

- 4 • t2 7

2 - 8 3 ^

10•t2 - 3 • t2 - 3•t

- 6 - 5 4

v 2 • t4 - 3 • t2 4 • t2 - 3 • t2 j

Возмущающая матрица, воздействующая на систему, имеет следующий вид:

Л (t) =

- 4 -1 2 3

20 -16 -1 - 3

5 - 2 -10 7

3 - 2 8 - 9

f t ,

где f (t) — функция возмущений, показанная на рис. 1.

Как видно, обе матрицы обладают свойством нулевых сумм компонент каждой своей строки и, кроме того, в матрице A(t) отрицательные элементы расположены только на главной диагонали.

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

Решение системы дифференциальных уравнений вида (3) будем искать при начальных условиях р0 = {l7, 2, - 9, -16} на временном интервале [о, t0).

Нулевой левый собственный вектор возмущающей матрицы A(t) в точке t0 = 1 имеет вид:

р * ={-1.47445, 0.751825, -2.55109, -2.72628}.

38

РИ, 2002, № 1

Решив систему дифференциальных уравнений (3), получаем в точке t0 = 1 следующие значения:

p ={-1,48477; 0,806447; -2,55336; -2,76832}.

Вектор отклонений теоретических и расчетных предельных значений:

5 ={0,0103183; 0,0546225; 0,00226064; 0,0420436}.

Графики поведения первой и третьей компонент решения системы дифференциальных уравнений вида (3) приведены на рис. 2.

Замечено, что, увеличивая силу возмущений, можно существенно уменьшить значения вектора отклонений сг . Так, после увеличения в предыдущем примере силы возмущений в 10 раз вектор 5 уменьшился приблизительно в 250-300 раз:

а ={0,000031; 0,000161; 0,000037; 0,000155}.

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

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

выбрали матрицу вида:

( “4 -1 2 3

(1 -1) 10 (1 -1) - 6 (1 -1) -1 (1 -1) - 3

4) = (1 -1) 4 (1 -1) - 2 (1 -1) -10 (1 -1) 8

(1 -1) 3 (1 -1) - 2 (1 -1) 8 (1 -1) - 9

1

Система дифференциальных уравнений (1) с такой матрицей удовлетворяет условиям утверждения 2, поэтому, как и в предыдущем случае, будут существовать предельные значения решения, не зависящие от начальных условий и момента времени, начиная с которого исследуется система. Мы снова будем искать решение системы (1) на интервале [о, t0) при начальных условиях p0 = {l7, 2, - 9, -16}.

Нулевой левый собственный вектор матрицы A(t) в точке t0 = 1 имеет вид:

p * ={-0,20438; 2,94891; -4,07299; -4,67153}.

Вектор решения системы (1) в точке t0 = 1:

p ={-0,20438; 2,94891; -4,07299; -4,67153}.

Как видно, в этом случае соответствующие компоненты векторов p* и p совпадают между собой. На рис. 3 приведены графики поведения решений исследуемой системы на интервале [о, l).

Pi

Рз

Рис. Д. Поведение компонент решения p1

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

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

Все вычисления были проведены с помощью пакета программ, разработанного авторами в системе символьной математики Mathematica 4©.

Литература: 1. Дикарев В.А. Фокусирующие факторы. Базисы фокусировки и стабилизации // Радиоэлектроника и информатика, 1998. №2(3). С.50-53. 2. Герасим С.Н. Проблемы стабилизации распределений неоднородных марковских систем. Харьков, изд-во ХТУРЭ, 1999. 212 с.

Поступила в редколлегию 28.11.2001

Рецензент: д-р физ. мат. наук, проф. Дикарев В.А.

Гибкина Надежда Валентиновна, инженер-стажер кафедры ВМ ХНУРЭ. Научные интересы: теория вероятностей и ее приложения, программирование. Адрес: Украина, 61166, Харьков, пр. Ленина, 14.

Паршин Олег Владимирович, канд. физ.-мат. наук, старший научный сотрудник кафедры ПМ ХНУРЭ. Научные интересы: математические методы анализа сложных систем. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-93-72.

РИ, 2002, № 1

39