М - метод

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

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

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

Логика использования искусственных переменных: имеем m=3 уравнения, n=6 неизвестных. Сле­до­вательно, базисное решение должно включать n-m= =6-3=3 нулевые переменные. Если положить рав­ны­ми нулю переменные x1, x2 и x3, то сразу же будет получено требуемое начальное допусти­мое решение: R1=3, R2=6, x4=4.

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

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

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

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

В результате

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

,

.

Таким образом, стартовой точке, в которой x1=x2=x3=0, соответствует значение z=9M, как и должно быть при R1=3, R2=6.

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

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

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

Таблица 11

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

Согласно условию оптимальности переменная x1 вводится в базис. Согласно условию допустимости переменная R1 выводится из базиса. Получаем таблицу 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

Согласно условию оптимальности переменная x2 вводится в базис. Согласно условию допустимости переменная R2 выводится из базиса. Получаем таблицу 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

Согласно условию оптимальности переменная x3 вводится в базис. Согласно условию допустимости переменная x4 выводится из базиса. Получаем таблицу 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

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