Пример решения задачи линейного программирования симплекс-методом

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

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

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

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

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

Для начальной таблицы базис включает в себя: – для ограничения 1, - для ограничения 2, - для ограничения 3. Символом обозначены коэффициенты базисных переменных в целевой функции. Для начальной таблицы

Из таблицы 2.1 легко находится начальное допустимое базисное решение , , , .

Таблица 2.1.

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

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

=0.

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

, .

Следовательно, рассматриваемое допустимое базисное решение не оптимально. Небазисная переменная имеет наибольшую относительную оценку, Следовательно, ее следует ввести в базис.

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

Таблица 2.2.

№ строки	Базисные переменные	Отношение
		14/3
		3/1

Заметим, что для первой строки это отношение не вычисляется и принимается равным бесконечности, так как в первой строке таблицы 2.1 коэффициент при отрицательный. Следовательно, в соответствии с уравнением из системы (2.8) , неограниченно увеличивается при росте . Из второй строки таблицы 2.1 (второе ограничение) следует, что убывает до нуля при возрастании до 14/3 (что и записано в таблице 2.2). Третья строка показывает, что если возрастает до 3, то обнуляется. Минимальное отношение равно 3, следовательно, при возрастании от нуля до трех, первой среди базисных переменных обратится в нуль ; она заменится в базисе переменной . Третья строка таблицы 2.1 называется ведущей строкой а коэффициент при в ведущей строке называется ведущим элементом.

Элементарное преобразование приводит к системе с новыми базисными переменными , и . При этом, поскольку входит в базис, то первый столбец должен состоять из нулей и только одной единицы в третьей строке:

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

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

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

Таблица 2.3.

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

Строка таблицы 2.3 все еще содержит положительный элемент , что указывает на возможность введения в базис небазисной переменной , улучшающей значение . По правилу минимального отношения находим минимум из набора (7/1, 5/5, ∞), который достигается во второй строке, где базисной переменной является . Следовательно, займет место базисной переменной . В таблице 2.4 представлено следующее допустимое базисное решение. Так как в строке все элементы не положительные, таблица 2.4 оптимальна. Оптимальное решение имеет вид: , , , , а оптимальное значение .

Таблица 2.4.

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

Неединственность оптимума. Небазисная переменная в таблице 2.4 имеет нулевую относительную оценку. Следовательно, изменение не приведет к изменению значения целевой функции. Таким образом, можно ввести в базис, причем для соответствующего базисного решения значения тоже. По определению, любое допустимое решение для которого соответствующее значение равно оптимальному, также оптимально. Следовательно, в данном случае у задачи ЛП имеются различные оптимальные решения. Одно из них получается, если ввести в базис. Согласно правилу минимального отношения из базиса необходимо вывести переменную . Получим оптимальную таблицу 2.5. Ей соответствует оптимальное решение, отличное от решения, представленного в таблице 2.4: , , , .

Итак, если в оптимальной таблице имеется небазисная переменная с нулевой относительной оценкой , то оптимальное решение не единственно.

Таблица 2.5.

			Постоянные
Базис
				5/8	-1/8		15/4
				3/8	1/8		13/4
				-1/4	1/4		5/2
– строка				-1

На рисунке 2.3 переход от таблицы 2.3 к таблице 2.4 при помощи симплекс-метода соответствует движению вдоль ребра ВС дополнительной области. Так как коэффициенты при переменных целевой функции совпадают с коэффициентами ограничения , определяющего отрезок CD допустимой области, то угловые точки С и D, а также все точки отрезка СD являются оптимальными.