Решить задачу ЛП М-методом

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

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

или . Поскольку в системе 3 уравнения, то и базисных векторов также должно быть 3. Один из них уже известен, это вектор . И других базисных векторов нет. Поэтому добавим их искусственно во второе и третье уравнения системы. Получим . Таким образом, мы перешли к расширенной задаче: при ограничениях (*). Рассмотрим векторы

.

Среди векторов векторы являются базисными.

Симплексная таблица при этом методе содержит еще и (m+2)-строку, куда записывают слагаемое из , содержащее M, а в (m+1)-строку – другое слагаемое из этой разности.

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

Т = 5x₁+ 2x₂+ (-1)x₃+ 0x₄+ 0x₅+ (-М)x₆+ (-М)х₇

i	Базис					-1			-М	-М
		-М
		-М						-1
m+1		-5	-2
m+2	-7	-8	-5	-5

Найдем разрешающий элемент в таблице 1 по (m+2)-строке.

Найдем по следующим формулам:

.

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

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

Правила 1-3 такие же как в предыдущем примере.

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

Правило 5: Процесс продолжается до тех пор пока из базиса не будут исключены все искусственные векторы, после чего переходят к (m+1)-строке. Удаленные из базиса искусственные векторы также исключаются и из таблицы.

Правило 6: Если не все искусственные векторы исключены из базиса, а в (m+2)-строке нет отрицательных, то расширенная и исходная задачи решений не имеют.

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

Таблица 2.

i	Базис					-1			-М
			14/3	1/3		-1/3		1/3
		-М	16/3	-1/3		-5/3		2/3
			1/3	5/3		4/3		-1/3
m+1	2/3	-5/3		11/3		-2/3
m+2	-16/3	1/3		5/3		2/3

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

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

Поскольку в (m+2)-строке нет отрицательных (начиная со столбца ), то задача новая, а, значит и исходная, оптимального плана не имеет.

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

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