Из системы (2.20) при возрастании от 0 до 1 получаем новое решение:

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

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

. (2.21)

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

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

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

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

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

.

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

Пусть .

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

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

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

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

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

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

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

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

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

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

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

Таблица. 1.

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

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

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

Номер строки	Базисная переменная	Отношение
1		
2
3

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

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

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

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

Таблица 2

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

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

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

Таблица. 3

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

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