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

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

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

Предположим, что исходная задача линейного программирования представлена в основной форме:

Алгоритм М-метода:

В каждое i-ое ограничение вводим искусственную переменную хn+i >0. Всего m новых искусственных переменных.

Если, то в целевую функцию L вводим m дополнительных слагаемых вида: -M×xn+1, -M×хn+2, ..., -M×хn+m; если же, то слагаемые вида: M×xn+1, M×хn+2, ..., M×хn+m, где М — произвольная очень большая константа.

Получим новую, вспомогательную задачу линейного программирования:

F(X) = c1Х1 +… + сnXn -M*Xn+1 — … -M*Xn+m => max

ai,1X1+… + ai,nXn +Xn+i = bi, (i=1,m)

Xj >0, (j=1,n+m)

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

Формируем начальное базисное решение новой М-задачи :

X' = ( 0,… 0, b1,… bm )

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

Анализируем решение М-задачи в соответствии со следующими правилами :

Если в оптимальном решении М-задачи:

X" = ( X"1,… X"n, X"n+1,… X"n+m )

все искусственные переменные равны 0, то вектор

X" = ( X"1,… X"n )

является оптимальным решением исходной ЗЛП.

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

Если М-задача не имеет решения, то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.

Исходная ЗЛП:

F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +1X6 => max

-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 = 1
3X1 -2X2 -1X3 +4X4 +3X5 -3X6 = 2
4X1 -2X2 +1X3 -1X4 -1X5 -1X6 = 2
2X1 +3X2 +3X3 +1X4 +2X5 -3X6 = 3

Вводим в ограничения искусственные переменные :

-3X1 +0X2 +2X3 +3X4 +3X5 +4X6 +X7 = 1
3X1 -2X2 -X3 +4X4 +3X5 -3X6 +X8 = 2
4X1 -2X2 +X3 -X4 -X5 -X6 +X9 = 2
2X1 +3X2 +3X3 +X4 +2X5 -3X6 +X10 = 3

Вводим в целевую функцию дополнительные слагаемые:

F(X) = 4X1 +4X2 +2X3 +4X4 +3X5 +X6 — MX7 — MX8 — MX9 — MX10 => max

Т.о. мы получили новую ЗЛП.

Сформируем начальное базисное решение новой М-задачи :

X'=( 0, 0, 0, 0, 0, 0, 1, 2, 2, 3 );

После решения М-задачи симплекс методом мы получили следующее оптимальное решение: X"=( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75, 0.00, 0.00, 0.00, 0.00 ); В этом решении все искусственные переменные равны 0, следовательно мы нашли оптимальное решение и для исходной ЗЛП: X = ( 1.2, 0.77, 0.00, 0.54, 0.00, 0.75 ).