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

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

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

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

2. Построить М-задачу. Для этого в каждое уравнение системы ограничений, не имеющее переменной, исключенной из других уравнений, необходимо ввести искусственную переменную с коэффициентом 1, не меняя знак равенства. Искусственные переменные также вводятся и в целевую функцию с коэффициентом –М (или +М, если решается задача на минимум), где М – сколь угодно большое число.

3. Выписать исходное опорное решение.

4. Рассчитать оценки свободных переменных по формуле

,

где

- коэффициенты при свободной переменной x_j,

- коэффициенты при базисных переменных в целевой функции,

- коэффициент при свободной переменной в целевой функции;

и записать оценки в двух строках и : строка содержит коэффициенты при множителе М в оценке ; строка содержит другую часть оценки.

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

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

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

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

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

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