Математическое программирование для студентов сельхозакадемии

МЕТОД ИСКУССТВЕННОГО БАЗИСА, ИЛИ М-МЕТОД

До сих пор мы всесторонне рассматривали задачу, решение кото­рой осуществлялось на основе простейшего алгоритма симплексного метода, поскольку все ограничения имели вид меньше либо равно. В этом случае дополнительные переменные задачи образуют единичный базис. Но может получиться так, что система ограничений представле­на в канонической форме, но она не приведена к единичному базису.

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

Алгоритм решения задачи симплексным методом с искусственным базисом рассмотрим на примере.

Пример 1:
Найти максимум Z = 4Х1 + 2Х2 + Хз
Х1 + Х2 + Х3 ? 8
2Х1 + Х2 + Х3 ? 8
3Х1 + 2Х2 + Х3 = 15
Хj ? 0, j = 1,…,3.

Переходим к канонической форме:
Х1 + Х2 + Х3 – Х4 = 8
2Х1 + Х2 + Х3 + Х5 = 8
3Х1 + 2Х2 + Х3 = 15
Хj ? 0, j = 1,…,5
Zmax = 4Х1 + 2Х2 + Х3 + 0*Х4 + 0*Х5.

Данная система ограничений не имеет единичного базиса, так как дополнительная переменная Х4 имеет коэффициент минус единица, а третье ограничение было представлено уравнением, и в нем отсутст­вует базисная переменная. Для того чтобы был единичный базис, вводим в соответствующие ограничения искусственные переменные У1 и У2 с положительными коэффициентами (+1).

Следует отметить, что искусственные переменные вводятся толь­ко для математической формализации задачи. Поэтому схема вычис­лений должна быть такой, чтобы искусственные переменные не мог­ли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например 10 000. Причем при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум — со знаком плюс. Те­перь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z-задачи и искусственные переменные с коэффи­циентом  ±М, то есть
m
Т = Z — М ? Уi    при решении на максимум целевой функции и
i =1
m
Т = Z + М ? Уi    при решении на минимум целевой функции.
i=1

В нашем случае:
Х1 + Х2 + Х3 – Х4 + У1  = 8
2Х1 + Х2 + Х3 + Х5 = 8
3Х1 + 2Х2 + Х3 + У2 = 15
Хj ? 0, j = 1,…,5
Тmax = 4Х1 + 2Х2 + Х3 + 0*Х4 + 0*Х5 – М(У1 + У2).

Эта задача решается в симплексных таблицах, но для удобства целевую функцию разбивают на 2 строки:

• в первую строку записываем оценки, которые не содержат ко­эффициент М;
• во вторую строку — оценки по каждой свободной переменной, содержащие коэффициент М.

Расчет элементов (оценок) этих двух строк производится по фор­муле (1). Только отличие:

• при расчете оценок Z-строки должны быть учтены коэффици­енты Сj, входящие вфункцию Z;
• при расчете оценок М-строки этот коэффициент во внимание не берется, а М — выносится, как общий множитель.

Для того чтобы Т-задача и Z-задача были равны, нужно, чтобы значения Уi были равны нулю. Поэтому, пока Уi не равно нулю, раз­решающий столбец выбирается по оценкам во второй строке, исполь­зуя алгоритм симплексного метода.

Лишь после того, как все Уi станут равны нулю, дальнейший рас­чет будет вестись по первой индексной строке, то есть — обычная Z-задача.

Причем, когда искусственная переменная будет выводиться из базиса, ее выбросим из симплексной таблицы, а в следующей сим­плекс-таблице не будет бывшего разрешающего столбца.
Между оптимальными решениями М-задачи и Z-задачи сущест­вует связь, устанавливаемая следующей теоремой:

1.Если в оптимальном решении М-задачи все искусственные пе­ременные (Уi) равны нулю, то это решение будет являться оптималь­ным решением Z-задачи

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

3. Если М-задача оказалась неразрешимой (Т>+? или-?), то ис­ходная задача также неразрешима либо по причине несовместности системы ограничений, либо по причине неограниченности функции Z.

Составим первую симплексную таблицу. При решении М-методом разрешающий столбец можно выбирать в М-строке не по наиболь­шей, по абсолютной величине отрицательной оценке (при решении на максимум) и не по наибольшей положительной оценке (при решении на минимум), а по той из них, которая быстрее выводит У из базиса. В данном примере разрешающим столбцом будет столбец свободной переменной Х2 с оценкой (-3).

Таблица 3.1
Первая симплексная таблица

Св.П Б.П.	Сj Ci	0	4	2	1	0	ai0/aip
		ai0	X1	X2	X3	X4
У1	-М	8	1	1	1	-1	8
X5	0	8	2	1	1	0	8
У2	-М	15	3	(2)	1	0	7,5 <
Z		0	-4	-2	-1	0
	М	-23	-4	-3 ^	-2	1

Заполнение Z-строки осуществляется по формуле:
a00 = 0*8-0=0
a01 = 0*2-4=-4
a02 = 0*1-2=-2
a03 = 0*1-1=-1
a04 = 0*0-0=0.

Заполнение М-строки:
a?00 = -М*8+(-М)*15=-23М
a?01 = -М*1+(-М)*3=-4М
a?02 = -М*1+(-М)*2=-3М
a?03 = -М*1+(-М)*1=-2М
a?04 = -М*(-1)+(-М)*0=1М.
М выносим как общий множитель.

В последнем столбце в разрешающей строке стоит 0, поэтому столбец свободной переменной Х4 переносим без изменений.

Таблица 3.2
Вторая симплексная таблица

Св.П Б.П.	Сj Ci	0	4	1	0	ai0/aip
		ai0	X1	X3	X4
У1	-М	1/2	-1/2	(1/2)	-1	1(-2) <
X5	0	1/2	1/2	1/2	0	1(0)
Х2	2	15/2	3/2	1/2	0	15(0)
Z		15	-1	0	0
	М	-1/2	1/2	-1/2 ^	1

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

Таблица 3.3
Третья симплексная таблица

Св.П Б.П.	Сj Ci	0	4	0	ai0/aip
		ai0	X1	X4
Х3	1	1	-1	-2	—
X5	0	0	(1)	1	0 <
Х2	2	7	2	1	3,5
Z		15	-1^	0

Теперь решаем обычным симплексным методом.
Таблица 3.4

Четвертая симплексная таблица

Св.П Б.П.	Сj Ci	0	0	0
		ai0	X5	X4
Х3	1	1	1	-1
X1	4	0	1	1
Х2	2	7	-2	-1
Z		15	1	1

В оценочной строке все элементы являются неотрицательными величинами, следовательно, получено оптимальное решение:
Zmax = 15     Хопт (0,7,1,0,0).

Пример 2:
Задача решалась на минимум (Z>min) целевой функции. На по­следней итерации получили следующую таблицу:

Таблица 3.5
Последняя симплексная таблица

Св.П Б.П.	Сj Ci	0	4	1	0
		ai0	X1	X3	X4
У1	М	-1/2	-1/2	-1/2	-1
X5	0	1/2	1/2	1/2	0
Х2	2	15/2	3/2	1/2	0
Z		15	-1	0	0
	М	-1/2	-1/2	-1/2	-1

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