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

Найти максимуму функции при ограничениях Решим задачу симплекс-методом.

Решение: Перепишем условие задачи в векторной форме: , где .

Среди векторов векторы единичные. Примем их за базисные.

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

z= 3x₁+ 0x₂+ 0x₃+ 0x₄+ 2x₅+ (-5)x₆

i	Базис					-5

					-3
						-4
			-3		-3
m+1		-3		-2

Найдем разрешающий элемент в таблице 1.

Поскольку , то найдем по следующим формулам:

. Таким образом, разрешающий будем выбирать из элементов . Для этого найдем минимум из произведений :

. Тогда разрешающим будет элемент . Следовательно, вместо базисного вектора в таблице 1 базисным становится вектор в таблице 2.

i	Базис					-5

					-3
					2= a₂₅	-4
			-3		-3
m+1		-3		-2

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

Правило 1: Все элементы k-ой строки (строки в которой находится разрешающий элемент ), начиная со столбца , делятся на разрешающий элемент ;

Правило 2: Все элементы столбца заменяются нулями, кроме ;

Правило 3: Любой элемент таблицы 2 вычисляется по правилу прямоугольника:

;

Правило 4: (m+1)-строка вычисляется аналогично: .

В таблице 2 базисными будут векторы .
Таблицу 2.

i	Базис		-5

		3/2	-1
		1/2	-2

m+1

Вычислим элементы в столбце : Вычислим элементы в столбце :

Опорный план найден, так как в (m+1)-строке среди нет отрицательных.

, .

Замечание 1. После конечного числа шагов получим оптимальный план или докажем отсутствие такового. Оптимальный план отсутствует, если некоторое , но среди чисел нет положительных (т.е. целевая функция не ограничена на множестве ее планов).

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