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


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


45

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

Максимизировать z = хх + Ъхг + Злг3

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

хх + 2х2 + х3 = 3, 2л:, - х2 = 4, х„ х2, х3>0.

a) Запишите соответствующую двойственную задачу.

b) Используя информацию о том, что оптимальное базисное решение этой задачи содержит переменные л:, и х3, найдите оптимальное решение двойственной задачи.

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

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

хх + 4х2 + xt = 8,

1 2> 3> 4 ~

Оптимальное решение этой задачи удовлетворяет уравнению (получено из 2-строки симплекс-таблицы)

2 + 2л:, + 0л:2 + 0л:3 + Зх4 = 16.

Используя эту информацию, найдите оптимальное решение двойственной задачи.

5. С помощью двойственной задачи найдите допустимое решение следующей системы неравенств:

2л:,+ 3л:2<12, -Зл:,+ 2л:2<-4, Зл:, - 5л:2<2,

хх - свободная переменная, л:2>0.

(Совет. Добавьте к этой системе неравенств тривиальную целевую функцию максимизировать z - Оле, + 0х2 и решите двойственную задачу.)

6. Найдите оптимальное значение целевой функции следующей задачи, основываясь только на свойствах ее двойственной задачи (т.е. не применяя симплекс-метод к двойственной задаче).

Минимизировать z = 10л:, + 4лс2 + 5х3

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

5л:,- 7лг2 + Зл:3>50, *р х2, х3>0.

4.2.4. Вычисление симплекс-таблиц

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



1. Вычисление значений в столбцах ограничений симплекс-таблицы (как левой, так и правой частей ограничений).

2. Вычисление значений в 2-строке.

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

Столбец коэффициентов ограничений на i-й итерации

(Обратная матрица на /-й итерации )

Столбец исходных коэффициентов ограничений J

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

Коэффициент при j-n f переменной в z-строке прямой задачи

Значение левой части j-ro неравенства двойственной задачи

Значение правой части у-го неравенства двойственной задачи

Отметим, что формула 2 такая же, какая используется в методе 2 (раздел 4.2.3) для определения оптимального решения двойственной задачи.

Пример 4.2.2

На основе задачи из примера 4.2.1 покажем, как использовать формулы 1 и 2. Из оптимальной симплекс-таблицы этой задачи получаем

обратная матрица =

2/5 -1/5 1/5 2/5

С помощью формулы 1 вычислим коэффициенты в столбцах ограничений оптимальной симплекс-таблицы.

Столбец коэффициентов ограничений, соответствующий переменной х,

Обратная матрица

из оптимальной симплекс-таблицы,

(2/5 -ф] (1 1/5 2/5 J [2

Столбец исходных коэффициентов ограничений, соответствующий переменной х,

Аналогично вычисляются другие столбцы коэффициентов ограничений.

Столбец коэффициентов ограничений, соответствующий переменной х2

Столбец коэффициентов ограничений, соответствующий переменной х3

< Столбец коэффициентов ограничений, соответствующий переменной xt

2/5 1/5

2/5 1/5

-1/5 2/5

-1/5 2/5

-1/5 7/5

-1/51

2/5 J



( Столбец коэффициентов ограничений, соответствующий

переменной R

(2/5 -1/5

( Столбец коэффициентов ! хг правых частей ограничений ) \х,

1/5 2/5

2/5 -1/5 1/5 2/5

-1/51 2/5

12/5 26/5

Теперь применим формулу 2 для вычисления коэффициентов в г-строке. Оптимальные значения двойственных переменных у2) =(29/5,-2/5) вычислены в примере 4.2.1 двумя различными методами. Эти значения используются для вычисления коэффициентов в г-строке.

Коэффициент при xi = y1 + 2y2-5 = 29/5 + 2х(-2/5) -5 = 0. Коэффициент при х2 = 2j/, - у2 - 12 = 2х(29/5) - (-2/5) -12 = 0. Коэффициент при х3 = г/, + Зу2 - 4 = 29/5 + Зх(-2/5) - 4 = 3/5. Коэффициент при xt = уг - 0 = 29/5 - 0 = 29/5. Коэффициент при R = y2- (-М) = -2/5 - (-М) = -2/5 + М.

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

УПРАЖНЕНИЯ 4.2.4

1. В задаче из примера 4.1.2 с помощью программы TORA (выполнив команду Iterations oM-method) определите элементы симплекс-таблицы первой итерации. Затем с помощью формул 1 и 2 найдите значения всех элементов оптимальной симплекс-таблицы.

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

Максимизировать г = 4лс1 + 14х2

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

2x1 + 7x2 + x3 = 21, 1хх + 2хг + xt = 2l,

jc,, х2, JCg, х4 0.

Проверьте оптимальность и допустимость следующих базисных решений.

f 1/7 0 ,-2/7 1,

(0 1/2 1 -7/2 J

а) Базисные переменные (х2, xt), обратная матрица:

Ь) Базисные переменные (х2, хг), обратная матрица =

ч * г7/45 -2/451

c) Базисные переменные (х2, XJ, обратная матрица = I

( 1/2 0\

d) Базисные переменные (лс,, xt), обратная матрица =

1-7/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]