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

1. Начальный опорный план (42) расширенной задачи содержит искусственные переменные

,

входящие в целевую функцию с коэффициентами (задача максимизации).

Соответствующие этому плану значения целевой функции и оценок равны

, (45)

. (46)

Таким образом, оценки состоят из двух слагаемых и , одно из которых не зависит от числа , а второе - зависит. Так как число сколь угодно велико по сравнению с единицей >>1), то на первом этапе расчета для нахождения вектора, вводимого в базис, используют только слагаемые оценки, которые записывают в дополнительную вторую строку оценок симплекс-таблицы.

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

3. После исключения из базиса всех векторов, соответствующих искусственным переменным, расчет продолжается по обычному алгоритму симплекс-метода с использованием оценок , не зависящих от числа .

4. Если в исходной задаче (34)-(37) среди векторов есть единичных , то их можно принять за базисные вектора при построении начального опорного плана расширенной задачи (38)-(41). Тогда необходимое количество искусственных переменных уменьшится и будет равно .

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

Решение. Математическая модель задачи примет вид

,

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

,

В векторной форме система уравнений ограничений канонической задачи имеет вид:

,

где

.

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

.

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

,

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

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

,

.

Заполним симплекс-таблицу (таблица 5) начального (нулевого) шага.

Вычислим оценки по формуле (46):

,

,

, и так далее.

В первую строку оценочного ряда заносим слагаемые оценок , не зависящие от числа , а во вторую – слагаемые оценок .

В столбце «План » оценочного ряда заносится значение целевой функции для начального плана .

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

Таблица 5. Симплекс-таблица.

Коэффициенты целевой функции					8	10	0		0	0	0	-M
Шаг	№	Базис		План
0	1		0	450	2	3	4	2	1	0	0	0	112,5
	2		0	380	3	2	1	2	0	1	0	0	380
	3		-M	9	0	0	1	0	0	0	-1	1	9
	Оценка			0	-8	-10	0	5	0	0	0	0
				-9M	0	0	-M	0	0	0	M	0
1	1		0	414	2	3	0	2	1	0	4	- 4	138
	2		0	371	3	2	0	2	0	1	1	-1	185,5
	3		0	9	0	0	1	0	0	0	-1	1
	Оценка			0	-8	-10	0	5	0	0	0	0
				0	0	0	0	0	0	0	0	M
2	1		10	138	2/3	1	0	2/3	1/3	0	4/3	-	207
	2		0	95	5/3	0	0	2/3	-2/3	1	-5/3	-	57
	3		0	9	0	0	1	0	0	0	-1	-
	Оценка			1380	-4/3	0	0	35/3	10/3	0	40/3	-
				-	-	-	-	-	-	-	-	-
3	1		10	100	0	1	0	2/5	3/5	-2/5	2	-
	2		8	57	1	0	0	2/5	-2/5	3/5	-1	-
	3		0	9	0	0	1	0	0	0	-1	-
	Оценка			1456	0	0	0	61/5	14/5	4/5	12	-
				-	-	-	-	-	-	-	-	-

Максимальной по абсолютной величине является оценка , так как число сколь угодно велико по сравнению с единицей >>1). В соответствие с критерием (30), третий столбец будет направляющим, а в новый базис войдет вектор и новая базисная переменная .

Все элементы направляющего столба положительны. Вычислим значение для этих элементов и запишем их в последний столбец «» симплекс-таблицы:

.

В соответствие с критерием (32), направляющей строкой будет третья строка, разрешающим элементом , а из базиса выводится вектор , соответствующий искусственной переменной .

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

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

После выполнения третьего шага все оценки оказались неотрицательными , а оценки векторов и , которые не входят в базис , отличны от нуля. То есть, выполняются критерии оптимальности (26) и единственности (29) опорного плана.

Единственным оптимальным решением задачи является план

.

Ему соответствует максимальное значение целевой функции

.

Ответ. Оптимальным планом является производство 57 единиц продукции вида , 100 единиц продукции вида и 9 единиц продукции вида , обеспечивающий максимум прибыли, равный 1456 (у.е).