11 Метод искусственного базиса

В примерах, рассмотренных ранее, предполагалось, что либо задан исходный допусти­мый базис, либо было известно базисное допустимое решение.

В этом подразделе рассматривается общий метод решения задачи ЛП в канонической форме, позволяющий на первом этапе найти базисное допустимое решение или установить, что X ≠ (пуст. Множ.), а на втором — оптимальный базис и соответствующее ему решение либо устано­вить неразрешимость задачи из-за неограниченности целевой функции. При этом не пред­полагается, что ранг матрицы А равен т.

Без ограничения общности можно считать, что система ограничений - равенств Ах = b записана таким образом, что b >= 0. Этого можно добиться, умножая нужные строки на —1.

Тогда метод искусственного базиса можно представить в виде следующих шагов.

0. Построить симплекс-таблицу для задачи ξ=sum{i=1,m}(x_n+i)->min (8)

a_ix+x_n+1=b_i i=1,m (9)

x_j>=0 j=1,n+m (10)

выбрав в качестве базиса В = (A_n+1,..., А_п+т). Здесь a_i — это i-я строка матрицы А (i = 1, т). Так как матрица В единичная, то для построения таблицы достаточно в целевой функции ξ выразить базисные переменные (искусственный базис) x_n+i (i= 1m) через небазисные переменные Xj (j = 1,п), используя ограничения (9). В результате получим, что

ξ=sum{i=1,m}(b_i-a_ix)

Следовательно, z₀₀=-sum{i=1,m}(b_i) ; a z_0j=-sum{i=1,m}(a_ij) j=1,n

При этом симплекс-таблица прямо допустима, а базисное допустимое решение имеет вид xj=0 (j=1,n) и xn+1=bi (i = 1, т).

1. Проделать шаги 1-4 алгоритма симплекс-метода, описанного в подразд. 4.4.

Так как целевая функция задачи (8)—(10) ограничена снизу нулем и допустимое мно­жество, задаваемое условиями (9)—(10), непусто, то задача (8)—(10) всегда разрешима и минимум неотрицателен. Поэтому на первом этапе вычисления могут завершиться толь­ко получением прямо и двойственно допустимого базиса. Как только такой базис будет получен, перейти к следующему пункту.

2. Если оптимальное решение ξ * > 0, то КОНЕЦ (исходная задача не имеет допусти­мых решений: X = (пуст. Множ.)), иначе удалить из симплекс-таблицы все столбцы, соответствующие искусственным переменным X_j (j = п + 1, п + т), и нулевую строку.

3. Если базисными переменными являются только переменные исходной задачи Xj (j <= п), то перейти на шаг 7.

4. Выбрать строку, соответствующую искусственной переменной х_r (r > п).

5. Если существует z_rs ≠ 0(1 <= s <= п), то выполнить элементарное преобразование базиса с ведущим элементом z_rs и перейти на шаг 3.

6. Если z_rj = 0 для всех j = 1, п, то удалить r-ю строку из симплекс-таблицы и перейти на шаг 3.

7. Добавить нулевую строку в симплекс-таблицу, записав в неё коэффициенты целе­вой функции основной задачи w(x), выраженной через небазисные переменные. Получена прямо допустимая симплекс-таблица исходной задачи.

8. Проделать шаги 1-4 алгоритма симплекс-метода, описанного в подразд. 4.4.

Шаги 0-7 описанного выше способа получения базисного допустимого решения обычно называют первым этапом симплекс-метода, а метод в целом — двухэтапным симплекс-методом.

Выполнение шага 6 свидетельствует о линейной зависимости уравнений Ах = и, что позволяет удалить часть уравнений. Подобная ситуация возникает, если ранг матрицы А меньше числа уравнений т. После выполнения шага 7 имеем прямо допустимую симплекс-таблицу исходной задачи, т. е. завершён 0-й шаг алгоритма подразд. 4.4. и можно переходить к его шагам 1-4. В результате либо установим, что целевая функция w(x) не ограничена снизу, либо получим оптимальное решение.