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


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


259

ГЛАВА 21

АЛГОРИТМЫ НЕЛИНЕЙНОГО ПРО ГРАМ М И РО В АН ИЯ

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

21.1. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ БЕЗ ОГРАНИЧЕНИЙ

В этом разделе представлены два метода решения задач нелинейного программирования без ограничений на переменные: метод прямого поиска и градиентный метод. В первом реализуется прямой поиск оптимальной точки в заданной области, тогда как во втором методе, чтобы найти экстремальную точку, используется градиент целевой функции.

21.1.1. Методы прямого поиска

Методы прямого поиска применяются главным образом для определения экстремумов функций одной переменной. Несмотря на то что такие задачи могут показаться тривиальными, в следующем разделе показано, что методы прямого поиска находят применение и при решении многомерных задач.

Идея методов прямого поиска проста. Сначала определяется интервал неопределенности, который содержит искомую точку оптимума. Затем длина интервала последовательно уменьшается до тех пор, пока не будет найдена точка оптимума. Процедура строится таким образом, что длину интервала, содержащего оптимальное решение, можно сделать сколь угодно малой.

В данном разделе рассматривается метод дихотомического поиска1 и метод золотого сечения. В обоих методах на интервале а<х<Ь ищется максимум функции f(x), имеющей на этом интервале только один максимум. (Такая функция называется одновершинной.) Начальный интервал неопределенности состоит из исходного интервала I0 = (а, Ь).

1 В русскоязычной математической литературе этот метод обычно называется методом деления отрезка пополам. - Прим. ред.



Пусть = (xL, xR) - интервал неопределенности на шаге I (на нулевом шаге xL = а и xR = b). Далее определяем х, и х2 такие, что

х, < х, < х2 <хя.

Следующий интервал неопределенности /, определяется после вычисления значений Дх,) и f(x2). При этом возможны три варианта.

1. Если Дх > f(x2), то точка экстремума х* должна лежать между xL и хг: х, < х < х2. Тогда положим х„ = х2 и получим новый интервал неопределенности/,= (xL, х2) (рис. 21.1, а).

2. Если f(X]) < f(x2), то хх < х" < х„. Тогда xL = хг и 7, = (xlt хя) (см. рис. 21.1, б).

3. Если Дх,) = Дх2), то х, < х* < х2. Положим xL = хх и хя = х2, тогда I, = (х,, х2).

Рис. 21.1. Иллюстрации к прямым методам поиска

Поскольку здесь на каждом шаге гарантировано It < в результате сужается интервал, в котором находится точка максимума функции f(x). Алгоритм заканчивается на некотором шаге k, когда будет выполняться неравенство 1к < Д, где Д - значение заранее заданной точности.

Различие между методами дихотомического поиска и золотого сечения заключается только в способе вычисления точек х, и х2. Формулы для вычисления этих точек, представлены в следующей таблице.

Метод дихотомического поиска

Метод золотого сечения

Xi = (xR + xL- Д)/2

v5-1

Х\ ~ ХК „ (XR XL>

XZ = (Xr+Xl + A)/2

Xi=XL+-j-(xx-XL)



В методе дихотомического поиска значения х, и х2 симметричны относительно средней точки текущего интервала неопределенности. Это означает, что /, = 0,5(7,.,+ Д). Последовательное применение этого равенства доказывает, что длина конечного интервала неопределенности достигнет значения желаемой точности Д.

Идея метода золотого сечения не такая очевидная. Заметим, что в методе дихотомического поиска вычисляются два значения f(xx) и f(x2), но после сравнения одно из них отбрасывается. В методе золотого сечения, то значение, которое отбрасывается в методе дихотомического поиска, сохраняется и используется на следующем шаге.

Введем параметр а такой, что 0 < а < 1. Пусть

х, = xR - a(xR - хJ, x2 = xL+afxR-xLJ.

Тогда интервал неопределенности /, на шаге i равен или (xL, х2) или (х,, xR). Рассмотрим ситуацию, когда ll = (xL, хг). Здесь точка х, содержится в интервале /(. На шаге i + 1 в качестве точки х2 выбирается точка х, с предыдущего шага, т.е.

х2(на шаге i + 1) = х,(на шаге г). Используя формулы для вычисления точек х, и х2, приведенные выше, это равенство можно переписать как

xl + «/"х/на шаге U - хJ = xR - a(xR - xj или, еще раз применяя аналогичную формулу для х2(на шаге i), в виде

xL + а[xL +а(xR- xj - xj = xR-a(xR- xj. Из последнего равенства после несложных преобразований получим

«VxR - хJ + a(xR - xj - (xR - xj = 0. Поделив последнее выражение на (xR - xL), получим уравнение относительно а:

d + а-1 =0.

Это квадратное уравнение имеет корни а = (-1±л/5)/2. Поскольку по условию 0 < а < 1, мы выбираем положительный корень а = (-1 + -Jb)12 = 0,681.

Метод золотого сечения построен таким образом, что каждый последующий интервал неопределенности меньше предыдущего в а раз, т.е. = alt. По сравнению с методом дихотомического поиска этот метод сходится значительно быстрее (т.е. через меньшее число шагов получается интервал неопределенности заданной длины Д, содержащий х*). Кроме того, метод золотого сечения требует в два раза меньше вычислений, чем метод дихотомического поиска, поскольку на каждом шаге используются вычисления, выполненные на предыдущем шаге.

Пример 21.1.1

Имеем следующую задачу.

[Зх, 0<х<2,

Максимизировать /(х) = < х 20

Гз+Т ~х~

Ясно, что максимум функции Дх) достигается в точке х = 2. В следующей таблице показаны вычисления для двух шагов методов дихотомического поиска и золотого сечения при Д = 0,1.

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