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

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

a_i1 X₁ + a_i2 X₂ +…a_in X _n ≥ b_i (7)

или уравнений a_i1 X₁ + a_i2 X₂ +…a_in X _n = b_i (7*),

то невозможно получить опорный план в искомом виде. В этом случае для соблюдения равенств (7*) вводится искусственный базис Y_i, причем искусственные переменные не имеют непосредственного отношения к содержанию поставленной задачи, но позволяют построить опорный (стартовый) план:

a_i1 X₁ + a_i2 X₂ +…a_in X _n +Y_i = b_i (8).

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

Z(X) =∑C_jX_j+(-M)∑Y_i (9),

при решении аналогичной задач на минимум:

Z(X)=∑C_jX_j+(M)∑Y_i (9*),

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

В случае неравенств (7) первоначально вводим дополнительные переменные Х_n+i со знаком минус. Их матрица не будет единичной, поэтому в каждое неравенство системы (7) вводим искусственные переменные У_i:

a_i1X₁+a_i2X₂+…a_inX_n–X_n+i+Y_i=b_i (10) Целевая функция при этом Z(X)=∑C_jX_j+0∑X_n+i+(-M)∑Y_i (для нахождения максимума). Применение искусственного базиса придает симплексному методу большую гибкость и позволяет использовать его для широкого круга задач.

Пример №4.

Определить максимальное и минимальное значение прибыли при выпуске двух видов продукции А и В, если затраты на производство и доходность от реализации единицы продукции приведены в таблице. Основным условием является полная занятость рабочих на предприятии.

Виды ресурсов	Нормы затрат на производство 1 т	Запасы ресурсов
Группа А	Группа В
Сырье,т	1,0	1,0
Рабочее время чел.-час	2,0	1,0
Доход с 1 т, тыс. руб.

Математически ограничения выпуска продукции запишутся в виде смешанной системы:

1Х₁ + 1Х₂≤ 6,

2Х₁ + 1Х₂ =8.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения искусственную переменную Y₁:

1Х₁ + 1Х₂+ Х₃ = 6,

2Х₁ + 1Х₂ +Y₁ =8.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X)= 3X₁+ 2X₂+0X₃ –MY₁= 3X₁+ 2X₂ –M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ –8M +2MX₁ + MX₂ = (2M + 3)X₁ + (M + 2)X₂ -8M

Для опорного плана - Х=(0,0,6,8). Построим симплексную таблицу:

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	Y1	Qmin
	X3							6/1=6
Y1	-M						8/2=4
Z(X) = -8M	-2M-3	-M-2			Индексная строка
	X3				0,5		-0,5	2/0,5=4
→X1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		М+1,5	Индексная строка
	→X2						-1	-
X1					-1		-
Z(X) =3*2+2*4=14				М+1	Индексная строка

Как правило, улучшение опорного плана начинается с выведения из базиса искусственной переменной Y₁.Оптимальный план Х=(2,4,0,0) получен на второй итерации, при этом доход максимален 14тыс. руб., а коэффициенты индексной строки неотрицательны. Легко убедиться, что в данной задаче при оптимальном плане ресурсы использованы полностью (2*1+4*1=6; 2*2+1*4=8).

При нахождении минимальной доходности иначе формулируем целевую функцию (в качестве слагаемого вводится +MY₁:

Z(X)= 3X₁+ 2X₂+0X₃ +MY₁= 3X₁+ 2X₂ +M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ +8M - 2MX₁ - MX₂ = (3 - 2M)X₁ + (2 - M)X₂ +8M

Опорный план тот же, но коэффициенты индексной строки в симплексной таблице иные. Ведущий столбец, по-прежнему, выбираем по наибольшему по абсолютному значению положительному коэффициенту при X_1, ведущая строка определяется по минимальному значению Q_min=4.При первой итерации из базиса выводится искусственная переменная Y₁.

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	Y1	Qmin
	X3							6/1=6
Y1	M						8/2=4
Z(X) = 8М	2M-3	M-2			Индексная строка
	X3				0,5		-0,5	2/0,5=4
→X1				0,5		0,5	4/0,5=8
Z(X) = 3*4=12		- 0,5		-М+1,5	Индексная строка

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

Он обеспечивается только выпуском продукции А (продукция В не выпускается), сырье не используется полностью (остаток Х₃=2т), при этом выполнено основное условие - рабочие полностью заняты на производстве.

Пример №5.

Цех выпускает краску для наружных (А) и внутренних работ (В), общие затраты на производство которой и доход от реализации представлены в таблице. Согласно исследованиям маркетингового отдела количество продаваемой краски день не менее 5 т. Определить максимальную доходность такого производства.

Виды ресурсов	Нормы затрат на производство 1 т	Запасы ресурсов
Группа А	Группа В
Сырье,т	3,0	2,0
Доход с 1 т, тыс. руб.

Математически ограничения выпуска продукции запишутся в виде системы неравенств:

3X₁ + 2X₂ ≤ 12,

X₁ + X₂ ≥ 5.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения отрицательную Х₄ и искусственную переменную Y₁:

3X₁ + 2X₂ + X₃ = 12,

X₁ + X₂ – X₄ + Y₁ = 5.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X) = 2X₁+ 1X₂+0X₃ +0Х₄ –MY₁=2X₁+ 1X₂ –M*(5 - X₁ –X₂ + Х₄) =

= (2 + М)X₁+ (1 + М)X₂ –MХ₄ - 5M

Для нулевого опорного плана Х=(0,0,12,5) построим симплексную таблицу:

План	Базис	Ci/Cj	Знач. Xi	X1	X2	X3	Х4	Y1	Qmin
	X3								12/3=4
Y1	-M					-1		5/1=5
Z(X) = - 5М	-M-2	-M-1		М		Индекс строка
	→X1				2/3	1/3			4/(2/3)=6
Y1	-M			1/3	-1/3	-1		1/(1/3)=3
Z(X) = 2*4 - M=8-M		-M/3+1/3	(M+2)/3	M		Индекс строка
	X1							-2	-
→X2					-1	-3		-
Z(X) = 2*2+1*3=7			2/3M+1		М-1	Индекс строка

Полученный план Х=(2,3,0,0), при этом доход максимален 7тыс. руб., ресурсы использованы полностью (2*3+3*2=12) и выполнено условие маркетинга (2*1+3*1=5).