Анализ модели на чувствительность

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

Останется ли решение оптимальным, если уменьшить вклад в прибыль одной из базисных переменных?

К каким последствиям приведет сокращение объема ресурсов?

Что произойдет, если ввести в рассмотрение новую управляемую пе­ременную?

Приемы, используемые при анализе модели на чувствительность, по своей сути весьма просты, хотя и отличаются некоторой громоздкостью. Разберемся в существе вопроса на примере, рассмотренном ранее. Запи­шем для этой цели исходную и «заключительную» системы уравнений, обозначим их соответственно через (Н) и (К).

где Х₀- подлежит максимизации.

Как используются выделенные ресурсы? При решении задач свобод­ные (дополнительные) переменные могут принимать следующие значе­ния.

1. Свободная (дополнительная) переменная равна нулю. Это значит, что в процессе производства используются все материалы (ресурсы).

2. Свободная переменная больше нуля, ресурсы используются не полностью, имеется остаток, который равен разности между запасами ре­сурсов и израсходованными ресурсами.

3. Свободная переменная равна запасам ресурсов. Это значит, что ре­сурсы не используются совсем.

Определим, останется ли уже найденный допустимый оптимальный базис оптимальным, если изменить коэффициенты в выражении для це­левой функции.

Для этого рассмотрим коэффициенты при небазисных переменных Х₂и Х₄в строке 0 системы уравнений (Н). При каком значении этих коэффициентов решение останется оптимальным, а при каком становится неоптимальным?

Предположим, что коэффициент при Х₂получает неотрицательное приращение δ, т. е. становится равным 5 + δ .Тогда строка 0 системы уравнений (Н) примет следующий вид:

При выполнении каждой симплекс-итерации мы прибавляли к строке 0 одну из остальных строк, предварительно умножив последнюю на некоторую константу. Следовательно, на заключительной итерации строка 0 системы уравнений (К) запишется в виде

Из полученного уравнения видно, что если δ > 3/7, то коэффициент при Х₂принимает отрицательное значение. В этом случае, согласно правилу 1 (максимизация), в очередное базисное решение вошла бы пе­ременная Х_2.Аналогично, если бы коэффициент при Х₄принял значе­ние, превышающее, то пробное базисное решение перестало бы быть оптимальным.

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

Рассмотрим, в каких пределах могут изменяться переменные, входящие в базис X₁ и Х₃, без ущерба для оптимальности полученного решения?

Запишем строку 0 системы уравнений (Н) в виде

В этом случае, строка 0 в (К) примет вид:

Чтобы ответить на вопрос, в каких пределах можно изменять δ,не нарушая оптимальности полученного решения, необходимо обратить в нуль коэффициент при X₁в строке 0. Для этого умножим δна строку 1 в (К) и прибавим полученный результат к полученному уравнению. Получим

Из полученного уравнения следует, что при выполнении условия –3/5 ≤δ<11/5полученное решение остается оптимальным. Приδ≤-3/5 коэффициент при Х₂принимает отрицательное значение. В случае, ко­гда δ≥ 11/5, отрицательным становится коэффициент приХ₄.Таким об­разом, как только значение δ выходит за пределы интервала -3/5≤δ≤11/5,прежний базис перестает быть оптимальным.

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

Останется ли допустимым полученный оптимальный базис, если из­менить значения констант в правых частях соотношений?

Рассмотрим правую часть строки 2 системы уравнений (Н). Произве­дем замену 120→120 + δ. Заметим, что свободная переменная X₆,фи­гурирующая в указанной строке, входит в базис (К). Следовательно Х₆изменится на величину δ. Таким образом, ранее полученное решение останется допустимым, еслиδ≥325/7,см. строку 2 в системе уравне­ний (К).

Рассмотрим правую часть уравнения в строке 1 системы уравнений (Н). Произведем замену 15 → 15 + δ . При таких значениях δ полученный базис остается допустимым?

Будем учитывать при выполнении симплекс-итераций произведен­ную замену. На последней итерации будем иметь:

Обратим внимание на то, что введение 8 в правую часть сопровож­дается появлением в левой части переменной Х₅.

Полагая, как обычно, небазисные переменные Х₁, Х₄, Х₅и Х₇ равными нулю, получим значения базисных переменных, которые опре­деляются теперь через δ.

Чтобы базис оставался допустимым, константы в правых частях уравнений должны иметь неотрицательные значения. Отсюда следует, что если

то пробное решение остается допустимым.

При δ≤50/10 значение базисной переменной Х₁становится отрицательным; при δ≥325/61 отрицательное значение принимает базисная пе­ременнаяХ₆.

Положим δ = 1, что можно интерпретировать как увеличение «ресур­са» в строке 1 на единицу.

С помощью соотношения в строке 0 системы уравнений (К) видно, что при этом значение целевой функции возрастет на 13/7. Другими сло­вами, при увеличении объема ресурсов на единицу дополнительная при­быль в оптимальном варианте составит 13/7.

Произведем одновременно следующие замены:

Затем после выполнения всех операций, позволяющих перейти от системы (Н) к системе (К), и обращения в нуль всех небазисных пере­менных, будем иметь:

Коэффициенты при δ₁совпадают с коэффициентами при соответст­вующих свободных переменных в (К). Базис остается допустимым, если значенияX₁,Х₆и Х₃неотрицательны. Следовательно, δ₁, δ₂и δ₃ должны удовлетворять соответствующей системе неравенств.