Параметрический анализ вектора ограничений

Пусть оптимальное решение X^* получено для вектора В. Как будет изменяться оптимальное решение при изменении правой части, заданной параметрически B (l)? Рассмотрим случай линейной зависимости: B (l)= B + l V, где l³0 – параметр, определяющий величину изменения вектора ограничений;

V – вектор размерности m, определяющий направление и относительную скорость изменения компонентов вектора ограничений. Задается ЛПР исходя из прогноза возможных изменений ресурсов. Пример: то есть ожидается одновременное уменьшение 1 и 3 ресурсов и увеличение 2 ресурса. При этом абсолютная величина изменения 1 ресурса в 3 раза, а 2 в полтора раза >, чем 3.

Для любого базисного решения условия задачи AX=B можно записать в виде

A _B X _B+ A _H X _H= B, где индексы “B” и “H” обозначают базисные и небазисные векторы (матрицы). Так как небазисные переменные равны нулю, то отсюда следует

A _B X _B= В и, в частности, для оптимального решения A ^*_B X ^*_B= В. Так как мы исходим из наличия решения X ^*, то базисная матрица - неособенная и существует обратная к ней матрица , .

Если заменить в B на B (l) при l =0, то ничего не изменится. При невырожденном оптимальном решении малое изменение B (l >0 мало ) не изменяет базис: оптимальная вершина хотя и смещается, но образуется теми же ограничениями. Поэтому в данном случае изменяется только оптимальное решение. Оптимальное решение при l >0 обозначим X^**. Тогда для малых l: , откуда находим изменяемое оптимальное решение или где

Таким образом, при линейном характере изменений ресурсов оптимальные значения переменных также меняются линейно. Это справедливо до тех пор, пока не происходит смена базиса. В невырожденном решении всегда найдется l >0, при котором базис не меняется. При неотрицательном векторе P возрастание l не может привести к уменьшению какой-либо базисной переменной и, значит, к смене базиса. В этом случае формула справедлива для любых l >0. Такая ситуация показана на рис, где изменение b ₁и b ₂в направлении стрелок не приводит к смене базиса (вершины, в которой достигается оптимальное решение).

Если же среди компонент вектора Р есть отрицательные, то соответствующие базисные переменные с увеличением l будут уменьшаться. Если хотя бы одна из переменных обратится в нуль, то произойдет смена базиса и, следовательно, изменится обратная матрица. Формула с исходными базисным решением и вектором P - несправедлива. На рис. оптимальная вершина сначала образована ограничениями по b ₁и b ₂, а затем – ограничениями по b ₁и b ₃.

Значение l, при котором происходит смена базиса (базисного решения), - критическое. Оно определяется по формуле где p_i – компоненты вектора Р. Исходное решение можно использовать для определения изменяемых решений только в диапазоне . Максимальное изменение правой части

Если диапазон изменения правой части недостаточен, то для его расширения необходимо заново решить задачу с вектором B ₁= B +Δ B _max.Получаем новое оптимальное решение, новую обратную матрицу и на их основе снова проводится параметрирование для B (l)= B ₁+ l ₁ V. Повторяя эти действия, можно охватить весь желаемый диапазон изменения ресурсов. При этом соотношение компонент (но не знаков!) в векторе V может остаться исходным или измениться (зависимость от параметра l на всем исследованном диапазоне будет кусочно-линейной).