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


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


254

Рис. 20.6. Пространство решений задачи ЛП

В точке (3, О) целевая функция двойственной задачи равна 5и, + Зиг = 15 и совпадает с оптимальным значением целевой функции прямой задачи. Полученное решение также удовлетворяет ограничениям двойственной задачи, т.е. является допустимым и, следовательно, оптимальным. Это значит, что коэффициенты чувствительности совпадают с переменными двойственной задачи линейного программирования.

Из процедуры применения метода Якоби к решению задач линейного программирования можно сделать несколько общих выводов. Рассмотренный численный пример показывает, что в силу необходимых условий экстремума независимые переменные задачи равны нулю. Достаточные же условия указывают на то, что матрица Гессе является диагональной. Следовательно, все диагональные элементы этой матрицы должны быть положительными, если в рассматриваемой точке имеет место минимум, и отрицательными - в случае максимума.

Из вышесказанного следует, что необходимое условие экстремума равносильно указанию на то, что оптимальное решение задачи следует искать только среди ее базисных решений. В этом случае в качестве небазисных переменных задачи линейного программирования выступают независимые переменные. Достаточное же условие приводит к выводу, что между диагональными элементами матрицы Гессе и разностями zf - с, задачи линейного программирования (см. раздел 7.2), получаемыми с помощью симплекс-метода, существует строгое соответствие.1

УПРАЖНЕНИЯ 20.2.2

1. Предположим, что задача из примера 20.2.2 решена следующим образом. Сначала из ограничений задачи выражаем переменные дг, и хг через дс3; затем используем полученные соотношения для представления целевой функции в зависимости лишь от переменной х3. Дифференцируя полученную целевую функцию по х3, находим точки минимума и максимума.

1 Формальное доказательство справедливости этих утверждений для общей задачи линейного программирования можно найти в статье Taha Н. and Curry G. "Classical Derivation of the Necessary and Sufficient Conditions for Optimal Linear Programs", Operations Research, Vol. 19, 1971, pp.1045-1049. В этой статье показано, что все основные положения симплекс-метода могут быть получены с помощью метода Якоби.



a) Будут ли производные новой целевой функции (выраженные через переменную х3) отличаться от полученных с помощью метода Якоби?

b) В чем основное отличие описанной процедуры решения задачи от метода Якоби?

2. Примените метод Якоби к решению задачи из примера 20.2.1, выбирая Y = (x2, х3) и Z = (x,).

3. С помощью метода Якоби решите следующую задачу.

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

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

П* = с,

где С - положительная константа. Пусть теперь правая часть ограничения равна С + S, где S- малое положительное число. Найдите соответствующее изменение оптимального значения целевой функции /.

4. Решите методом Якоби следующую задачу.

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

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

g(X) = Xlx2 - 10 = 0.

a) Найдите изменение оптимального значения целевой функции /(X), если ограничение задачи примет вид хух2 - 9,99 = 0.

b) Найдите изменение значения целевой функции /(X) в окрестности допустимой точки (2, 5) при условии, что х1х2 = 9,99 и Эх, = 0,01.

5. Решите следующую задачу.

Максимизировать /(X) = х2 + 2х\ + КЪг2 + 5х,х2

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

g, (X) = х, + х\ + Ъхгхг -5 = 0,

g2 (X) = х,2 + 5х,х2 + х32 - 7 = 0.

Используйте метод Якоби для нахождения df(X) в окрестности допустимой точки (1, 1, 1). Пусть указанная окрестность определяется условиями dgl = -0,01, dg2 = 0,02 и дх1 = 0,01.

6. Решите следующую задачу.

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

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

g,(X) = хг + 2х2 + Зха + 5xt - 10 = 0,

g2(X) = х1 + 2х2 + 5х3 + 6х4 -15 = 0.

а) Покажите, что при выборе х3 и xt в качестве независимых переменных метод Якоби не дает оптимального решения.



b) Решите задачу, выбрав х, и х3 в качестве независимых переменных, и примените достаточные условия для исследования полученной стационарной точки.

c) Найдите коэффициенты чувствительности для этой задачи. 7. Решите следующую задачу линейного программирования.

Максимизировать /(Х) = с;ху

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

й(Х) = Е«Л-*,=0. - = 1,2,..., и,

х>0, j=l, 2, п.

Покажите, что если в этой задаче пренебречь условиями неотрицательности переменных, то приведенные производные Vcf(X) совпадают с разностями Ц-cv}, определяемыми условием оптимальности задачи линейного программирования (раздел 7.2), а именно

{Zj - с) = {CP, - с) для всех

Можно ли непосредственно применять метод приведенного градиента к решению задачи линейного программирования? Почему можно или почему нельзя?

Метод множителей Лагранжа. Коэффициенты чувствительности метода Якоби можно использовать для решения задач с ограничениями в виде равенств. Пусть

>i = v¥j-=£.

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

df-kdg = 0.

Это уравнение соответствует необходимым условиям стационарности точек, так как формула для - получена с учетом того, что Vcf = 0. Представленное уравнение

можно записать в более удобной форме, если перейти к частным производным по всем переменным xjt что приводит к системе уравнений

т-(/-»в) = о, У = 1,2,...,«.

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

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

L(X, X) = f(X)-Xdg(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] [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]