close

Вход

Забыли?

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

?

Жесткостные структуры матриц.

код для вставкиСкачать
УДК 512.64,519.248:[57+61]
Вестник СПбГУ. Сер. 1, 2006, вып. 2
А. Г. Барт
ЖЕСТКОСТНЫЕ СТРУКТУРЫ МАТРИЦ
В различных разделах математики и ее приложений, связанных с частичным упорядочиванием рассматриваемых объектов, мы сталкиваемся с анализом систем линейных
неравенств. Наиболее существенным вопросом здесь является определение размерности пространства, в котором находятся решения системы. Она определяется размерами
жесткой подсистемы системы линейных неравенств (для всех решений системы неравенства этой подсистемы выполняются как равенства). В отличие от классического
подхода [1], в данной работе указывается способ определения жесткостной структуры
системы неравенств на языке вводимых классов жесткости для матриц этой системы.
Такой подход позволяет сводить вопрос частичной упорядоченности данной системы к
анализу частичной упорядоченности ее подсистем. Эти вопросы имеют принципиальное значение для многих задач. Например, для таких, как статистическая проблема
классификации наблюдений, построение обобщенных обратных матриц [2], решение
различного рода экстремальных задач и т. д.
Следует сделать некоторые замечания к терминологии. А. У. Таккер делит неравенства линейной системы на жесткие и нежесткие [5]. С. Н. Черников нежесткие неравенства называет устойчивыми [1]. Мы примем разграничение неравенств: жесткие
(для всех решений системы неравенства выполняются как равенства) и устойчивые (существуют решения системы, обращающие их в строгие). Естественная двойственность
строк (горизонталей) и столбцов (вертикалей) матрицы в рассматриваемой далее основной системе неравенств соответствуют делению ограничений на функциональные
и координатные. Наконец, вводимые понятия доминантности и рецессивности заимствованы из генетики, где данный подход также представляется перспективным.
В дальнейшем полагаем: A(k, n) — матрица k × n, Nn — начальный отрезок натурального ряда длины n, 1n — единичная матрица порядка n. Греческими буквами будем обозначать подмножества индексов строк или столбцов матрицы. Так ν(l|n) =
[ν 1 , . . . , ν l ] — подмножества Nn , с элементами, упорядоченными по возрастанию. Через
(ν) обозначим дополнение ν до Nn . Само ν будем отмечать квадратными скобками [ν],
если есть необходимость подчеркивать его отличие от (ν). Например: [145] ∪ (145) =
[12345] = N5 . Через Aν (k, l), Aλ (l, n), Aνλ (l, , l) обозначим блоки матриц, соответствующие множествам индексов строк (нижний индекс) λ(l|r) и столбцов (верхний индекс)
ν(l|n). Размеры матриц могут быть не указаны, когда они очевидны из контекста.
Наконец, для всякой матрицы
A = A(k, n) и всякого l = 1 ÷ min(k, n) определим
ν
блочную матрицу A(l) = Aνλ , где λ = λ(l|k) — сочетания из элементов Nk по l в
λ
лексикографическом упорядочивании, соответствующие блок-строкам Aλ матрицы A,
а ν = ν(l|n) — такие же сочетания из элементов Nn по l, соответствующие ее блокстолбцам Aν . A(l) назовем матрицей l-ассоциированных блоков матрицы A по аналогии с l-ассоциированной матрицей, в которой вместо блоков берутся их определители.
1. Классы жесткости. Рассмотрим двойственные (по Таккеру, см. [5]) системы
однородных линейных неравенств
c
14
А. Г. Барт, 2006
Ax ≥ 0 x ≥ 0, y≥0
∗
A y≥0 ,
где матрица A = A(k, n), векторы x = x(n, 1), y = y(k, 1) и A∗ = −AT . Так как
эта система полностью определяется ее матрицей, будем говорить о жесткости или
устойчивости вертикалей и горизонталей матрицы A, отождествляя их с аналогичными
жесткостными свойствами соответственно координатных и некоординатных неравенств
указанной системы.
Определим для матриц классы жесткости:
Zq (k, n) = {A(k, n); q ее горизонталей жестко в A},
Z p (k, n) = {A(k, n); p ее вертикалей устойчиво в A},
Zqp (k, n) = Zq (k, n) ∩ Z p (k, n).
Свойство дополняющей нежескости двойственных систем неравенств для классов
матриц имеет вид
(1)
(Zqp (k, n))∗ = Zpq (n, k),
где индекс ∗ обозначает косое транспонирование: Z ∗ = {A∗ ; A ∈ Z}.
Существенную роль в дальнейшем играют классы для крайних случаев, в определении которых отражены граничные эффекты:
def
Z0 (k, n) = Z0n (k, n) = S(k, n),
def
Z 0 (k, n) = Zk0 (k, n) = R(k, n),
def
Zkn (k, n) = T (k, n).
Введение особых обозначений для этих классов связано с тем, что с точки зрения жесткостных свойств они, при k = n, являются матричными аналогами положительных (S),
отрицательных (R) чисел и нуля (T ). При этом оказывается, что «квадратный матричdef
ный нуль» неоднороден, так что следует определить Tl (n, n) = Zll (n, n); l = 1, . . . , n,
где l — порядок нуля. Пусть, например, A = −AT , тогда из (1) следует p = q = 0, т. е.
все кососимметрические матрицы принадлежат классам Tl .
Жесткостные свойства блоков могут проявляться в матрице доминантным и рецессивным образом. Доминантность свойства по указанному направлению означает его
инвариантность (сохранение) к расширению матрицы (присоединение произвольного блока) в этом направлении. Рецессивное свойство проявляется в матрице только
при условии, что этим свойством обладают все блоки соответствующей блочной
структуры матрицы.
Очевидно, что накладывание новых ограничений не может изменить жесткость
неравенств, так же как расширение пространства за счет увеличения его размерности
не влияет на устойчивость неравенств. Отcюда следует:
Свойство 1 (Доминантность по линиям). Для всякой матрицы A = A(k, n) и
всяких λ = λ(t|k) и ν = ν(l|n) выполнено: если Aλ ∈ Zt (t, n), то строки Aλ жестки в
A; если Aν ∈ Z l (k, l), то столбцы Aν устойчивы в A.
Свойство 2 (Рецессивность по линиям). Если в матрице A = A(k, n) при k ≤ n
для всякого сочетания ν = ν(k|n) Aν ∈ Zk (k, k), то A ∈ Zk (k, n). Если, при k ≥ n, для
всякого λ = λ(n|k) Aλ ∈ Z n (n, n), то A ∈ Z n (k, n).
15
Доказательство. Для первого утвержднения в свойстве 2 достаточно показать,
что если существует x0 ≥ 0 такое, что Ax0 ≥ 0, и для некоторого ω ⊂ Nk , Aω x0 > 0,
то найдется ν = ν(k|n), для которого Aν имеет устойчивые горизонтали. Пусть такое x0 существует. Тогда очевидно, что существует μ = μ(l|n), l = 0, для которого
x0μ > 0, x0(μ) = 0. Можно считать l минимальным. Если l > k, то система Aμ xμ = 0
имеет ненулевые решения. Отсюда следует, что конус {Aμω xμ ≥ 0; xμ ≥ 0}, имеющий,
очевидно, нулевое ядро и, по предположению, не пуст, должен иметь в качестве грани
конус с такими же свойствами, но в пространстве меньшей размерности. Это противоречит минимальности l. Таким образом, l ≤ k и, очевидно, что для всякого ν = ν(k|n),
содержащего μ, Aν имеет устойчивые строки. Двойственное утверждение следует
из (1).
Для матрицы A(l) полных блоков (l = min(k, n)) рассмотренные свойства означают,
что жесткость строк в блоках доминантна по вертикали и рецессивна по горизонтали, а
устойчивость столбцов доминантна по горизонтали и рецессивна по вертикали. В общем
случае (l ≤ min(k, n)) комбинация свойств 1 и 2 приводит к следующему их усилению.
Свойство 3. Если для λ = λ(l|k), 1 ≤ l ≤ min(k, n), все блоки в Aλ (l) принадлежат
классу Zl и при некотором ν = ν(l|n) Aνλ ∈ R, то строки Aλ жестки в A, а столбцы
Aν рецессивно жестки в A. Если для ν = ν(l|n) все блоки в Aν (l) принадлежат классу
Z l и для некоторого λ = λ(l|k) Aνλ ∈ S, то столбцы Aν устойчивы в A, а строки Aλ
рецессивно устойчивы в A.
Здесь рецессивная жесткость (устойчивость) линий матрицы означает, что указанное свойство линий имеет место в A при условии, что оно не нарушается ограничениями, задаваемыми всеми остальными блок-линиями в A.
Введенные классы жесткости лежат в основе следующего способа упорядочивания
блоков матрицы A.
Будем говорить, что блок-линия из A больше или равна нулю (меньше или равна
нулю), если все ее блоки принадлежат классу Z l (классу Zl ), и строго больше (строго
меньше) нуля, если все ее блоки из класса S (из R класса). Блок-линия равна нулю, если
все ее блоки принадлежат классу Tl . Блок-линии матрицы A, не удовлетворяющие
указанным свойствам, назовем несравнимыми с нулем или неупорядоченными.
Для сравнимых с нулем блок-линий сохраним в обозначениях те же знаки неравенств, что и для чисел. Например: Aν ≥ 0 или Aν ≤ 0. Свойство 3, описывающее
достаточные условия жесткости и устойчивости матрицы, позволяет в некоторых случаях решить полностью вопрос о ее жесткостной структуре, а в общем случае сократить
ее до матрицы, у которой все блок-линии всех размерностей не сравнимы с нулем. Назовем такую матрицу вполне неупорядоченной.
2. Вполне неупорядоченная матрица. Процедура знакового сокращения.
Относительно жесткостной структуры вполне неупорядоченная матрица устроена достаточно просто: она может принадлежать только крайним классам жесткости — S, R
или T . Конкретный тип класса зависит от соотношения знаков определителя матрицы
и алгебраических дополнений ее элементов. Основным здесь является геометрический
фактор: все гиперплоскости, соответствующие горизонталям такой матрицы, пересекаются в положительном квадранте x > 0, откуда следует, что элементы взаимной
матрицы (составленной из алгебраических дополнений) знакопостоянны.
Свойство 4. Если матрица A = A(k, n) вполне неупорядоченна, то
а) k = n;
б) A = A(k, k) принадлежит одному из классов: R, S или Tk .
16
Доказательство. Сначала отметим, что если для некоторого l, 1 ≤ l ≤ min(k, n),
существует ν = ν(l|n) такое, что система {Ax ≥ 0; x ≥ 0} имеет решение x0 вида
x0ν > 0; x0(ν) = 0, то Aν ≥ 0, ибо x0ν является решением системы {Aν xν ≥ 0; xν ≥ 0}, а
следовательно, и любой ее подсистемы, что означает Aνλ ∈ Z l для всякого λ(l|k).
Пусть k < n. Тогда из предыдущего замечания следует, что для всякого ν =
ν(k|n) Aν должно принадлежать R(k, k), т. е. Aν < 0. Это противоречит полной неупорядоченности матрицы A. Аналогично, предположение k > n противоречит полной
неупорядоченности матрицы A∗ . Так как матрицы A и A∗ вполне неупорядоченны
или не являются таковыми одновременно, k = n.
Из Aν (l) ≤ 0 и Aν (l) ≥ 0 для всяких l = 1 ÷ (k − 1) и ν = ν(l|n) следует, что
A, A∗ ∈ Zm при m = 0, k, то есть A ∈ Zqp , где p и q равны либо нулю, либо k.
Теорема 1. Если A = A(n, n) — вполне неупорядоченна, то для всякого λ = λ(l|n)
и всякого l = 1 ÷ (n − 1) система Aλ x = 0 имеет строго положительные решения.
Доказательство.
1. При l = 1 утверждение очевидно. Для всякого ω ⊂ λ обозначим через Xωc множество решений системы, обладающее свойством c (c = 0, 1):
Xω0 = {x = 0; Aω x = 0};
Xω1 = {x > 0;
Aω x = 0}.
Очевидно, что для всякого фиксированного t ≤ l и подмножеств вида ω = ω(t|l)
выполнено
Xωc .
(2)
Xλc =
ω⊂λ
Так как Xλ1 = ∅ (не пусто) влечет, по (2), Xω1 = ∅ для всяких t ≤ l и всяких ω =
ω(t|l) ⊂ λ, достаточно рассматривать случай l = n − 1.
2. Пусть для некоторого λ = λ(n − 1|n) система {Aλ x = 0} не имеет строго
положительных решений. Тогда существуют λ1 ; λ2 ∈ λ такие, что гиперплоскости
π1 = {Aλ1 x = 0} и π2 = {Aλ2 x = 0} не пересекаются в квадранте {x > 0}.
Действительно, из Aλ = Aλ (n−1, n) следует, что Xλ0 не пусто. Из (2) следует, что Xω0
не пусто для всяких ω ⊂ λ. Если же для всякого ω = ω(2|n) ⊂ λ; Xω0 ⊂ {x > 0}∪{x < 0},
то по (2) при t = 2 Xλ0 ⊂ {x > 0} ∪ {x < 0}, т. е. Xλ1 не пусто, что противоречит
предположению.
3. Из Aλ ≤ 0 следует, что существует ν = ν(n − 1|n) такое, что система {Aνλ xν ≥ 0}
имеет положительные (не обязательно строго) решения: x0ν ≥ 0, x0ν = 0. В частности,
этим свойством обладает подсистема {Aνω xν ≥ 0} при ω = [λ1 ; λ2 ], где λ1 и λ1 указаны
в пункте 2. Так как гиперплоскости π1 и π2 не пересекаются в квадранте {x > 0}, то
найдется μ = μ(n − 1|n) = ν, для которого система {Aμω xμ ≥ 0} также имеет положительные решения.
Покажем, что и вся система {Aμλ xμ ≥ 0} имеет положительные решения.
Действительно, если это не так, то существует t ∈ λ ∩ (ω), такое, что Aμt x1μ < 0
для некоторого положительного решения x1μ системы {Aμω xμ ≥ 0}. По предыдущему
ν 0
ν 0
существует x0ν ≥
= 0 такое, что At xν ≥ 0 и Aω xν ≥ 0. Следовательно, гиперплоскость πt =
{At x = 0} пересекается в положительном квадранте с π1 и π2 . Причем пространства
этих пересечений не содержат π1 ∩ π2 и их размерности не меньше n − 2.
Но гиперплоскости πt и πi (i = 1, 2) имеют ненулевые общие точки и на множестве
π1 ∩ π2 , ибо система {Aλ x = 0} имеет ненулевые решения. Отсюда следует, что πt
должна совпадать с каждой из гиперплоскостей π1 и π2 , а следовательно, и последние
17
совпадают друг с другом. Это противоречит утверждению пункта 2 о том, что система
{Aω x = 0} не имеет строго положительных решений.
1≥
4. Так как для всякого ν = ν(n−1|n) Aν ≥ 0, то для всяких решений x0ν ≥
= 0 и xμ = 0
μ
ν
систем {Aλ xν ≥ 0} и {Aλ xμ ≥ 0}, соответствующих ν и μ из пункта 3, должны выполняться Aν(λ) xν < 0 и Aμ(λ) xμ < 0. Откуда следует, что существует i ∈ λ, для которого
система {Ai x ≥ 0; A(λ) x ≥ 0; x ≥ 0} имеет только ненулевое решение. Последнее влечет, что для ω = [(λ); i] Aω < 0. Это противоречит полной неупорядоченности матрицы A.
Теорема 2. Если A = A(k, n) вполне неупорядоченна, то элементы взаимной матрицы Ā знакопостоянны и A принадлежит классам
R
Tn
S
при Δ = 0, āij Δ ≤ 0
при Δ = 0
при Δ = 0, āij Δ ≥ 0,
(i)
где āij = (−1)i+j Δij — алгебраическое дополнение элемента aij , Δij = det A(j) , Δ =
det A.
Доказательство.
1. Для всякого λ = λ(n−1|n) по теореме 1 существует строго положительное решение
x0 системы {Aλ x = 0}. Отcюда по тождеству Крамера
(i)
(j)
(−1)i |Aλ |x0i = (−1)j |Aλ |x0j ,
справедливому для всяких i, j = 1 ÷ n, получаем знакопостоянство элементов взаимной
матрицы по строкам. Аналогичное исследование матрицы A∗ влечет знакопостоянство
элементов матрицы Ā по столбцам. Следует также отметить, что матрица не имеет
нулевых линий, ибо иначе соответствующая блок-линия в A(n − 1) равна нулю.
2. Рассмотрим систему {Ax ≥ 0; x ≥ 0}. Пусть Δ = 0. Тогда для всякого j = 1 ÷ n
xj =
n
Δij
Ai x ≥ 0.
(−1)i+j
Δ
i=1
Если āij Δ ≤ 0, то xj = 0, откуда следует A ∈ R. Если āij Δ ≥ 0, то ā∗ij Δ∗ ≤ 0, ибо
detA∗ (n, n) = (−1)n detA(n, n) и предыдущие рассуждения влекут A∗ ∈ R. Наконец, по
(1) имеем A ∈ S.
Пусть Δ = 0, тогда для всякого j = 1 ÷ n справедливо тождество
n
(−1)i+j Δij Ai x = 0.
i=1
Причем, по пункту 1 для всякого i = 1 ÷ n существует j0 = j0 (i) такое, что Δij0 = 0,
следовательно
Δrj0
(−1)r+i
Ar x ≤ 0.
Ai x = −
Δij0
r=i
Отсюда для всякого i = 1÷n, Ai x = 0, т. е. A ∈ Zn . Проводя аналогичные рассуждения
для матрицы A∗ , получаем A∗ ∈ Zn . Таким образом, A ∈ Tn .
18
Следует отметить, что требование полной неупорядоченности матрицы в теореме 2,
как видно из доказательства, не является необходимым. Теорема остается верной, если матрица не упорядочена по доминантным линиям, т. е. в ней отсутствуют блокгоризонтали Aν ≤ 0 и блок-вертикали Aν ≥ 0.
На основании рассмотренных свойств можно указать следующую процедуру знакового сокращения матрицы для определения соответствующего ей класса жесткости.
В матрице A = A(k, n) вычеркиваются все линии (одномерные), сравнимые с нулем. При этом жесткостная структура доминантных линий устанавливается окончательно, а рецессивных линий отмечается условно, ибо она может измениться при дальнейшем анализе матрицы. Для сокращенной таким образом матрицы эта процедура
повторяется. Если знаковая структура одномерных линий не определяет полностью
жесткостную структуру матрицы A, то для сокращенной матрицы, последовательно
по l = 1, 2, . . . строим матрицы l-ассоциированных блоков, в которых блоки заменяем на соответствующие им классы жесткости. При наличии сравнимых с нулем блоклиний делаем вывод о типе их жесткости в исходной матрице. В силу теоремы 2 эта
процедура должна закончиться полным выяснением жесткостной структуры матрицы A.
3. Примеры применения процедуры знакового сокращения. 1. Сначала
рассмотрим простой пример для пояснения техники процедуры знакового сокращения
(ПЗС).
Так как нас интересуют только знаки чисел, будем положительные числа, независимо от их абсолютных значений, обозначать буквой s, отрицательные — буквой r, нуль —
t. Жесткие неравенства отмечаем знаком плюс, а свободные неравенства знаком минус
у соответствующей линии (столбец или строчка) матрицы.
Матрица
⎡
t
⎢ t
⎢
A=⎣
s
r
t
r
t
s
t
s
r
t
r
r
t
s
⎤
r
s ⎥
⎥
r ⎦
s
имеет первую строку, доминантно сравнимую с нулем, и по ПЗС ее можно вычеркнуть, наряду с четвертым и пятым столбцами, поставив этим линиям знак жесткости (+).
Очевидно, оставшаяся матрица (блок Aνλ , где λ = [234], ν = [123]) вполне неупорядоченна, так как все ее блок-линии порядка 2 также не сравнимы с нулем, как это
легко видеть по матрице
⎡
T1
Aνλ = ⎣ R
S
S
T1
R
⎤
R
S ⎦,
T1
в которой вместо блоков поставлены их классы жесткости. Следовательно, по теореме 2
блок Aνλ принадлежит одному из трех классов жесткости — либо S, либо R, либо T , в
зависимости от знака его определителя.
19
Получающиеся таким образом возможные варианты жесткостных структур для
матрицы A собраны в следующую схему:
1
2
3
4
r
t
s
1
t
t
s
r
+
−
−
2 3
t t
r s
t r
s t
+ +
− −
− −
4 5
r r
r s
t r
s s
+ +
+ +
+ +
r
+
+
+
+
R
t
+
+
+
+
Z43
s
+
−
−
.
−
Z13
Буквы r, s, t у строчек и столбцов из плюсов и минусов указывают на знак упомянутого определителя. Если, например, предположить, что оставшийся после ПЗС блок
кососимметричен, то, очевидно, его определитель равен нулю (буква t), и он принадлежит классу жесткости T3 . Таким образом, для всех решений системы Ax ≥ 0; x ≥ 0,
все четыре функциональных неравенства являютсятся равенствами, а последние две
координаты — нулевые: x4 = x5 = 0. Остальные коодинаты — свободные и матрица
принажлежит классу жесткости Z43 .
2. Второй пример относится к центральному утвкерждению теории статистических
решающих функций — лемме Неймана—Пирсона [4]. Ее результат получается непосредственно из свойства дополняющей нежесткости соответствующих двойственных систем
линейных неравенств. Этот факт, хорошо известен с 60-х годов ([6], [8]).
С точки зрения нашего метода, вопрос о виде оптимального правила в схеме выбора
из двух простых гипотез сводится к выяснению принадлежности жесткостному классу
определенной матрицы из плотностей исходных распределений.
Обозначим решающее правило в виде вектор-теста ψ T = [ψ1 , ψ2 ] = [ϕ, 1 − ϕ], где
ϕ(x) — критическая функция для простой гипотезы согласия с распределением fx против простой альтернативы gx . Функции fx и gx являются плотностями по σ-конечной
мере на пространстве выборок X . Двойственные экстремальные задачи в предположении ϕ ∈ L1 (X , μ) и f, g, v из класса L∞ (X , μ) (пространство μ-существенно ограниченных функций на X [7]) имеют следующий вид:
ϕgdμ → sup,
αt + vdμ → inf ,
ϕ
X
(t,vx )
X
ϕf dμ ≤ α,
t ≥ 0,
X
vx ≥ 0, tfx + vx ≥ gx .
0 ≤ ϕ ≤ 1,
Далее нагляднее рассматривать эти задачи в матричном виде, полагая указанные
функции вектор-столбцами (соответственно выделяя их полужирным шрифтом). Выбранная более компактная матричная форма записи хотя формально и предполагает
конечность указанных пространств, но принципиально сохраняет проблему построения
оптимального вектор-теста и в нашем случае.
Теперь, применяя стандартный метод симметризации Неймана в схеме линейного
программирования [5], приводим дуальные задачи к самодвойственной системе линейных неравенств {K0 z ≥ 0; z ≥ 0}, где
⎡
⎤
⎡
⎤
0
0
α −f T
t
⎢ 0
⎢ v ⎥
0 1x −1x ⎥
⎥;
⎥
K0 = ⎢
z=⎢
⎣ −α −1Tx
⎣ s ⎦.
0
gT ⎦
f
1x −g
0
ϕ
20
Здесь 1x — тождественный оператор на множестве X , а 1x константная функция, равная единице.
Разбиение X на области X (далее x принадлежит только X) и Y значений нерандомизированного правила ϕ влечет удвоение матрицы K0 , которая после перехода к
вектору ψ T = [ψ1 , ψ2 ] имеет вид матрицы K (соответственно изменяется структура вектора z). Здесь ψi — вероятности не попасть в i-ю область, i = 1, 2, (аналоги критических
функций):
⎡
⎡
⎤
⎤
0
0
0
δ −fxT
fyT
t
⎢ Vx
⎢
⎥
0
0
0
1x −1x
0 ⎥
⎢
⎢
⎥
⎥
⎢
⎢
⎥
⎥
0
0
0
1
0
−1
V
y
y ⎥
y
⎢
⎢
⎥.
z=⎢
K=⎢
T
T
T
T ⎥;
⎥
−δ
−1
−1
0
g
g
s
x
y
x
y ⎥
⎢
⎢
⎥
⎣ ψ1 (x) ⎦
⎣ fx
1x
0 −gx
0
0 ⎦
ψ2 (y)
−fy
0
1y −gy
0
0
Обозначим через ν множество из двух индексов строк матрицы K, соответствующих переменным t и s, а через ξ — множество, соответствующее переменным ψ1 и ψ2 .
Если разбиение оптимально (ψ1 , ψ2 — индикаторы множеств Y и X соответственно), то
все горизонтали в K, соответствующие этим множествам, устойчивы, а строки Kν —
жесткие. Таким образом, построение оптимального правила эквивалентно выяснению
условий, при которых K ∈ T2 . Для этого, ввиду кососимметричности матрицы K, необходимо и достаточно, чтобы Kν (2) — матрица ассоциированных с K блоков размера 2 —
была сравнима с нулем, более того, должно быть Kν (2) ≤ 0. Так как все вертикали в
Kν , соответствующие переменным t, Vx , Vy , сравнимы с нулем, то по ПЗС их можно вычеркнуть. При этом следует отметить, что используемое здесь свойство доминантности
по линиям не зависит от размерности пространств.
В итоге, оптимальное правило определяется следующими условиями:
−fxT
fyT
0 δ
∈ T2 ;
Kξν =
Kνν =
∈ R,
−δ 0
gxT −gyT
δ = α − fy dμ.
Y
Первое из этих условий возможно только при δ = 0. Второе, после применения ПЗС
и теоремы (2) указывает вид оптимального разбиения в канонической форме:
X = {x; Δxy < 0
для всяких y ∈ Y },
Y = {y; Δxy > 0 для всяких x ∈ X},
где
Δxy = det
−fx
gx
fy
−gy
.
Классический вид оптимального разбиения соответствует границе
k = inf
x
gx
.
fx
21
Summary
A. G. Bart. Non-slackness matrices structures.
Classes of non-slackness for matrices are introduced basing on the number of slack and nonslack inequalities in the system of linear inequalities set by a matrix. A procedure of signs reduction
(PSR) in the matrix blocks is constructed. For any matrix it permits to determine its native class
of non-slackness. The examples of PSR applications are also given.
Литература
1. Черников С. Н. Линейные неравенства. М.: Наука, 1968. 488 с.
2. Барт А. Г. Анализ медико-биологических систем. Метод частично-обратных функций.
2002. СПб.: Изд. С.-Петербургского Университета. 280 с.
3. Макарова Е. В., Денисов В. И., Полетаева И. А., Пономарев В. В. Дисперсионный анализ
и синтез планов на ЭВМ. М.: Наука, 1982. 195 с.
4. Леман Э. Проверка статистических гипотез. М.: Наука, 1964. 498 с.
5. Таккер А. У. Двойственные системы однородных линейных соотношений // Линейные
неравенства и смежные вопросы. М.: ИЛ, 1959. С. 127–141.
6. Witting H. Problems in Testing Statistical Hypotheses Viewed as Linear Programs // European Meeting of Statisticians. London, 1966.
7. Вершик А. М., Рубинов М. И. Общая теорема двойственности в линейном программировании // Математическая экономика и функциональный анализ. Наука, 1974. С. 35–55.
8. Темельт В. Двойственность бесконечномерных задач линейного программирования и
некоторые смежные вопросы // Кибернетика. Т. 4. 1969. С. 80–87.
Статья поступила в редакцию 16 февраля 2006 г.
22
Документ
Категория
Без категории
Просмотров
4
Размер файла
236 Кб
Теги
структура, матрица, жесткостных
1/--страниц
Пожаловаться на содержимое документа