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


[Старт] [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] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [ 267 ] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


267

Z-Уу = У) > 0 для всех J-

Эти уравнения, именуемые условиями ортогональности и нормировки, определяют единственное решение для yj при условии, что все уравнения независимы и п + 1 = N. Задача усложняется при N > п + 1, так как в этом случае решение для I/. не является единственным. Ниже показано, что и в этом случае существует возможность однозначно определить у. для минимизации функции z.

Пусть yj - элементы единственного решения представленной выше системы

уравнений. Тогда величины г* и х], i = 1, 2,п , определяются следующим образом. Рассмотрим величину

Поскольку Z* = -г , то

П Пс)"

В последнем выражении учтено условие X"-iav-vj = • Следовательно, значение г" можно вычислить, как только будут определены все уг При известных у] я z можно определить U] = у*г* Значения х] находятся как решение системы уравнений

Рассмотренная процедура показывает, что исходная задача минимизации позино-ма z может быть сведена к решению системы линейных уравнений относительно у. При этом значения всех у* определяются из необходимых условий существования

минимума. Можно показать, что эти условия являются также и достаточными. Доказательство этого приводится в книге [2].

Фактически переменные yt определяют двойственные переменные, соответствующие прямой задаче минимизации z. Чтобы установить эту зависимость, запишем целевую функцию прямой задачи в виде

Определим теперь функцию



Поскольку " ,у, = 1 и yj > О, в силу неравенства Коши1 имеем w<z.

Функция w с переменными ух, у2, yN определяет задачу, двойственную к исходной. Поскольку w является нижней границей значений z и рассматривается задача минимизации г, то, максимизируя функцию w, мы получим

w = max w = min z = z

У) *:

Это значит, что максимальное значение w (= w ) на множестве допустимых значений г/, совпадает с минимальным значением z (= z") на множестве допустимых значений xt.

Пример 21.2.4

В этом примере рассматривается задача, где N = п + 1, так что решение, получаемое из условий ортогональности и нормировки, является единственным. (Следующий пример иллюстрирует случай, когда N > п + 1.)

Рассмотрим задачу

минимизировать z = 7х,х; + 3x,xf + 5х~3х,х3 + х,х,х3.

Эту функцию можно записать в виде

z = 7х!х,-х" + 3x°xU2 + 5х73х\х\ + х\х\х\,

так что здесь

(с,, с2, с3, ct) = (7, 3, 5, 1), а,, а,, а,3 а14 Г 1 0-3 Г

а,. а„ а,, а,.

-1111 0-211

чя3, а,, а33 а,4/

Условия ортогональности и нормировки приводят к системе уравнений

-3 Г

1 1

1 1

ч 1

Эта система имеет единственное решение

.1.1

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

>

= 15,23.

1 Неравенство Коши (неравенство между средним арифметическим и средним геометрическим) устанавливает, что при Zj > 0 выполняется J,%Zy - Г1"-гу" Где "О > и Xjiy = •



Пример 21.2.5

Рассмотрим задачу

минимизировать г = 5.v,.v, + 2.v, .v, + 5.v, + .vj1. Условия ортогональности и нормировки приводят к системе уравнений

1-11 0 1 10-1 1 11 1

Уз 04

Поскольку N > п + 1, эти уравнения не позволяют непосредственно определить искомые значения у/. Выражая уи у2 и у, через у4, имеем

-1 п

f-vl

0 1

1 0

1 V,

1 -

1 b

У-у,,

V, =-

I - 3 \-

Двойственную задачу можно записать в следующем виде.

Максимизировать iv =

-.0.5(1 3..I

0,5(1-Зу4)

0.5(1- у4)

Из уравнения U) = y)z следует, что

7,v,.v, = (/, =-(15,23) = 7,615,

3.v,jc,2 ={/, =-(15,23) = 2,538,

5л,3хЛ=(/3=(15.23) = 3,173,

.v,.v:.v, = U4 = -(15.23) = 1,904. 8

Эта система имеет решение =1,316, л* =1,21, .vj =1,2, которое является оптимальным решением прямой задачи.

[Старт] [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] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [ 267 ] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]