Тема 4. Симплекс-метод с искусственным базисом

Для задачи, записанной в канонической форме задачи линейного програм­мирования, можно непосредственно указать ее опорный план, если среди векторов A_j, компонентами которых служат коэффи­циенты при неизвестных в системе уравнений данной задачи, име­ется m единичных. Однако для многих задач линейного програм­мирования, записанных в канонической форме задачи линейного програм­мирования и имеющих опорные планы, среди векторов A_j не всегда есть т единичных.

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

Метод искусственного базиса заключается в применении правил симплекс-метода к так называемой М-задаче. Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной ЗЛП таких искусственных единичных векторов P_i, с соответствующими неотрицательными искусственными переменными s_i, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов.

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

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

Пример 8. Рассмотрим ЗЛП вида:

Целевая функция

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

Решить симплекс-методом.

Решение: Задача была решена графическим методом в примере 4. Решим и сравним результаты.

Приведем ЗЛП к канонической форме:

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

Среди векторов A₁, A₂, A₃, A₄, A₅, A₆ нет четырех еди­ничных вектора, необходимых для перехода к решению задачи симплекс-методом.

Поэтому в левые части 1-го и 2-го уравнений добавляем неотрицательные искусственные переменные s₁ и s_2, чтобы вновь полученная матрица A содержала систему единичных линейно-независимых векторов.

Получаем следующую М-задачу:

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

Первоначальный опорный планХ=(0; 0; 0; 0; 6; 7; 4; 3), определяемый системой четырех единичных векторов P₁, P₂, A₅ и A₆. Искусственной переменной s₁ соответствует единичный вектор P₁, а переменной s₁ вектор P₂. Составляем симплексную таблицу:

Таблица 3.9

I	i	Базис	Сб	B	2	1	0	0	0	0	-M	-M	Qmin
A1	A2	A3	A4	A5	A6	P1	P2
1	P1	-M			-1	-1						2
2	P2	-M					-1					1
3	A5	0			-1							2
4	A6	0										1
	-7M	-5M-2	-M-1	M	M

Как видно из табл. 3.9, план не оптимален, так как есть отрицательные оценки , самая наименьшая из которых 5M-2, так как под М понимается достаточно большое положительное число. Вектор P₂ исключаем из базиса. Этот вектор не имеет смысла вводить ни в один из последую­щих базисов, поэтому в дальнейшем столбец данного вектора не заполняется. Рассчитываем оценки Q_min, и переходим к новому опорному плану и строим новую симплексную таблицу:

Таблица 3.10

II	i	Базис	Сб	B	2	1	0	0	0	0	-M		Qmin
A1	A2	A3	A4	A5	A6	P1
1	P1	-M				-1
2	A1	2									-
3	A5	0			-3						3
4	A6	0									0
	2-2M	0		M

Из табл. 3.10 видно, что план не оптимален, одна отрицательная оценка и не искусственные векторы выведены из базиса. Рассчитываем оценки Q_min и переходим к новому опорному плану и строим новую симплексную таблицу:

Таблица 3.11

III	i	Базис	Сб	B	2	1	0	0	0	0	-M		Qmin
A1	A2	A3	A4	A5	A6	P1
1	P1	-M				-1
2	A1	2
3	A5	0
4	A4	0
	2-2M	0		M

Так как все оценки неотрицательны, но искусственный вектор P₁ не выведен из базиса, следовательно М-задача неразрешима, что означает, что исходная задача также неразрешима, что и было также получено при ее решении графическим методом в примере 4.

Пример 9. Рассмотрим ЗЛП вида:

Целевая функция

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

Решить симплекс-методом.

Решение: В канонической форме записи целевая функция стремится к максимуму. Переход от минимуму к максимуму осуществляется по правилу:

f₁( ) = - f( ).

А затем полученный максимум взять с противоположным знаком.

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

Первоначальный опорный планХ=(0; 0; 2; -4; 2), определяемый системой трех единичных векторов A₃, A₄ и A₅ не являетсядопустимым решением, так как координата x₄ =-4, что является недопустимым по условию неотрицательности переменных x_j . Для того, чтобы первоначальный опорный план был допустимым решением, исистема ограничений содержала систему единичных векторов, сделаем следующие преобразования 2-го ограничения и целевой функции:

Первоначальный опорный планХ=(0; 0; 2; 0; 2; 4), определяемый системой трех единичных векторов A₃, P₁ и A₅. Составляем симплексную таблицу:

Таблица 3.12

	i	Базис	Сб	B	-1	-5	0	0	0	-M	Qmin
A1	A2	A3	A4	A5	P1
I	1	A3	-0			-2					-
2	P1	-M					-1
3	A5	0		-2						2
	-4M	1-2M	5-3M	0	M		0
II	1	A3	0								2
2	A2	-5							2
3	A5	0							-
III	1	A1	-1
2	A2	-5
3	A5	0
	-2

Значение f₁( )=F₀= -1·2+0·0=-2, полученный результат возьмем с противоволожным знаком f₁( ) = - f( )=2- минимум функции иоптимальный план Х=(2; 0; 0; 0; 6).

Пример 10. Рассмотрим ЗЛП вида:

Целевая функция

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

Решить симплекс-методом.

Решение: Приведем ЗЛП к канонической форме записи:

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

Составляем симплексные таблицы итераций:

Таблица 3.13

	i	Базис	Сб	B	3	1	0	0	0	-M	Qmin
A1	A2	A3	A4	A5	P1
I	1	P1	-M		-1		-1				1
2	A4	0								5
3	A5	0		-2						4
	-M	M-3	-1-M	M	0		0
II	1	A2	1		-1		-1				-
2	A4	0							3
3	A5	0		-1					-
		-4		-1
III	1	A2	1
2	A1	3
3	A5	0
	13

Значение F₀= 3·3+1·4=13, максимум функции иоптимальный план Х= (3; 4; 0; 0; 6).

Дата добавления: 2014-12-26