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

В предыдущем разделе обсуждались вопросы, связанные непосредственно с нахождением оптимального решения задачи линейного программирования. Однако помимо техники нахождения оптимального решения, немалый интерес представляют собой методы, с помощью которых можно было бы системным образом выявить и проанализировать взаимосвязи между всеми факторами, учитываемыми при нахождении решения какой-либо из задач линейного программирования, встречающихся на практике.

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

Исследование, позволяющее ответить на эти вопросы, носит название анализ модели на чувствительность или, просто, анализ на чувствительность.

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

При ответе на другие вопросы анализ на чувствительность в значительной степени будет опираться на информацию относительно уже найденного оптимального решения и будет значительно затруднен всякий раз при модификации рассматриваемой модели.

Рассмотрим некоторые аспекты анализа на чувствительность применительно к задаче линейного программирования в стандартной форме, т.е. максимизировать целевую функцию:

,

если задана следующая система ограничений:

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

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

Рассмотрим коэффициент при свободной переменной в первой строке системы уравнений (I). Предположим, что коэффициент при получает некоторое неотрицательное приращение , то есть становится равным . Тогда первая строка системы уравнений (I) примет следующий вид:

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

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

Из полученного выражения видно, что в случае, если , суммарный коэффициент при переменной примет положительное значение. В этом случае в соответствии с алгоритмом симплекс-метода, в очередной базис вошла бы рассматриваемая нами переменная . Аналогично, можно утверждать, что если бы коэффициент при переменной увеличил бы свое значение на величину, большую , то изначально найденный базис перестал бы обеспечивать оптимальное решение.

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

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

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

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