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


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


19

Пусть / некоторый опорный план задачи (3.7) и

Обозначим сг =

d, , I его базис.(3.8)

Отметим, что задание базиса полностью определяет опорный план. Действительно, если =(а\ а ...,а") - квадратная wxm матрица,

составленная из столбцов матрицы А, участвующей в базисе (3.8), то А - невырожденная матрица и существует обратная ей матрица . Так как = О при j е а, то Ах = Ах , т.е. Ах = Ъ , откуда

х>А-:ъ.

Таким образом, задание базиса (3.8) однозначно определяет т-мерный вектор , откуда находим вектор х :

о (0. если jea . . =(х;, если Jea = Ь 2,(3.9)

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

Пусть есть некоторый начальный опорный план х.

Будем считать, что он вычислен еще до начала применения симплекс-процедуры.

Сопоставим задаче (3.7) систему уравнений

-Хо+Хс,х,=0 AxL(3.10)

Рассмотрим матрицу следующего вида:

О Ср ...,с/

Ъ d, a...,a )

в первой строке которой стоят числа, во второй т-мерные векторы. Размерность этой матрицы {т + l)x(w + 1). 64



Так как система векторов

\ im

(3.11)

линейно независима в пространстве , то матрица

1 ,1j /2 5 •••»;>1

а , а ,...,а

квадратная невырожденная матрица размера (/w+l)x(/w+l) и поэтому существует обратная к ней матрица . Введем матрицу U следующим образом:

Матрицу и назовем симплексной таблицей, соответствующей базису (3.8) опорного планах.

Будем обозначать элементы первой строки симплексной таблицы через До,Аь An. В дальнейшем будем обозначать ао = (До, Аь А2, А„), А = (Дь Д2,А,,). Отсюда, в частности, следует, аоу= А,,; = 1,2,

Элементы остальных строк обозначим а,у, / g а, у = О, 1, 2, «. Строку с номером / g а обозначим а, = (a,o, а, а,„).

Вектор, состоящий из последних т координат у-го столбца матрицы U обозначим через a! = (anj, ацр а,,„у) у = О, 1, 2, « так, что весь у-й столбец симплексной таблицы имеет вид:

Элементы симплексной таблицы имеют наглядный смысл: если z, у g /г\ то запись у = означает, что вектор z представляет собой координаты вектора у в базисе (3.11). Так как BU = Л , то, записав матри-

цу 5стввиде5а =

OA"

нетрудно заметить, что

<с<„а°>-Ао=0 A=d,j= 1,2, ...,п <с„, а!>-Aj = Cj,j=\,2, ...,п.

(3.12) (3.13) (3.14) (3.15) 65



Из равенства (3.12) следует, что

а» = Л

(3.16)

Используя, что л: у = 0,7 е а, получим

Ао = <с,/>.(3.17)

Из (3.14) видно, что вектор ос представляет собой координаты вектора а в базисе (3.8) и из (3.15) следует, что

Aj = <c,a!>-Cj,(3.18)

Учитывая (3.12)-(3.18), получим общий вид симплексной таблицы:

<с/>

СХ;1.1

а/1.2

а,,.*

a/i.;, .

»2

а/2.2

«5.2

а/.,2

Заметим, что если бы вместо матрицы А рассмотрели матрицу системы уравнений (3.10):

0 -1 q, ...,с„ ,6 О а\ a...,a" J

то при умножении на В \ получили бы матрицу, элементы которой в точности соответствуют коэффициентам системы (3.0).

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

Пусть S = ite а

{ аЧ d-K a+i, d }(3.19)

(к е с) - новый базис пространства тогда система векторов

(3.20)

является базисом пространства Л" * . 66

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