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

Отыскание начального опорного плана

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

Пусть исходная ЗЛП имеет каноническую форму записи:

;

где ,

.

Если ни одно из ограничений не имеет предпочтительной переменной, то М-задача запишется так:

;

,

,

.

Тогда начальный опорный план этой задачи: .

Если некоторое уравнение имеет предпочтительный вид, то в него не следует вводить искусственную переменную.

Например, воспользуемся канонической формой записи ЗЛП примера 2 и найдем начальный опорный план методом искусственного базиса.

Составим М-задачу:

;

Тогда начальный опорный план: , значение целевой функции на этом плане:

.

Дата добавления: 2014-01-11