Метод искусственного базиса (м-метод)

Используется, когда первое БР – недопустимое.

В каждое уравнение, дающее отрицательную компоненту в БР, вводится своя новая неотрицательная искусственная переменная У1, У2, …, Ук, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаются в число основных (базисных) все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты БР. Составляется новая линейная функция Т = F – М(У1 + У2 + … + Ук), где М – произвольно большое число, и ищется ее максимум. (Слайд 6)

Справедлива теорема (без доказательства):

1. Если в оптимальном решении новой функции все искусственные переменные = 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. Тмах = Fмах, если У1=У2=…=Ук=0, т.е. минимум М-функции = 0) .

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

3. Если Тмах = ¥, то исходная задача также неразрешима, причем либо Fмах = ¥, либо условия задачи противоречивы.

Из теоремы следует, что сначала надо найти минимум М-функции. Если он = 0, то далее можно отбросить эти переменные и решать исходную задачу, исходя из полученного БР. На практике находят не минимум М-функции, а максимум (-М)-функции.

Пример:

F=x1 + 2х2  max х1 - х2 <= -1 х1 - х2 >= -3 х1 <= 3 х1, х2 >= 0

Расширенная система имеет вид: х1 – х2 + х3 = -1 х1 - х2 - х4 = -3 х1 + х5 = 3 х1, х2, х3, х4, х5, х6 >= 0

Х1= (0; 0; -1; 3; 3) – недопустимое БР, поэтому в первое уравнение введем искусственную переменную У1 с тем же знаком, что и свободный член.

х1 – х2 + х3 – у1= -1 х1 - х2 - х4 = -3 х1 + х5 = 3

- х1 + х2 - х3 + у1= 1 - х1 + х2 + х4 = 3 х1 + х5 = 3

В первой симплексной таблице последняя строка – это (-М)-функция, т.е. (-М)У1. Заполняется умножением строки У1 на коэффициент (-М).

Б (Слайд 7) азис	Свободный член	Переменные						Оценочное отношение
		Х1	Х2	Х3	Х4	Х5	У1
У1	1	-1	1	-1	0	0	1	1
Х4	3	-1	1	0	1	0	0	3
Х5	3	1	0	0	0	1	0	¥
F	0	-1	-2	0	0	0	0
-Мф	-М	М	-М	М	0	0	-М

Заменяем У1 на Х2.

Базис	Свободный член	Переменные					Оценочное отношение
		Х1	Х2	Х3	Х4	Х5
Х2	1	-1	1	-1	0	0
Х4	2	0	0	1	1	0
Х5	3	1	0	0	0	1
F	2	-3	0	-2	0	0
-Мф	0	0	0	0	0	0

Последняя строка показывает, что критерий оптимальности выполнен: мах (-М) = 0, значит мин М = 0. далее эту строку можно не рассматривать. Получено ДБР (0; 1; 0; 2; 3), начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом.