close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 519.21
МЕТОДЫ СТАБИЛИЗАЦИИ
РЕШЕНИЙ В ЗАДАЧАХ
РАСПРЕДЕЛЕНИЯ РЕСУРСОВ
средства переходят не от i -го предприятия к j -му,
а наоборот. Матрица A t удовлетворяет следующему свойству: в любой момент времени сумма
элементов каждой ее строки равна нулю, т.е.
n
¦ aij
t
0 , i 1, 2, !, n . Это означает, что суммар-
j 1
ГИБКИНА Н. В., ПАРШИН О.В.
Исследуется поведение решений задач управления
ресурсами. Приводятся условия, при выполнении которых происходит выход траектории системы на заданное распределение под воздействием сильных внешних возмущений.
На практике часто приходится сталкиваться с
задачами, в которых рассматривается хозяйственная деятельность экономических объектов, связанная с использованием некоторого вида ресурсов.
Представляет интерес вопрос о перераспределении
объемов ресурсов между взаимодействующими
объектами с течением времени и зависимость такого перераспределения от внешних воздействий.
Пусть n объектов занимаются экономической
деятельностью. Они могут представлять собой
различные предприятия, подразделения одного предприятия, физических лиц, финансовые учреждения (банки, биржи) и т. д. В начальный момент
времени каждый из объектов имеет в наличии
определенное количество данного вида ресурсов
или же испытывает недостаток в них (например,
должен другому объекту). В зависимости от конкретной задачи под ресурсами могут пониматься
денежные средства, товары, сырье и др.
Предположим, что в процессе своей деятельности
объекты взаимодействуют друг с другом, осуществляя при этом обмен ресурсами. Однако в любой
момент времени суммарное количество ресурсов
остается неизменным и совпадает с их количеством
в начальный момент времени.
Процесс взаимодействия таких объектов удобно
описывать с помощью соответствующим образом
подобранного графа. Вершины графа соответствуют рассматриваемым объектам, а дуги изображают
связи между ними. Дуги в данном случае будут
направленными, поскольку имеет значение направление связи между двумя объектами. Всем
вершинам и дугам графа соответствуют данные о
процессе производства и характере взаимодействия
между объектами.
Описанному графу можно поставить в соответствие
матрицу A t , которая отображает числовую информацию о связях между объектами. Каждый
элемент aij t этой матрицы представляет собой
интенсивность перехода ресурсов с течением времени от i -го объекта к j -му; если между объектами i
и j нет связи, т.е. i -я и j -я вершины графа не
соединены ребром, то aij t 0 , в противном случае
aij t z 0 . Знак ?-? перед элементом aij t говорит
об обратной связи, т.е. о том, что на самом деле
36
ные ресурсы, скажем банка, распределены между
всеми его партнерами.
Зависимость перераспределения ресурсов между
рассматриваемыми объектами с течением времени
может быть получена как решение на интервале
s0 , t 0 системы дифференциальных уравнений
колмогоровского вида:
G
d G
pt
pt At .
(1)
dt
Распределение ресурсов в начальный момент времени s 0 задается вектором начальных условий
G
0
p0
p10 , p20 , !, p n0 , приче м вел ичи ны p j ,
j 1, 2, !, n могут быть как положительными, так
и отрицательными, например, в случае имеющихся
в наличии финансовых средств или задолженностей у каждого из n объектов.
На практике часто встречаются такие ситуации,
когда система функционирует под воздействием
сильных, быстро изменяющихся внешних возмущений. Такая ситуация имеет место в случае, когда
финансовая система испытывает сильные возмущения, которые вызывают резкие колебания курса
валют, акций и курса вторичных финансовых
инструментов (опционов, свопов, фьючерских
контрактов). Резкие колебания курсов можно в
нашей модели отразить добавкой возмущенной
матрицы с быстро изменяющимися коэффициентами. В этом случае коэффициенты системы дифференциальных уравнений (1) возмущаются на
~
заданном интервале элементами матрицы / t . Эта
матрица обладает следующим свойством: сумма
элементов каждой ее строки равна нулю, однако, в
~
отличие от матрицы A t , у матрицы / t все
элементы, расположенные на главной диагонали,
должны быть отрицательными. Воздействие возмущений задается таким образом, что возмущенная
матрица может быть представлена в виде
~
(2)
/ t At / t .
Матрица / t будет сохранять свойство равенства
нулю суммы элементов каждой своей строки за счет
выполнения этого свойства у каждой из матриц
~
At и /t .
Рассмотрим теперь возмущенную систему дифференциальных уравнений с матрицей / t :
d G
pt
dt
G
~
p t At / t
G
при заданных начальных условиях p s0
(3)
G
p0 .
РИ, 2002, № 1
Имеет место следующее утверждение.
Утверждение 1. Рассмотрим систему дифференциальных уравнений вида
G
d G
pt
pt At
dt
G
G
при заданных начальных условиях p s 0
p 0 . Пусть
матрица A t этой системы обладает следующим
сходится, возможно изменение порядка суммирования, т.е.
f t
f
¦¦ і aij
j 1 i 1 s0
¦ aij
t
0, i
1, 2, !, n . Тогда для
G
любого t Џ s0 , t0 вектор p t решения системы
удовлетворяет соотношению
n
n
¦ pj t
¦ p 0j .
j 1
j 1
¦ aij
t
0
j
для всех i .
Проинтегрировав каждое из уравнений системы (4)
от s 0 до t Џ s 0 , t 0 , получим выражения вида
pj t t n
і ¦ aij
s0 i 1
t n
aij
і¦
i 1
p 0j pj t
s0
[ p i [ d[ , j
1, 2, ! , n ,
[ pi [ d[ , j 1, 2, ! , n . (5)
f
s 0 , t и в случае, когда n o f , ряд
¦ aij
[ pi [
i 1
t
[ p i [ d[
s0 i
¦ і aij
i s0
[ p i [ d[ .
i s0
1, 2, ! , n . (6)
Далее, просуммировав последнее выражение по
всем j , получим
¦ pj t
j
t
¦ p 0j ¦¦ і aij [ pi [ d[ .
j
j
i s0
В случае, когда ряд
f
f
t
¦¦ і aij
j 1 i 1 s0
[ pi [ d[ d ¦¦ і aij [ � p i [ d[
РИ, 2002, № 1
t
¦ pj
¦ p 0j ¦ і ¦ aij
t
j
j
Поскольку
i s0 j
j 1 i 1 s0
[ p i [ d[ ,
t
Є
є
0
p
¦ j ¦ і pi [ � «¦ aij [ » d[ .
»ј
j
i s0
¬« j
¦ aij [
(8)
0 для всех i , то второе слага-
j
емое в выражении (8) обращается в нуль. Таким
образом, получаем
¦ p j t ¦ p 0j , что и требоваj
j
лось доказать.
Полученный результат говорит о том, что при
~
описанной выше особенности матриц A t и / t
в любой момент времени совокупное количество
ресурсов, распределенных между n объектами, остается постоянным и совпадает с их исходным количеством при t
s0 .
Утверждение 2. Пусть на интервале s0 , t 0 задана
система (1) с конечным числом уравнений n
( n f ). Предположим, что возмущенная матрица
системы / t , которая определяется выражением
(2), удовлетворяет следующим условиям:
(7)
і O ij
0
f , s Џ : , i 1, 2, ..., n ;
0
t dt
s0
3) левый собственный вектор
G
pt
p1 t , p 2 t , ! , p n t
матрицы / t , отвечающий ее нулевому собственному значению, удовлетворяет условию:
lim pi t
f f t
[ p i [ d[ .
На основании свойства, описанного выше,
t0
t
p 0j ¦ і aij [ pi [ d[ , j
j s0
2) существует столбец j 0 , элементы которого удовлетворяют условию:
Тогда выражение (5) можно переписать в виде
pj t
i
1) матрица / t непрерывна в некоторой левой
полуокрестности : точки t 0 ;
сходится равномерно на s 0 , t , то
t
j
Приведем теперь условия, при выполнении которых имеет место выход траектории возмущенной
системы на заданное распределение за сколь угодно
малое время.
Если все aij [ pi [ интегрируемы на интервале
і ¦ aij
¦ p 0j ¦¦ і aij
t
j
этой системы удовлетворяет свойству:
[ p i [ d[ .
t
¦ pj
¦ pj t
Д о к а з а т е л ь с т в о . Рассмотрим систему дифференциальных уравнений
G
d G
pt
pt At ,
dt
n
dp j t
aij t p i t , j 1, 2, ! , n
¦
(4)
dt
i 1
G
G
при начальных условиях p s 0
p 0 . Матрица A t
p 0j
i 1 j 1 s0
j
j 1
f t
Тогда выражение (7) можно записать в виде
n
свойством:
f
¦¦ і aij
[ p i [ d[
t nt 0
pi , i
1, 2, ..., n .
G
Тогда при любых начальных условиях p 0 , задан
pi , i 1, 2, ..., n , где
ных в точке s 0 , lim pi s 0 , t
t nt 0
37
G
p s 0 , t ? вектор решения возмущенной системы с
матрицей / t .
До каз ате л ь ств о. Выберем в столбце j 0 матрицы
/ t элемент O ij0 t такой, что
t
і O ij0 t dt t
s0
t
і O kj
0
s0
f
100
80
60
40
t dt для любого t t .
0
20
Вынесем данный элемент из матрицы / t , тогда
0.2
1
/t .
O ij0 t
получим матрицу / t
lim / t
t ot0
/ ,
t0
Отметим, что в случае, когда величины
і O ij
0
Рассмотрим далее модельные примеры воздействия
возмущений, позволяющих вывести решение системы на заданные значения точно и приближенно.
Вначале рассмотрим случай, когда компоненты
решения системы локализуются в окрестностях
своих теоретических значений.
Для эксперимента была выбрана матрица
2
10 � t 2
8
3�t 2
6
5
4�t2
3 ·
ё
3�t2 ё
4 ё.
ё
3 � t 2 ё№
Возмущающая матрица, воздействующая на систему, имеет следующий вид:
~
/t
2
3 ·
§ 4 1
Ё
ё
Ё 20 16 1 3 ё
�f t ,
Ё 5
2 10 7 ё
Ё
ё
Ё 3
2
8
9 ё№
©
где f t ? функция возмущений, показанная на
рис. 1.
38
12.5
10
7.5
5
2.5
0.2
0.4
s0
Утверждение 2 позволяет прогнозировать поведение системы с течением времени. Зная характер
возмущений, оказывающих влияние на систему,
можно предсказать, как будут перераспределяться
ресурсы между взаимодействующими объектами за
любое, сколь угодно малое время, при условии, что
суммарное их количество останется неизменным.
3�t
t
p1
t dt
имеют достаточно большое, но конечное значение,
решение системы будет не точно принимать заданные теоретические значения, а локализоваться в их
окрестности [3].
2
1
15
где / имеет следующую структуру: все ее элементы равны нулю, за исключением тех, скорость роста
которых в точке t 0 такая же, как и у элемента
O ij0 t . Нулевой собственный вектор числовой матG
рицы / совпадает с p p1 , p 2 , !, p n .
At
0.8
§ 3
Ё
2
Ё 4�t
Ё 7
Ё
Ё 2�t4
©
0.6
Рис. 1. Возмущающая функция f t
Матрица / t обладает следующим свойством:
0.4
0.6
0.8
1
0.6
0.8
1
t
а
p3
-4
-6
0.2
0.4
t
-10
-12
-14
б
Рис. 2. Поведение компонент решения p1 t (а) и
p3 t (б) системы дифференциальных уравнений
вида (3)
Как видно, обе матрицы обладают свойством нулевых сумм компонент каждой своей строки и, кроме
~
того, в матрице / t отрицательные элементы
расположены только на главной диагонали.
Таким образом, для возмущенной системы (3)
выполнены условия утверждения 2 о существовании предельных значений решения, не зависящих
от начальных условий и момента времени, начиная
с которого исследуется система.
Решение системы дифференциальных уравнений
вида (3) будем искать при начальных условиях
G
p 0 17, 2, 9, 16 на временном интервале 0, t 0 .
Нулевой левый собственный вектор возмущающей
~
матрицы / t в точке t 0 1 имеет вид:
G
p * ={?1.47445, 0.751825, ?2.55109, ?2.72628}.
РИ, 2002, № 1
Решив систему дифференциальных уравнений (3),
получаем в точке t 0 1 следующие значения:
G
p ={?1,48477; 0,806447; ?2,55336; ?2,76832}.
Вектор отклонений теоретических и расчетных
предельных значений:
G
V ={0,0103183; 0,0546225; 0,00226064; 0,0420436}.
Графики поведения первой и третьей компонент
решения системы дифференциальных уравнений
вида (3) приведены на рис. 2.
Замечено, что, увеличивая силу возмущений, можно существенно уменьшить значения вектора отG
клонений V . Так, после увеличения в предыдущем
G
примере силы возмущений в 10 раз вектор V
уменьшился приблизительно в 250-300 раз:
G
V ={0,000031; 0,000161; 0,000037; 0,000155}.
Однако величина изменения вектора отклонений
зависит не только от силы, но и от характера
возмущений, поэтому для разных типов возмущений при одинаковой силе воздействия значения
G
вектора V будут отличаться.
Далее рассмотрим случай, когда возмущения позволяют вывести исследуемую систему на точно
заданное распределение. Для моделирования мы
выбрали матрицу вида:
At
§ 4
Ё
Ё (1 t )
Ё 10
Ё (1 t )
Ё
Ё 4
Ё (1 t )
Ё 3
ЁЁ
© (1 t )
1
(1 t )
6
(1 t )
2
(1 t )
2
(1 t )
2
(1 t )
1
(1 t )
10
(1 t )
8
(1 t )
3 ·
ё
(1 t ) ё
3 ё
(1 t ) ё
ё
8 ё
(1 t ) ё .
9 ё
ё
(1 t ) ё№
Система дифференциальных уравнений (1) с такой
матрицей удовлетворяет условиям утверждения 2,
поэтому, как и в предыдущем случае, будут существовать предельные значения решения, не зависящие от начальных условий и момента времени,
начиная с которого исследуется система. Мы снова
будем искать решение системы (1) на интервале
G
0, t 0 при начальных условиях p 0 17, 2, 9, 16 .
Нулевой левый собственный вектор матрицы A t
в точке t 0 1 имеет вид:
G
p * ={?0,20438; 2,94891; ?4,07299; ?4,67153}.
Вектор решения системы (1) в точке t0 1 :
G
p ={?0,20438; 2,94891; ?4,07299; ?4,67153}.
Как видно, в этом случае соответствующие компоG
G
ненты векторов p * и p совпадают между собой. На
рис. 3 приведены графики поведения решений
исследуемой системы на интервале 0, 1 .
РИ, 2002, № 1
p1
15
12.5
10
7.5
5
2.5
0.2
0.4
0.6
0.8
t
1
а
p3
-4
-5
-6
-7
-8
0.2
0.4
0.6
0.8
1
t
б
Рис. 3. Поведение компонент решения p1 t (а) и
p3 t (б) системы дифференциальных уравнений
вида (1)
Нетрудно проверить, что в обоих
описанных случаях
G
суммы компонент вектора p решений рассматриваемой системы дифференциальных уравнений совпадаютGс суммой компонент вектора начальных условий p 0 , причем это равенство выполняется в любой
точке рассматриваемого временного интервала. Следует также заметить, что изменение вектора начальных условий не изменяет предельных значений
компонент решения системы.
Итак, проведенные исследования позволяют, соответствующим образом подбирая возмущения, воздействующие на систему, предсказать ее поведение
в любой момент времени и вывести траекторию
системы на произвольное, заранее заданное распределение, сохранив при этом суммарное количество
ресурсов, заданное вектором начальных условий.
Все вычисления были проведены с помощью пакета
программ, разработанного авторами в системе символьной математики Mathematica 4©.
Литература: 1. Дикарев В.А. Фокусирующие факторы.
Базисы фокусировки и стабилизации // Радиоэлектроника и информатика, 1998. №2(3). С.50-53. 2. Герасин С.Н.
Проблемы стабилизации распределений неоднородных
марковских систем. Харьков, изд-во ХТУРЭ, 1999. 212 с.
Поступила в редколлегию 28.11.2001
Рецензент: д-р физ. мат. наук, проф. Дикарев В.А.
Гибкина Надежда Валентиновна, инженер-стажер кафедры ВМ ХНУРЭ. Научные интересы: теория вероятностей и ее приложения, программирование. Адрес:
Украина, 61166, Харьков, пр. Ленина, 14.
Паршин Олег Владимирович, канд. физ.-мат. наук,
старший научный сотрудник кафедры ПМ ХНУРЭ.
Научные интересы: математические методы анализа
сложных систем. Адрес: Украина, 61166, Харьков, пр.
Ленина, 14, тел. 40-93-72.
39
Документ
Категория
Без категории
Просмотров
3
Размер файла
487 Кб
Теги
решение, метод, стабилизацией, распределение, задача, ресурсов
1/--страниц
Пожаловаться на содержимое документа