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

Процедура перехода от вершины к вершине связана с пересчетом большого числа параметров. К ним относятся коэффициенты разложения 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¹. Он может быть представлен как через исходный, так и смежный базисы:

(17)

(18)

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

(19)

получаем

(20)

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

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

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

(21)

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

(22)

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

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

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

.

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

и

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

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

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

.

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

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

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

(23)

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

Отсюда имеем

,

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

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

Дата добавления: 2014-01-11