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

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

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

Исходная ЗЛП в канонической форме:

F(X) = c₁Х₁ +... + с_nX_n => max

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

X_j>0, (j=1,n)

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

1. В каждое i-ое ограничение вводим искусственную переменную X_n+i >0. Всего m новых искусственных переменных.
2. В целевую функцию F вводим m дополнительных отрицательных слагаемых вида:
   
   -M*X_n+1 -M*X_n+2...-M*X_n+m,
   
   где М - произвольная очень большая константа.
3. Получим новую ЗЛП вида:
   
   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_n+i = b_i - a_i,1X₁ -... - a_i,nX_n, (i=1,m)
4. Формируем начальное базисное решение новой М-задачи:
   
   X^' = (0,... 0, b₁,... b_m)
5. Решаем М-задачу симплекс-методом
6. Анализируем решение М-задачи в соответствии со следующими правилами:
• Если в оптимальном решении М-задачи:
  
  X^" = (X^"₁,... X^"_n, X^"_n+1,... X^"_n+m)
  
  все искусственные переменные равны 0, то вектор
  
  X^" = (X^"₁,... X^"_n)
  
  является оптимальным решением исходной ЗЛП.
• Если в оптимальном решении М-задачи хотя бы одна искусственная переменная не равна 0, то исходная ЗЛП не имеет решения в силу несовместимости ограничений.
• Если М-задача не имеет решения, то исходная ЗЛП также не имеет решения в силу неограниченности целевой функции на допустимом множестве.