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


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


257

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

-4(2jc,-5

)-к = 0,

-4(2х2-1) = 0,

-х, = 0.

Решением этой системы будет точка (х,,х2) = (0, 1/2), которая является точкой максимума, в чем можно убедиться, используя достаточное условие. Поскольку эта точка удовлетворяет остальным ограничениям исходной задачи, вычислительная процедура завершается: (х1,х2) = (0, 1/2) - точка локального максимума задачи. (Заметим, что если поочередно активизировать оставшиеся ограничения задачи хг > 0 и х, + 2х2 < 2, то получаются недопустимые решения.) Оптимальное значение целевой функции z = -25.

Как видно из рис. 20.7, допустимому решению (х,, х2) = (2, 0) рассматриваемой задачи, которое определяется точкой пересечения двух прямых х2 = 0 и х, + 2х2 = 2, соответствует значение целевой функции z = -2. Оно лучше значения функции z, которое получено с учетом одного активного ограничения.

Как следует из описанной вычислительной процедуры, при реализации обобщенного метода множителей Лагранжа на большее, чем получение приемлемого допустимого решения задачи, не следует рассчитывать. Особенно это проявляется тогда, когда целевая функция задачи не является одновершинной. Если в оптимизационной задаче имеется единственный (глобальный) условный экстремум (как в примере 20.2.6), то, чтобы его найти, можно использовать откорректированный обобщенный метод множителей Лагранжа. Для этого необходимо провести сравнение безусловного оптимума и условных экстремумов, полученных с учетом всех возможных наборов активных ограничений, т.е. когда сначала отдельные ограничения делаются активными поочередно, затем рассматриваются пары активных ограничений, и так до тех пор, пока все т ограничений рассматриваемой задачи не станут активными. Наилучший из всех таких допустимых экстремумов является глобальным.

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

Условия Куна-Таккера. Данный раздел посвящен рассмотрению необходимых условий Куна-Таккера, которые позволяют определять стационарные точки в задаче нелинейного программирования с ограничениями в виде неравенств. В основу изложения положен метод множителей Лагранжа. Эти условия являются также и достаточными, если выполняются определенные правила, которые описаны ниже.

Рассмотрим следующую задачу.

Максимизировать г = ДХ)

g(X)<0.



Ограничения-неравенства можно преобразовать в равенства с помощью неотрицательных дополнительных переменных. Пусть Sf[>Q) - дополнительная переменная, которая прибавляется к левой части t-ro ограничения gt(X.) < 0 и пусть

S = (S„S1,...,S\T и S2 =(S12,S22,...,5)r,

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

ДХ, S,X) = /(X)-X[g(X) + S2].

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

то как только правая часть ограничения g(X) < 0 увеличивается и становится больше нуля, область допустимых решений задачи расширяется и, следовательно, оптимальное значение целевой функции не может уменьшиться. Это значит, что X > 0. Аналогично в задаче минимизации при увеличении правой части ограничения оптимальное значение функции / не может увеличиться, откуда следует, что X < 0. Если же ограничения задачи имеют вид равенств, т.е. g(X) = 0, то компоненты вектора X по знаку не ограничены (см. упражнение 20.2.4.2).

Указанные выше ограничения на вектор X должны рассматриваться как часть необходимых условий Куна-Таккера. Теперь получим остальные условия.

Вычисляя частные производные функции L по X, S и X и приравнивая их к нулю, получаем

l = V/(X)-Wg(X) = 0,

- = -2XS = 0, ; = 1, 2,...,/я,

dS,

Из второй группы уравнений следуют такие результаты.

1. Если Я, не равняется нулю, то S2 = 0 . Это означает, что соответствующий этому ограничению ресурс является дефицитным и, следовательно, полностью исчерпан (ограничение имеет вид равенства).

2. Если S2 > 0 , то Я, = 0. Это значит, что i-й ресурс дефицитным не является и, следовательно, не влияет на значение целевой функции/(т.е. Х,=-- = 0).

Из второй и третьей групп уравнений следует, что

Яд(Х) = 0, i=l,2, ...,т.



Полученные условия фактически подтверждают предыдущий результат, ибо если Я, > 0, то gt(X) = 0 или S,2 = 0 . Аналогично при gX) < О S2 > 0 и, следовательно, \ = 0.

Теперь для задачи максимизации можно сформулировать условия Куна-Таккера, необходимые для того, чтобы векторы X и X определяли стационарную точку:

Х>0, Vf(X)-XVg(X) = 0, Лд(Х)-0, i = l,2, .... те, g(X)<0.

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

Достаточность условий Куна-Таккера. Если целевая функция и область допустимых решений рассматриваемой задачи обладают определенными свойствами, связанными с выпуклостью и вогнутостью, то необходимые условия Куна-Таккера являются также достаточными. Упомянутые свойства перечислены в табл. 20.1.

Таблица 20.1

Требуемые свойства

Тип оптимизации

Целевая функция

Область допустимых решений

Максимизация

Вогнутая

Выпуклое множество

Минимизация

Выпуклая

Выпуклое множество

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

Максимизировать или минимизировать z = f(X)

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

g,(X)<0, 1=1,2.....г,

g,(X)>0, i= r+1.....р,

gt(X) = 0, i=p + l.....те.

При этом функция Лагранжа имеет вид

L(X,S,X) = /(X)-±Х,[gl(X) + S?]-±X,[g,(X)-S,2]- £ X,g,(X),

1 = 1 i=r+l / = (,.1

где Я, - множитель Лагранжа, соответствующий i-му ограничению. Требования, которые устанавливают достаточность условий Куна-Таккера, приведены в табл. 20.2.

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