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


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


256

Наконец, в точке (Х0, А0)3 = (2,8, 0, 1,4, 1,4)

0 4 0 4 2 0 0 0 -0,8

= 12,8 > 0 и

0 4 0 2

4 2 0 0

О 0 -0,8 О

2 0 0 2

= 32>0.

Отсюда следует, что (ХД и (Х„)2 - точки минимума. Тот факт, что в точке (Х„)3 не удовлетворяются достаточные условия максимума или минимума, не означает, что эта точка не является экстремальной. Это следствие того, что используемые условия являются лишь достаточными.

Для иллюстрации схемы проверки достаточных условий экстремума, которая использует корни полинома, рассмотрим матрицу

0 4 2х2 2

4 2-й 0 0

2х2 0 2-2X-U 0

к2 0 0 2-й,

В точке (Х„, А0), = (2, 2, 1,1) имеем

Д = V- 26/+16 = 0,

откуда получаем ju= 2 и =8/9. Так как все ju> 0, то (Х0), = (2, 2, 1) - точка минимума. В точке (Х0, Л0)2 = (2, -2, 1,1)

Д = 9 - 26 + 16 = 0,

что совпадает с рассмотренным выше случаем. Следовательно, (Х0)2 = (2,-2, 1) является точкой минимума. Наконец, в точке (Х„, Л0)3 = (2,8, 0, 1,4, 1,4)

Д = 5 -6 -8 = 0,

откуда получаем ju=2 и =-0,8, что свидетельствует о том, что точка (Х„), = (2,8, 0, 1,4) не является экстремальной.

УПРАЖНЕНИЯ 20.2.3

1. Методом Якоби и методом множителей Лагранжа решите следующую задачу линейного программирования.

Максимизировать /(X) = 5х, + Зх2

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

g,(X) = х, + 2х2 + х3 - 6 = О, g2(X) = Зх, + х2 + х4 - 9 = 0,

"1* "2 "3> "4 -

2. Найдите оптимальное решение следующей задачи.

Минимизировать /( X) = х2 + 2х2 + 1 Ох2

gl(X) = x,+x2+x3-5 = 0, £2(Х) = лг, +5дг2 + х3-7 = 0.



Пусть g,(X) = 0,01 и g2(X) = 0,02. Найдите величину соответствующего изменения оптимального значения функции /(X).

3. Решите упражнение 20.2.2.6 методом множителей Лагранжа и проверьте, что полученные значения множителей Лагранжа совпадают со значениями коэффициентов чувствительности, полученными ранее при решении этого упражнения.

20.2.2. Ограничения в виде неравенств

В данном разделе показано, как метод множителей Лагранжа можно обобщить на случай задачи с ограничениями в виде неравенств. Основную часть раздела составляет вывод условий Куна-Таккера, которые играют важную роль в нелинейном программировании.

Обобщенный метод множителей Лагранжа. Пусть дана задача, в которой требуется

максимизировать г = /(X)

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

£(Х)<0, j = 1,2.....т.

Если в рассматриваемой задаче имеются условия неотрицательности переменных X > 0, то предполагается, что они включены в указанные т ограничений.

Основная идея обобщенного метода множителей Лагранжа состоит в том, что если точка безусловного оптимума функции /(X) не удовлетворяет всем ограничениям задачи, то оптимальное решение задачи с ограничениями должно достигаться в граничной точке области допустимых решений. Следовательно, одно или несколько из т ограничений задачи должны выполняться как равенства. Поэтому вычислительная процедура обобщенного метода множителей Лагранжа включает следующие шаги.

Шаг 1. Решается задача без учета ограничений

максимизировать 2=/(Х).

Если полученное оптимальное решение удовлетворяет всем ограничениям задачи, вычисления заканчиваются, так как все ограничения являются избыточными. Иначе следует положить k = 1 и перейти к шагу 2.

Шаг 2. Активизируются любые k ограничений задачи (т.е. преобразовываются в равенства), и оптимизируется функция /(X) при наличии k ограничений методом множителей Лагранжа. Если оптимальное решение этой задачи является допустимым по отношению к остальным ограничениям исходной задачи, вычисления заканчиваются: полученная точка является локальным оптимумом2. Иначе нужно сделать активными другие k ограничений исходной задачи и повторить данный шаг. Если все подмножества, состоящие из k активных ограничений, не приводят к допустимому решению, следует перейти к шагу 3.

Шаг 3. Если k = m, вычисления прекращаются: задача не имеет допустимых решений. Иначе необходимо положить k - k + 1 и перейти к шагу 2.

В описанной вычислительной процедуре часто игнорируется то важное обстоятельство, что она не гарантирует получения глобального оптимума даже в тех

Локальный оптимум определяется из множества оптимумов, полученных в результате оптимизации целевой функции f(X.) при учете всех комбинаций из k ограничений-равенств, k = 1, 2, т.



случаях, когда задача имеет единственное оптимальное решение. Другим важным моментом является ошибочность интуитивного представления, что если p<q, то оптимальное значение целевой функции /(X) при р ограничениях-равенствах всегда лучше, чем при q ограничениях-равенствах. В общем случае это имеет место лишь в том случае, когда набор из р ограничений является подмножеством набора из q ограничений. Рассматриваемый ниже пример служит иллюстрацией сказанного.

Пример 20.2.6

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

Максимизировать z = - (2.x, - 5 )2 - (2дг2 -1 )2

х, + 2х2 < 2, хх,хг>0.

Графическое представление данной задачи (рис. 20.7) призвано помочь в понимании аналитических выкладок. Как видим, целевая функция задачи является вогнутой, а область допустимых решений выпуклой. Отсюда следует, что эффективный алгоритм должен гарантировать определение глобального оптимума. Однако обобщенный метод множителей Лагранжа, как будет показано, позволяет найти лишь точку локального максимума.

Рис. 20.7. Пространство решений для задачи примера 20.2.6

Точка безусловного экстремума находится как решение уравнений

- =-4(2*.-5) = 0,

дх, У 1

= (2x2-l) = 0.

Отсюда имеем (xv х2) = (5/2, 1/2). Так как это решение не удовлетворяет условию .г, + 2лг2 < 2, ограничения поочередно активизируются. Рассмотрим ограничение х, = 0. Функция Лагранжа в этом случае примет вид

L(x,,x2,\) = -(2x, - 5)2 -(2дг2 -I)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]