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

 

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

Если же ограничения задачи заданы в виде неравенств вида или уравнений

и (или) ,

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

Преобразование ограничений, заданных в виде уравнений, рассмотрим на примере:

В систему равенств вводим искусственные переменные , , с коэффициентами, равными единице, позволяющими образоватьискусственный базис решения:

Целевая функция имеет вид:

при решении задачи на максимум —

;

при решении задачи на минимум —

.

3a использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается ().

Преобразования ограничений в виде неравенств вида рассмотрим на примере:

Для получения системы уравнений вводим дополнительные переменные .

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

Целевая функция имеет вид:

при решении задачи на максимум —

;

при решении задачи на минимум —

.

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

Сначала образуем систему уравнений, для чего вводим в первое неравенство дополнительную переменную , а в третье неравенство - дополнительную переменную :

Для образования единичной матрицы вводим недостающие элементы: во второе уравнение искусственную переменную , а в третье :

Целевая функция имеет вид:

при решении задачи на максимум —

;

при решении задачи на минимум —

.

Поставленные таким образом задачи можно решать симплексным методом.

Пример 4. Определим минимальное и максимальное значения целевой функции при следующих смешанных условиях-ограничениях:

Запишем систему ограничений в виде равенств, для чего введем дополнительные переменные и , в результате получим следующую систему:

Затем введем искусственные переменные и в первое и второе уравнения:

Для постановки задачи на минимум целевую функцию запишем так:

.

С целью формулировки задачи для решения ее в табличной форме воспользуемся выражениями из системы уравнений для искусственных переменных:

которые подставим в целевую функцию:

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

Последовательность решения задачи симплексным методом представлена в таблице 2.4.5.

 

Таблица 2.4.5

План	Базисные переменные	Значения базисных переменных
I
				-1
								2.5
	11M	6M-1	9M-3	-M
II			1.5		1/8			-1/8
		0.5		-1/8			1/8
				1/4			-1/4	-
	3+2M	0.5+1.5M		(M-3)/8			(3-9M)/8
III					1/12		2/3	-1/12
	1/3			-1/6		-1/3	1/6
				1/4			-1/4
				-5/12		-1/3-M	(3-9M)/8

 

Поскольку задача решается на минимум, то ведущий столбец выбирают по максимальному положительному числу в индексной строке в плане I (9M - 3), а все остальные преобразования проводятся по стандартной схеме до тех пор, пока не получатся в индексной строке только неположительные числа ( 0), а в оптимальном решении должны отсутствовать положительные значения искусственных переменных и . Оптимальному решению соответствует точка с координатами = и =1/3, где , а = =0.

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

Для решения этой же задачи на максимум целевую функцию следует записать иначе:

Затем, подставив выражения для искусственных переменных, получим:

Таблица 2.4.6

План	Базисные переменные	Значения базисных переменных
I
				-1
								2.5
	-11M	-6M-1	-9M-3	M
II			1.5		1/8			-1/8
		0.5		-1/8			1/8
				1/4			-1/4	-
	3-2M	0.5-1.5M		(-M-3)/8			(3+9M)/8
III					1/12		2/3	-1/12
	1/3			-1/6		-1/3	1/6	-
				1/4			-1/4
				-5/12		-1/3-M	(3-9M)/8
IV		1/3				-1/3	2/3
					2/3	-1/3
							-1
						-1/3+M	M

 

Преобразуем это выражение в удобную форму для записи в симплексную таблицу:

Полученные выражения вместе с условиями ограничения записываем для преобразования в симплексную таблицу 2.4.6.

Преобразования проводим до тех пор, пока все значения в индексной строке не станут неотрицательными. В плане IV получили =1/3, = , = , что совпадает с решением задачи, полученным геометрическим методом.