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


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


110

+ АпХл = bo

= Ь,

= ь2

D„Xn = Ьл

Х;>0, ; = 1,2.....п.

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

Метод декомпозиции основан на определении крайних точек множеств {Xj DyXy = b;, Ху > О}, / = 1, 2, п. Для этого необходимо, чтобы каждое множество {XjXb,, Ху>0} было ограниченным. Это требование выполнимо всегда, поскольку при необходимости для любого множества / можно добавить искусственное ограничение IX. < М, где М - достаточно большое положительное число.

Обозначим через Yyt, k=l, 2, KJt крайние точки множества {XjDXb X. > 0}. Тогда можно записать

ху=ЕРЛ У-1.2,..., п,

где Р>4 > 0 для всех k и /*, причем = 1.

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

*1 к. к.

Максимизировать z = XCiyi.Pu +ZC2Y2*P2. + - + ZC»Y»»P«* при ограничениях

I A.Y»P" +I a2y..p*+-+=b0.

4=1 4=1 4 = 1

IP- =1-

4 = 1

P > 0 для всех k и j.

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

вычисляется путем обратных подстановок по следующей формуле.

Х,=1Р"Л , / = 1,2,...,п.

4 = 1

AiXi + D,X,

А2Х2 + D2X2



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

При решении главной задачи с использованием модифицированного симплекс-метода (раздел 7.2) на каждой итерации нам необходимо определить вводимую и исключаемую переменные. Начнем с определения вводимой переменной. Зная текущий базис главной задачи (и, следовательно, матрицы Св и В"1), для любой небазисной переменной Pyt. имеем

-СвВ"Р-Сд,

j Х1к

Напомним: чтобы определить, какая из небазисных переменных Рук должна войти в базис, следует найти

гг1.-с,.к.= min {zjk-cjt\.

по всем] и к

Если z .к. -с/,1, <0 , тогда в соответствии с условием оптимальности задачи максимизации переменная р t, должна войти в базис. При выполнении обратного нера-

с;,4.. "Секрет" вычисле-

венства считаем, что оптимальное решение достигнуто. Теперь покажем, как можно вычислить разность zf

ний заключается в равенстве

min \zjk-ск} = mm\mm{zJk -с,}}

Это равенство вытекает из того, что каждое выпуклое множество, определяемое ограничениями DX; = Ьу, Ху > 0, имеет собственное независимое множество крайних точек. В соответствии с этим равенством мы можем найти разность 7ч,к. - cJ4. за два этапа.

1. Для каждого выпуклого множества {XjDXb, Х>0} определяем крайнюю точку Yjk„ на которой достигается минимум разностей zjk - cjk, т.е. zjk, -<: = mmk{zik-cjk}.

2. Далее определяем zt.k,-crk, =mmi{zjkt- с1к,}.

Из теории линейного программирования мы знаем, что конечное оптимальное решение ассоциируется с крайней точкой пространства решений. Поскольку каждое из множеств {X. D;X. = b;, Х; > 0} ограничено по определению, действия, выполняемые в п. 1, математически эквивалентны решению п задач линейного программирования вида

минимизировать wj = {z; - cj D.X. = Ъг Ху > 0}.

Фактически здесь целевая функция wj является линейной функцией от Ху (см. упражнение 7.4.1.8).

Таким образом, определение вводимой переменной pfk, в главной задаче сведено к решению п задач линейного программирования (меньшего размера) для вычис-



ления "вводимых" крайних точек Yy,t.. Такой подход не требует определения всех крайних точек всех п выпуклых множеств. После того как требуемая крайняя точка определена, нетрудно определить все элементы вектора Р . На основе этой информации мы можем определить исключаемую переменную. Далее с помощью модифицированного симплекс-метода вычисляем следующую обратную матрицу В"1.

Пример 7.4.1

Решим с помощью метода декомпозиции следующую задачу ЛП.

Максимизировать z = Здс, + 5х2 + х3 + х4

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

х, + х2 + х3 + х4 < 40, 5x, + x2<12, х3 + х4> 5, х3 + 5х4 < 50, Х, х2, х3, х4 - 0.

Данную задачу можно разбить на две подзадачи, которым будут соответствовать следующие множества переменных:

X, = (xv х2) , Х2 = (х3, х4) .

Основную задачу можно записать следующим образом.

Подзадача 1

Подзадача 2

Начальное базисное решение

Р" Р« - Р„,

р21 ргг - р2а:,

Х5 Хб х7

С,Уц C,Y12 C,YlK,

C2Y21 C2Y22 ... C,Y,,

0 -М -М

AiY,, A,Y12 ... A,Y,X]

1 1 ... 1 0 0 ... 0

AaY21 AaY22 ... A,Y2Jt,

0 0 ... 0

1 1 ... 1

1 0 0 =40

0 1 0 =1 0 0 1 =1

С, = (3, 5), А, = (1, 1). Пространство решений D1X1 < Ьь 5xi +х2 < 12, xi, х2 >0.

C2 = (1, 1), Аг = (1. 1). Пространство решений 02Хг < b2: Хз + xi > 5, хз + 5xi < 50,

Хз, Х4 > 0.

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

jCj + х2 + х3 + х4 + хь = 40.

Эта переменная не входит ни в одну подзадачу, ее значение находится как часть решения главной задачи. Другие переменные в начальном базисе, хе и х7, являются искусственными переменными.

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