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


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


111

Итерация 0

Х„ = (*5, хе, х7)т = (40, 1, if, Св = (0, -М, -М), В = В 1 = I.

Итерация 1

Подзадача 1 (j = 1). Имеем

z,-c,=CeB-

0.1)

-с,х,=

= (о,-м,-м)

-(3.5)

= -Зх, - 5х, - М.

Таким образом, соответствующая задача ЛП имеет следующий вид.

Минимизировать ш, - -Здс, - 5хг - М

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

5*, +х2< 12, д:2>0.

Решив эту задачу (обычным симплекс-методом), получаем

yu = (o, i2f, z;-c; = w;=-6o-m.

Подзадача 2 (j - 2). Соответствующая задача ЛП имеет следующий вид.

Минимизировать г, -с, =С6В

(0,-М,-М)

С,Х, =

-(1.1)

= ~хъ ~хА-М.

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

х3 + х4> 5, х3 + 5х4 < 50 ж„ 4S0.

Находим оптимальное решение этой задачи.

Y21 = (50,0f, z;-c;=-50-Af.

Поскольку главная задача - задача максимизации и z* - с < г* - с2, а также г,*-с*<0, следовательно, переменная (3U, соответствующая крайней точке Y,,, должна быть введена в базисное решение.



Для определения исключаемой переменной запишем

f (О"

Р„ =

A,Y„ 1 О

12} 1

Отсюда В"РП = (12, 1, 0)т. Имея Хв = (х6, х6, х7)т = (40, 1, 1)г, делаем вывод, что из базисного решения следует исключить переменную х6 (искусственную переменную).

Новый базис получается путем удаления из базиса вектора, соответствующего переменной х9, и введения в базис вектора Р„. Получим (проверьте!)

(\ 12 0\

1 О О 1

-12 0} 1 о

0 1

и новое базисное решение

Хв = (х„ рп, х/ = В-(40, 1, 1)г = (28, 1, 1)т, Св = (0, C.Y,,, -М) = (0, 60, -М).

Итерация 2

Подзадача 1 (j = 1). Вы должны проверить, что соответствующая задача ЛП останется такой же, как и на первой итерации (это простое совпадение, а не общее правило). Ее оптимальное решение дает г,* -с\ = wt = 0 . Отсюда следует, что никакая из

оставшихся крайних точек пространства решений подзадачи 1 не может улучшить решение главной задачи. (Оптимальным решением этой подзадачи будет крайняя точка Y,,, которой соответствует переменная (Зп, уже входящая в состав базиса. Именно поэтому z -с[ = 0 .)

Подзадача 2 (j = 2). Снова вы должны проверить, что соответствующая задача ЛП такая же (опять совпадение), как и на первой итерации. Ее оптимальное решение

Y22 = (50, Of, z;-c;=-50-Af.

Отметим, что точка Y22 фактически совпадает с крайней точкой Y21, но мы используем нижний индекс 2, чтобы показать, что эта точка соответствует второй итерации.

Из решений обеих подзадач следует, что zj - с\ < 0 . Это указывает на то, что переменная р22, соответствующая крайней точке Y22, должна войти в базисное решение. Для определения исключаемой переменной запишем

р,, =

(1,1)



Отсюда В"Р22 = (50, 0, if. Поскольку Хв = (х5, рп, х7)т - (28, 1, if, из базисного решения следует исключить переменную х5.

Находим новый базис и новую обратную матрицу В"1 (проверьте!)

0"

Г 1

V 50

Новое базисное решение равно

Хв = (р22, рп, х7)т = В",(40, 1, If = (14/25, 1, 11/25), Св = (C2Y22, C,YU, -М) - (50, 60, -М).

Итерация 3

Подзадача 1 (j = 1). Вы должны проверить, что на этой итерации целевая функция для данной подзадачи имеет следующий вид.

(М А (М Л \2М ло

Минимизировать w=\--2 \х, + \--4 j,---1-48.

{50 ) 1 1.50 ) - 50

Соответствующее оптимальное решение дает

Y13 = (o,of, z;-c; =

12 М 50

•48.

Подзадача 2 (j = 2). Здесь целевая функция имеет следующий вид (проверьте!).

Минимизировать w1=-(xi+xi)-M.

Находим оптимальное решение:

Y23 = (5,0f, .-с\=~

Небазисная переменная хь. Исходя из вида главной задачи, разность z; - cj для переменной л:й необходимо вычислять отдельно.

M+As-~m\uo,o)t-o=iA

{ 50 50 Г 50

Отсюда вытекает, что переменная хь не может улучшить решение.

Из приведенных вычислений следует, что вводимой в базис будет переменная Р23, соответствующая крайней точке Y23. Для определения исключаемой переменной вычисляем следующее.

Р2з =

(1,1)

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