Суть метода искусственного базиса

В случаях, когда сразу не выделяются базисные переменные (а они сразу выделяются только после приведения к каноническому виду задачи, в которой имеются только неравенства типа «≤» при неотрицательных правых частях) можно применять так называемый метод искусственного базиса, который является по сути разновидностью симплекс-метода.

Пусть задача приведена к каноническому виду (1.6), в котором в некоторых уравнениях, скажем в i ₁-м, i ₂-м, …, i_s -м, явно не выделяются базисные переменные. Добавим в эти уравнения искусственные переменныеx_{m +1}, x_{m +2}, …, x_{m + s}, а в целевую функцию - слагаемые ± Mx_{m +1}, ± Mx_{m +2}, …, ± Mx_{m + s}, где M >>1 (M - достаточно большое положительное число) причём «±» - это «+», если решается задача на min, и «±» - это «-», если решается задача на max. Получается новая задача, которая называется дополнительной или вспомогательной.

Например, вспомогательная (дополнительная) задача с искусственными переменными для задачи (1.5) будет иметь вид

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n + Mx_{n + m +1}+ Mx_{n + m +2}+…+ Mx_{n +2 m} ®min

Аналогично, если задача (2.1) решается на max и придётся вводить искусственные переменные во все ограничения, то получаем следующую вспомогательную задачу:

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n - Mx_{n +1}- Mx_{n +2}-…- Mx_{n + m} ®max

(5.1)

5.1.1. Если (, , …, , , …, ) оптимальное решение вспомогательной задачи, где , …, - значения искусственных переменных, , , …, - значения переменных в исходной задаче в канонической форме, то =…= =0 и (, , …, ) - оптимальное решение исходной задачи. При этом значения целевой функции исходной и вспомогательной задач совпадают.

Отсюда получаем, что для решения задачи линейного программирования, методом искусственного базиса достаточно:

1. Привести задачу к каноническому виду.

2. Если в задаче в каноническом виде нет базиса из единичных векторов, то составить вспомогательную задачу (если в задаче в каноническом виде имеется базис из единичных векторов, то задача решается обычным симплекс-методом).

3. Решить вспомогательную задачу, и если (, , …, , , …, ) - оптимальное решение вспомогательной задачи, где x ₁, x ₂, …, x_m - основные и дополнительные переменные (из задачи в каноническом виде), x_{m +1}, x_{m +2}, …, x_{m + s} - искусственные переменные то (, , …, ) - решение задачи в каноническом виде. Оптимальное значение целевой функции вспомогательной задачи равно оптимальному значению исходной задачи.

При этом к вспомогательной задаче применяется обычный симплекс-метод с некоторыми своими особенностями:

1. Так как целевая функция вспомогательной задачи имеет слагаемые с коэффициентами ± M, то оценки D _k имеют вид ± M, причём M - достаточно большое число. Поэтому при ≠0 знак D _k фактически определяется знаком при . В связи с этим в симплекс-таблице на начальном этапе (пока в базис входят искусственные переменные) вместо одной строки D _k записывают две строки и , и при применении критерия оптимальности ориентируются только на строку .

2. Искусственные переменные по мере их выведения из базиса исключаются из дальнейшего рассмотрения.

3. После того, как все искусственные переменные будут выведены из базиса, коэффициенты D _k при M будут равны нулю, в таблице остаётся только строка =D _k.

Пример. Решить пример из предыдущего параграфа методом искусственного базиса.

Решение. Напоминаем задачу:

-3 x ₁+ x ₂+2 x ₃ ® max(min)

1. Приведём задачу к каноническому виду:

-3 x ₁+ x ₂+2 x ₃ ® max(min)

2. В базис в виде единичного вектора входит только вектор при x ₄, то есть переменная во втором уравнении. В первое и третье уравнения системы ограничений вводим искусственные переменные x ₆ и x ₇:

В целевую функцию они войдут с коэффициентами M или - M в зависимости от того, решается задача на min или на max.

Решим задачу на максимум. Тогда вспомогательная задача - следующая:

-3 x ₁+ x ₂+2 x ₃- Mx ₆- Mx ₇ ® max

3. Решаем полученную вспомогательную задачу с применением симплекс-таблиц:

Базис

С б

Своб. чл.

-3

- M

- M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

- M

-1

min

x 4

-

x 7

- M

-1

-1

-2

-8

-2

-3

