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


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


115

Первое и третье неравенства выполняются при всех положительных t (напомним, что t > 0), второе - справедливо при t < 1. Отсюда имеем, что £, = 1, т.е. решение остается оптимальным (и допустимым) для всех t из интервала 0 < t < 1.

При t = 1 разность z4(f) - ct(t) = 1 -1 равна нулю и становится отрицательной при t > 1. Поэтому при f > 1 вектор Р4 должен войти в базис, тогда вектор Р2 будет исключен из базиса (см. симплекс-таблицу с оптимальным решением при t = 0). Итак, при t = 1 (вследствие включения в базис вектора Р4) получаем новое решение Х .

Оптимальное решение при f, = 1. Имеем новый базис и новую обратную матрицу.

\ .1 о4

. ВГ =

о ; о

0 0 1,

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

Х = (xt, х3, хв)т = В-Ь = (10, 30, 30)т, Ся(0 =(0, 5 + 5i, 0).

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

{C,(0Br-P,-ciW}=(.-2 + 2i.)20

В соответствии с этими условиями базисное решение Хв остается оптимальным для

всех t > 1. Это означает, что t2 = °° и вычислительный процесс параметрического анализа закончен. Отметим, что условие оптимальности -2 + 2t > 0 автоматически "запомнило", что решение Х оптимально в интервале, который начинается со значения £, = 1. Такое "запоминание" всегда имеет место при параметрическом анализе.

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

0< f< 1

160 + 140г

t> 1

150 + 150f

УПРАЖНЕНИЯ 7.6.1

1. Пусть в примере 7.6.1 параметр t может принимать как положительные, так и отрицательные значения. Определите интервал изменения значений параметра t, при которых решение Х% остается оптимальным.

2. Проведите параметрический анализ задачи ЛП из примера 7.6.1, если целевая функция задана следующими выражениями.

a) Максимизировать z = (3 + 3i) xt + 2х2 + (5 - 6t) х3.

b) Максимизировать z = (3 - 2t) xx + (2 +1) x2 + (5 + 2t) x3.

c) Максимизировать z = (3 +1) дг1 + (2 + 2t) x2 + (5 - t) x3.



3. Проведите параметрический анализ оптимального решения следующей задачи ЛП, здесь t > 0.

Минимизировать z = (4 - t) xl + (1 - 3t) x2 + (2 - 2t) x3 при ограничениях

3jc, +Je2+ 2x3 = 3, 4xt + 3x3 + 2x3 > 6, jc, + 2x2 + bx3 < 4,

X j j ОС - 0 •

4. При выполнении параметрического анализа в этом разделе предполагалось, что оптимальное решение задачи ЛП при t = 0 получено обычным симплекс-методом. Однако в некоторых ситуациях предпочтительнее получить оптимальное решение двойственным симплекс-методом (раздел 4.4). Разработайте схему проведения параметрического анализа для такого случая и выполните анализ задачи ЛП из примера 4.4.1, предполагая, что целевая функция задана следующим выражением.

Минимизировать z = (3 + t) xl + (2 + 4t) x2

5. Пусть в примере 7.6.1 целевая функция нелинейная по t (t > 0) и задается следующим выражением.

Максимизировать z = (3 + 2t2) jc, + (2 - 2t2) x2 + (5 - t) x3.

Найдите первое критическое значение tv

7.6.2. Параметрическое изменение правых частей ограничений

Параметрическое изменение вектора правых частей ограничений Ь(£) влияет только на свойство допустимости решения. В этом случае критические значения параметра t определяются на основе условия

Х„ = ВЬ(0>0.

Пример 7.6.2

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

Максимизировать z = Зх1 + 2х2 + Ъх3

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

х, + 2х2 + x3<40~t, 3x1 + 2x3<60 + 2t, xl + 4х2 < 30 - It,

Предполагается, что t > 0.

Оптимальное решение этой задачи при t = 10 = 0 приведено в примере 7.6.1. Имеем

ХВ(] = (*„ х3, х/ = (5, 30, 10)т,

1 о

1 1.



Чтобы найти первое критическое значение используем условие допустимости Хя = В„Ь(/) > 0, которое в данном случае примет вид

5-t N

30 + f

>

\хь)

,10-3/,

Эти неравенства выполняются при t < 10/3. Таким образом, = 10/3, и базис В0 остается допустимым при изменении параметра t в интервале 0 < t < 10/3. Отметим, что здесь значения базисных переменных хг, х3 и хв изменяются при изменении параметра t.

Значение базисной переменной х6 (= 10 - 3t) равно нулю при t = tх = 10/3 и становится отрицательным для t > 10/3. Следовательно, при t = 10/3 необходимо определить новый базис В,. Для этого применим модифицированный симплекс-метод (см. упражнение 7.2.2.5). Исключаемой из базиса будет переменная х6.

Новый базис при t = 10/3.

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

х«„ = (Х2> хз> *в) и ся„ С) = (2> 5> °)>

к-и,={в0-ру-сл14а-(4,1,2).

Далее вычисляем

{(ВРД. };=М], = (строка в В"1, ассоциированная с х6) (Р„ Р4, Р5) =

= (3-я строка в В0) (Р„ Р4, Р5) -= (-2, 1, 1)(Р„Р4,Р6) = = (2,-2, 1).

Отсюда следует, что

e = min< -

соответствует переменной xt. Следовательно, в базис вводится вектор Р4. Вычисляем новый базис и обратную матрицу В~.

ХВ; (2 XV "4

2 1 \\

В,=(Р2,Р3,Р4) =

0 2 0 4 0 0

0 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]