М - метод

Вернемся к введенной в примере 11.1 линейной модели.

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

За использование этих переменных в составе целевой функции можно ввести штраф, при­пи­сывая им достаточно большой положительный коэффициент М. Такой способ введения искусст­венных переменных R₁ и R₂ приводит к следующей линейной модели:

Логика использования искусственных переменных: имеем m=3 уравнения, n=6 неизвестных. Сле­до­вательно, базисное решение должно включать n-m= =6-3=3 нулевые переменные. Если положить рав­ны­ми нулю переменные x₁, x₂ и x₃, то сразу же будет получено требуемое начальное допусти­мое решение: R₁=3, R₂=6, x₄=4.

Рассмотрим теперь, каким образом “новая” структура модели автоматически приводит к тому, что на конечной стадии процесса оптимизации переменные и принимают нулевое значение. Так как мы имеем дело с задачей на отыскание минимума, а переменным R₁ и R₂ в целевой функции приписан большой по величине коэффициент М, то метод оптимизации, направленный на нахождение минимального значения z, приведет к тому, что переменные R₁ и R₂ в оптимальном решении обратятся в ноль. Заметим:

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

Если целевая функция подлежит максимизации: приписываем искусственным переменным в целевой функции достаточно большой по абсолютной величине отрицательный коэффициент –М (М>0), что обусловит недопустимость положительных значений искусственных в оптимальном решении.

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

В результате

При этом z-уравнение в симплекс-таблице будет иметь вид:

,

.

Таким образом, стартовой точке, в которой x₁=x₂=x₃=0, соответствует значение z=9M, как и должно быть при R₁=3, R₂=6.

Построим симплекс-таблицу (таблица 11).

Так как целевая функция минимизируется, переменные, включаемые в базис, должны иметь наибольшие положительные коэффициенты в z-уравнении. Оптимум достигается на той итерации, где все небазисные переменные имеют неположительные коэффициенты в z-уравнении (М – положительный коэффициент, значение которого принимается очень большим).

Итерация 0 (начало вычислений).

Таблица 11

БП	x1	x2	x3	R1	R2	x4	Решение
z	- 4+7M	-1+4M	-M				9M
R1
R2			-1
x4

Согласно условию оптимальности переменная x₁ вводится в базис. Согласно условию допустимости переменная R₁ выводится из базиса. Получаем таблицу 12.

Итерация 1.

Таблица 12

БП	x1	x2	x3	R1	R2	x4	Решение
z		(1+5M)/3	-M	(4-7M)/3			4+2M
x1		1/3		1/3
R2		5/3	-1	-4/3
x4		5/3		-1/3

Согласно условию оптимальности переменная x₂ вводится в базис. Согласно условию допустимости переменная R₂ выводится из базиса. Получаем таблицу 13.

Итерация 2.

Таблица 13

БП	x1	x2	x3	R1	R2	x4	Решение
z			1/5	8/5-M	-1/5-M		18/5
x1			1/5	3/5	-1/5		3/5
x2			-3/5	-4/5	3/5		6/5
x4					-1

Согласно условию оптимальности переменная x₃ вводится в базис. Согласно условию допустимости переменная x₄ выводится из базиса. Получаем таблицу 14.

 

 

Итерация 3.

Таблица 14

БП	x1	x2	x3	R1	R2	x4	Решение
z				7/5-M	-M	-1/5	17/5
x1				2/5		-1/5	2/5
x2				-1/5		3/5	9/5
x3					-1

Согласно условию оптимальности данное решение является оптимальным.