Условия оптимальности

Обозначим через коэффициент линейной функции, соответствующий вектору .

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

. (5)

Теорема 1. Если для некоторого вектора выполняется условие , то план не является оптимальным, и можно построить такой план , для которого выполняется неравенство .

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

Теорема 2. Если для некоторого вектора выполняется условие , то план не является оптимальным, и можно построить такой план , для которого выполняется условие .

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

Пример 1. Найти максимальное значение функции при ограничениях

Решение.

1. Перейдем от неравенств к уравнениям, прибавляя к левым частям неотрицательные дополнительные переменные (дополнительным переменным в линейной функции соответствуют коэффициенты, равные нулю)

Запишем систему в векторной форме:

,

где

.

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

Первоначальный опорный план

.

3. Для проверки плана составим первую симплексную таблицу и находим значение и оценки .

	Базис			2	1	0	0	0
				4.
			-2	-1

Проверка:

.

.

.

В ()-й строке и , следовательно, первоначальный план не оптимален. План можно улучшить, включив в базис вектор, которому соответствует , .

Найдем эти значения:

.

.

.

.

.

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

4. Составим вторую симплексную таблицу

	Базис			2	1	0	0	0
					11/4			-1/4
					2.			-1
					1/4			1/4
				-1/2			1/2

Проверка:

.

.

.

.

.

– опорный план , .

В ()-й строке , следовательно, опорный план не является оптимальным и вектор подлежит включению в базис.

5. .

Число 2 на пересечении второй строки и второго столбца, является разрешающим элементом. Вектор включается в базис, а вектор исключается.

6. Составим третью симплексную таблицу

	Базис			2	1	0	0	0
			33/2				-11/8	9/8
							1/2	-1/2
			33/2				-1/8	3/8
						1/4	1/4

.

.

.

.

.

.

В ()-й строке все оценки , значит, план является оптимальным и ему соответствует .

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

Пример 2. Найти минимальное значение функции при ограничениях

Решение.

Приведем ограничения к равенствам

Составим функцию .

Составим первую симплексную таблицу:

	Базис			2	3	0	0
				-3	2.
			-2

Возьмем базисные: . – свободные.

Первоначальный план: .

Критерий оптимальности: .

Проверка:

.

.

.

Критерий оптимальности не выполнен, т.к. . План неоптимален.

Необходимо ввести , т.к. , вывести , т.к.

.

Разрешающий элемент .

Составим вторую симплексную таблицу:

	Базис			2	3	0	0
			19/2	7/2			-1/2
		-3	9/2	-3/2			1/2
		-27/2	5/2			-3/2

Разделим разрешающую строку на разрешающий элемент .

.

Опорный план не является оптимальным, т.к. – не выполняется критерий оптимальности .

Необходимо ввести вектор , а вывести .

Составим третью симплексную таблицу:

	Базис			2	3	0	0
			19/2			2/7	-1/7
		-3	60/7			3/7	2/7
		-142/7			-5/7	-8/7

– разрешающий элемент, разделим всю строку на .

.

.

.

Все оценки отрицательные, критерий оптимальности на выполнен, опорный план оптимален.

.