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


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


37

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

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

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

2х, + х2 + х3 < 2,

Зх, + 4х2 + 2х3 > 8,

х„ х2, х3>0.

Оптимальная симплекс-таблица, полученная в конце первого этапа, имеет следующий вид

Базис

Решение

Покажите, что небазисные переменные х,, х3, х3 и х4 никогда не примут положительных значений в конце второго этапа. Следовательно, столбцы этих переменных можно удалить из симплекс-таблицы еще до начала второго этапа. В сущности, удаление этих переменных сводит ограничительные равенства к одному: х2 = 2. Это означает, что не было необходимости выполнять второй этап вовсе, так как пространство допустимых решений состоит только из одной точки.

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

8. Дана задача линейного программирования.

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

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

5х, - 6х2 + 2х3 > 5,

-х, + Зх2 + 5х3 > 8,

2хх + 5х2 - 4х3 < 9,

х„ х2, х3>0.

Покажите, что неравенства можно свести к множеству равенств, которое потребует введения только одной искусственной переменной (вместо возможных двух искусственных).

3.5. ОСОБЫЕ СЛУЧАИ ПРИМЕНЕНИЯ СИМПЛЕКС-МЕТОДА

В этом разделе рассмотрим четыре особых случая, встречающихся при использовании симплекс-метода.

1. Вырожденность.

2. Альтернативные оптимальные решения.



3. Неограниченные решения.

4. Отсутствие допустимых решений.

При изучении этих случаев основное внимание мы уделим, во-первых, теоретическому обоснованию причин, приводящих к таким ситуациям, и, во-вторых, их практическим интерпретациям применительно к реальным задачам.

3.5.1. Вырожденность

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

В вырожденном решении нет никакой опасности, за исключением небольших теоретических неудобств, которые мы далее кратко обсудим. С практической точки зрения вырожденность объясняется тем, что в исходной задаче присутствует по крайней мере одно избыточное ограничение. Для того чтобы лучше понять практические и теоретические аспекты явления вырожденности, рассмотрим численный пример. Графическая интерпретация задачи поможет наглядно разобраться в этом явлении.

Пример 3.5.1. Вырожденное оптимальное решение

Рассмотрим следующую задачу ЛП.

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

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

х, + 4х2 < 8, х, + 2х,<4, х„х2>0.

Обозначим через х3 и х4 дополнительные переменные. Результаты применения симплекс-метода представлены в следующей таблице.

Итерация

Базис

Решение

Начальная

Вводится хг

Исключается хз

Первая

-3/4

ВВОДИТСЯ Х

Исключается х4

-1/2

0

Вторая

Оптимум

-1/2

На начальной итерации в качестве исключаемой можно выбрать как переменную хъ, так и х4. Если оставить в базисе переменную х4, на следующей итерации она



примет значение 0 (как показано в таблице), т.е. получим вырожденное базисное решение. Оптимальное решение получается на следующей итерации.

Что же практически приводит к вырожденности решения? Рассмотрим рис. 3.9, графически представляющий решение этой задачи. Точка оптимума х, = О, хг - 2 является пересечением трех прямых. Поскольку данная задача двухмерна, эта точка переопределена (на плоскости для определения точки достаточно двух прямых), и, следовательно, одно из ограничений избыточно.

Оптимальное вырожденное решение

Рис. 3.9. Вырожденность задачи примера 3.5.1

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

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

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

х, = 0, х2 = 2, х3 = 0, х4 = 0, z = 18.

Можно ли, несмотря на то, что оптимальное решение не достигнуто, остановить вычисления на первой итерации (когда впервые обнаруживается вырожденность)? Ответ отрицательный, так как решение может быть только временно вырожденным (упражнение 3.5.1.2).

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