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


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


108

Пример 7.3.1

Решим следующую задачу ЛП вышеописанным методом решения задач с ограниченными переменными.

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

х,+у + 2x3<14,

2 л:, + 4у + 3х3<43,

О < х, < 4, 7 < у < 10, 0 < х3 < 3.

Поскольку переменная у ограничена положительной константой не только сверху, но и снизу, производим замену у = х2 + 7, где 0 < х2 < 10 - 7 = 3.

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

Итерация 0

Базис Xi хг хз Х4 х5 Решение

z -3 -5 -2 0 0 35

xt 112 10 7

хъ 2 4 3 0 1 15

Имеем В = В"1 = I и Хв = (л:4, л:5)г = B~b = (7,15). Принимая переменную х2 в качестве вводимой в базис переменной (z2 -с2 = -5), получаем B~lP2 = (1, 4). Отсюда следует

02 = °° (поскольку В 1Р2 > 0).

Так как по условию л:2 < 3, получаем значение, принимаемое переменной х2.

х2 = min{3,75, ее, 3} = 3 = иг.

Поскольку л:2 = и2, базис остается неизменным; переменная х2 в базис не вводится (остается небазисной), но принимает значение своей верхней границы. После подстановки х2 = 3 - х\ получаем новую симплекс-таблицу.

Базис

Решение

.. 2

Выполненная подстановка изменяет исходный вектор правых частей ограничений с Ь = (7, 15)г на Ь = (4, 3)г. Эти изменения должны учитываться в последующих вычислениях.

Максимизировать z = Зл:, + 5у + 2х.

8, = ггагн-, - > = 3,75 , что соответствует переменной хй,



Итерация 1. Определяем вводимую в базис переменную де,. Базисный вектор Хв и обратная матрица В"1 (= I) такие же, как на предыдущей итерации. Вычисляем

в-р.-а.г).

Отсюда следует

6, = rran j у, - > = 1,5 , что соответствует переменной де5,

92 = оо (поскольку В-1Р, > 0).

Так как по условию задачи де, < 4, получаем значение, принимаемое переменной де,.

jeI-min{l,5,oo, 4} = 1,5 (=9,).

В данной ситуации переменная де, становится базисной со значением 1,5, переменная дс5 выводится из базиса и принимает нулевое значение. Получаем следующую симплекс-таблицу.

Базис

Решение

109/2

-1/2

Итерация 2. Имеем новую обратную матрицу.

В =

Значения базисных переменных определяются так:

Хв = (*4> xj = В1 V = (5/2, 3/2)т,

где Ь = (4, 3)г- значения правых частей ограничений, вычисленные в конце нулевой итерации.

Определяем хг как вводимую в базис переменную. Учитывая, что К = -Р2, получаем

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

5 2 1

Вр; =(1,-2)г

= 2,5 , что соответствует базисной переменной дс4,

= 1,25 , что соответствует базисной переменной хг.

Так как по условию хг < 3, получаем значение, принимаемое переменной х\.

х2 = min{2,5,1,25, 3} = 1,25 (= 82).



Таким образом, переменная х\ вводится в базис (со значением 1,25), из которого

исключается переменная дс, с ненулевым значением, равным ее верхней границе. Применяем подстановку xt = 4 - х\ и получаем следующую симплекс-таблицу.

Базис

Решение

109/2

-1/2

-5/2

Далее в базис вводится переменная

х и исключается х\

, что приводит к следующей

симплекс-таблиц

Базис

Решение

223/4

1/2

-1/4

-3/4

-1/4

Данная таблица представляет допустимое оптимальное решение. Оптимальные значения переменных х1У хг и х3 получаем обратной подстановкой: дс, = их - х\ =4-0 = 4, хг = и2 - х2 = 3 - 5/4 = 7/4 и х3 = 0. Теперь вычисляем значение переменной у: у = 12 + х2=7 + 7/4 = 35/4. Оптимальное значение целевой функции равно z = 223/4.

УПРАЖНЕНИЯ 7.3.1

1. Дана следующая задача линейного программирования.

Максимизировать z = 2xt + х2

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

х1 + х2<3, 0 < х, < 2, 0 < х2 < 2.

a) Решите задачу графическим способом и определите последовательность крайних точек пространства решений, ведущих к оптимальному решению.

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

c) Как алгоритм решения задач с ограниченными переменными распознает крайние точки пространства решений?

2. Решите следующую задачу ЛП методом решения задач с ограниченными переменными.

Максимизировать z = бя, + 2х2 + 8х3 + 4xt + 2xs + 10х6 при ограничениях

8jc, + х2 + 8х3 + 2xt + 2хъ + 4х6 < 13, 0<x<l,j = l,2, ...,6.

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