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


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


261

ДХ) = 4х, + 6х2 - 2xf- 2ххх2 - 2х22

1 1 3 2 х1

Рис. 21.3. Последовательность точек, ведущая к оптимуму функции

Отсюда получаем выражение для функции 1г(г):

h(r) =Д1 - 2r, 1) = -2(1 - 2rf + 2(1 - 2г) + 4.

Оптимальная длина шага г, при которой функция h(r) достигает максимума, равна 1/4. Таким образом, мы нашли, что X1 = (1/2, 1).

Итерация 2.

УДХ) = (0, 1).

Теперь следующая точка X2 определяется выражением

Х = (1,1) + К0,1) = (,1+/-).

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

h(r) = -2(1 + rf + 5(1 + г) + .

Отсюда получаем г = 1/4 и X2 = (1/2, 5/4). Итерация 3.

УДХ2) = (-1,0). Точка X3 определяется выражением



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

/i(r) = --(l-r)2+ -а-г)+ - 2 4 8

Отсюда получаем г = 1/4 и X = (3/8, 5/4). Итерация 4.

V/(X3) = (0, -).

Точка X4 определяется выражением

x=VWan Г35+Г

,8 4J I. А) 1,8 4 Поэтому

*(0 = -(5 + r)s+g(5 + r) + g.

Отсюда имеем г = 1/4 и X4 = (3/8, 21/16). Итерация 5.

УДХ4) = (-1,0).

Точка X5 определяется выражением

3 21 V-i,oi=fc:

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

Х ,8l6j Л &") { 8 16

Л(Н =--(3-г) +- (3-Н+-.

v 32v ; 64v 128

Отсюда получаем г = 1/4 и Xй = (11/32, 21/16). Итерация 6.

УДХ6) = (0, -).

Так как V/(X°) = 0, вычисления можно закончить. Получена приближенная точка максимума X5 = (0,3437, 1,3125). Точный максимум достигается в точке Х* = (0,3333, 1,3333).

УПРАЖНЕНИЯ 21.1.2

1. Покажите, что метод Ньютона-Рафсона (раздел 20.1.2), применяемый к решению задачи максимизации строго вогнутой квадратичной функции, в общем случае сходится в точности за один шаг. Примените указанный метод к задаче максимизации функции

/(X) = 4,v, + 6х2 - 2.x2 - 2х,х, - 2х\.



2. Выполните не более пяти итераций метода наискорейшего спуска (подъема) для каждой из следующих задач. Во всех случаях положите Х° = О.

a) min/(Х) = (*2-*?)*+(1-х,)*.

b) max/(X) = сХ + ХГАХ, где

с = (1,3, 5),

с) min/(X) = X[-х2 +xf-х,х2.

21.2. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ С ОГРАНИЧЕНИЯМИ

Общая задача нелинейного программирования с ограничениями записывается в виде:

максимизировать (или минимизировать) z = /(X) при ограничениях

g(X) <0.

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

Универсальных алгоритмов решения задач нелинейного программирования не существует, и связано это, главным образом, с разнообразием нелинейных функций. Возможно, наиболее общим результатом, имеющим отношение к рассматриваемым задачам, являются условия Куна-Таккера. Как показано в разделе 20.2.2, эти условия являются необходимыми лишь для существования экстремума, за исключением ситуации, когда функции /(X) и g(X) являются выпуклыми или вогнутыми (тогда эти условия будут также достаточными).

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

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

21.2.1. Сепарабельное программирование

Функция /(ж,, х2.....хп) называется сепарабельной (разделимой), если она представляется в виде суммы п функций одной переменной /,(х,), f2(x2), /„(*„), т.е. ffx,, х2,хJ = f,(x,) + f/xj + ... + f/xj.

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