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


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


264

, g/K)-g/K-u)

Pt; -

Задача максимизации преобразуется аналогично. В этом случае р„ >p2l >...>pKl,

откуда следует, что при р < q переменная х всегда будет входить в решение раньше хд1 (см. упражнение 21.2.1.7).

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

Пример 21.2.2

Рассмотрим задачу

максимизировать z = х, - х2

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

Зх4+х2<243, х1+2х\<Ъ2, х,>2,1, х2>3,5.

Отдельными (сепарабельными) функциями этой задачи являются

У!(*.) = *.. Ь{хг) = ~хг< «j(x1) = 3x14, g\{x2) = x2,

gl{*\) = x\> gl{xi) = 2xl-Эти функции выпуклые, что и требуется в задачах минимизации.

Область допустимых значений переменных хх и х2, как следует из ограничений задачи, определяется неравенствами 0<Xj<3 и 0<х2<4. Разбиваем эти интервалы изменения переменных х, и х2. Пусть А", = 3 и К2 = 4 при а01 = а02 = 0. Значения тангенсов углов наклона, соответствующих отдельным функциям рассматриваемой задачи, приведены в следующих таблицах.

Для i = 1 имеем

U (вил) = вил

*i(a.i) = 3a*i

S.2(a.i) = ati



Для i = 2 имеем

Теперь задача принимает следующий вид.

Минимизировать z ~ хп + х21 + х31 - х12 - х22 - х32 - х42 при ограничениях

Зхи + 45х21 + 195х31 +х12 +х22 + х32 +х42< 243, хп +х21 +х31 + 2х12 + 6х22 + Юх32 + 14х42 < 32, хп +х21 "Ьх31 2,1,

*12 + 22 + 32 + Xi2 S 3,5,

0<xtl < 1, к= 1, 2, 3, 0<xi2< 1,к= 1,2,3,4. С помощью программы TORA получено следующее оптимальное решение:

z = -0,52, хп = х12 = 1, х13 = 0,98, х21 = х22 = х23 = 1, х24 = 0,5. Отсюда получаем решение исходной задачи (х,, х2) = (2,98, 3,5).

УПРАЖНЕНИЯ 21.2.1

1. Для следующей задачи постройте аппроксимирующую модель в виде задачи частично-целочисленного программирования.

Максимизировать z = е~х + х, + (х2 +1)2

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

х,2 + х2 < 3, х,, х2>0.

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

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

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

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

х,2 + х, + х3 < 4, х,, х2, х3 > 0.

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



4. Покажите, каким образом приведенная ниже задача может быть приведена к сепарабельному виду.

Максимизировать г = х,х2 + х3 + х,х3

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

х,х2 + хг + х,х3 < 10,

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

Минимизировать z = е2"*"*2 + (х3 - 2)2

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

х, + х2 + х3 < 6, хх,х2, х3>0.

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

Максимизировать z = eVl + XjX3 + х4

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

хх + х2х3 + х3 < 10,

х4 не ограничена в знаке.

7. Покажите, что при реализации метода выпуклого сепарабельного программирования оптимальное решение не содержит переменной хк1 > 0, если переменная хк Х1 не достигает своей верхней границы.

8. Решите представленную ниже задачу как задачу выпуклого сепарабельного программирования.

Минимизировать z-xf + 2х2 + х]

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

х2 + х, + Хз < 4,

х,+х,<0,

х„ х3>0, х2 не ограничена в знаке.

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

Минимизировать г = (х, - 2)2 + 4(х2 - б)2 при ограничениях

6х, + 3(х2 + 1)2< 12, хх, х2>0.

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