Способ перехода от одного ДБР к другому

Пусть ДБР x⁰ соответствует преобразованной задаче (13)-(15). Перейдем от него к новому ДБР x¹. При этом рассмотрим возможность того, что только одна небазисная переменная станет возрастать, принимая по­ложительные значения, в то время как остальные небазисные переменные останутся нулевыми [10]. Обозначим

и запишем систему ограничений преобразованной задачи по столбцам:

.

Пусть начиная с нуля, возрастает переменная (xN)p, значит, вектор базисных переменных изменяется согласно уравнению

так как другие небазисные переменные остаются равными нулю. При этом, в зависимости от значений ком­понент вектора a
*p возможны 3 следующих случая:

– если ая компонента вектора равна нулю (), то соответствующий ей элемент вектора останется без изменений;

– если ая компонента вектора отрицательна (), то соответствующий ей элемент будет увеличиваться;

– если ая компонента вектора положительна () – соответствующий ей элемент будет уменьшаться и станет меньше нуля, когда величина (x_N)_p сделается достаточно большой. Этого допустить нельзя, т.к. будет нарушена допустимость x¹.

 

Отсюда получаем максимально допустимое увеличение значения (x_N)_p

где a_ip и β_i – элементы векторов a_*p и β соответственно.

Пусть минимум в этом уравнении достигается при i=q тогда, если , то в новом ДБР имеем:

Отметим, что выбор q однозначен. Если уже выбрана увеличиваемая небазисная переменная p-я, то базисная q-я, которая первая обратится в нуль, определяется величинами a_*p и β. Если в нуль обращаются одновременно две или более базисных переменных, мы имеем дело с вырожденным случаем, однако выбрать мы должны только одну из них.

Итак, мы пришли к следующей ситуации: переменная (x_N)_p стала базисной со значением , а переменная (x_B)_q – небазисной (со значением 0). Это означает такую перестановку в разбиении матрицы A, что столбец a_*p становится на место q-го столбца матрицы B. В этом случае будем говорить, что (x_N)_p «вводится» в базис, а (x_N)_p «выводится» из него.

Описанный способ перехода от одного ДБР к другому называется операцией замещения.