Здесь D₂=-2 M -1, D₃=-3 M -2. Коэффициенты при M записаны в строке . Имеем, что D₂<0 и D₃<0, то есть для переменных x ₂ и x ₃ нарушается критерий оптимальности. Поэтому в базис будем вводить x ₂ или x ₃. Какую именно из этих переменных, и вместо какой из искусственных (вместо x ₆ или вместо x ₇), определяем с помощью столбцов q ₂ и q ₃. На пересечении столбца q ₂ и строк и числа соответственно 2 и 4 означают, что в случае включения в базис x ₂ значение функции возрастёт на - q ₂D₂=4 M +2, а в случае включения в базис x ₃ значение функции возрастёт на - q ₃D₃=3 M +2<- q ₂D₂. Поэтому в базис включаем x ₂ (что обеспечивает большее возрастание функции и в конечном итоге ускоряет процесс решения задачи). Так как min =2 достигается в строке x ₆, то из базиса исключаем x ₆. Строим новую симплекс-таблицу, в который уже столбец с искусственной переменной x ₆ отсутствует (вычеркнут), так как искусственная переменная x ₆ из дальнейшего процесса исключается. В новой таблице коэффициент при x ₂ в первой строке (которая теперь соответствует новой базисной переменной x ₂) равен 1, а во второй равен нулю. Поэтому первые две строки в новую таблицу переписываем из старой. Для того, чтобы в строке x ₇ при x ₂ получить 0, из строки x ₇ в старой таблице вычитаем новую первую. Получаем следующую, очередную, таблицу:

Базис

С б

Своб. чл.

-3

- M

- M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

- M

-1

-1

min

-4

-2

Так как D _k <0 только для одного значения k =1, а именно, D₁=-2 M +2<0 (напоминаем, что M - достаточно большое число, так что -2 M <2 и D₁<0), то ищем только отношения q ₁. Минимум этих отношений достигается в строке x ₇: min =2. Поэтому искусственная переменная исключается из базиса, а вместо неё в базис включается x ₁.

Искусственные переменные теперь исключены из базиса. Поэтому дальше работаем с обычной симплекс-таблицей, в которой новая третья строка (соответствующая переменной x ₁) получается делением старой третьей строки на 2. Затем эту новую третью прибавляем к старой первой и вычитаем из старой второй. В результате в новой таблице в столбце x ₁ появятся соответственно 0, 0 и 1:

Базис	С б	Своб. чл.	-3
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2
x 4					3/2		1/2
x 7	-3				-1/2		-1/2
D k	-2

В полученной таблице D _k ³0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X ₀=(2; 4; 0) является оптимальным решением, при котором значение целевой функции равно -2 (x ₄ в окончательном ответе не учитывается, так как она является дополнительной переменной, и не входит в первоначальную задачу).

Решим задачу на минимум (min). Тогда вспомогательная задача - следующая:

-3 x ₁+ x ₂+2 x ₃- Mx ₆- Mx ₇ ® max

Как и выше, решаем полученную вспомогательную задачу с применением симплекс-таблицы:

Базис

С б

Своб. чл.

-3

M

M

q 2

q 3

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 6

M

-1

min

x 4

-

x 7

M

-1

-1

-2

-1

Критерий оптимальности нарушается для переменных x ₂ и x ₃: D₂=2 M -1>0, D₃=3 M -2>0. Так как - q ₂D₂=-4 M +2 по абсолютной величине превосходит - q ₃D₃=-3 M +2, то в базис включаем x ₂. При этом min =2 достигается в строке x ₆, и из базиса исключаем x ₆. Переход к новой таблице аналогичен переходу при решении задачи на max:

Базис

С б

Своб. чл.

-3

- M

- M

q 1

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 2

-1

-

x 4

x 7

- M

-1

-1

min

-1

-1

Теперь D₁>0. Поэтому переход к новой таблице аналогичен соответствующему переходу при решении задачи на max: в базис вводится x ₁ вместо x ₇:

Базис	С б	Своб. чл.	-3					q 3	q 5
x 1	x 2	x 3	x 4	x 5
x 2					3/2		-1/2	8/3	-
x 4					3/2		1/2	4/3
x 7	-3				-1/2		-1/2	-	-
D k	-2						-4/3	-4

Имеем D₃=1>0 и D₅=1>0. Так как |- q ₅D₅|=|- q ₃D₃|, то вводим в базис x ₅ (вместо x ₄): сначала умножаем 2-ю строку на 2, а затем новую вторую строку, умноженную на ½, прибавляем к первой и третьей (фактически вторую старую прибавляем к первой и третьей):

Базис	С б	Своб. чл.	-3
x 1	x 2	x 3	x 4	x 5
x 2
x 4
x 7	-3
D k	-6			-2	-2

В полученной таблице D _k £0 для всех k =1, 2, …, 5, то есть критерий оптимальности выполнен. Поэтому X ₀=(4; 6; 0) является оптимальным решением, при котором значение целевой функции равно -6.

Ответ: F _min=-6, минимум достигается в точке X ₂=(4; 6; 0);

F _max=-2, максимум достигается в точке X ₁=(2; 4; 0).

5.2. Упражнение. Решить соответствующие задачи линейного программирования из Упражнения 1.3 методом искусственного базиса.