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


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


263

g;(x2) = 2xl

Функции/,(х,) и gl(xt) остаются в исходном виде, поскольку они уже являются линейными. В этом случае дг, рассматривается как одна из переменных. Для функций /2(х2) и g~{x,) полагаем, что количество точек разбиения равно четырем (Кг = 4). Так

как значение*,, не может превышать 3, отсюда следуют данные, приведенные ниже.

**№)

Получаем

fM) = t\fM) + if(«Ч) + If,) + t.f, №) =

= 0 х t\ +1 х t2 +16 х t\ + 81 х f4 = i; +1 btl + 8 If*.

Аналогично

£,2(x,) = 2f2+8f3 + 18f:4. Следовательно, аппроксимирующая задача принимает вид

максимизировать z = х, +t; + 16f3 + 8 If4

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

Зх,+2f;+8f,3+18f24<9, t\+t;+tl+!* = {, f* >0, Jt = 1,2,3,4, xO.

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

Базис

Решение

Здесь 5, (> 0) - дополнительная (остаточная) переменная. (В этой задаче начальное решение является очевидным. В общем же случае для его получения могут понадобиться искусственные переменные, см. раздел 3.4.)

Коэффициенты г-строки указывают на то, что в число базисных необходимо ввести переменную /*. Поскольку при этом переменная t\ уже входит в базисные в силу



правила ограниченного ввода в базис, она должна быть выведена из числа базисных перед тем, как базисной станет переменная /,4. Вместе с тем, согласно условию допустимости при введении в базисные переменной t* переменная s, должна выводиться из базиса. Это значит, что t\ нельзя сделать базисной. Следующей подходящей для введения в базисные является переменная t\. Снова при этом переменная t\ должна быть выведена из числа базисных. Условие допустимости на этот раз позволяет вывести из числа базисных переменную t\, что и требуется. Таким образом, получаем новую симплекс-таблицу.

Базис

Решение

Очевидно, что базисной следует сделать переменную t\ . То, что переменная t\ уже

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

Базис

Решение

37/2

13/2

45/2

3/10

-6/10

1/10

-8/10

1/10

-3/10

16/10

-1/10

18/10

9/10

Из этой таблицы следует, что в базис могут вводиться переменные t\ и t;. Переменная t\ не может быть базисной, поскольку не является смежной с переменными / и /2, которые уже находятся среди базисных. Далее, переменную гг также нельзя сделать базисной, поскольку t* нельзя исключить из числа базисных. Поэтому

процедура решения задачи на этом завершается, и полученное решение является наилучшим допустимым решением аппроксимирующей задачи.

Воспользуемся найденными значениями t\ = 9/10 и(= 1/10, чтобы выразить полученное решение через переменные х, их,. Получаем

х, = 0, х2~ 2t32+3t4=2j+3j=2,l, z = 0 + 2,14 = 22,5.

Полученное приближенное оптимальное значение для хг (=2,1) мало отличается от истинного оптимального значения (= 2,12).

Сепарабельное выпуклое программирование. Задача выпуклого сепарабельного программирования возникает в том случае, когда функции g!(xt) являются вы-



пуклыми, обеспечивая, таким образом, выпуклость области допустимых решений. Кроме того, считаем, что функции f,(x:) являются выпуклыми в задаче минимизации и вогнутыми в задаче максимизации (см. табл. 20.2 в разделе 20.2.2). При этих условиях можно использовать следующий упрощенный метод аппроксимации.

Рассмотрим задачу минимизации. Пусть функция ft(x) имеет такой вид, как показано на рис. 21.4. Обозначим точки разбиения для функции fx) через xt = ам, k = 0, 1, К,. Пусть xhi - величина изменения переменной xt на интервале (ак , ак), А = 1, 2,К,, a.ph - тангенс угла наклона линейного сегмента на том же интервале.

Тогда

Рис. 21.4. Кусочно-линейная аппроксимация выпуклой функции

Здесь предполагается, что 0 < хы < аы - a„ u, k = 1, 2, Кг

Так как функция /Дх,) выпуклая, то р„ < р,; <... < pKi,. Это означает, что в задаче

минимизации при р < q большее влияние на значение целевой функции оказывает переменная хр1, чем xql. Следовательно, переменная хр1 всегда будет входить в решение до того, как в него войдет xql При этом значения каждой переменной хк1 должны быть ограничены сверху величиной (ак1 - а4 ,,).

Выпуклые функции ограничений #/(л->) аппроксимируются аналогичным образом. Пусть pi, - тангенс угла наклона ft-го линейного сегмента, соответствующего функции #/(-*,). Тогда функция аппроксимируется формулой

Следовательно, рассматриваемая задача принимает вид

I ( К:

минимизировать z = 9ихк: + / (а0,)

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

0<хк1<ак1- ак и, k=l, 2, tf„ i = 1, 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]