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


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


253

Анализ чувствительности с помощью метода Якоби. Метод Якоби можно использовать для анализа чувствительности оптимального значения целевой функции / к малым изменениям правых частей ограничений оптимизационной задачи. В частности, можно определить, как повлияет на оптимальное значение функции / замена ограничения g,(X) = О на g,(X) = dgr Исследование такого типа именуется анализом чувствительности и в некотором смысле аналогично соответствующей процедуре, которая была рассмотрена в линейном программировании (глава 4). Следует однако заметить, что анализ чувствительности в нелинейном программировании приводит к результатам, справедливым лишь в малой окрестности экстремальной точки. Знакомство с такими процедурами будет полезно при изучении метода множителей Лагранжа.

Выше было показано, что

a/(Y, z> = vY/dY + vz/az,

dg = JdY + CdZ.

Предположим, что dg * 0, тогда

бт = jag-J"c az.

Подставляя последнее выражение в уравнение для o/(Y, Z), получаем

o/(Y,z) = vY/i-ag+vc/az,

где Vc/ = VZ./ -VY/J~C, как было определено ранее. Полученное выражение для 5/(Y, Z) можно использовать при анализе изменений целевой функции f в малой окрестности допустимой точки Х°, обусловленных малыми изменениями dg и 5Z.

В экстремальной (фактически любой стационарной) точке Х0 = (Y0, Z0) приведенный градиент Vc/ должен быть равен нулю. Следовательно, в точке Х0 имеем

5/(Y0,Z0) = VYn/J-5g(Y0,Z0)

dg YJ

вычисленному в точке Х0. Это значит, что влияние малых изменений dg на оптимальное значение функции / можно оценить через скорость изменения функции / по отношению к изменениям g. Эти величины принято называть коэффициентами чувствительности.

Пример 20.2.3

Рассмотрим задачу из примера 20.2.2. Оптимальной точкой является Х0=(х,0,х20,х3°) = (0,81, 0,35, 0,28). Так как Y0 =(х,°,х20), то

Vv„/ =

чйх,йх2,

= (2х,°,2х2) = (1,62,0,70).

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

= VYo/J-=(1,62,0,7)

( 2 П 3 3

5 Jl 3 3,

= (0,0876,0,3067).



Это свидетельствует о том, что изменение dgx = 1 приводит к увеличению значения целевой функции / приблизительно на 0,0867. Аналогично при dg2 = 1 имеет место увеличение значения/приблизительно на 0,3067.

Использование метода Якоби в задачах линейного программирования. Рассмотрим задачу линейного программирования.

Максимизировать г - 2л:, + Зхг

при ограничениях

JCj "Ь Х2 "Ь Х3 = б,

хг - х2 + xt = 3,

2> 3 4 -

Для каждого условия неотрицательности xf > 0 введем соответствующую (неотрицательную) дополнительную переменную w2. Таким образом, дгу - w2 = 0

или ху = w2. При такой замене условия неотрицательности становятся неявными,

и исходная задача принимает вид

максимизировать z = 2wf + 3w2

при ограничениях

w, + ve, + w, = 5,

= 3.

Для метода Якоби положим Y = (ц>,, и>2) и Z = (u>3, ц>4). (В терминологии линейного программирования векторы Y и Z образованы базисными и небазисными переменными соответственно.) Следовательно,

(2w,

J- =

J 1

4ve, 4vv,

J -1

4vv, 4ve,

w, и VV2 * 0,

так что

2w, 0 4 4 0 2w4,

,VY/ = (4w„6w2),Vz/ = (0,0),

Vc/ = (0,0)-(4w„6w2)

4vv, 4vv,

4ve2 4w2,

2w, 0 0 2w4

=(-5w3,w4).

Решение системы уравнений, состоящей из уравнения V/ = 0 и ограничений задачи, позволяет определить стационарную точку w1 = 2, w2=l, w3 = 0, w4 = 0. При этом матрица Гессе имеет вид



dcw3drwt

Поскольку Н. является неопределенной матрицей, стационарная точка не будет точкой максимума.

На самом деле полученный результат не является неожиданным, поскольку (небазисные) переменные w3 и ш4 (и, следовательно, х3 и х4) равняются нулю, как и предусмотрено теорией линейного программирования. Следовательно, решение, полученное с помощью метода Якоби, определяет ту или иную крайнюю точку пространства допустимых решений рассматриваемой задачи, которая связана с конкретным выбором векторов Y и Z. При этом найденное решение может как быть, так и не быть оптимальным. Однако метод Якоби позволяет распознать оптимальное решение задачи путем использования достаточных условий экстремума.

Приведенные рассуждения свидетельствуют о том, что для оптимального решения задачи линейного программирования необходимо менять конкретный выбор Y и Z, пока не будут выполнены достаточные условия. Пусть, например, Y = (ц>2, wt) и Z = (ц>,, w3). Тогда соответствующий приведенный градиент принимает вид

VJ = (4w„0)-(6w2,0)

2ve2 l

f2w, 2w,

2ve3 0

=(-2wp6wj).

Соответствующая стационарная точка определяется значениями wl = О, w2 w3 = 0, wt=J&. Так как матрица

-2 0}

0 -6)

является отрицательно определенной, то указанная точка - точка максимума.

Полученный результат можно проверить графически, используя рис. 20.6. Первое из найденных решений (дг, = 4, дс2 = 1) не является оптимальным, в то время как второе (х, = 0, дс2 = 5) оказывается таковым. Читатель имеет возможность проверить, что две оставшиеся крайние точки пространства допустимых решений не являются точками максимума. Кроме того, с использованием достаточных условий экстремума можно показать, что в точке дг, = 0, дс2 = 0 возникает минимум целевой функции рассматриваемой задачи.

Заметим, что введенные ранее коэффициенты чувствительности VYj/J" в задаче

линейного программирования являются переменными двойственной задачи. Чтобы проиллюстрировать это на рассматриваемом численном примере, обозначим через и, и и2 соответствующие переменные двойственной задачи. В оптимальной точке и>1 = 0, w2 = VJ, w3 = 0, w4 = переменные двойственной задачи вычисляются по формуле

(«„«2) = VYr=(6w2,0)

24 2w4

=(3,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] [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]