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


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


104

3. Дана следующая задача ЛП.

Минимизировать г = 2хх + х2

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

Зяг, -(- х2 - х3 3, 4л:, + Зл;2 - х4 = 6, х, + 2лг2 + хь = 3, х,, х2, ят3, х4, я:5 > 0.

Вычислите симплекс-таблицу, соответствующую Хв = (xv х2, хь)Г, и определите, будет ли это решение допустимым и оптимальным.

4. Дана следующая симплекс-таблица с оптимальным решением задачи ЛП.

Базис

Решение

Здесь переменные ха, xt и хь являются дополнительными (остаточными). С помощью матричных вычислений реконструируйте исходную задачу ЛП, затем вычислите оптимальное значение целевой функции.

5. В стандартной задаче ЛП разобьем вектор X на два - X = (X,, Х„)т. Здесь вектор Х„ соответствует начальному базисному решению, состоящему из дополнительных и искусственных переменных (так что В = I). Тогда матрицу А можно представить как А = (D, I). Вектор С также разделим на два вектора С, и С„ в соответствии с векторами X, и Х„. Покажите, что в этом случае симплекс-таблицу можно записать в следующем виде, который в точности соответствует виду симплекс-таблицы из главы 3.

Базис

Решение

CSB"1D-C

СвВ 1 - Сц

с8вчь

B"1D

7.2. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД

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

Модифицированный симплекс-метод предусматривает выполнение точно таких же этапов, как и обычный табличный симплекс-метод, описанный в главе 3. Основное отличие между ними заключается в том, что в обычном симплекс-методе при переходе от одного базиса к другому используется процедура преобразования строк симплекс-таблицы с помощью метода Гаусса-Жордана, тогда как



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

7.2.1. Условия оптимальности и допустимости

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

Максимизировать или минимизировать г = СХ при ограничениях PjX, =b, х.>

0,j= 1, 2, га.

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

г + £ц-су)*;=св в-ь

(XB)i+X(B-PJ),x;=(B-1b)l,

где Zj - с\ = СВВ~!Р; - с\. Здесь запись (V), используется для обозначения t-ro элемента вектора V.

Условие оптимальности симплекс-метода. Из уравнения для значений z-строки, приведенного выше, следует, что увеличение значения небазисной переменной xf приводит к возрастанию (убыванию) значения целевой функции z выше текущего значения СВВ 1Ь только в том случае, если разность zj - с\ строго отрицательна в задаче максимизации или строго положительна в задаче минимизации. В противном случае переменная не может улучшить текущее решение и должна остаться небазисной с нулевым значением. Таким образом, любая небазисная переменная, удовлетворяющая этому условию, может быть включена в базис, что, возможно, улучшит значение целевой функции. В симплекс-методе действует эмпирическое правило, которое гласит, что в качестве вводимой в базис переменной выбирается переменная, которой соответствует наибольший (по модулю) отрицательный коэффициент г - с\ в z-строке в задаче максимизации или наибольший положительный аналогичный коэффициент в задаче минимизации.

Условие допустимости симплекс-метода. Определение исключаемого из базиса вектора основано на проверке ограничения, представленного в виде равенства, соответствующего i-й базисной переменной. Это равенство имеет следующий вид.

(ХД.+В-РДхВ-Ь),.

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

(Хв), = (В-1Ь),-(В-1РДх4 Это уравнение показывает, что при (В~РД > 0 возрастание переменной хк не приведет к отрицательному значению базисной переменной (Хв)( только в том случае, если будет выполняться неравенство

(B"b), - (В 1РД хк > 0 для всех L



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

Базисная переменная, на которой достигается этот минимум, становится исключаемой.

УПРАЖНЕНИЯ 7.2.1

1. Дана следующая задача ЛП.

Векторы Р,, Р2, Р3 и Р4 показаны на рис. 7.4. Предположим, что текущим базисом является В = (Рр Р2).

a) Если вектор Р3 ввести в базис, какой вектор необходимо из него исключить, чтобы полученное базисное решение было допустимым?

b) Может ли вектор Р4 быть частью допустимого базиса?

2. Докажите, что для всех базисных переменных соответствующие разности гу - с\ равны нулю.

3. Докажите, что если в задаче максимизации (минимизации) для всех небазисных переменных х; выполняется неравенство г. - с. > О (< 0), то задача имеет единственное оптимальное решение. Если же для некоторых небазисных переменных х. выполняется равенство z.-c=Q, задача имеет альтернативное оптимальное решение.

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

Максимизировать z - с,*, + с2х2 + с3х3 + с4х4

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

РЛ+РЛ + РЛ + РЛ = Ь х„ хг, х3, х4>0.

Рис. 7.4. Векторы для упражнения 1

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