Новое значение целевой функции находится по формуле

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

. (2.21)

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

Относительная оценка небазисной переменной обозначается через и определяется по формуле

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

Если относительные оценки небазисных переменных допустимого базисного решения задачи максимизации отрицательны или равны 0, то решение оптимально. Ясно, что если для всех небазисных переменных, то любому смежному допустимому базисному решению соответствует значение целевой функции, не превосходящее уже достигнутое. Отсюда следует, что в рассматриваемой точке имеется максимум. Поскольку целевая функция линейна, он совпадает с глобальным.

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

.

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

Пусть .

Следовательно, при увеличении до базисная переменная первой среди базисных переменных обращается в 0 и заменяется в базисе переменной . Переменная становится новой базисной переменной в r–й строке, причём новое допустимое базисное решение имеет вид

Поскольку при увеличении на единицу приращение составляет , для нового решения общее приращение определяется по формуле

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

Пример. Использовать симплекс – метод для решения следующей задачи:

максимизировать

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

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

максимизировать f(x)=3x₁+2x₂ при ограничениях

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

Элементы таблиц представляют собой коэффициенты задачи (в табл.1 содержится начальное допустимое базисное решение). Заметим, что для каждого ограничения записаны лишь коэффициенты при входящих в него переменных. Коэффициенты целевой функции находятся над коэффициентами соответствующих им переменных . Понятие “базис” обозначает совокупность базисных переменных начальной таблицы ( для ограничения 1, для ограничения 2, для ограничения 3), а символом – совокупность оценок переменных базиса. Из табл.1 находится начальное допустимое базисное решение:

Значение целевой функции задаётся скалярным произведением вектора и вектора правых частей уравнений:

Таблица. 1.

	базис		Постоянные
		-1	-1
-строка

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

Вычисляются соотношения для всех ограничений с положительным коэффициентом при :

Номер строки	Базисная переменная	Отношение
		¥

Следует отметить, что для первой строки это отношение не вычисляется (оно принимается равным ), поскольку коэффициент при x_i в строке 1 отрицателен. Это означает, что можно неограниченно увеличивать , причём при этом значении остаётся положительным. С другой стороны, из значения для отношения во второй строке следует, что станет равным 0 при возрастании до . Аналогично, если возрастает до 3, то обращается в нуль. Минимальное отношение равно 3, поэтому при возрастании от 0 до 3 первой среди базисных переменных обратится в 0 ; она заменится в базисной переменной . Строка 3 называется ведущей строкой, а коэффициент при в ведущей строке называется ведущим элементом. Элементарное преобразование приводит к системе с новыми базисными переменными , и :

1) прибавить ведущую строку (строку 3) к первой, чтобы исключить переменную ;

2) умножить ведущую строку на (-3) и прибавить её ко второй строке, чтобы исключить .

Для проверки оптимальности полученного в табл. 2 допустимого базисного решения необходимо вычислить вектор относительных оценок (строку ). Это можно выполнить, пользуясь правилом скалярного произведения. С другой стороны, новую строку можно вычислить, применяя элементарное преобразование. Относительная оценка переменной должна быть равна 0, поскольку вошла в базис. Равенства нулю можно добиться, умножая третью строку на (-3) и прибавляя её к строке . В результате автоматически получается новая строка (табл. 2).

Таблица 2

	базис		Постоянные
			-1			-3
-строка					-3

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

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

Таблица. 3

			Постоянные
	базис
					-1/5	8/5
					1/5	-3/5
					1/5	2/5
-строка				-1

Представленный алгоритм метода ЛП, нашедший широкое применение для решения организационно–экономических задач, стал применяться и при проектировании элементов РК, например, при компоновке оборудования на ракете.