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


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


266

Итерация 2. Так как /и2 = 0, вводимой в базис переменной является х2. В результате приходим к следующей таблице.

Базис

Решение

-1/3

-1/3

-1/6

-1/6

Итерация 3.

Так как

*i =

0, в число базисных можно ввести переменную Яг В ре-

зультате получаем симплекс-таблицу.

Базис

Решение

-1/3

-1/6

-1/2

-1/12

-1/6

1/12

Последняя таблица дает оптимальное решение рассматриваемой на этапе I задачи. Так как г = 0, полученное решение х, = 1/3, хг = 5/6 является допустимым. Оптимальное значение z вычисляется подстановкой полученного решения в выражение для целевой функции исходной задачи и равняется 4,16.

Средство Excel Поиск решения можно использовать для решения задач квадратичного программирования. На рис. 21.5 показано решение задачи из данного примера (файл ch21SolverQuadraticProgramming.xls). Исходные данные для задачи представлены в таком же виде, как и в задачах линейного программирования (см. раздел 2.4.2). Основное отличие состоит в том, что целевая функция сейчас нелинейна. Поскольку в данном примере целевая функция имеет вид

z = 4х, + 6х, - Ix1 ~ х,х2 - 2x1,

в ячейку D5 записывается формула

=4*В10+6*С10-2*В10*2-2*810*С10-2*С10*2

Здесь в ячейках В10 и СЮ записаны значения х, и х2. Отметим, что ячейки В5:С5 не используются (в отличие от задач линейного программирования), поэтому мы ввели в них значения NL, показывающие, что ограничения нелинейны. Чтобы указать, что переменные неотрицательны, надо или установить соответствующую опцию в диалоговом окне Параметры или задать нужные ограничения непосредственно в диалоговом окне Поиск решения.



« =4*В10+6*С10-2*В10Л2-2"В1и*С10-2*С10Л2

el .

Quadratic Programming Model

Input data:

Totals

Limits

Objective

4 16P6R7

Constraint

2 ,

<=

>=0

>=0

Output results:

Solution

0 333333

0 833333

4 166667

Поиск . ешения

установить целевую ячейку $D$5 Равной. уаксимальноиу значению г

f минимальному значению Изменяя ячейки

Рис. 21.5. Решение в Excel задачи примера 21.2.3

УПРАЖНЕНИЯ 21.2.2

1. Дана задача, в которой требуется

максимизировать z = 6х, + Ъх2 - 4jc,x2 - 2х\ - Ъх\

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

JC, + х2< 1, 2хх + Зх2 < 4, xt, х2> 0.

Покажите, что г - строго вогнутая функция, и решите задачу, используя алгоритм квадратичного программирования.

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

Минимизировать z = 2х,2 + 2х\ + Ъх] + 2хххг + 2х2х} +х,- Ъх2 - 5х3

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

X. + X, + X > 1,

1 2 d

3xl + 2x2 + xa<6, X ) ~ 0»

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



21.2.3. Геометрическое программирование

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

Методами геометрического программирования решаются нелинейные задачи, в которых как целевая функция, так и функции ограничений имеют следующий вид:

г = /(Х) =

uj=cjfl*?> У = Ь2,...,Л.

Предполагается, что здесь все с;. > 0, а число N является конечным. Показатели степени atj по знаку не ограничены. Функция /(X) имеет вид полинома, если не учитывать того, что показатели степени atj могут принимать отрицательные значения. По этой причине, а также в связи с тем, что все коэффициенты с; > 0, функция /(X) называется позиномом.

В этом разделе будут рассмотрены задачи геометрического программирования без ограничений. Исследование задач геометрического программирования с ограничениями выходит за рамки настоящей главы. Детальное рассмотрение излагаемых здесь вопросов содержится в книге [2], глава 6.

Рассмотрим задачу минимизации позиномиальной функции /(X). Будем называть эту задачу прямой. Предполагается, что переменные xt принимают строго положительные значения, т.е. область xt < 0 недопустима. Далее будет показано, что требование х Ф 0 является существенным при получении основных результатов.

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

Поскольку по предположению все хк > 0, имеем

= 0 = -JXt/., А =1,2,...,я.

Эх x,

к У-1

Пусть z - минимальное значение функции z. Очевидно, что z > 0, так как z - по-зином, и все хк > 0. Обозначим

Из определения следует, что у1 > 0 и X-i-vj = Величина yt характеризует относительный вклад у-го слагаемого V в оптимальное значение целевой функции z. Необходимые условия экстремума теперь можно записать в следующем виде.

I>V,=0. к = 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]