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


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


106

Вычисления условия оптимальности свв- = (0, 0, 0, 0).

Ц " *,Ui - С*Л (Pi. Р.) - <*„ сг) = (-5, -4). Отсюда следует, что вводимым в базис вектором будет Р,. Вычисления условия допустимости

xe„ = (*з> *4> *6. e)r = (24> 6 *> 2)Г-В-Р, =(6, 1,-1, 0)г.

Следовательно,

х, =1шпру,-,- =min{4, 6,-,-}=4, и вектор Р3 определяется как исключаемый из базиса.

Результаты выполненных вычислений представим в виде знакомой симплекс-таблицы. Такое представление поможет сравнить модифицированный и обычный симплекс-методы.

Базис

хг хз

Решение

-Л 0

Итерация 1

Х«, = (*,. *4> *5> *в) СВ, = (5> °> 0> 0)-

(6 О О ОЛ

В.-.Р,, Р5,Рв) =

110 0 -10 10 0 0 0 1,

Используя подходящий метод вычисления обратной матрицы В~ (в разделе А.2.7

приведен метод вычисления обратных матриц на основе их мультипликативного представления), находим

i 0 0 0Л

-110 0 6

i 0 1 о

0 0 0 1

Отсюда получаем

В~ Ь = (4, 2, 5, 2)\ 2 = Св Хв = 20.



Вычисления условия оптимальности

снв: = -,о,о,о

Ц " с)ггя = С„В-1 (Р2, Р3) - (с2, с3) = -,

Отсюда следует, что вводимым в базис будет вектор Р2. Вычисления условия допустимости

ВГР2=1т.т.г.1

2 4 5

Следовательно,

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

Итерация 2

Хв, = (*„ хг, х5, х/, Св, = (5, 4, 0, 0).

В2 = (Р„Р2,Р5,Р6) =

(Ь 4 0 0} 12 0 0 -1110 0 10 1

Находим

в;1 =

i \ 0 0

М 1 0

i л о i

Отсюда получаем

хв, = в2-ь=з,т,т.

z= СЯХЙ. -21.

Вычисления условия оптимальности

ад=(2.1, о, о].

izj - *,U« = С8;В2- (Р3, Р4) - (с3, с4) = , 1 Отсюда следует, что решение ХЛ оптимально. Вычисления заканчиваются. Оптимальное решение:

х. = 3. л:„ = 1.5. 2 = 21.



УПРАЖНЕНИЯ 7.2.2

1. В примере 7.2.1 представьте результаты вычислений, выполненных на первой и второй итерациях, в виде симплекс-таблиц.

2. Решите модифицированным симплекс-методом следующие задачи ЛП.

a) Максимизировать z = 6л:, - 2хг + Зх3 при ограничениях

2 л:, - х2 + 2х3 < 2, х1+4х3<4,

b) Максимизировать г = 2л:, + л:2 4- 2л:3 при ограничениях

4 л:, + Зл:2-1-8д:3< 12, 4 л:, + л:2 +12лг3<8, 4л:,-л:2 + 3л:3<8, л:,, л:2, х3>0.

c) Минимизировать z = 2jc, + л:2 при ограничениях

Зл:, 4- л:2 = 3, 4л:, 4-Зл:2 > 6, л:, 4-2л:2<3, л:,, jc2>0.

d) Минимизировать z = 5jc, - 4л:2 4- 6л:3 4- 8л:4 при ограничениях

л:, + 7л:2 4- Зл:3 4- 7л:4 < 46, Зл:, - л:24-л:34-2л:4<20, 2xl + 3x2-x3 + xi>18,

2 3* 4 ~ *

3. Решите следующую задачу ЛП с помощью модифицированного симплекс-метода, используя в качестве начального базиса вектор = (л:2, л:4, л:5)г.

Минимизировать z = 7х2 + 11л:3 - 10л:4 4- 26л:6 при ограничениях

хг-х3 + х, + хв = 6,

л:2 - л:3 л:4 4- Зл:6 - 8,

л:, 4- л:2 - Зл:3 4- л:4 4- л:5 = 12,

Х\> %2> 3> Ч 5 6 -

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

a) Задача из упражнения 2,с.

b) Задача из упражнения 2,d.

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