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


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


102

5 4 3 2 1

О 1 2 3 4 5 6 Рис. 7.2. Пространство решений для упражнения 4

7.1.1. Базисные решения

В этом разделе задачу ЛП, записанную в стандартной форме (см. раздел 3.1), представим в новой форме записи с использованием матричных обозначений. Обозначим

через X = (х,, х2.....хп)т n-мерный вектор переменных, через А - матрицу размер

тхп, содержащую коэффициенты левых частей ограничений, b = (ft,, b2, bm)T - m-мерный вектор правых частей ограничений, С = (cv с2, сп) - л-мерный вектор коэффициентов целевой функции. С помощью матричной формы записи стандартную задачу ЛП можно представить следующим образом.

Максимизировать или минимизировать г = СХ

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

АХ = Ь, Х>0.

На основе стандартной формы для симплекс-таблиц из главы 3 (см. также рис. 4.1) т крайних справа столбцов матрицы А всегда можно представить в виде единичной матрицы I, для чего, возможно, придется надлежащим образом расположить переменные и использовать при необходимости искусственные переменные.

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

Крайние точки множества {X АХ = Ь} <=> Базисные решения системы АХ = Ь. Это соответствие означает, что все крайние точки области решений задачи ЛП полностью определяются базисными решениями системы АХ = b и наоборот. Отсюда следует, что множество базисных решений содержит всю информацию, необходимую для оптимального решения задачи ЛП. Более того, если наложить условия неотрицательности X > 0, поиск оптимального решения ограничится только множеством допустимых базисных решений.



Чтобы формализовать определение базисного решения, представим систему АХ = b в векторной форме

где вектор Р; - j-й столбец матрицы А. Подмножество из т векторов Ру формирует базис В тогда и только тогда, когда эти векторы линейно независимы. Для этого необходимо (и достаточно), чтобы определитель матрицы В, состоящей из данных т векторов, был отличен от нуля, т.е. det(B) Ф О.1 В этом случае матрица В называется невырожденной. Обозначим через Хв вектор из т переменных, ассоциированных с векторами Р;, составляющих невырожденную матрицу В. Тогда Хв будет базисным решением, если он будет решением системы ВХВ = Ь.

Пусть В"1 - матрица, обратная к матрице В (напомним, что матрица В невырожденная). Тогда базисное решение находим по формуле:

XB = Bb.

Если выполняется неравенство B"b > 0, тогда Хв будет допустимым решением.

В заключение отметим, что количество базисных решений у системы из т уравнений с п неизвестными не превышает величины

т\(п - т)\

Пример 7.1.2

Найдем и классифицируем (как допустимые или недопустимые) все базисные решения следующей системы уравнений

В следующей таблице показаны все базисные решения. Матрица, обратная к матрице В, вычислена методами, приведенными в разделе А.2.7.

BXs = b

Решение

Статус

(Рь Рг)

(Pi. Рз) (Рг, Рз)

Не является базисом

3>

1 \*

( Л

1 1

4 8

1 3

ч~4 %)

Допустимое

Недопустимое

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



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

Здесь векторы Р,, Р2, Р3, b являются двухмерными; в общем виде они представимы как (о,, а2)т. На рис. 7.3 на плоскости (alt а2) показаны векторы данной системы. Например, вектор b = (4, 2)т, где а, = 4, а2 = 2.

Рис. 7.3. Векторное представление системы уравнений

Поскольку у нас только два уравнения (т = 2), базис должен состоять из двух векторов, выбранных среди Р,, Р2 и Р3. Из рис. 7.3 видно, что пары векторов (Р,, Р2) и(Р2Р3) могут быть базисами, поскольку векторы в этих парах независимы. Но пара векторов (Р,, Р3) не может составить базис, так как эти векторы линейно зависимы.

Алгебраический подход к определению базиса требует, чтобы определитель матрицы, составленной из векторов, претендующих на роль базисных, был отличен от нуля. Вычисления определителей показывают, что пары векторов (Рр Р2) и (Р2 Р3) будут базисами, а векторы (Р,, Р3) не могут составить базис.

det(P,, Р,) = det Q j = (1 х (-2)) - (2 х 3) = -8 * 0. det(P2,P3) = detj Ъ ~М = (Зх(-2))-(-2х(-1)) = -80.

det(P1,P3) = det

fl -Г 2 -2

= (1х(-2))-(2х(-1)) = 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]