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


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


258

Таблица 20.2

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

Тип оптимизации fl[X)

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

Минимизация

Вогнутая

Выпуклая

Выпуклая Вогнутая Линейная

Выпуклая

Вогнутая

Линейная

>0 (1</<г)

<0 (r + \<i<p)

Нет ограничений (р +1 < i < /и)

<0 (1 <i <г)

> 0 (г +1 < i < р)

Нет ограничений (p + \<i<m)

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

Законность положений табл. 20.2 основана на том, что при сформулированных условиях функция Лагранжа L(X, S, Я) является вогнутой в задаче максимизации и выпуклой - в задаче минимизации. Это подтверждается тем, что если £,(Х) - выпуклая функция, то функция Яд(Х) оказывается выпуклой при Я,>0 и вогнутой- при Я, <0. Аналогичные рассуждения подтверждают все остальные условия. Заметим также, что линейная функция является как выпуклой, так и вогнутой. Наконец, если функция f вогнутая, то функция -/ является выпуклой, и наоборот.

Пример 20.2.7

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

Минимизировать /(X) = х,2 + х2 + х,

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

gl(X) = 2x,+x2-5<0, g2(X) = x,+x3-2<0, g,(X)=l-x,S0, g4(X) = 2-x2<0, g5(X) = -*3<0.

Поскольку рассматривается задача минимизации, то к < 0. Поэтому условия Куна-Таккера записываются в следующем виде.

(Я,, Я2, Я3, Я4, Я5) < 0,

(2 10)

(2х;2х2,2хз)-(Х,Д2ДзД4Д5)

1 0 1 -10 0 0-10 0 0-1

= 0,



g(X)<0.

Эти условия можно упростить и привести к виду

Я,, Я2, Я3, Я4, Я6 < О, 2х, - 2Я, - Я2 + Я3 = О, 2х2 - Я, + Я4 = О, 2х3 - Я2 + Я5 = О, Я,(2х, +х2- 5) = О, Я2(х,+х3-2) = 0, Я3(1-х,) = 0, Я4(2-х2) = 0,

2х,+х2<5,

х,+х3<2,

х,>1,х2>2,х3>0.

Отсюда получаем решение: х, = 1, х2 = 2, х3 = 0, Я, = Я2 = Я5 = О, Я3 = -2, Я4 = -4. Поскольку и целевая функция ДХ), и область допустимых решений g(X) < 0 являются выпуклыми, функция L(X, S, X) также должна быть выпуклой, и полученная стационарная точка определяет глобальный минимум задачи. Рассмотренный пример показывает также, что решение системы, порожденной условиями Куна-Таккера, в явной форме может быть затруднительным. Следовательно, для численных расчетов описанная процедура не подходит. Тем не менее условия Куна-Таккера играют основополагающую роль при рассмотрении алгоритмов решения задач нелинейного программирования в главе 21.

УПРАЖНЕНИЯ 20.2.4

1. Покажите, что условия Куна-Таккера для задачи

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

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

g(X)>0

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

2. Дана следующая задача.

Максимизировать /(X)

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

g(X) = 0.

Покажите, что условия Куна-Таккера для этой задачи имеют вид

Vf(X)-XVg(X) = 0, g(X) = 0, X по знаку не ограничен.



3. Запишите необходимые условия Куна-Таккера для следующих задач.

a) Максимизировать /(X) = х3 -xl + х,х2

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

х, + xj + х, = 5, 5х2 - xl - хъ > 0, х,>0, х2>0, х3>0.

b) Минимизировать /(X) = х4 + х22 + 5х,;с2х,

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

*2-x2+.x33 <10, х, +х22+4д:220.

4. Дана задача

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

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

g(X) = 0.

Пусть ДХ) - вогнутая функция, а g,(X) (t = 1, 2, т) - линейные функции. Покажите, что в этом случае необходимые условия Куна-Таккера оказываются также и достаточными. Верно ли последнее утверждение, если ёДХ) является выпуклой нелинейной функцией для всех г? Почему?

5. Дана задача

максимизировать /(X)

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

gi(X)>0,g2(X) = 0,g3(X)<0.

Сформулируйте условия Куна-Таккера для данной задачи и установите требования к функциям, при реализации которых выполняются указанные условия.

ЛИТЕРАТУРА

1. Bazaraa М., Shrali Н. and Shetty С. Nonlinear Programming Theory and Algorithms, 2nd ed., Wiley, New York, 1993. (Существует перевод первого издания: Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. - М.:Мир, 1982.)

2. Beightler С, Phillips D. and Wilde D. Foundations of Optimization, 2nd ed., Prentice Hall, N. J., 1979.

3. Rardin R. Optimization in Operations Research, Prentice Hall, N. J., 1998.

Литература, добавленная при переводе

1. Банди Б. Методы оптимизации. Вводный курс. - М.: Радио и связь, 1988.

2. Зангвилл У. И. Нелинейное программирование. - М.: Сов. радио, 1973.

3. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. - М.: Наука, 1986.

4. Поляк Б. Т. Введение в оптимизацию. - М.: Наука, 1983.

5. Химмельблау Д. Прикладное нелинейное программирование. - М.: Мир, 1975.

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