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


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


262

К примеру, линейная функция

h(х,, хг,хJ = а,х, + арсг + ... + а.х,, (здесь at, i = 1, 2, п - константы) является сепарабельной. Функция же

h(.xl,x2,xi) = х\ +лг, sin(x, + х3) + х,е*

таковой не является.

Некоторые нелинейные функции сепарабельными непосредственно не являются, однако могут быть приведены к такому виду путем соответствующих подстановок. Рассмотрим, к примеру, задачу максимизации функции z = х,х2. Если ввести обозначение у = х,х2, то Iny = lnxt + lnx2 и задача принимает следующий вид.

Максимизировать z = у

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

\щ = lnx, + lnx2,

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

В случае, когда переменные х, и х2 принимают и нулевые значения (т.е. х,, х2 > 0), можно поступить следующим образом. Пусть Sx и 82 - положительные константы, введем новые переменные wx = х, + 8Х и w2 = х2 + 52. Эти переменные принимают только положительные значения. Теперь имеем

х,х2 = wxw2 - 82wl - 8xw2 + 5Х52.

Пусть у = wxw2, тогда исходная задача эквивалентна следующей.

Максимизировать2 = у - 82и>х - Sxw2 + 8Х62

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

1ш/= lnw, + lnw2, wx>Sv w2>52.

В этой задаче все функции сепарабельные.

Примерами других функций, которые в результате замены переменных приводятся к сепарабельным, могут служить е*- и х,": . В этих случаях для реализации

свойства сепарабельности следует применить соответствующий вариант описанной выше процедуры.

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

Функцию одной переменной f(x) можно аппроксимировать кусочно-линейной функцией с помощью методов частично-целочисленного программирования (глава 9). Пусть требуется аппроксимировать функцию f(x) на интервале [а, Ь]. Обозначим через ак, k=l, 2, К, k-ю точку разбиения интервала [а, Ь], причем а = а, < а2 < ... < аК - Ъ. Тогда функция /(х) аппроксимируется следующей кусочно-линейной функцией:

*=1 *=i



где tk - неотрицательный весовой коэффициент, связанный с fe-й точкой разбиения интервала. Весовые коэффициенты удовлетворяют условию

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

1. Если не больше двух весовых коэффициентов tk имеют положительные значения.

2. Если значение tk больше нуля, то положительным может оказаться лишь один из смежных весовых коэффициентов tk+1 или tk x.

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

Максимизировать (минимизировать) z = (х>)

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

2>/7 = 1,2.....т.

Эту задачу можно привести к задаче частично-целочисленного программирования следующим образом. Обозначим через К, число точек разбиения для i-й переменной х,, а через а- - k-ю точку разбиения. Пусть f* - весовой коэффициент, ассоциируемый с k-й точкой разбиения для i-й переменной. Тогда эквивалентная задача частично-целочисленного программирования имеет вид

максимизировать (или минимизировать) г = Х- (а* К

: = 1 *=1

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

±ts!Wr у = 1,2,...,и.

1=1 *=i

0<t<y], i=l, 2,.... re, 0<г* < у,* 1 +у* к = 2,3.....AT, - I,

К,-1

у{=0 или 1, it = 1,2.....К„ = 1,2,...,л.

В аппроксимирующей задаче переменными являются / и у- .

Данное представление свидетельствует о том, что в принципе любая задача сепарабельного программирования может быть решена методами частично-



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

Для решения аппроксимирующей задачи можно использовать также обычный симплекс-метод (глава 3), дополненный правилом ограниченного ввода в базис. В этом случае игнорируются вспомогательные ограничения, содержащие у*. Согласно данному правилу в базисе может находиться не более двух положительных весовых коэффициентов if. Более того, два коэффициента if могут быть положительными лишь тогда, когда они являются смежными. Таким образом, строгое условие оптимальности симплекс-метода только тогда используется для выбора переменной /*, подлежащей введению в число базисных, когда она удовлетворяет

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

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

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

Пример 21.2.1

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

Максимизировать z = х, + х\

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

Зх, + 2х; < 9, хр х2 > 0.

Точное оптимальное решение этой задачи находится непосредственной проверкой: х, =0, х2 = 2,12 и г* = 20,25. Чтобы продемонстрировать использование метода аппроксимации, рассмотрим отдельные функции

/,(*,) = *,> *>(*>) = 3jfi-

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