Связь между параметрами последовательных итераций

Процедура перехода от вершины к вершине связана с пересчетом большого числа параметров. К ним относятся коэффициенты разложения a_ij, относительные оценки Δ_j, базисные переменные и критерий. В симплекс-методе для их вычисления применяются обобщенные преобразования Жордана – Гаусса.

Пусть { A_i }⁽⁰⁾, iÎI⁰ ={1,2,…, k,…, m }- исходный базис. Смежный базис отличается от него только одной компонентой:

{ A_i }⁽¹⁾, iÎI¹ ={1,2 ,…,r,…, m }.

Если из множества I⁰ исключить индекс k, а из I¹ удалить r, то эти множества будут тождественно равны.

Возьмем вектор A_j такой, что jÏ I⁰ & jÏ I¹. Он может быть представлен как через исходный, так и смежный базисы:

(4.17)

(4.18)

Зная коэффициенты разложения по исходному базису a_ij, найдем коэффициенты разложения по смежному базису Для этого в (4.17) заменим вектор A_k на вектор A_r. Из представления A_r через исходный базис

(4.19)

получаем

(4.20)

В (4.17) выделим слагаемое с вектором A_k

и заменим в нем A_k выражением (4.20):

После преобразования получаем:

(4.21)

В формулах (4.18) и (4.21) вектор A_j представлен через одну и ту же систему векторов. Приравнивая коэффициенты при одноименных векторах, находим искомые зависимости:

(4.22)

где - число переменных в канонической модели.

В базисном решении выполняется равенство

в котором x_i - базисные переменные. Переобозначим вектор ограничений В на А₀:

.

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

и

Значит, для базисных переменных справедливы соотношения (4.22). Этого и следовало ожидать, так как полученные ранее формулы (4.11) и (4.12) для пересчета базисных переменных являются частным случаем (4.22). Действительно, достаточно заменить в них x_i на a_i0 , чтобы прийти к (4.22).

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

Введем расширенные векторы следующим образом:

.

Так как размерность векторов увеличилась на единицу, базис должен включать m +1 векторов. В качестве недостающего базисного вектора возьмем единичный вектор

в котором единица стоит на позиции m +1. Такой вектор линейно независим от расширенных векторов условий. Как и раньше, рассмотрим два смежных расширенных базиса, образованных векторами с индексами и .

Представим небазисный вектор через расширенный базис:

(4.23)

Так как первые m компонент вектора равны нулю, первые m уравнений в (4.23) тождественны (4.17) и, следовательно, Новыми здесь являются только коэффициенты Чтобы выяснить их смысл, запишем последнее уравнение системы (4.23):

Отсюда имеем

,

то есть оценки и критерий тоже являются коэффициентами разложения.

Таким образом, все параметры симплекс-метода математически представляют собой коэффициенты разложения, а рекуррентные формулы (4.22) справедливы для