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

Метод искусственного базиса применяется для решения задач ЛП в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов.

Пусть задана задача ЛП в канонической форме, то есть имеет вид (2.1.1), и в ней отсутствует единичный базис. К этой задаче строим вспомогательную задачу (ВЗ):

Здесь w₁,w₂,…,w_m– искусственные переменные. Запишем ограничения в векторном виде:A₁x₁+A₂x₂+…+A_nx_n+A_n+1w₁+…+A_n+mw_m=B, где , , …, , , , …, , . Таким образом, вектора , , …, образуют единичный базис вR^m, и все искусственные переменные соответствующие этим векторам будут базисными. Далее строится обычная симплекс-таблица. Если ВЗ не имеет решения в силу неограниченности целевой функции, то исходная задача также не имеет решения по той же причине. Пусть в результате знакомых по симплекс-методу необходимых преобразований получили оптимальную симплекс-таблицу к ВЗ. Очевидно, что максимальное значение целевой функции ВЗ равно 0, то естьmaxF=0. Если жеmaxF<0, то исходная задача ЛП не имеет решения в силу несовместности системы ограничений. Предположим, чтоmaxF=0. Тогда возможны такие ситуации:

1) все искусственные переменные стали свободными и были исключены из таблицы. В этом случае вычеркиваем столбцы, соответствующие искусственным переменным и последнюю строку. Вместо неё приписываем новую строку оценок, но с использованием исходной целевой функции Z(X). Тем самым получена начальная симплекс-таблица для исходной задачи ЛП, к которой применяем симплекс-метод;

2) в оптимальном решении ВЗ хотя бы одна искусственная переменная осталась базисной. Тогда:

а) либо все числа в строках, соответствующих оставшимся базисным искусственным переменным, равны 0;

б) либо есть хоть одно отличное от 0.

В первом случае, поступаем также как и пункте 1). Во втором, выбираем любой ненулевой элемент в качестве ведущего и делаем шаг жордановых исключений. Через конечное число шагов мы придем или к пункту 1), или к пункту 2)а).

Заметим, что если среди векторов A_j,j=1,2,…,n, были вектора, которые могли бы войти в базис, то искусственные переменные вводят только в те уравнения системы ограничений, в которых отсутствует базисная переменная.

Пример 5.2. Максимизировать функцию Z=x₁+2x₂-2x₃при ограничениях

Решение. Преобразуем исходную задачу линейного программирования к канонической (см. (2.1.1). Для этого введём в ограничения дополнительные неотрицательные переменные. А именно, в первое неравенство – переменную x₄со знаком «+», во второе –x₅со знаком «-» (см. §2.2). Система ограничений примет вид:

Эту систему запишем в векторной форме: A₁x₁+A₂x₂+A₃x₃+A₄x₄+A₅x₅=B, где

, , , , , . Очевидно, что в данной системе ограничений отсутствует единичный базис. Это означает, что среди векторовA_jнет трёх необходимых единичных векторов, которые должны образовывать базис вR³. Однако заметим, что векторA₄ является частью базиса. Ему соответствует базисная переменнаяx₄. Необходимо найти ещё два единичных вектора. Для этого применим метод искусственного базиса. Введём искусственные переменные в те уравнения ограничений, в которых не присутствует базисная переменнаяx₄и построим следующую вспомогательную задачу (ВЗ):

F=-w₁-w₂max

где w₁,w₂– искусственные переменные. Система ограничений ВЗ в векторном виде имеет вид:A₁x₁+A₂x₂+A₃x₃+A₄x₄+A₅x₅+A₆w₁+A₇w₂=B, где вектораA_j,j=1,2,3,4,5 определяются также, как и выше, а и . Таким образом, вектораA₄,A₆,A₇ образуют базис вR³и им соответствуют базисные переменные (БП) –x₄,w₁,w₂. Все остальные переменные, а именноx₁,x₂,x₃,x₅объявляются свободными (СП). Далее к ВЗ применяем обычный симплекс-метод. Как и раньше, см. §5.1, начальный опорный план получается, если присвоить свободным переменным значения, равные нулю. При этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных коэффициентовВ, то естьx₁=x₂=x₃=x₅=0¸ аx₄=8,w₁=4,w₂=12. Строим симплекс-таблицу, соответствующую начальному опорному плану:

С этой таблицей проводим необходимые преобразования (см. §5.1) симплекс-метода, пока не получим оптимальную симплекс-таблицу или не получим неразрешимость. В нашем случае, мы уже на втором шаге будем иметь такую симплекс-таблицу:

Эта таблица будет оптимальной для ВЗ. При этом все искусственные переменные стали свободными и maxF=0. Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием исходной целевой функцииZ(X), получим начальную симплекс-таблицу для исходной задачи ЛП:

Проанализировав последнюю таблицу, делаем вывод, что исходная задача ЛП не имеет решения в силу неограниченности целевой функции.

Пример 5.3. Минимизировать функцию при ограничениях

Если ввести дополнительные неотрицательные переменные ,,,, и перейти к задаче на нахождение максимума целевой функции, исходная задача примет вид:

Z₁=

По виду ограничений (5.2.1) следует, что очевидного базисного допустимого решения нет. Для порождения базисного допустимого решения применим метод искусственного базиса. Изменим первые два ограничения (два других не создают проблем) введением в левую часть искусственных переменных w₁иw₂(w₁, w₂ 0). Решаем ВЗ:

F=-w₁-w₂max

Базисное решение (допустимый план) будет иметь вид: , а,,w₁=10,w₂=5. Строим симплекс-таблицу к ВЗ, соответствующую начальному опорному плану:

Проводя преобразования по методу Жордана-Гаусса, на втором шаге будем иметь оптимальную симплекс-таблицу ВЗ (5.2.2). Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием целевой функцииZ₁(X), получим начальную симплекс-таблицу для задачи (5.2.1):

Преобразования по методу Жордана-Гаусса с последней таблицей приведены ниже:

Все оценки стали положительными, и, следовательно, ,,,,x₅=x₆=0. Так каки, то ограничения, в которые эти переменные входят, превращаются в строгие неравенства. При этом,Z_1max=Z₁(12;8;2;3;0;0)=68, аZ_min= -Z_1max=-68.