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

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

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

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

Пример 1

Найти максимум Z=4X1+2X2+X3

Х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=4X1+2X2+X3+0×X4+0×X5

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

Следует отметить, что искусственные переменные вводятся только для математической формализации задачи. Поэтому схема вычислений должна быть такой, чтобы искусственные пременные не могли попасть в окончательное решение в числе базисных переменных. С этой целью для искусственных переменных в целевой функции вводят коэффициент М, обозначающий очень большое число. На практике (особенно при решении задачи на ЭВМ) вместо М берут конкретное большое число, например, 10000. Причем, при решении задачи на максимум этот коэффициент вводится в целевую функцию со знаком минус, а при решении на минимум – со знаком плюс. Теперь будем решать Т (М)-задачу, целевая функция которой содержит целевую функцию Z–задачи и искусственные переменные с коэффициентом ±М, т.е.

m

T=Z-M S yi, при решении на максимум целевой функции и

i=1

m

T=Z+M S y, при решении на минимум целевой функции

i=1

В нашем случае:

Х1+Х2+Х3-Х4+y1=8

2Х1+Х2+Х3+Х5=8

3Х1+2Х2+Х3+y2=15

Хj³0, j=1,...,5

Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)

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

- в первую строку записываем оценки , которые не содержат коэффициент М;

- во вторую строку- оценки по каждой свободной переменной, содержащие коффициент М.

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

- при расчете оценок Z -строки должны быть учтены коэффициенты Cj , входящие в функцию Z ;

- при расчете оценок М-строки этот коэффициент во внимание не берется, а М -выносится как общий множитель .

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

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

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

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

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

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

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

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

Таблица 3.1.

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

Заполнение Z- строки осуществляется по формуле (2):

а00 = 0 × 8– 0 = 0

а01 =0 × 2– 4 = -4

а02 =0 × 1– 2 = -2

а03 =0 × 1– 1 = -1

а02 =0 × 0– 0 = 0

Заполнение М- строки:

а¢00 = -М × 8 + (–М) × 15 = -23М

а¢01 = -М × 1 + (–М) × 3= -4М

а¢02 = -М × 1 + (–М) × 2= -3М

а¢03 = -М × 1+ (–М) × 1 = -2М

а¢04 = -М ×(-1)+ (–М) × 0 = 1М

М выносим как общий множитель.

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

Таблица 3.2.

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

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

Таблица 3.3.

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

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

Таблица 3.4.

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

В оценочной строке все элементы являются неотрицательными величинами, следовательно получено оптимальное решение:

Zmax=15 Xopt(0,7,1,0,0)

Пример2

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

Таблица 3.5.

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

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