2.1 Базисные решения

Рассматривая задачу (2.1)-(2.3), будем (временно) предпола­гать, что матрица А имеет ранг то, т.е. в А имеется набор из то линейно независимых столбцов. В этом случае то < п и система линейных уравнений (2.2) является совместной и неизбыточной.

Любой набор Аа^,..., ACT(m) из то линейно независимых столб­цов матрицы А будем называть базисом, также как и матрицу В = [^4(j(i), . ..,ACT(m)], составленную из этих столбцов. Очевид­но, (тохто)-матрица В является невырожденной и, следовательно, имеет обратную матрицу В~1.

Пусть S = {(т(1),. .., ст(то)}, S' = {1,..., п} \ S.

Перестановкой столбцов матрицу А можно привести к виду А = [B,N], где N - подматрица, составленная из столбцов Aj, j G S'. Аналогичным образом можно поступить с вектором х и полу­чить представление х = (ж^), где Хв = (ж<т(1)) • • • > ж<т(т))Т> а XN

образован компонентами х^, ] £ 5". Переменные х^, являющи­еся компонентами вектора хв (соответственно ждг) называются базисными (соответственно небазисными).

Теперь система (2.2) может быть представлена в виде

Вхв + А^ждг = Ь.

Используя невырожденность матрицы В, можно перейти к систе­ме

хв + В~1Нх^ = В~1Ь, (2.2') которая эквивалентна исходной системе (2.2). Если положить ждг = 0, то получим решение системы х = = (о По-

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

х — базисное решение системы (2.2) тогда и только тогда, когда множество столбцов {Aj \ х^ ф 0} матрицы А линейно независимо.

В самом деле, если базисное решение х соответствует бази­су В, то 5 — множество номеров базисных столбцов — содер­жит множество б'(ж) = {] | х^ ф 0} и, следовательно, множество {Л? I 3 С $(х)} линейно независимо. С другой стороны, если мно­жество {Aj | 2 £ 5*(ж)} линейно независимо, то оно либо является базисом (в случае |5*(ж)| = то), либо может быть дополнено дру­гими столбцами матрицы А до некоторого базиса В, которому будет соответствовать базисное решение ж.

Замечание В случае |5*(ж)| < то может быть несколько бази­сов, которым соответствует базисное решение ж, тогда как при |5*(ж)| = то такой базис является единственным. В любом случае число базисных решений является конечным и не может привос-ходить числа различных базисов, в частности, числа сочетаний из п по то, т.е. С™.

Базисным допустимым решением (б.д.р.) называется любой элемент множества (^) = {х \ Ах = Ь, х > 0}, являющийся ба­зисным решением системы (2.2). Геометрический смысл понятия б.д.р. поясняет

Утверждение 2.1 Вектор х является базисным допустимым решением тогда и только тогда, когда х есть крайняя точка множества С}.

Доказательство. Пусть х — допустимое, но не базисное реше­ние. Тогда множество столбцов {Aj \ х^ > 0} линейно зависимо и, следовательно, существует ненулевой вектор у, такой, что Ау = 0 и у^ = 0 в случае х^ = 0, т.е. {] \ у^ ф 0} С {] \ > 0}. При любом £ £ В: вектор г = ж + £у является решением системы (2.2), а при достаточно малых £ имеем г £ (^). Из сказанного следует, что существует е > 0, при котором х1 = х+еу £ ж х2 = х — еу £ (^, т.е. х = 1/2(ж1 + ж2), ж1 ф ж2 и, следовательно, ж не является крайней точкой множества (^).

Предположим теперь, что ж = 1/2(ж1 + ж2), ж1 ф ж2 и ж1, ж2 6 <5, т.е. ж принадлежит множеству <5 и не является его край­ней точкой. Тогда из Ах1 = Ах2(= Ъ) следует А(х1 — ж2) = 0, что свидетельствует о линейной зависимости множества столб­цов {Aj | х1- ф ж2}. Отсюда далее следует линейная зависимость множества {Aj | ж| + ж2 > 0}, поскольку оно содержит предыду­щее множество (ввиду того, что неравенство х1- ф ж| при условии ж|,ж2 > 0 влечет х1- + ж2 > 0). Таким образом, установленная линейная зависимость означает, что ж не является базисным ре­шением. Утверждение доказано.