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

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

(n>m)

где M – достаточно большое положительное число,

при ограничениях:

( );

( ); ( ).

Для расширенной задачи исходное допустимое базисное решение очевидно:

( ); ( ).

Значение целевой функции для этого решения .

Введение в целевую функцию коэффициентов – M при дополнительных переменных эквивалентно введению «штрафа» за включение в базисное решение переменных ( ). Поэтому числа – M, которые по абсолютной величине значительно больше остальных коэффициентов целевой функции, позволяют выводить из базиса дополнительные переменные,заменяя их переменными исходной задачи. Поэтому метод имеет еще одно название – «больших штрафов».

Таким образом, если в результате решения расширенной задачи получено оптимальное решение вида:

( ); ( ),

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

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

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

Исходная задача:

при ограничениях:

Расширенная задача:

Представим целевую функцию в виде двух групп слагаемых (с множителем M и без него):

Перепишем для записи в симплекс – таблицу в виде двух строк:

Симплекс – таблица:

Номер итерации	F, и базовая переменная	Значения
		-6M	-3 M	-5 M	-3 M	-3 M
	-5	-3	-4
			3
		-M	- M		M	M
	-4		-2
				-2
			-3
				-	-

в точке (1,0,1,0) ит.к. значения переменных .

Дата добавления: 2014-08-04; просмотров: 342; Нарушение авторских прав

Мы поможем в написании ваших работ!