Понятие базиса, переход от одного базисного решения к другому

Векторы А ₁, А ₂, …, А_S являются линейно-независимыми, если равенство k ₁ A ₁ +k ₂ A ₂ +…+k_SA_S =0 выполняется только при k ₁ =k ₂ =…=k_S= 0. Признаком линейной независимости векторов является ненулевое значение определителя, составленного из этих векторов, так как однородная система имеет единственное (нулевое) решение только при таком определителе. Если есть система линейно-независимых векторов, то любой другой вектор может быть выражен в виде их линейной комбинации и притом единственным образом: A_p=a ₁ A ₁ +a ₂ A ₂ +…+a_SA_S, pÏ[1, S].

В канонической форме условия записываются в виде Пусть система имеет базисное решение: Тогда (1)

Так как система совместна, то ее определитель не равен нулю, векторы являются линейно-независимыми. Система m линейно-независимых векторов, соответствующих базисным переменным, - базис. Каждой экстремальной точке соответствует своё базисное решение и свой базис.

Теперь, имея исходные базисное решение и базис , построим новое базисное решение. Смежные вершины отличаются по составу базисных переменных только одной. Поэтому новое решение можно получить путем замены одной небазисной переменной на базисную (r, rÏ[1,m]), принимающая в новом решении некоторое положительное значение В новом решении условия также должны выполняться: (2)

Задача состоит в том, чтобы определить X ⁽¹⁾ по X^{( 0)}. Выразим вектор A_r через исходный базис: A_r=A ₁ a _{1 r} +A ₂ a _{2 r} +…+A_ma_mr -> qA_r=qA ₁ a _{1 r} +qA ₂ a _{2 r} +…+qA_ma_mr. (3)

Вычитая (3) из (1), получим:

(4)

Сравнивая (1) и (2), видим, что правые части равны, а левые содержат одну и ту же систему векторов. Поэтому коэффициенты при одноименных векторах должны совпадать. Получаем: Для допустимости решения X ⁽¹⁾ необходимо, чтобы q было ограничено сверху:

Теперь решение всегда будет допустимым, но число ненулевых переменных в нем может превышать m, так как добавлена x_{r ,} а значит, оно может быть небазисным. Если же в качестве значения q выбрать q₀, то одна из переменных станет равной нулю, а решение - базисным. Пусть минимум q₀ достигается на переменной x_k. Тогда базисные переменные в новом опорном решении будут вычисляться по формулам:

Этому решению соответствует новый базис {A_i}⁽¹⁾={A ₁ ,…,A_{k- 1} ,A_r, A_{k+ 1} ,…,A_m}. Таким образом, переход к новому базисному решению произошел путем замены переменной X_k на X_r, соответсвенно в базисе - A_k на A_r.

Рассмотрим возможные ситуации при переходе от одного решения к другому. Как было показано выше, при существовании положительных коэффициентов a_ir достигается новое базисное решение (смежная вершина), что иллюстрируется рис. а. Если же все a_ir неположительны, величина q, а это значениевводимой переменной, не ограничена сверху. Следовательно, введение такой переменной не приведет к получению базисного решения (достижению новой вершины). Это признак того, что соответствующее ребро допустимого множества, а значит, и само множество оказываются неогранниченными (рис. б).

При вычислении q₀ минимум может достигаться более чем на одном индексе. При этом обнуляется более одной переменной из входящих в исходное решение. Следовательно, в новом решении будут базисные переменные с нулевым значением, что означает попадание в вырожденное базисное решение.

Если исходное решение вырожденное и нулевой переменной соответствует коэффициет a_kr >0, то q₀ =0 и значения переменных не изменяются. Однако состав базиса и базисных переменных изменится - произойдет замена на