Теорема

1. Если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующее ему решение является оптимальным решением исходной задачи.

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

3. Если М-задача не имеет оптимального решения, то и исходная задача также не имеет оптимального решения.

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

1. Задачу линейного программирования привести к каноническому виду.

2. Построить М-задачу.

3. Решить М-задачу симплексным методом, при этом оценки свободных переменных находятся по формуле . Они состоят из двух слагаемых, одно из которых содержит М. Поэтому их будем записывать в двух строках и

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

а) если в оптимальном решении М-задачи все искусственные переменные равны 0, то соответствующее решение исходной задачи является оптимальным и экстремумы целевых функций равны;

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

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