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


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


251

УПРАЖНЕНИЕ 20.1.2

1. Примените метод Ньютона-Рафсона для решения упражнений 20.1.1.1, с и 20.1.1.2, Ъ.

20.2. ЗАДАЧИ НА ЭКСТРЕМУМ ПРИ НАЛИЧИИ ОГРАНИЧЕНИЙ

В настоящем разделе рассматриваются задачи поиска экстремумов непрерывных функций при наличии ограничений на переменные. В разделе 20.2.1 рассматривается ситуация, когда дополнительные ограничения имеют вид равенств, а в разделе 20.2.2 - неравенств. Основная часть материала раздела 20.2.1 изложена в соответствии с [2].

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

В данном разделе рассматривается два метода решения оптимизационных задач при наличии ограничений в виде равенств: метод Якоби и метод Лагранжа. Метод Лагранжа можно логически получить из метода Якоби. Эта связь позволяет дать интересную экономическую интерпретацию метода множителей Лагранжа.

Метод приведенного градиента (метод Якоби). Рассмотрим задачу

минимизировать z = /(X)

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

g(X) = 0,

X = (дг,, х2, дсл),

S (.§!> &2> *

Функции /(X) и g,(X), t= 1, 2, т, предполагаются дважды непрерывно дифференцируемыми.

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

Для пояснения изложенной идеи рассмотрим функцию /(дг,, х2), график которой представлен на рис. 20.5. Предположим, что эту функцию необходимо минимизировать при ограничении

g,(*i. х2) = х2 - Ь = 0,

где Ь - некоторая константа. На рис. 20.5 видно, что кривая, которая проходит через точки А, В и С, состоит из значений функции /(дг,, х2), для которых заданное ограничение выполнено. В соответствии с рассматриваемым методом определяются компоненты приведенного градиента функции /(дг,, х2) в каждой точке кривой ABC. Точка В, в которой приведенная производная обращается в нуль, является стационарной для рассматриваемой задачи с ограничением.

Теперь рассмотрим общую математическую формулировку метода. Из теоремы Тейлора следует, что для точек X + АХ из окрестности точки X имеем

/(х+дх)-/(х) = у/-(х)дх+о(дх,2),

g(X + AX)-g(X) = Vg(X)AX + 0(Ax2).



Лх{,х2)

/ J / 1

1 1 \ 1 \ \

\ \

• : 1

ч в У7\

---- \ л:2 = 6

Линия минимального значения целевой функции

Рис. 20.5. Иллюстрация к методу Якоби

При hxj -» 0 эти уравнения принимают вид

d/(X) = V/(X)c5X,

dg(X) = vg(X)ax.

Поскольку g(X) = 0, 9g(X) = 0 в допустимой области. Отсюда следует, что

о/(Х) - V/(X)3X = 0,

vg(x>ax = o.

Как видим, задача сводится к решению т + 1 уравнений с п + 1 неизвестными, которыми являются 9/(Х) и ЭХ. Неизвестную величину 9/(Х) можно определить, как только будет найден вектор 5Х. Это означает, что, по существу, имеется т уравнений с п неизвестными.

При т > п по меньшей мере т- п уравнений системы являются избыточными. После устранения избыточности количество независимых уравнений в системе становится равным т (< п). Если т = п, решением является ЭХ = 0. При этом точка X не имеет допустимой окрестности, и, следовательно, пространство решений задачи состоит из единственной точки. Такая ситуация является тривиальной. Ситуацию, когдат<п, рассмотрим подробно.

Пусть X = (Y, Z), где

Y = (j/p уг, ...,ym)nZ = (z1,z2, ...,zn m)



называются зависимыми и независимыми переменными соответственно. Переписывая градиенты функций / и g в новых обозначениях, получим

V/(Y, Z) - (VY/, Vz/), Vg(Y, Z) = (VYg, Vzg). Введем в рассмотрение матрицы

fvYg, ] J=vYg= ; ,

c = vzg =

Матрица JmXm называется матрицей Якоби, a CmX((1 m) - матрицей управления. Матрица Якоби J предполагается невырожденной. Это всегда можно обеспечить, поскольку рассматриваемые т уравнений являются независимыми по определению. Поэтому компоненты вектора Y можно выбрать среди компонентов вектора X таким образом, что матрица J окажется невырожденной.

Исходную систему уравнений с неизвестными 9/(Х) и ЭХ можно переписать в следующем виде

a/(Y, Z) = VY/5Y + Vz/dZ,

JdY=-caz.

Так как матрица J невырожденная, существует обратная матрица J-1. Следовательно,

oY = - jcaz.

Подставляя это выражение 5Y в уравнение для 9/(Y, Z), можно выразить df через 9Z в следующем виде

a/(Y, Z) = (yzf-VYfJ1C)dZ.

Из этого уравнения получаем формулу для производных функции f по вектору независимых переменных Z

v£/ =

a./(v,z)

= vz/-vy/j-c,

где VJ представляет вектор приведенного градиента функции / по Z. Следовательно, вектор Vc/(Y,Z) должен обращаться в нуль в стационарных точках.

Достаточные условия экстремума в стационарной точке аналогичны изложенным в разделе 20.1. В этом случае элементы матрицы Гессе будут соответствовать компонентам вектора независимых переменных Z. Между тем элементы матрицы Гессе должны быть приведенными вторыми производными. Чтобы показать, как они вычисляются, положим

ve/ = vz/-wc.

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