Метод искусственного базиса (метод больших штрафов)

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

Согласно методу для данной задачи составляется так называемая расширенная задача, которая решается симплексным методом. На основе решения расширенной задачи находят решение исходной или устанавливают его отсутствие.

Пусть имеется КЗЛП:

(1.24)

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

(1.25)

; ; .

Базисом здесь будет являться система искусственных переменных. Данной системе соответствует начальный опорный план . И решается она обычным симплекс – методом.

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