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


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


81

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

.3*4

откуда XI Х2

2x1 +2=2,

9.5. Метод множителей Лагранжа

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

Пусть требуется решить задачу нелинейного программирования следующего вида:

/(xi,...,x„)->max(min). gl (xi,...,x„)=Z>i, g2 (х,,...,х„)=Й2,

где функции / и gi, i = \,m непрерывны, и непрерывны их частные про-

изводные по ху, j= 1,« .

Для решения поставленной задачи может быть применен метод множителей Лагранжа. Объясним идею метода на примере задачи нелинейного программирования, зависящей от двух переменных и имеющей только одно ограничение:

max/(xi,X2) g(xi,X2) = fe.

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



fix)

Рис. 9.5

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

/ (х ) = (х ), где Я есть некоторый коэффициент пропорционально-СТИ. Координаторами векторов / (х ) и g (х ) являются значения част-ных производных функций/и g соответственно в точке х .

gix) =

дх\ дХ2

dg . dg Щдх2)

Из условия пропорциональности в точке х имеем

Sjcj dxi

дх2 дх2

Для определения значений х и Х2, в которых функция / достигает максимума, к этим уравнениям надо добавить условие принадлежности точки X* графику функции gx*,X2=i.

Окончательно получаем систему уравнений, определяющую оптимальное решение поставленной задачи



dxi dxi

дх2 дх2 8{х\,Х2) = Ь.

Введем новую функцию

,Х2,Я) = /(1 ,Х2 ) + Я() - g(xi Х2 )).

Тогда последняя система перепишется в виде

дР{х1,Х2,Л) df{xi,X2) Sg{xi,X2)Q,

dxidxiSxTj

дР{х1,Х2,Я) df{x\,X2) 6g(xi,X2) dx2dx2dx2

= b-g{xi,X2) = 0.

Функцию F называют функцией Лагранжа.

Приведем ниже алгоритм метода множителей Лафанжа решения задач нелинейного программирования.

Этап 1. Составляют функцию Лафанжа

F(xi,...,x„,Ai,...,A) =

= /(xj,) + 2 Л- (» - gi {х\.«)) /=1

Этап 2. Находят частные производные функции Лафанжа по х и Л,-, у = 1,и; i = \,m и приравнивают их к нулю

dF df

dXj dXj ,-=1 dXj

(9.5)

g,(xi,...,x,,) = i,-, /= \,m.

Этап 3. Решают систему (9.5) и определяют точки, в которых функция /(xi,...,x„) может иметь экстремум.

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