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


[Старт] [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]


126

(45:1) Соотношение

(45:12). \W = \[jD*(e0)

устанавливает взаимно однозначное соответствие между всеми решениями V для Е (е0) и всеми решениями W для F(eQ).

Это утверждение будет доказано в следующем пункте.

45.5. Доказательство теоремы

45.5.1. Мы начнем с доказательства некоторых вспомогательных лемм.

Первая лемма состоит в совершенно очевидном утверждении, имеющем, однако, широкие приложения:

-У ~>

(45: J) Пусть два обобщенных дележа у = {у4, ..., уп} и б = {б1? ..., дп}

связаны соотношением

(45:13) yt}>di для всех £ = 1, ...,тг;

тогда для каждого а из а в-у следует as-б. Смысл этого результата состоит, очевидно, в том, что соотношение

-У ->

(45:13) выражает в некотором смысле подчиненность дележа б дележу уу несмотря на нетранзитивность отношения доминирования. Однако эта подчиненность не столь полна, как этого можно было бы ожидать. Так,

из соотношения 6 £- (3 нельзя сделать представляющийся правдоподобным

вывод о том, что у £- р, потому что из эффективности множества S для б

->

может и не следовать его эффективность для 7. (Читатель должен вспомнить основные определения п. 30.1.1.)

Нужно также заметить, что утверждение (45:J) является содержательным только потому, что мы обобщили понятие дележа. Для наших

старых определений (см. п. 42.4.1) мы должны были бы иметь =

i=l i=l

следовательно, из угЬг для всех i = 1, . . ., п должно было быть

-у ->

уг = 8j при всех i = 1, . . ., п, т. е. 7 = б.

45.5.2. Приведем теперь леммы, непосредственно осуществляющие требуемое доказательство теоремы (45:1).

->->-> ->

(45:К) Если а е- р, где a - исключенный дележ, a £ F (е0),

->->-> а р £ Е (е0), то существует дележ а, для которого а £- р, причем

а - исключенный дележ и а 6 Е (е0).

Доказательство. Пусть S - множество, участвующее в условиях (30:4:а) - (30:4:с) из п. 30.1.1 применительно к отношению

-У -У

доминирования a е- р. Из равенства S = I следовало бы, что для всех i = 1, . . ., п аг > рь так что

Sa,-v(/)>S pi-v(I).



Но так как а £ F (е0), a р f£ (е0), должно быть 2а* - v (-0 = ео =

- 2Рг ~ v 00» что противоречит предыдущему неравенству.

Следовательно, S Ф I. Выберем поэтому некоторое i0 = 1, . . ., п, не принадлежащее S. Положим ее = {av . . ., ап}, где

а\ = аг- для г =5= t0»

a 80 выбрано так, что ]а[ - v (/) = е0- Тогда для всех г будет

а\ аг-; следовательно, дележ а является исключенным и, очевидно, принадлежит Е (е0). Кроме того, так как ai = at для i Ф i0, а значит,

и для всех i £ S, то а е- Р влечет а е- р.

(45:L) Каждое решение W для F (е0) имеет вид (45:12) из теоремы

(45:1) для единственного множества V Е (е0) *).

Доказательство. Очевидно, рассматриваемое множество V, если оно вообще существует, есть пересечение MV [] Е (е0), так что оно единственно. Для того чтобы соотношение (45:12) выполнялось для

Y = Wr)E(e0)4

нам необходимо только, чтобы остаток W был равен D*(e0), т. е. чтобы (45:14) W-E(e0) = D*(e0).

Докажем поэтому равенство (45:14).

Каждый элемент множества D* (е0) является исключенным и принадлежит F (е0), так что ввиду (45: G) он принадлежит W. Кроме того, он не принадлежит Е (е0), так что он принадлежит W - Е (е0). Таким образом,

(45:15) W-£WI)*W.

Если, кроме того, (45:16) W-E(e0)<=D*(e0),

то (45:15) и (45:16) вместе дадут нам (45:14), что и требуется. Предположим поэтому, что включение (45:16) неверно. В соответствии с этим предположением мы рассмотрим дележ

а = {(*!, . . ., ап}, принадлежащий W - Е (е0) и не принадлежащий

D* (е0). Тогда а принадлежит F (е0), но не принадлежит Е (е0), так что

- v (/) < е0. Так как дележ а не принадлежит D* (е0), он не может

быть исключенным. Поэтому существует такое непустое множество S, что 2<*г < v (S).

i£S

*) Мы еще не утверждаем, что это множество V есть решение для Е (е0),- это будет установлено в (45:М).



Положим теперь а = {а, . . ., ап}, где

а1 = аг-{-г для i, принадлежащих S, al = аг для г, не принадлежащих S, а 8>0 выбрано так, что все еще

2сц-у(/)е0 и Saiv(5).

г=1 i£S

Такой дележ а принадлежит F (е0). Если он не принадлежит W,

то (так как W есть решение для F (е0)) существует такой дележ Р £ W,

-> ->

что Р е- а. Так как для всех i оца*, отсюда следует ввиду (45:J), что

р е- а. Но это невозможно, так как и р, и а принадлежат решению W.

Следовательно, дележ а должен принадлежать W. Но для всех i £ S а[ >

>06jH 2aiv()- Поэтому а е- а. Но это отношение противоречит тому,

что оба дележа, а и а, принадлежат решению W.

(45:М) Множество V из леммы (45:L) есть решение для Е (е0).

Доказательство. Очевидно, что V Е (е0) и V удовлетворяет условию (44:Е:а) из п. 44.7.3 вместе с W (которое является решением для F (е0)), так как V W. Таким образом, нам необходимо только проверить свойство (44:Е:Ь) из п. 44.7.3.

Рассмотрим дележ р £ Е (е0), не принадлежащий V. Тогда Р принадлежит и F (е0), но не принадлежит W; следовательно, существует такой ->->-> ->

дележ а £ W, что а е- р (W есть решение для F (е0)). Если этот дележ а

->

принадлежит Е (е0), то он принадлежит W [}Е (е0) = V, т. е. а должно

принадлежать Е (е0), причем а е- р.

Если же дележ а не принадлежит Е (е0), то он принадлежит W - Е (е0) = Z)* (е0) и, следовательно, является исключенным. Таким

образом, ос е- р, дележ а - исключенный и принадлежащий F (е0). Сле-довательно, ввиду (45:К) существует такой исключенный дележ а, принадлежащий Е (во), что а е- р. Ввиду (45:G) этот дележ а принадлежит W (так как Е (е0) <=- F (е0), a W есть решение для Е (е0)\); следовательно,

он принадлежит Wfl (о) = V. Таким образом, мы получаем, что -> -> ->

а £ Е (е0), причем а е- р.

Итак, условие (44:Е:Ь) из п. 44.7.3 выполнено в любом случае.

(45:N) Если V есть решение для Е (е0), то W, определенное соот-

ношением (45:12) теоремы (45:1), есть решение для F (е0).

Доказательство. Очевидночто W F (е0), так что мы должны доказать свойства (44:Е:а) и (44:Е:Ь) из п. 44.7.3.

Свойство (44:Е:а). Предположим, что для двух дележей а и р из W

имеет место а е- р. Ввиду отношения а е- р и свойства (45:D) невозможно,

чтобы дележ Р был исключенным. Поэтому р не содержится в D* (е0)

[Старт] [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]