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


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


260

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

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

Шаг 1

Шаг 1

/о = (0, 3) = (xL, хя),

/о = (0, 3) = (xL, xR),

xi =0,5(3 + 0-0,1) = 1,45, /(xi) = 4,35,

х, = 3 - 0,618(3 - 0) = 1,146, /(х,) = 3,438,

хг = 0,5(3 + 0 + 0,1) = 1,55, i\x2) = 4,65,

х2 = 0 + 0,618(3 - 0) = 1,854, /(хг) = 5,562,

/(х2) > /(Xi) => xL = 1,45, /т = (1,45, 3).

/(х2) > /(X!) => X/. = 1,146, /, = (1,146, 3).

Шаг 2

Шаг 2

/, = (1,45, 3) = (xL, хв).

/1 =(1,146, 3) = (xL, хд),

Xi = 0,5(3 + 1,45 - 0,1) = 2,175, /(Xi) = 5,942,

Хт = х2 на шаге 1 = 1,854, /(Xi) = 5,562,

х2 = 0,5(3 + 1,45 + 0,1) = 2,275, f(x2) = 5,908,

Хг = 1,146 + 0,618(3 - 1,146) = 2,292, /(х2) = 5,903,

fxi) > i\x2) => Хя = 2,275, /, = (1,45, 2,275).

/(х2) > /(Xi) => X/. = 1,854, /, = (1,854, 3).

Продолжая вычисления, получим с заданной точностью интервалы, содержащие точку максимума функции f(x).

На рис. 21.2 показан шаблон Excel ch21DichotomousGoldenSection.xls, предназначенный для поиска экстремумов функций описанными методами. Входными данными являются функция f(x) и константы a, b и Д. В данном примере функция f(x) задается в ячейке ЕЗ с помощью формулы

=ЕСЛИ(СЗ<=2;3*СЗ;(-СЗ+20)/3) Отметим, что здесь ссылка СЗ играет роль переменной х. Константы а и Ь, введенные в ячейки В4 и D4, задают интервал поиска точки экстремума функции f(x). Значение предела точности Д вводится в ячейку ВЗ. Метод поиска задается путем ввода символа х в ячейку D5 (метод дихотомического поиска) или в ячейку F5 (метод золотого сечения).

На рис. 21.2 для сравнения показаны результаты вычислений в соответствии с обоими методами. Как видно на рисунке, метод золотого сечения потребовал всего 40 % числа итераций, выполненных методом дихотомического поиска.

УПРАЖНЕНИЯ 21.1.1

1. С помощью шаблона ch21DichotomousGoldenSection.xls решите задачу из примера 21.1.1, положив Д = 0,01. Сравните точность полученных результатов с данными, показанными на рис. 21.2.

2. Методом дихотомического поиска найдите максимумы следующих функций, полагая при этом, что Д = 0,05.

a) /(*)=•;-т, 2<х<4;

b) f(x) = х cosx, 0 < х < я;

c) f(x) = хsinrcx, 1,5<х<2,5;

d) f(x) = -(х - З)2, 2<х<4;

,. . \Ах, 0<*<2, W [4-х, 2<*<4.



в с d в

DichotomoirsGolden Section Seaich

Input data: Type f(C3) in E3, where C3 represents x m )

oooootd

1 450000 1 450000 1 812500 1.812500 1 903125 1 948438 1 971094 1 982422 1.988086 1 988086 1 989502 1 989502 1 969856 1 969856 1 989944 I 989989 1 989989 1990000 1 990000

3OXO00 3OXO00 2 275000 2 275000 2093750 2 093750 2093750 2093750 2.093750 2.093750 2 090918 2 090918 2 090210 2 090210 2 0900ЭЗ 2 090033 2 0900ЭЗ 2 090011 2 090011 2090005

1 450000 2.175000 1 812500 1 993750 1 903125 1 948438 1 971094 1 982422 1 988086 1 990918 1 989502 1 990210 1 989856 1 990033 1 989944 1 9899B9 1 990011 1 990000 1.990005; 1 990003

