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

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

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

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

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

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

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

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

F(X) = c₁Х₁ +... + с_nX_n -M*X_n+1 -... -M*X_n+m => max

a_i,1X₁+... + a_i,nX_n +X_n+i = b_i, (i=1,m)

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

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

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

X^' = (0,... 0, b₁,... b_m)

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

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

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

X^" = (X^"₁,... X^"_n, X^"_n+1,... X^"_n+m)

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

X^" = (X^"₁,... X^"_n)

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

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

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

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

F(X) = 4X₁ +4X₂ +2X₃ +4X₄ +3X₅ +1X₆ => max

-3X₁ +0X₂ +2X₃ +3X₄ +3X₅ +4X₆ = 1
3X₁ -2X₂ -1X₃ +4X₄ +3X₅ -3X₆ = 2
4X₁ -2X₂ +1X₃ -1X₄ -1X₅ -1X₆ = 2
2X₁ +3X₂ +3X₃ +1X₄ +2X₅ -3X₆ = 3

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

-3X₁ +0X₂ +2X₃ +3X₄ +3X₅ +4X₆ +X₇ = 1
3X₁ -2X₂ -X₃ +4X₄ +3X₅ -3X₆ +X₈ = 2
4X₁ -2X₂ +X₃ -X₄ -X₅ -X₆ +X₉ = 2
2X₁ +3X₂ +3X₃ +X₄ +2X₅ -3X₆ +X₁₀ = 3

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

F(X) = 4X₁ +4X₂ +2X₃ +4X₄ +3X₅ +X₆ - MX₇ - MX₈ - MX₉ - MX₁₀ => 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).