Выбор столбца для ввода (вывода) в базис (из базиса) и неоднозначность данного выбора. Обоснования этих выборов

Можно доказать, что допустимость базиса, к которому осуществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса:

F для столбца l, претендующего на ввод в базис, и вектора ограничений b рассматриваются

отношения

и определяется такая строка r, что

Полученный индекс r определяет номер столбца в N(β^(q)), выводимого из базиса, а именно, N(β^(q)).

Таким образом, если базис на q-й итерации включал столбцы с номерами

то базис на итерации q + 1 будет состоять из столбцов с номерами:

Отдельно следует обсудить тот случай, когда столбец a_l (β^(q)), претендующий на ввод в базис, не содержит положительных компонентов a_l (β^(q)) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана. Геометрически ситуация, когда a^l (β^(q)) ≤ 0, соответствует тому, что ось ординат оказывается внутри конуса, натянутого на систему расширенных столбцов а^j, а значит, прямая, проведенная через конец вектора b параллельно оси аппликат, однажды «войдя» в этот конус, более никогда из него «не выходит».

Вообще говоря, после перехода от базиса β^(q) к базису β^(q+1) мы можем заново сформировать матрицы ∆ (β^(q+1)), Δ^-1 (β^(q+1)) и, вычислив А(β^(q+1)) = Δ^-1 (β^(q+1))A, делать выводы о его оптимальности. Однако, учитывая, что β^(q+1) отличается от β^(q) всего лишь одним столбцом, с точки зрения техники вычислений представляется рациональным непосредственно переходить от A (β^(q)) и b (β^(q)) к A (β^(q+1)) и b (β^(q+1)). Дело в том, что у матриц типа A (β^(q)) столбцы, соответствующие базисным векторам, состоят из нулей, за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется порядковым номером базисного столбца в N(β^(q)). Поэтому для получения матрицы A (β^(q+1)) достаточно с помощью линейных операций над строками матрицы A (β^(q)) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.