ВУЗ: Омский государственный технический университет
Категория: Книга
Дисциплина: Методы оптимальных решений
Добавлен: 12.02.2019
Просмотров: 13054
Скачиваний: 110
191
Теорема 8.4. Матрица
A
приводима тогда и только тогда, когда по крайней ме-
ре один из главных миноров порядка
1
n
−
матрицы
(
)
max
I A
λ
−
равен нулю.
Теорема 8.5. Если
A
– неотрицательная неприводимая матрица порядка
n
, то
(
)
1
0
n
I A
−
+
>
.
(Это говорит о том, что если граф – сильно связный и добавить петли к каждой
вершине, то результирующая матрица будет примитивной, т. е. любая вершина бу-
дет достижима из любой другой вершины посредством пути фиксированной длины.)
Теорема 8.6. Сильно связный граф (с
2
h
≥
вершинами) с матрицей вершин
A
примитивен тогда и только тогда, когда наибольший общий делитель длин всех про-
стых контуров есть единица.
Теорема 8.7. Примитивная стохастическая (по столбцам) матрица
A
обладает
свойством:
lim
k
A
имеет одинаковые столбцы (единственный вектор равновесной
вероятности) и, следовательно,
A
ω
ω
=
имеет единственное решение; кроме того,
для любого начального вектора вероятности
( )
( )
( )
(
)
0
0
0
0,
1
i
i
ω
ω
ω
≥
=
∑
,
( )
0
k
A
ω
ω
→
.
Это ключевая теорема для вычисления приоритетов, когда матрица примитивна.
Суперматрица иерархии имеет следующую форму:
21
32
1,
2
,
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
n
n
n n
W
W
W
W
W
I
−
−
−
=
…
…
…
…
…
…
…
… … …
…
…
…
…
… … …
…
…
…
…
… … …
…
…
…
…
.
Эта матрица имеет устойчивую форму
,
1
1,
2
32
21
,
1
1,
2
32
,
1
1,
2
,
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
k
n n
n
n
n n
n
n
n n
n
n
n n
W
W
W
W W
W
W
W
W
W
W
I
−
−
−
−
−
−
−
−
−
−
=
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
…
для всех
1
k n
≥ −
. Каждый коэффициент в последней строке является общим при-
оритетом влияния последней компоненты на каждую из оставшихся компонент. За-
метим, что принцип иерархической композиции проявляется в позиции
( )
,1
n
как
влияние
n
-й компоненты на первую;
n
-я компонента – ведущая в иерархии и явля-
ется аналогом поглощающего состояния в марковской цепи. Это компонента элемен-
тов, которые рассредоточиваются и являются источником влияния. Сущность выше-
сказанного подытоживается принципом иерархической композиции:
Обобщенный вектор
n
-уровневой иерархии есть элемент
( )
,1
n
матрицы
1
k
W
−
,
1
k n
≥ −
.
192
Теперь кратко рассмотрим, что происходит с контурами. Здесь повторяющиеся
степени обычного множества компонент показывают отсутствие устойчивости. На-
пример, для трехкомпонентного контура имеем
12
23
31
0
0
0
0
0
0
W
W
W
W
=
;
12
23
2
23
31
31
12
0
0
0
0
0
0
W W
W
W W
W W
=
;
12
23
31
3
23
31
12
31
12
23
0
0
0
0
0
0
W W W
W
W W W
W W W
=
;
(
)
(
)
(
)
12
23
31
3
23
31
12
31
12
23
0
0
0
0
0
0
k
k
k
k
W W W
W
W W W
W W W
=
;
(
)
(
)
(
)
12
23
31
12
3
1
23
31
12
23
31
12
23
31
0
0
0
0
0
0
k
k
k
k
W W W
W
W
W W W
W
W W W
W
+
=
;
(
)
(
)
(
)
12
23
31
12
23
3
2
23
31
12
23
31
31
12
23
31
12
0
0
0
0
0
0
k
k
k
k
W W W
W W
W
W W W
W W
W W W
W W
+
=
.
Так как произведение стохастических матриц есть стохастическая матрица, а
предел степеней стохастической матрицы, элементы которой положительны, есть
матрица с одинаковыми столбцами, умножение этой предельной матрицы справа на
любую стохастическую матрицу оставляет ее неизменной. В результате для контура
получим, что в пределе по различным последовательностям степеней
W
влияние
каждой компоненты на каждую другую компоненту (включая саму эту компоненту)
описывается одним и тем же выражением, т. е. ее предельным приоритетом по от-
ношению к соседней компоненте.
Начиная с
i
-й компоненты контура, мы индексируем соседние компоненты по-
следовательно
1
2
, , ,
, ,
n
i i i
i i
…
. Следующий вывод согласуется с нашими интуитивны-
ми ожиданиями.
В простом контуре компонент предельный относительный приоритет
i
-й компо-
ненты дается собственным вектором, который получается как решение задачи
1
ii
W x x
=
. Чтобы показать это, нужно учесть предыдущее замечание, сделанное при
оценке влияния
i
-й компоненты (не принимая во внимание стохастические матрицы
справа, так как они не влияют на результат),
(
)
1
1 2
1
1 2
1
lim
lim
lim
n
n
k
k
k
k
k
ii
i i
i i
ii
i i
i i
ii
k
k
k
W W
W
W W
W
W
→∞
→∞
→∞
=
=
…
…
.
Это – стохастическая матрица с одинаковыми столбцами. Следовательно, в пре-
деле приоритет компоненты в контуре дается собственным вектором, который соот-
ветствует наибольшему собственному значению (равному единице для стохастиче-
ской матрицы) его матрицы влияния.
193
8.5. ОТНОСИТЕЛЬНЫЕ И АБСОЛЮТНЫЕ ПРИОРИТЕТЫ
Нас интересуют приоритеты двух типов: показывающие влияние или воздейст-
вие одного элемента на любой другой элемент в системе, известные как относитель-
ные приоритеты, а также абсолютный приоритет любого элемента безотносительно
того, на какие элементы он влияет. В общем случае мы ищем предельные значения
этих приоритетов. Вычисление приоритетов показывает, к чему могут привести су-
ществующие тенденции, если нет изменений в предпочтениях, которые влияют на
приоритеты. Экспериментируя с процессом модификации приоритетов и наблюдая
за их предельными тенденциями, можно направлять систему к более желаемому ре-
зультату.
Теперь займемся формальными определениями. Если
ij
ω
– относительный при-
оритет
i
-го элемента над
j
-м элементом в системе, тогда [38, 70, 120]
( )
1
ij
ij
ω
ω
=
,
( )
2
ij
im
mj
m
ω
ω ω
=
∑
,
(
)
( )
1
k
k
ij
im
mj
m
ω
ω ω
+
=
∑
,
(
)
( )
( )
h k
h
k
ij
im
mj
m
ω
ω
ω
+
=
=
∑
.
Сумма относительных приоритетов по всем возможным путям от данного элемен-
та дает приоритет элемента. Это равносильно возведению матрицы
W
в степени.
(Последнее выражение эквивалентно следующему
h k
h
k
W
W W
+
=
.)
При заданном начальном приоритете
i
-го элемента, равном
( )
0
i
ω
, имеем следую-
щий абсолютный приоритет
j
-го элемента по путям длины
0
k
≠
:
( )
( ) ( )
0
k
k
j
i
ij
i
ω
ω ω
=
∑
.
Задача заключается в нахождении матрицы предельного относительного приори-
тета (ПОП)
W
∞
и вектора предельного абсолютного приоритета (ПАП)
ω
∞
при
k
→ ∞
. (Что касается приоритетов системы, нас также может интересовать опреде-
ление приоритетов для конечных значений
k
. Это не выдвигает задачи существова-
ния, возникающей в предельном случае.) Особый интерес вызывает определение
условий, когда ПАП не зависит от начальных приоритетов
( )
0
i
ω
. Такая независимость
называется эргодичностью системы.
Далее следует классификация элементов, полезная для характеристики системы.
Читатель при желании может продолжить обсуждение существования и построения
ПОП и ПАП решений.
Элемент
j
может быть достигнут из элемента
i
, если для некоторого
1
k
≥
,
( )
0
k
ij
ω
>
, где
( )
( )
k
k
ij
W
ω
=
. Здесь
k
W
—
k
-предел достижимости каждого элемента.
Подмножество элементов
C
системы замкнуто (в противоположность определению в
марковских цепях), если
( )
0
k
ij
ω
=
, где бы ни было
i
в
C
и
j
не в
C
. Отсюда следу-
ет, что ни один элемент в
C
не может быть достигнут из любого элемента, не нахо-
дящегося в
C
. Подмножество
C
минимально, если оно не содержит соответствую-
щих замкнутых подмножеств элементов. Множество элементов, которые образуют
минимальное замкнутое подмножество, соответствует неприводимой матрице. Если
194
матрица всей системы или подсистемы неприводима, то система или подсистема са-
ма называется неприводимой. Система называется разложимой, если она состоит из
двух или более замкнутых множеств.
Если мы вначале стартуем с
j
-го элемента для некоторого фиксированного
j
и
обозначим его первое воздействие на самого себя по пути длины
1
k
≥
через
k
j
f
, то
имеем
( )
( )
( )
( )
( ) ( )
( )
( )
( ) (
)
(
) ( )
1
1
2
2
1
1
1
1
1
1
,
k
k
k
k
j
jj
j
jj
j
jj
j
jj
j
jj
j
jj
f
f
f
f
f
f
ω
ω
ω
ω
ω
ω
−
−
=
=
−
=
−
− −
…
…
( )
1
k
j
j
k
f
f
∞
=
=
=
∑
показывает совокупное воздействие
j
на себя. Среднее воздействие (
j
на себя)
получаем в виде:
( )
0
k
j
j
k
u
kf
∞
=
=
∑
.
В соответствии с приоритетом влияния имеем (новые термины, вводимые ниже,
существенны, так как мы не занимаемся временными переходами):
1. Если
1
j
f
=
, то
j
называют устойчивым (рекуррентным) элементом. Таким об-
разом, элемент называется устойчивым, если сумма его относительных приоритетов
на себя за один шаг (петля), два шага (по контуру, включающему один другой эле-
мент), три шага (включающими два других элемента) и т. д., равна единице.
2. Если
1
j
f
<
, то
j
называют неустойчивым (преходящим). Элемент
j
, который
является или устойчивым, или неустойчивым, называется циклическим (периодиче-
ским) с цикличностью (периодом)
c
, если
j
u
имеет величины
c
,
2
c
,
3
c
, …, где
c
–
наибольшее целое, большее единицы, с этим свойством (
( )
0
k
ij
ω
=
, где
k
не делится
без остатка на
c
). Устойчивый элемент
j
, для которого
j
u
бесконечно, называют
исчезающим (нулевым). Устойчивый элемент
j
, который не является ни цикличе-
ским, ни исчезающим (т. е.
j
u
< ∞
), называют поддерживающим (эргодическим).
И для неустойчивого, и для исчезающего элемента
j
( )
0
k
ij
ω
→
для всех
i
. Если
один элемент в неприводимой подсистеме – циклический с периодом
c
, то все эле-
менты в этой подсистеме – циклические с периодом
c
. Известно, что если
j
– под-
держивающий элемент, то при
k
→ ∞
,
( )
1
k
jj
j
u
ω
→
;
j
– исчезающий элемент, если
это число ноль, и поддерживающий элемент, если оно положительно. Все элементы
неприводимой подсистемы являются либо неустойчивыми, либо устойчивыми, и со-
ответственно система называется неустойчивой или устойчивой.
1,
,
0,
.
ij
если i зависит от j
b
в противном случае
=
Замечание. Следующее выражение всегда имеет место, независимо от того, при-
водима система или нет. В случае неприводимости ее значения известны:
( )
1
0
1,
,
lim
1
,
.
m
k
ij
m
k
j
если i и j неустойчивы
u если i и j устойчивы
ω
−
→∞
=
=
∑
Все конечные системы элементов должны иметь, по крайней мере, один поддер-
живающий элемент, который образует замкнутое неприводимое подмножество эле-
ментов. Так как все устойчивые элементы конечной системы являются поддержи-
195
вающими, образованный таким образом блок (компонента) называют поддержи-
вающим.
Если
j
– циклический элемент с периодом
1
c
>
, то
если
k
не является множителем
c
и
( )
m
jj
j
c u
ω
→
,
при
m
→ ∞
;
k mc
=
,
m
– положительно и
c
– наибольшее целое, для которого
k mc
=
.
Ранее отмечалось, что приводимость и примитивность играют важную роль при
доказательстве существования ПОП и ПАП. Теперь представим несколько основных,
относящихся к этим понятиям фактов, которые будут полезны при дальнейшем об-
суждении.
Неотрицательная неприводимая матрица примитивна, если имеет единственное
главное собственное значение. Если матрица имеет другое собственное значение с
тем же модулем, что и главное собственное значение, то ее называют импри-
митивной.
Если главное собственное значение имеет кратность больше единицы (равную
единице), но не имеется других собственных значений с таким же модулем, как у
главного собственного значения, то матрицу называют правильной (регулярной).
Примитивная матрица всегда регулярна и, следовательно, правильна, однако об-
ратное утверждение неверно, например, что единичная матрица имеет собственным
значением единицу. Кратность собственного значения равна порядку матрицы. Мат-
рица правильна тогда и только тогда, когда в нормальной форме изолированные
блоки примитивны. Для регулярной матрицы число изолированных блоков равно
единице.
Заметим, что если все элементы
W
положительны, то мы имеем примитивную
матрицу и справедлива теорема о стохастических примитивных матрицах, сущест-
вуют и ПОП и ПАП. Они совпадают и получаются в результате решения задачи о
собственном значении
W
ω ω
=
. В действительности
ω
– любой столбец
lim
k
W
. Та-
кой же результат справедлив, если
W
– примитивная матрица.
В общем случае неотрицательная матрица
W
может иметь нулевые элементы.
Тогда матрица или неприводимая, или приводимая. Если она неприводимая, то она
примитивная, и в этом случае применимы приведенные выше соображения, либо
она импримитивная. В последнем случае матрица имеет
s
не равных единице собст-
венных значений (
s
называется индексом импримитивности), модули которых рав-
ны единице. Это число играет важную роль для получения решения в общем случае,
из которого следует решение в данном случае. Здесь достаточно заметить, что все
2
1
,
,
,
s
W W
W
−
…
не являются правильными матрицами, и их степени имеют тенден-
цию к периодическим повторениям. Система циклична с периодом
s
.
Замечание. Система ациклична, циклична, неприводима, приводима в зависимо-
сти от того, является ли соответствующая матрица
W
примитивной, импримитивной,
неприводимой или приводимой.
Если
W
неотрицательна и приводима, то она приводится к нормальной форме.
Если изолированные блоки примитивны (говорят, что они соответствуют существен-
ным компонентам, а оставшиеся матрицы соответствуют несущественным компонен-
там), то система по определению называется примитивной и ПОП и ПАП существуют
(см. [53], стр. 112).
Важное замечание. Когда стохастическая по столбцам матрица приводима, ее
существенные компоненты определяют систему, так как они являются «источника-
ми», или воздействующими на приоритет компонентами, в противоположность
«сточным колодцам», или переходным – поглощающим состояниям марковской це-