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


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


50

Рис. 4.2. Итерации двойственного симплекс-метода из примера 4.4.1 х2

I \

3 4

Рис. 4.3. Пространство решений для задачи упражнения 1

а) Если начальное базисное (недопустимое) решение соответствует точке G, будет ли алгоритм двойственного симплекс-метода проходить через точки G, Е, F7 Обоснуйте это.



Ь) Если начальное базисное (недопустимое) решение соответствует точке L, определите на рис. 4.3 возможную последовательность точек, через которые будет проходить алгоритм двойственного симплекс-метода для достижения оптимального решения в точке F.

2. Решите следующие задачи двойственным симплекс-методом с помощью программы TORA и определите на графически представленном пространстве решений этих задач последовательность точек прохождения алгоритма двойственного симплекс-метода для достижения оптимального решения.

a) Минимизировать z = 2хл 4- 3jc2 при ограничениях

2хг + 2х2 < 30, х1 + 2х2>10, х„ х2>0.

b) Минимизировать z = 5х1 + 6х2 при ограничениях

х1+ х2> 2, 4х1 + х2 > 4, xv х2>0.

c) Минимизировать z - 4дс, + 2х2 при ограничениях

х1 + х2 = 1, 3xx2, хг, jc2>0.

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

2х, + л:2 > 3, xt+x2 = 2, xv х2 > 0.

3. Двойственный "симплекс-метод с искусственными ограничениями. Дана следующая задача ЛП.

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

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

2хг + Зх2-5х3>4, -л:, + 9х2- х3> 3, 4х, + 6х2 + Зх3 < 8, х„ х2, х3>0.

Начальное базисное решение содержит дополнительные переменные х4, хь их6 и является недопустимым, поскольку х4 = -4 и хб = -3. Но непосредственное применение двойственного симплекс-метода невозможно, так как переменные х1 и х3 не удовлетворяют условию оптимальности для задачи максимизации. Покажите, что введение искусственного ограничения х1 + х3<М (где М- достаточно большое положительное число и такое, что данное неравенство не сужает область допустимых решений исходной задачи) и последующее использование



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

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

a) Максимизировать z = 2х3 при ограничениях

-я, + 2х2 - 2х3 > 8,

-дс, + х2 + х3 <4, 2хх -х2 + 4х3 < 10, х1У х2, х3>0.

b) Максимизировать z = хх - Зх2 при ограничениях

х1~х2<2, + х2> 4, 2хг-2х2>3, хг, х2>0.

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

х, - 4х2> 5, х,-3х2<1, 2х, - 5х2> 1, х,, х2 > 0.

d) Максимизировать z = 2х3 при ограничениях

-х1 + 3х2-7х3>5, -х1 + х2-х3<1, Зх, + х2 - 10х3 < 8, х„ х2, х3>0.

5. Решите следующую задачу ЛП тремя различными методами (используя в качестве инструмента программу TORA). Определите, какой метод будет наиболее эффективным при вычислениях.

Минимизировать z = 6х, + 7х2 + Зх3 + 5х4

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

5x, + 6х2 - Зх3 + 4х4 > 12, х2 - 5jc3 - 6х4 > 10, 2xl + 5x2 + x3 + xi>&, х,, х2, х3, х4>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]