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


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


35

При использовании М-метода следует обратить внимание на следующие два обстоятельства.

1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации по крайней мере одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения. В разделе 3.5.4 показана такая ситуация.

2. Теоретически применение М-метода требует, чтобы М-Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Как понимать термин "достаточно большая" - это открытый вопрос. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

УПРАЖНЕНИЯ 3.4.1

1. Завершите решение задачи из примера 3.4.1 и получите оптимальное решение.

2. Найдите решение задачи из примера 3.4.1 с помощью программы TORA (файл ch3ToraMmethodEx3-4-l.txt), используя команду Iterations1M-method (ИтерацииМ-метод). Сравните решения при М=1,М=10иМ = 1000. Какое заключение можно сделать из этого эксперимента?

3. В примере 3.4.1 найдите начальную симплекс-таблицу для каждого из следующих (независимых) случаев и подсчитайте коэффициенты z-строки после определения всех искусственных переменных.

a) Третье ограничение имеет вид л:, + 2х2 > 4.

b) Второе ограничение имеет вид 4л:, + Зх2 < 6.

c) Второе ограничение имеет вид 4л:, + Зх2 = 6.

d) Целевая функция имеет вид: максимизировать z = 4л:, + х2.

4. Существует следующее множество ограничений.

Для каждой из следующих задач найдите коэффициенты z-строки симплекс-таблицы после введения искусственных переменных.

a) Максимизировать z = 5л:, + 6л:2 при ограничениях (1), (3) и (4).

b) Максимизировать z = 2л:, - 7х2 при ограничениях (1), (2), (4) и (5).

c) Минимизировать z = Зл:, + 6л;2 при ограничениях (3), (4) и (5).

-2xi + Зх2 = 3,

4xi +5х2> 10, xi + 2X2 < 5, 6x1 + 7х2 < 3, 4xi + 8x2 > 5,

(1) (2) (3) (4) (5)

X1, X2>0.



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

e) Минимизировать z = Зх, + 2х2 при ограничениях (1) и (5).

5. Дано следующее множество ограничений:

X j "т~ Х *т~ g ~~ 7

2х, - 5х2 + х3 > 10, х,, х2, х3>0.

При этих ограничениях решите задачи ЛП для следующих целевых функций.

a) Максимизировать z = 2х, + Зх2 - 5х3.

b) Минимизировать z = 2х, + Зх2 - 5х3.

c) Максимизировать z = х, + 2х2 + х3.

d) Минимизировать z = 4х, - 8х2 + Зх3.

6. Дана следующая задача.

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

Xj ~\~ Х *т~ >

х, + 4х2 + х4 = 8, х,, Х2, Х3, Х4 0.

В этой задаче переменные х3 и х4 могут выполнить роль дополнительных остаточных переменных. Они отличаются от остаточных переменных тем, что имеют ненулевые коэффициенты в выражении целевой функции. Поэтому, если использовать их как начальные базисные переменные, перед выполнением симплекс-метода следует преобразовать в симплекс-таблице z-строку (как это делается для искусственных переменных). Решите эту задачу без искусственных переменных, используя в начальном базисном решении переменные х3 и х4.

7. Без применения искусственных переменных решите следующую задачу, используя в начальном базисном решении переменные х3 и х4.

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

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

х, + 4х2 + х3 > 7, 2х, + х2 + х4 > 10, х,, х2, Х3, х4 0.

8. Дана следующая задача.

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

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

х, + 2х2 + х3 = 3, Х2 4)

Xt) х2$ 3 -

В первом равенстве переменная х3 может войти в базисное решение вместо искусственной переменной. Однако во втором равенстве искусственная переменная R2 необходима. Используя начальное базисное решение, состоящее из переменных х3 и R2, найдите оптимальное решение этой задачи.

9. Покажите, как с помощью М-метода можно определить, что следующая задача не имеет допустимого решения.



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

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

Зх, + 2х2>6, 2х, + х2<2, х„ х2>0.

3.4.2. Двухэтапный метод

Двухэтапный метод лишен недостатков, которые присущи М-методу вследствие ошибок округления. Как следует из названия этого метода, процесс решения задачи ЛП разбивается на два этапа. На первом этапе ведется поиск начального допустимого базисного решения. Если такое решение найдено, то на втором этапе решается исходная задача.

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

Этап 2. Оптимальное базисное решение, полученное на первом этапе, используется как начальное допустимое базисное решение исходной задачи.

Пример 3.4.2

К задаче из примера 3.4.1 применим двухэтапный метод. Этап 1

Минимизировать г = Л, + R2

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

Зл-1+л-2 + Л1 = 3, 4л-, + 3x2 -х3 + R2 = 6, л-, + 2хг +xt - 4, xi Х2у д-g, л*4, Л,, R2, - 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]