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

(М-задача)

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

Рассмотрим задачу в общем виде:

(1)

(2)

Пусть система (1) не является системой с базисом. Прибавим к левой части каждого уравнения системы (1) переменную у_i ≥ 0, которую назовем искусственной. Система примет вид:

(3)

(3) – система с базисом.

Составим новую целевую функцию:

(4)

Задача нахождения максимума функции (4) при ограничениях (3) называется М-задачей.

Замечание 1. Если исходная задача решается на минимум, то целевая функция М-задачи составляется так:

В обоих случаях М может принимать сколь угодно большое положительное значение.

Замечание 2. Искусственные неизвестные следует вводить только в те ограничения, которые не содержат базисных неизвестных.

Связь между решениями исходной и М-задачей устанавливается следующими теоремами.

Теорема 1. Если в оптимальном плане М-задачи все искусственные переменные равны нулю, то соответствующее решение исходной задачи также является оптимальным.

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

Алгоритм метода искусственного базиса имеет свои особенности:

1) симплексная таблица имеет две оценочные строки: М-строку и Z-строку. Оценка в М-задаче имеет вид: а + bМ, где М > 0 сколь угодно большое число. Следовательно, знак оценки определяется знаком коэффициента b. Число а записываем в Z-строку (первую строку оценки), а коэффициент b – в М-строку (вторую строку);

2) разрешающий столбец выбирается по оценкам М-строки;

3) если все искусственные переменные вышли из базиса, задача решается дальше обычным симплекс-методом;

4) если М-задача решена, но искусственные переменные не вышли из базиса, то исходная задача решения не имеет.

Пример 1.

Преобразуем систему ограничений к системе уравнений:

Второе и третье ограничения не содержат базисных неизвестных, поэтому мы добавляем искусственные переменные именно в эти уравнения:

Целевая функция М-задачи:

Составляем симплексную таблицу:

Сj	Б	0	5	2	-1	0	0	θ
0		5 6 1	2 3 5	1 2 3	1 1 4	1 0 0	0 0 -1	5/2 2 1/5
		0	-5	-2	1	0	0
		-7	-8	-5	-5	0	1
0 5		23/5 27/5 1/5	0 0 1	-1/5 1/5 3/5	-3/5 -7/5 4/5	1 0 0	2 /5 3/5 -1/5	23/2 27/3 -
		1	0	1	5	0	-1
		-27/5	0	-1/5	7/5	0	-3/5
0 0 5		1 9 2	0 0 1	-1/3 1/3 2/3	1/5 -7/5 1/3	1 0 0	0 1 0
		10	0	4/3	8/3	0	0

Оптимальный план:

Замечание. Как только искусственные переменные выходят из базиса, элементы М-строки обращаются в ноль, и в дальнейшем М-строка из рассмотрения исключается.

Пример 2.

Вводим балансовые переменные:

Система не каноническая.

Составляем М-задачу:

Решаем М-задачу симплексным методом:

Сj	Б		2	3	0	0	θ
0		1 6	1 3	1 2	1 0	0 -1	1 2
		0	-2	-3	0	0
		-6	-3	-2	0	1
2		1 3	1 0	1 -1	1 -3	0 -1
		2	0	-1	2	0
		-3	0	1	3	1

М-задача решена (нет отрицательных оценок в М-строке), но в этом решении искусственная неизвестная y осталась в базисе, следовательно, исходная задача не имеет оптимального решения, так как область допустимых решений этой задачи пустая.

Решить следующие задачи:

1.

3.

5.

7.

9.

11.

2.

4.

6.

8.

10.

12.

13.

15.

14.

16.