Анализ чувствительности оптимального решения к вариациям правых частей ограничений - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

Ограничение чувствительность задача программирование

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

Ограничение 2 - активное. Крайнюю точку и соответственно, базисное решение определяют ограничения 2 и 3. Предельная положительная вариация находятся из условия параллельного перемещения прямой, определяющей 2-е ограничение до точки 6. При большей вариации новый оптимальный базис будет определяться ограничениями 1 и 3, т. е. изменится состав активных ограничений. Аналогично, предельная отрицательная вариация определяется параллельным перемещением этой же прямой до крайней точки 5, после чего базисное решение будет определяться только ограничением 2 и, т. е. опять изменится состав активных ограничений. Ограничение 1 - пассивное. Предельная вариация, т. к она не может привести к изменению состава систем ограничений.

Предельная отрицательная вариация определяется параллельным смещением ограничения 1 до крайний точки 4, после чего оптимальный базис будет определяться ограничениями 1 и 3.

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

структура симплекс-таблицы

Рис.3.5 Структура симплекс-таблицы.

Вариация правой части любого, например, k-о ограничения, приводит к изменению вектора

Действительно, если то. (3.9)

Каждая i-я компонента вектора определяется следующим соотношением:

(3.10)

Где - номер ограничения, правая часть которого варьируется,

- i - я строка матрицы,

- элемент [i, k] матрицы.

Из формулы (3.10) видно, что изменяться при вариации величины будут лишь те элементы, которым в k-м столбце матрицы соответствует ненулевой элементов.

К неоптимальности прежнего базиса может привести лишь уменьшение. При положительной вариации () это будет в случае <0, а при отрицательной () наоборот - при >0.

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

(3.11)

(3.12)

Где (3.13)

Соотношение (3.13) получается из (3.10) приравниванием последнего к нулю.

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

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

Известно, что,

Где - оптимальные значения двойственных переменных. Известно также, что

Следовательно, если, то соответствующее i-ое ограничение является активным (т. е. любое изменение b[i] приводит к изменению оптимального значения целевой функции ЗЛП), в противном случае оно является неактивным.

После проведения вариации величины b[k] меньше предельной для получения нового оптимального решения достаточно скорректировать вектор соответствии с формулой (3.10). Если же осуществляется вариация больше предельной, то после пересчета вектора среди новых значений первых m его компонент появятся отрицательные, т. е. прежнее базисное решение станет недопустимым. При этом прежний базис станет сопряженным, т. е. таким, которому соответствуют значения двойственных переменных, определяющие допустимое базисное решение двойственности ЗЛП.

Для поиска нового решения скорректированной ЗЛП, начиная с сопряженного базиса, необходимо применить алгоритм двойственного симплекс-метода. В результате его работы либо будет найдено новое оптимальное решение, либо установлено, что сделанная вариация привела к пустоте допустимого множества ЗЛП.

Похожие статьи




Анализ чувствительности оптимального решения к вариациям правых частей ограничений - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

Предыдущая | Следующая