назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [ 51 ] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


51

(мы заменили tu ..., tp на tu .... tm, s4, sn). В покомпонентной записи это равносильна

Jjtja(h /)+ 2*-0.

j=i z=i

Второе слагаемое слева равно st, так что можно написать

(16:7) Sa(i, -5,.

Если бы имело место 2 tj" 0, то были бы справедливы равенства f4 -

= ...=-0и, следовательно, из (16:7) вытекало бы, что s4 - . . . = 5Л=0.

Это, однако, противоречит (16:6). Следовательно, 2/>0- Заменим

равенство (16:7) его следствием

(16:8) 2а(£, j)tj0.

т i т

Положим теперь Xj= tjl 2 tj Для 7 = 1» • • •» Тогда мы получим 2 #7 = 1»

j=l i=l

и (16:5) дает нам #42г0, #mi0. Следовательно,

(16:9) х = {хи . . ., л:т}6т,

и (16:8) приводит к условию

(16:10) J\a(i9j)xj0 для / = 1, п.

Рассмотрим, с другой стороны, случай, когда С не содержит 0. Теорема (16:В) из п. 16.3 позволяет нам сделать вывод о существо-

вании такой содержащей у гиперплоскости (см. (16:2:а) из п. 16.2.1), что множество С содержится в полупространстве, порожденном этой гиперплоскостью (см. (16:2:Ь) из п. 16.2.1). Обозначим эту гиперплоскость через

2 dtXi = ъ.

Поскольку 0 принадлежит ей, то 6 = 0. Таким образом, рассматриваемое полупространство имеет вид

(16:11) 2>0.

-»• ->•-» ->

Векторы х1, хт, б1, бп принадлежит этому полупространству.

При записи этого факта для 6* неравенство (16:11) принимает вид

2а*г>0, т. е. ai>0. Таким образом, мы получаем г=1

(16:12) а4>0, ап>0.



§ 16]

ЛИНЕЙНОСТЬ и выпуклость

При аналогичной записи для xJ мы получаем

(16:13) 2а(*, /)а.>0.

Положим теперь Wiaijat для £=1, п. Тогда мы получаем

2 м>$ = 1, и (16:12) дает нам м;1>0, . . ., ы>0.

Следовательно,

->

(16:14) = {1!, Wn}£Sn.

Неравенство (16:13) дает нам

(16:15) a(U ])u>i>0 для / = 1, ..., т.

Объединяя соотношения (16:9), (16:10), (16:14), (16:15), мы можем утверждать следующее:

(16:С) Пусть задана прямоугольная матрица с т столбцами и п стро-

ками. Обозначим элементы этой матрицы через а (&, /), i = = 1, . . ., п; 7 = 1, . . иг. Тогда либо существует такой вектор

х = {а?!, . . ., хт) е Sm, что

(16:16:а) 2 а (*> /) ж7 = 0 Для * = 1> • • •» п,

либо такой вектор w = {и, . . ., £ £л, что

(16:16:b) 2a(*» j)wi>0 для / = 1, «г.

Заметим, далее, следующее:

Альтернативы (16:16:а) и (16:6:Ь) исключают друг друга.

Доказательство. Предположим, что (16:6:а) и (16:16:Ь) имеют место одновременно. Умножим каждое из неравенств (16:6:а) на u?i и просуммируем по всем i = 1, . . ., п; это дает нам

п т

2 2а (*"» /) = о.

i=l j=l

Умножим, далее, каждое из неравенств (16:16:Ь) на xt и просуммируем по / = 1, т; это дает нам

п т

2 2*(*i О1).

г=1 j=l

Таким образом, мы получаем противоречие.

16.4.2. Заменим матрицу a (i, j) отрицательно транспонированной к ней матрицей; это значит, что мы обозначим столбцы (а не строки,

*) Здесь >0, а не просто > 0. Действительно, из =0 мы получили бы xt = . . . =

= хт - 0, что невозможно, так как 2 xi - !•



как раньше) через i = 1, . . ., п и строки (а не столбцы, как раньше) через f*= 1, . . ., т. Пусть, далее, элементами матрицы будут - а (£, ;) (а не а (£, /), как раньше). (Таким образом, числа пит также поменялись ролями.)

Сформулируем окончательный результат п. 16.4.1 для новой матрицы

в терминах первоначальной матрицы. Пусть при этом х = {xiy . . ., хт}

t -> ->

играет роль w = {wl9 . . ., wn}, a w = {wv . . ., wn} играет роль

X - {#1? * * * #7n}*

Мы получим следующее:

(16:D) Пусть прямоугольная матрица с п строками и т столбцами

задана. Обозначим элементы этой матрицы через а(£, /), i = 1, п,

/ = 1, . . ., т. Тогда либо существует вектор х = {х[, . .., хт) £ Sm,

для которого выполняется

(16:17:а) 2 a(i, j) х-<0, i = l, л,

либо существует вектор м? = {, wn}£Sn, для которого выполняется

(16:17:Ь) 2 /)0.

Эти две альтернативы исключают одна другую.

16.4.3. Объединим результаты пп. 16.4.1 и 16.4.2. Из них следует,

что выполняются либо (16:17:а), либо (16:16:Ь), либо, наконец, (16:16:а)

и (16:17:Ь) одновременно; эти три возможности исключают друг друга.

->->->• ->

Используя ту же самую матрицу a(i, j) и переобозначая х, ш, xf, w из пп. 16.4.1, 16.4.2 через х, w, х, и?, мы получаем следующее:

(16:Е) Либо существует вектор x = {xi9 xm}£Sm, для которого

(16:18:а) a(i, j) xj<.0 Для i=l, п,

либо вектор w - {wu wn}£Sn, Для которого

(16:18:Ь) 2 a(U ])т<0 для 7 = 1, т,

-> ->

либо два вектора: жг = {, a:m}m и w = {wv WnJgiSn, для которых

2 л (i, у) xj 0 для i = l, . . ., /г,

(16:18:с)

2 а (г, у) 0 для 7 = 1, ..., т.

Три альтернативы (16:18:а), (16:18:Ь) и (16:18:с) исключают друг друга.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [ 51 ] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]