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


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


105

автоматически приведет к вычислению разностей г} - cj для всех переменных в начальной симплекс-таблице.

5. Пусть начальное базисное решение задачи ЛП сформировано только из искусственных переменных. Используя матричное представление симплекс-таблицы, покажите, что применение процедуры исключения искусственных переменных из целевой функции (для чего использовались ограничения-равенства), описанной в разделе 3.4.1, приведет к вычислению разностей zt - ct для всех переменных в начальной симплекс-таблице.

6. Пусть дана задача ЛП, в которой не накладываются ограничения на знак переменной хк. Докажите, что после замены хк=хк - хк , где х\ и х~к неотрицательны, невозможна ситуация, когда переменные х\ и хк заменяют одна другую в альтернативных оптимальных решениях.

7. Дана задача ЛП, записанная в стандартной форме и имеющая т ограничений (в виде равенств) и п неизвестных. Определите число смежных крайних точек, которые можно достичь из невырожденной крайней точки пространства решений. Почему здесь существенно условие невырожденности крайней точки?

8. Применяя условие допустимости симплекс-метода, предположим, что хг - базисная переменная, имеющая нулевое значение, а дс.- вводимая. Объясните, почему для того, чтобы переменную л:г исключить из базиса, необходимо выполнение неравенства (В 1Р;)г>0. Какие возникнут проблемы при выполнении неравенства (В-1РД.<0? {Подсказка. При ответе учитывайте, что переменная хг должна остаться неотрицательной.)

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

10. Каковы соотношения между крайними точками пространства решений и базисными решениями при вырожденности и невырожденности решений? Какое максимальное число итераций симплекс-метода может быть выполнено в одной и той же крайней точке?

11. Дана следующая задача ЛП: максимизировать г = СХ при ограничениях АХ < b, X > 0, где b > 0. Предположим, что вводимый в базис вектор Ру таков, что по крайней мере один элемент вектора В~Ру положителен.

a) Пусть вектор Р, заменен на аР;, где а - положительное число, при этом переменная лгу остается переменной, вводимой в базис. Найдите соотношения между значениями переменной xjt соответствующими векторам Ру и ссР

b) Ответьте на вопрос предыдущего пункта, если дополнительно вектор b заменен на вектор рЧЬ, где (3 - положительное число.

12. Дана следующая задача ЛП: максимизировать z = СХ при ограничениях АХ<Ь, Х>0, где Ь>0. Предположим, что после получения оптимального решения возникла идея сделать небазисную переменную xt базисной (т.е. приносящей доход, если вспомнить экономическую интерпретацию задач ЛП) путем уменьшения ресурсов, расходуемых на единицу x/t до величины 1/а от исходного значения, где а- число, превышающее единицу. По-



скольку сокращено потребление ресурсов, ожидается, что доход на единицу Xj также уменьшится до величины 1/а от исходного значения. Может ли это изменение привести к рентабельности переменной xt? Каковы ваши рекомендации относительно того, чтобы сделать переменную х. приносящей доход?2

13. Дана следующая задача ЛП: максимизировать z = СХ при ограничениях (A, I)X = b, X > 0. Обозначим через Хв текущий базисный вектор, через Св - вектор коэффициентов целевой функции, соответствующих базисным переменным. Допустим, что вектор Св изменен на DB. Докажите, что в этом случае разности соответствующие базисному вектору Хв, останутся равными нулю. Дайте объяснение этому.

7.2.2. Вычислительная процедура модифицированного симплекс-метода

Имея условия оптимальности и допустимости, приведенные в разделе 7.2.1, можно описать последовательность вычислений, выполняемых в модифицированном симплекс-методе.

Шаг 0. Находится начальное базисное допустимое решение. Пусть В и Св - базис и вектор коэффициентов целевой функции, соответствующих базисным переменным.

Шаг 1. Каким-либо подходящим способом вычисляется обратная мат-рица В .

Шаг 2. Для каждой небазисной переменной х/ вычисляется величина

zrcrCBWlVrcr

Если для всех небазисных переменных х. величины zi - с}>0 в задаче максимизации или г. - с < 0 в задаче минимизации, то вычисления заканчиваются, так как получено оптимальное решение

хв = в-1ь,г = свхв.

Иначе на основе условия оптимальности определяется вводимая (в базис) переменная дс как небазисная переменная, которой соответствует наибольшая (по модулю) отрицательная величина zj - с/ в задаче максимизации или наибольшая положительная в задаче минимизации.

Этот вопрос можно переформулировать без "экономического" подтекста: при каких условиях переменная xt может быть представлена в оптимальном решении? - Прим. ред.

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



Шаг 3. Вычисляется вектор В~Ру. Если все элементы этого вектора отрицательны или равны нулю, вычисления заканчиваются, так как задача не имеет ограниченного решения. Иначе вычисляется вектор В b. Для всех строго положительных элементов вектора В 1Р вычисляется отношение, определенное в условии допустимости. Базисная переменная xt, которой соответствует наименьшее отношение условия допустимости, становится исключаемой из базиса переменной.

Шаг 4. Из текущего базиса В формируется новый базис путем замены в базисе В вектора Р; на вектор Р,. Выполняется переход к этапу 1 для начала новой итерации.

Пример 7.2.1

С помощью модифицированного симплекс-метода решим заново задачу о компании Reddy Mikks из раздела 2.1. Решение этой задачи обычным симплекс-методом дано в разделе 3.3.2. Сравнение двух решений данной задачи показывает, что оба метода выполняют одну и ту же последовательность действий.

Представим в матричном виде рассматриваемую задачу, уже приведенную к стандартной форме:

максимизировать г = (5, 4, 0, 0, 0, 0)(л:1, хг, х3, xt, х5, х6)Т

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

6 4

1 2

-1 1

, 0 1

#2»

*5> *60.

Мы используем запись С = (с,, с2, с6) для представления вектора коэффициентов целевой функции и (Р,, Р2, Р6)- для представления столбцов коэффициентов левых частей ограничений. Вектор правых частей ограничений обозначим Ь.

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

Итерация О

Х„ - (*„ xt, xt, х/, СВо = (0, 0, 0, 0). В0 = (Р3,Р4,Р5,Рв) = 1, в- -I.

Таким образом,

Х,о = B-1b = (24,6,l,2)r, z=CBXlh =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]