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

В примере 4.2 нам пришлось выбрать вектор наугад. Благодаря некоторому везению автора первый «попавшийся под руку» опорный план оказался оптимальным. Однако всего для данной задачи можно было составить =3 опорных плана, из которых два были бы неудачными. Конечного гораздо комфортнее решать задачу, когда первоначальный опорный план уже задан, как в примере 4.1. Для того, чтобы в общем случае задачи ЛП сразу получить набор базисных векторов существует метод искусственного базиса.

Рассмотрим общую задачу ЛП,

Требуется найти минимальное (максимальное) значение линейной функции

Z = C₁x₁ + C₂x₂ + … + C_nx_n

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

Предположим, что система ограничений не содержит единичной матрицы.

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

Z^* = C₁x₁ + C₂x₂ + … + C_nx_n + M x_{n + 1} +…+ M x_{n + m}.

Справедливо следующее утверждение.

Теорема 4.3. Если в оптимальном плане Х^*(х₁, х₂, …, х_n, 0, …, 0) расширенной задачи искусственные переменные равны нулю, то план
Х(х₁, х₂, …, х_n) является оптимальным планом исходной задачи.

Рассмотрим работу метода искусственного базиса на примере.

П р и м е р 4.3. Найти минимальное значение линейной функции

Z = 2x₁ + x₂ – х₃ – х₄

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

Решение. Так как в системе ограничений нет единичного базиса, составим расширенную задачу.

Z^* = 2x₁ + x₂ – х₃ – х₄ + M x₅ + M x₆ + M x₇ ® min.

Составим симплексную таблицу. Теперь, опять таки, для удобства вычислений добавим еще одну оценочную строку . По этой строке будем определять вектор, подлежащий включению в базис.

Предстоит решить две задачи:

1) исключить из базиса все искусственные векторы;

2) отыскать (в случае необходимости) оптимальное решение задачи.

Таблица 4.4.

Базис	Сбазиса	А0	С1=2	С2=1	С3=-1	С4=-1	С5=М	С6=М	С7=М
А1	А2	А3	А4	А5	А6	А7
А5	М					-1
А6	М				-3
А7	М
Zj – Cj		-2	-1

 

В данном случае в строке Z_j – C_j записываются оценки векторов при условии, что М = 0. В строке записываются только коэффициенты перед М, т.е.

Z₀ = 2× 0 + 6× 0 + 7× 0;

= 2 М + 6 М + 7 М = 15 М (записываем 15);

Z₁ – C₁ = 0 – 2 = – 2;

= М + 2 М + М – 2 = 4 М – 2 (записываем 4) и т.д.

В строке имеются положительные оценки (векторы А₁, А₂, А₄), поэтому опорный план расширенной задачи не является оптимальным.

Вычислим максимальное значение q_j(Z_j – C_j) для первой итерации

q₁(Z₁ – C₁) = min × 4 = 2 4 = 8,

q₂(Z₂ – C₂) = min × 3 = 6,

q₄(Z₄ – C₄) = min × 2 = 12.

Наибольшую выгоду принесет введение в базис вектора А₄. При этом вектор А₆ покинет базис.

Таблица 4.5.

Базис	Сбазиса	А0	С1=2	С2=1	С3=-1	С4=-1	С5=М	С6=М	С7=М
А1	А2	А3	А4	А5	А6	А7
А5	М				-1
А4	-1				-3
А7	М		-1					-1
Zj – Cj	-6						-1
							-1

 

Проведем еще одну итерацию. Т.к. векторы А₁, А₂, А₃ имеют положительные оценки

q₁( ) = min × 2 = ,

q₂( ) = min × 2 = 8,

q₃( ) = × 3 = .

Выгоднее всего ввести в базис вектор А₂.

Таблица 4.6.

Базис	Сбазиса	А0	С1=2	С2=1	С3=-1	С4=-1	С5=М	С6=М	С7=М
А1	А2	А3	А4	А5	А6	А7
А2			1, 5		-0, 5		0, 5	0, 5
А4	-1		0, 5		-2, 5		-0, 5	0, 5
А7	М		-1					-1
Zj – Cj		-1				0, 5
		-1				-1	-2

 

План Х₂ не является оптимальным, поскольку > 0.

 

Таблица 4.7.

Базис	Сбазиса	А0	С1=2	С2=1	С3=-1	С4=-1	С5=М	С6=М	С7=М
А1	А2	А3	А4	А5	А6	А7
А2							0, 5
А4	-1		-				-0, 5	-
А3	-1		-					-
Zj – Cj		-1						-
						-1	-1	-1

 

В таблице 4.7 в строке оценки всех векторов, кроме искусственных равны нулю, таким образом, исключены из базиса все искусственные векторы.

Оценим теперь план
х₆ = 0, х₇ = 0) расширенной задачи на оптимальность, для этого объединим строки Z_j – C_j и в одну.

	А1	А2	А3	А4	А5	А6	А7
	-1					- М	- - М

 

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

Þ .

Таким образом, план является оптимальным планом расширенной задачи. Следовательно, согласно теореме 4.3 план является оптимальным планом исходной задачи. При этом

.

В заключение пункта приведем еще одно утверждение.

Теорема 4.4. Исходная задача ЛП не имеет решения, если расширенная задача не имеет решения или если оптимальное значение расширенной задачи соответствует плану, в котором в качестве базисных присутствуют искусственные переменные.

 

⇐ Предыдущая12345678Следующая ⇒

Поделиться: