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


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


43

4.2. СООТНОШЕНИЯ МЕЖДУ ПРЯМОЙ И ДВОЙСТВЕННОЙ ЗАДАЧАМИ

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

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

4.2.1. Обзор простых матричных операций

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

1. Матрица А порядка тхп - это прямоугольный массив элементов с т строками и п столбцами.

2. Вектор-строка V размерности п - матрица порядка 1 х п.

3. Вектор-столбец Р размерности т - матрица порядка mxl.

Эти определения математически можно представить следующим образом.

а12 .

V = (i

,,v2,.

••.v„), А =

«2.

а21 .

а2п

, Р =

ат2

Теперь определим три матричные операции умножения.

1. Умножение вектор-строки V на матрицу А: V х А. Эта операция определена только тогда, когда количество элементов в вектор-строке V равно числу строк в матрице А.

Например,

(11,22,33) 3 4

ч5 6)

VxA = Xv,,£vyi,2,...,£v,a,,

= (1x11 + 3x22 + 5x33, 2x11+4x22 + 6x33) = (242,308).

2. Умножение матрицы А на вектор-столбец Р: А х Р. Эта операция определена только тогда, когда количество столбцов матрицы А равно количеству элементов вектор-столбца Р.

1 В приложении А приведен более полный обзор теории матриц.



АхР =

Например,

1 3 5

2 4 6

11x1 + 22x3 + 33x5 11x2 + 22x4 + 33x6

242 308

Умножение скаляра на матрицу. При умножении скаляра (константы) а на матрицу А, ссА, получаем матрицу порядка т х п, у которой (i, ;)-й элемент равен aatj. Например, для а = 10 имеем

Л 2 Ъ\ (10 20 301 (10)

4 5 6) {40 50 60

В общем случае ссА = Аа. Этим же свойством обладает операция умножения вектора на скаляр: aV = Va и aP = Pa.

УПРАЖНЕНИЯ 4.2.1

1. Даны следующие матрицы.

fl 4

V,-(ll,22), V2 = (-1,-2,-3).

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

a) AV,.

b) АР,.

c) АР2.

d) V,A.

e) V2A. О Р,Р2. g) V.P..

4.2.2. Структура симплекс-таблицы

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

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



эффициенты на главной диагонали равны 1, а все внедиагональные - 0). Сохраняя ту же структуру таблицы, после серии симплекс-преобразований методом Га-усса-Жордана получим то, что называется обратной матрицей. Как будет показано далее в этой главе, обратная матрица играет ключевую роль при вычислении всех элементов симплекс-таблиц.

z-строка целевой функции

Начальные базисные переменные

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

0 •

• 0

1 •

•• 0

0 •

• 1

(Начальная таблица)

Единичная матрица

z-строка целевой функции

Начальные базисные переменные

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

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

(Общая таблица)

Рис. 4.1. Схематическое представление начальной и общих симплекс-таблиц

УПРАЖНЕНИЯ 4.2.2

1. Вернитесь к таблице с оптимальным решением примера 3.3.1.

a) Определите в этой таблице обратную матрицу.

b) Покажите, что вектор значений в столбце "Решение" (без значения z-строки) равен произведению обратной матрицы на вектор правых частей исходных ограничений.

2. Повторите упражнение 1 для последней таблицы примера 3.4.1.

4.2.3. Оптимальное решение двойственной задачи

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

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

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