1 550000 2.275000

1 912500

2 09Э750 2 003125 2 048438 2.071094 2 082422 2 088086 2 090918 2 089502 2 090210 2089856 2 090033 2 089944 2089989 2090011 2 090000 2090005 2 090003

4 350000

5 941667 5 437500 5981250 5 709375 5 845313 5913281 5 947266 5 964258 5 972754 5968506 5.9706X 5969568 5.970099 5 969833 5 969966 5 970033 5 969999 5 970016 5 970008

4 650000

5 908333 5 7Э7500 5 968750 5 998958 5 983854 5 976X2 5 972526 5 970638 5 969694 5 970166 59699X 5 970048 5 969969 5 97X19 5.970004 5 969996 5 9700ГО 5 969996 5 969999

ВС D 1 E

Dichotomou&Golden Section Seaich

Input data: Type t{C3) in E3. aiare СЗ гедч :ents и in fy>

0 000000

1 145898 1 854102 1 854102 1 854102 1 854102 1957428 1 957428 1 996894

3000000 30000X 3000000 2 562306 2 291796 2124612 2124612 2 060753 2 060753

1 145898

1 854102

2 291796 2124612 2 021286

1 957428 2021266 1.996894"

2 021286

1 854102

2 291796 2 562Э06 2 291796 2124612 2 021286 2060753 2.021286 2 036361

3 437694 5 562306 5 902735 5 958463 5 992905 5 872283 5 992905 5 990683 5992905

5 562306 5.902735 5 812565 5 902735 5 958463 5 992905 5.979749 5 992905 5 987BB0

Рис. 21.2. Реализация методов прямого поиска в Excel

Получите формулу для определения максимального числа итераций, выполняемых в методе дихотомического поиска при заданной величине Д и длине начального интервала неопределенности I0 = b- а.

21.1.2. Градиентный метод

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

Одним из градиентных методов является изложенный в разделе 20.1.2 метод Ньютона-Рафсона, который ориентирован на решение систем уравнений. Здесь рассматривается еще один метод, который называется методом наискорейшего подъема2.

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



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

Рассмотрим задачу максимизации функции f(X). Пусть Х° - начальная точка, с которой начинается реализация метода, УДХ*) - градиент функции f в k-й точке X*. Идея метода сводится к определению в данной точке направления р, вдоль которого производная по направлению df/dp достигает своего максимума. Это происходит в том случае, когда последовательные точки X* и Х*+1 связаны соотношением

где г* - параметр, называемый длиной шага в точке X*.

Обычно значение параметра г* выбирается из условия, чтобы в точке Х*1 наблюдалось максимальное увеличение значения целевой функции /. Другими словами, если функция Л(г) определяется соотношением

то г* равен значению г, на котором функция h(r) достигает максимума. Поскольку Л(г) является функцией одной переменной, чтобы найти ее максимум, можно применить метод поиска экстремума, описанный в подразделе 21.1.1, если, конечно, функция h(r) строго одновершинная.

Описанная процедура заканчивается, когда две последовательные точки X* и X**1 близки. Это эквивалентно тому, что rVf(Xk) = 0. Поскольку г * 0, последнее соотношение означает, что в точке X* выполняется необходимое условие экстремума УДХ*) = 0.

Пример 21.1.2

Рассмотрим задачу максимизации функции

/(х,,х2) = 4х, + 6х2 -2х] -2хххг -2х22.

Функция Дх,, х2) является квадратичной, и нам известно, что ее абсолютный мак-

Решим эту задачу методом наискорейшего подъема. На рис. 21.3 изображена последовательность получаемых точек. Градиенты в двух последовательных итерационных точках с необходимостью являются ортогональными (перпендикулярными) друг к другу. Для данной функции градиент вычисляется по формуле

k+l

X" + rkVf(Xk),

h(r) = f(Xk + rVf(Xk)),

УДХ) = (4 - 4x, - 2x2, 6 - 2x, - 4x2). Пусть начальной точкой является Х° = (1, 1).

X = (l, l) + r(-2, 0) = (l-2r, 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]