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


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


34

2xl + 3x2-2x3 + 3xi<3, -х1 + х3 + 2х4 < О,

1» "2 *3 "4 -

a) С помощью программы TORA найдите оптимальное решение данной задачи.

b) Имея оптимальное решение, выберите любую небазисную переменную и попробуйте ввести ее в базис, щелкнув на кнопке Next Iteration. Сравните полученное значение целевой функции с оптимальным. (Идея этого упражнения заключается в том, чтобы показать, что в оптимальном решении любая небазисная переменная, введенная в базис, не может улучшить значения целевой функции.)

3.4. ИСКУССТВЕННОЕ НАЧАЛЬНОЕ РЕШЕНИЕ

В примере 3.3.1 при начальном допустимом базисном решении гарантировалось, что все последующие базисные решения, получаемые при выполнении симплекс-метода, также будут допустимыми. В задачах линейного программирования, где все ограничения являются неравенствами типа "<" (с неотрицательной правой частью), дополнительные (остаточные) переменные позволяют сформировать начальное допустимое базисное решение. Естественно, возникает вопрос: как найти начальное допустимое базисное решение в задачах ЛП, где есть ограничения в виде равенств или неравенств типа ">"?

Наиболее общим способом построения начального допустимого базисного решения задачи ЛП является использование искусственных переменных. Эти переменные в первой итерации играют роль дополнительных остаточных переменных, но на последующих итерациях от них освобождаются. Разработано два тесно связанных между собой метода нахождения начального решения, которые используют искусственные переменные: М-метод5 и двухэтапный метод.

3.4.1. М-метод

Пусть задача ЛП записана в стандартной форме (см. раздел 3.1). Для любого равенства i, в котором не содержится дополнительная остаточная переменная, введем искусственную переменную Д, которая далее войдет в начальное базисное решение. Но, поскольку эта переменная искусственна (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

Переменная i?, с помощью достаточно большого положительного числа М штрафуется путем ввода в целевую функцию выражения -MRt в случае максимизации целевой функции и выражения +MRt - в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной Rt. Следующий пример проясняет детали этого метода.

5 М-метод также называют методом больших штрафов. - Прим. ред.



Пример 3.4.1

Минимизировать z = 4х, + х,

при выполнении условий

Зх, -¥ х2 = 3, 4а-, + Зл-2 > 6, х, + 2х2 < 4, х„х2>0.

Стандартная форма этой задачи получается в результате добавления дополнительной (избыточной) переменной х3 во второе неравенство и дополнительной (остаточной) переменной xt в третье неравенство. Эта задача в стандартной форме будет записана следующим образом.

Минимизировать z = 4х, + х2

при выполнении условий

Зх, + х2 = 3, 4л-, + Зх2 - х3 = 6, х, + 2х2 + xt = 4, л",, х2, х3, х4 0.

В полученной задаче первое и второе уравнения не имеют дополнительных (остаточных) переменных, которые можно ввести в базисное решение. Поэтому введем в эти уравнения искусственные переменные Л, и R2, а в целевую функцию добавим штраф MRX + MR2. В результате получим следующую задачу ЛП.

Минимизировать z = 4х, + х2 + МЛ, + MR2

при выполнении условий

Зх, + х2 + Л, = 3,

4а-, + Зх2 -х3 + Л2 = 6,

х, + 2х2 + х4 = 4,

" -К,, Л, "Kg, -

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

Базис

«1

Решение

Прежде чем применять симплекс-метод, надо согласовать значения в z-строке с остальной частью таблицы. В частности, значение функции z, соответствующее начальному базисному решению Л, = 3, Л2 = 6 и х4 = 4, должно равняться ЗМ+ 6М + 0 = 9М, а не 0, как показано в таблице. Это противоречие связано с тем,



что переменным Л, и R2 соответствуют ненулевые коэффициенты (-М, -М) в строке г (сравните с начальным решением в примере 3.3.1, где дополнительным переменным соответствуют нулевые коэффициенты в z-строке). Чтобы сделать эти коэффициенты нулевыми, следует умножить элементы строк Л, и R2 на величину М, и затем сложить эти строки с z-строкой. (Обратите внимание на "подсвеченные" единицы в этих строках - если бы эти коэффициенты были отличны от единиц, то необходимо было бы сначала разделить все элементы этих строк на данные коэффициенты.) Кратко это действие можно записать следующим образом.

Новая z-строка = старая z-строка + М х /?,-строка + М х /?2-строка

Измененная симплекс-таблица примет следующий вид (проверьте!).

Базис

Решение

-4 + 7м

-1 + AM

Я

Отметим, что теперь z = 9М, что соответствует базисному решению Л, = 3, R2 = 6 и х4-4.

Последняя таблица готова к применению симплекс-метода с использованием условий оптимальности и допустимости, описанных в разделе 3.3.2. Поскольку мы минимизируем целевую функцию, находим наибольший положительный коэффициент в z-строке. Наибольший коэффициент -4 + 7М соответствует переменной д-,, которая и будет вводимой. Условие допустимости указывает на переменную Л, в качестве исключаемой.

Поскольку вводимая и исключаемая переменные определены, новую симплекс-таблицу можно вычислить с помощью метода Гаусса-Жордана. Заметим, что вычисления в z-строке, где присутствует М, следует проводить алгебраически. Так, для получения новой г-строки надо новую ведущую строку умножить на -(-4 + 7М) и сложить с текущей z-строкой. В результате получим следующую таблицу.

Базис

Решение

(1 + 5А*)/3

(4 - 7М)/3

4 +2м

-4/3

-1/3

Отметим, что уже первая итерация исключила из базисного решения искусственную переменную Rlt что является результатом включения штрафа в целевую функцию.

Последняя таблица показывает, что следующими (вводимой и исключаемой) переменными будут д:2 и R2 соответственно. Конечно, для получения оптимального решения может потребоваться больше двух итераций. В данной задаче оптимальным решением будет хх = 2/5, л\, = 9/5, х3 = 1 и z = 17/5.

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