Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Правило вывода столбца из текущего базиса

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

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

отношения

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

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

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

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

Отдельно следует обсудить тот случай, когда столбец al(q)), претендующий на ввод в базис, не содержит положительных компонентов al(q)) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана. Геометрически ситуация, когда al(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)) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.