Вернемся к введенной в примере 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 |
Согласно условию оптимальности данное решение является оптимальным.