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

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

Задача представлена в каноническом виде, если

- критерий стремиться к максимуму,

- все условия представлены в виде равенств,

- все переменные неотрицательные.

Приведем задачу к каноническому виду:

L = 12 x ₁+ 15 x ₂+ 0 x ₃+ 0 x ₄+ 0 x ₅® max

x ₁ + x ₂ + x ₃ = 6

2 x ₁ + x ₂ + x ₄ = 10

x ₁ + 2 x ₂ + x ₅ = 10

x_i ≥ 0, i = 1, 5

Базисной называется такая переменная, которая входит только в одно из уравнений системы условий с коэффициентом +1.

Переменные x ₃, x ₄, x ₅ – базисные.

Таблица 2.1 – Исходная симплекс-таблица

Базис	Св.чл.	x 1	х 2	x3	x 4	x 5	Q
x 3	6		1				6/1
x 4							10/1
x 5	10						10/2
(- L)

Таблица является оптимальной и последней, если все элементы строки (-L) не положительны. Т.к. в таблице в строке (- L) есть положительные элементы, то необходимо продолжить решение и выполнить пересчет таблицы.

Таблица 2.2 – Вторая симплекс-таблица

Базис	Св.чл.	x 1	x 2	x 3	x 4	x 5	Q
х 3		1/2				-1/2
х 4		3/2				-1/2	10/3
х 2		1/2				1/2
(- L)	-75	9/2				-15/2

Вторая таблица тоже не оптимальная.

Таблица 2.3 – Третья симплекс-таблица

Базис	Св.чл.	x 1	x 2	x 3	x 4	x 5	Q
x 1						-1
x 4				-3
x 2				-1
(- L)	-84			-9		-3

В строке (- L) все элементы неположительные, следовательно, данная таблица оптимальная и последняя.

х ₁ ^* = 2, x ₂ ^* = 4, L^* = 84.

Вывод: для получения максимальной стоимости продукции в размере 84 денежные единицы необходимо выпустить 2 машины и 4 мотоцикла.