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


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


265

21.2.2. Квадратичное программирование

Задача квадратичного программирования имеет следующий вид.

Максимизировать (или минимизировать) г = СХ + XTDX

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

АХ<Ь, Х>0

X - (х,, х2.....xJT,

С - (Cj, с2, сь), b = (b,,b2, ...,bm)T,

tin J

Функция XTDX, где D - симметрическая матрица, является квадратичной формой (см. раздел А.З). Матрица D будет отрицательно определенной в задаче максимизации и положительно определенной - в задаче минимизации. Это означает, что функция z является строго выпуклой по переменным X в задаче минимизации и строго вогнутой - в задаче максимизации. Ограничения в этой задаче предполагаются линейными, что гарантирует выпуклость области допустимых решений.

Решение сформулированной задачи основано на использовании необходимых условий Куна-Таккера. Так как целевая функция z строго выпуклая (или вогнутая) и область допустимых решений задачи является выпуклым множеством, эти условия (как показано в разделе 20.2.2) также достаточны для установления наличия глобального оптимума.

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

Обозначим через X = (Я,, Л2, Лт)т и U = ( ,, цг, рУ множители Лагранжа, связанные с ограничениями АХ - b < 0 и -X < 0 соответственно. Применяя условия Куна-Таккера, получаем

Максимизировать г = СХ + XTDX

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

X>0,U>0, Vz - (Х\ UT)VG(X) = 0,



= 0, I = 1, 2,т,

UjXj = 0,j = l, 2, ...,п, АХ<Ь, -Х<0.

Отсюда имеем

VG(X) =

Vz = С + 2XTD,

Обозначим через S = b - АХ > 0 вектор дополнительных (остаточных) переменных. Тогда приведенные выше условия принимают следующий вид.

-2XTD + ХТА - UT = С, AX + S=b, UjXj = 0 = XiSi для всех i и j, X,U,X,S>0.

Так как DT = D, в результате транспонирования первой системы уравнений получим

-2DX + АТХ - U = Ст. Следовательно, необходимые условия можно записать в виде

-2D А -I 0 АО 0 1

гс>л

4°,

= 0 = XiSi для всех i и j, X, U, X, S > 0.

Все уравнения, за исключением pxj = О = ЯД, являются линейными относительно переменных X, X, U и S. Следовательно, исходная задача сводится к поиску решения системы линейных уравнений, удовлетворяющему дополнительным условиям fipc! = 0 = \St. Поскольку функция z строго вогнутая, а область допустимых решений представляет собой выпуклое множество, допустимое решение, удовлетворяющее всем этим условиям, должно быть единственным и оптимальным.

Решение рассматриваемой системы находится путем реализации этапа I двух-этапного метода (раздел 3.4.2). При этом единственным ограничением является необходимость удовлетворения условий ЯД = 0 = х. Выполнение этого условия означает, что если переменная Я( в базисном решении принимает положительное значение, то переменная S, не может быть базисной и принимать положительное значение. Аналогично переменные Ц. и х. не могут одновременно принимать положительные значения. Это обстоятельство подобно правилу ограниченного ввода в базис, которое было использовано в разделе 21.2.1.

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



Пример 21.2.3

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

Максимизировать г = 4х, + 6х, - 2х[ - 2х,х, - 2х;

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

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

Эту задачу можно записать в матричной форме

r-2 -iy*.

максимизировать г = (4, 6) +(х,,х2)

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

(1,2),2, х„х2>0.

Условия Куна-Таккера принимают следующий вид.

(4 2 1 2 4 2 1 2 О

-1 0 0 0-10 0 0 I,

Ч51 )

Начальная симплекс-таблица для этапа I строится путем введения искусственных переменных /?, и R2. Имеем

Базис

Решение

Итерация 1. Поскольку , = 0, вводимой в базис переменной может быть х,, при этом из числа базисных исключается переменная Rr Получаем следующую симплекс-таблицу .

Базис

Решение

-3/2

-1/4

-1/2

-1/4

-1/4

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