Теорема 1.7

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

Теорема 1.8 Если расширенная задача (1.25) не имеет решения в виду неограниченности целевой функции, то исходная задача не имеет оптимального решения в силу несовместимости системы ограничений или неограниченности целевой функции.

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

1. Искусственные переменные следует вводить только в те уравнения системы ограничений, которые не разрешены относительно «естественных» базисных переменных.

2. При решении расширенной задачи оценки свободных переменных x_j содержат два слагаемых , которые размещают в двух строках: в m+1 – ой строке слагаемое , не содержащее М и в m+2 – ой строке коэффициенты при М. Т.к. М - сколь угодно большое положительное число, то на первом этапе для выбора разрешающего столбца принимают в расчет только .

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

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

Пример 11. На животноводческой ферме для откорма животных в их суточный рацион включают два продукта питания П₁ и П₂, причем продукта П₁ должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта П₁ составляет 2 руб., продукта П₂ – 4 рубля. Содержание питательных веществ в 1 ед. продукта и минимальные нормы потребления приведены в таблице 1.5.

Таблица 1.5

		Содержание питательных веществ в 1 ед. продукта
Питательные вещества	Минимальная норма потребления	П1	П2
А		0,2	0,2
В		0,4	0,2

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

Решение: Построение математической модели задачи начинается с обозначения переменных: X₁ – количество продукта П₁ в суточном рационе; X₂ - количество продукта П₂ в суточном рационе (ед.).

Целевая функция должна представлять собой общие расходы на оба продукта в сутки: f = 2X₁ + 4X₂ рублей.

Ограничения накладываются на содержание питательных веществ:

0,2X₁+0,2X₂ 120; (по веществу А)

0,4X₁+0,2X₂ 160. (по веществу В)

Ограничение на величину продукта П₁ в рационе: Х₁ 200.

Вводятся так же условия неотрицательности переменных, т. к. количества продуктов в рационе не могут быть отрицательными: Х_1,2 0.

В итоге, получаем следующую математическую модель задачи:

2Х₁ + 4Х₂

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

0,2Х₁ + 0,2Х₂ 120

0,4Х₁ + 0,2Х₂ 160

Х₁ 200

Х₁ 0, Х₂ 0.

Умножим первых два неравенства на 5, что бы не было дробных чисел и приведем задачу к каноническому виду.

– 2Х₁ – 4Х₂ + 0X₃+ 0X₄ + 0X₅

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

Х₁ + Х₂ –X₃ = 600

2Х₁ + Х₂ – X₄ = 800

Х₁ +X₅ =200

Х_j 0, j=1,..,5.

Поскольку в системе нет трех базисных векторов, есть только один при X₅, то необходимо ввести две искусственные переменные в первое и второе уравнение системы. Расширенная задача примет вид:

– 2Х₁ – 4Х₂ + 0X₃+ 0X₄ + 0X₅ – МY₁ – MY₂

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

Х₁ + Х₂ –X₃ + Y₁ = 600

2Х₁ + Х₂ – X₄ + Y₂ = 800

Х₁ +X₅ =200

Х_j 0, j=1,..,5; Y₁,Y₂ 0.

Составляем для неё симплекс-таблицу:

Таблица 1.6

№	Базис	cj базиса	– 2	– 4				–М	–М	bi
x1	x2	x3	x4	x5	y1	y2
	y1	–M			-1
	y2	–M				-1
	x5		1
		-3	-2						-1400

Разрешающий столбец – первый, выбрали его по последней строке, ему соответствует меньшая из отрицательных оценок. Для всех положительных элементов первого столбца вычисляем отношение . Находим минимальное из этих отношений: . Оно соответствует третьей строке, следовательно, она будет разрешающей. Таким образом, разрешающий элемент показывает, что из базиса выводится переменная x₅, а вместо неё в базисе будет переменная x₁. Заполняем новую симплекс – таблицу (табл. 1.7). Для этого превращаем первый столбец в единичный. Умножаем третью строку на (-2) и складываем со второй, записываем результат в первую строку новой симплекс – таблицы; аналогично, умножаем третью строку на (-1) и складываем с первой; третью переписываем без изменений.

Таблица 1.7

№	Базис	cj базиса	–2	–4				–М	–М	bi
x1	x2	x3	x4	x5	y1	y2
	y1	–M		1	-1		-1
	y2	–M				-1	-2
	x1	–2
						–2			–400
			–2						–800

Далее разрешающим столбцом будет второй. Разрешающей строкой может быть любая: первая или вторая, для них отношение одинаково. Выбираем первую. Новая симплекс – таблица:

Таблица 1.8

№	Базис	cj базиса	–2	–4				–М	–М	bi
x1	x2	x3	x4	x5	y1	y2
	x2	–4			-1		-1
	y2	–M			1	-1	-1	-1
	x1	–2
							-4		–2000
				-1

На следующей итерации из базиса выводится последняя искусственная переменная y₂, она заменяется на x₃.

Таблица 1.9

№	Базис	cj базиса	–2	–4				–М	–М	bi
x1	x2	x3	x4	x5	y1	y2
	x2	–4				-1	-2
	x3				1	-1	-1	-1
	x1	–2
								-4	–2000

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

Ответ: животноводческой ферме следует в суточный рацион животных включать 200 ед. продукта П₁ и 400 ед. продукта П₂. При этом будет обеспечено необходимое содержание веществ и наименьший расход средств 2000 рублей.