Графический анализ чувствительности задач линейного программирования

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

Рассмотрим пример изменения коэффициентов в целевой функции.

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

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

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

Пример:

2 LnhtbEyPwU7DMBBE70j8g7VIXCrqEJKQhjgVqsQFDoXCBzixSSLsdYjd1P17lhMcd+ZpdqbeRmvY omc/OhRwu06AaeycGrEX8PH+dFMC80GiksahFnDWHrbN5UUtK+VO+KaXQ+gZhaCvpIAhhKni3HeD ttKv3aSRvE83WxnonHuuZnmicGt4miQFt3JE+jDISe8G3X0djlbA8/51dU5jsfq+z9tdXEoTX7wR 4voqPj4ACzqGPxh+61N1aKhT646oPDMC0s0mI5SMLKMNRNwlOSktKUVeAm9q/n9D8wMAAP//AwBQ SwECLQAUAAYACAAAACEAtoM4kv4AAADhAQAAEwAAAAAAAAAAAAAAAAAAAAAAW0NvbnRlbnRfVHlw ZXNdLnhtbFBLAQItABQABgAIAAAAIQA4/SH/1gAAAJQBAAALAAAAAAAAAAAAAAAAAC8BAABfcmVs cy8ucmVsc1BLAQItABQABgAIAAAAIQC3T3WM8QEAAOgDAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQAPtELA3wAAAAsBAAAPAAAAAAAAAAAAAAAAAEsEAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAVwUAAAAA " strokecolor="black [3040]"/>t bEyPwU7DMBBE70j8g7VIXCrqNNAkSuNUqBIXOFAKH+DEbhJhr0Pspu7fsz3BcWafZmeqbbSGzXry g0MBq2UCTGPr1ICdgK/Pl4cCmA8SlTQOtYCL9rCtb28qWSp3xg89H0LHKAR9KQX0IYwl577ttZV+ 6UaNdDu6ycpAcuq4muSZwq3haZJk3MoB6UMvR73rdft9OFkBr+/7xSWN2eInXze7OBcmvnkjxP1d fN4ACzqGPxiu9ak61NSpcSdUnhnSefJEqIC0WNOGK5Fn5DQCHtNVAbyu+P8N9S8AAAD//wMAUEsB Ai0AFAAGAAgAAAAhALaDOJL+AAAA4QEAABMAAAAAAAAAAAAAAAAAAAAAAFtDb250ZW50X1R5cGVz XS54bWxQSwECLQAUAAYACAAAACEAOP0h/9YAAACUAQAACwAAAAAAAAAAAAAAAAAvAQAAX3JlbHMv LnJlbHNQSwECLQAUAAYACAAAACEAluoK+e4BAADoAwAADgAAAAAAAAAAAAAAAAAuAgAAZHJzL2Uy b0RvYy54bWxQSwECLQAUAAYACAAAACEATZLJheAAAAALAQAADwAAAAAAAAAAAAAAAABIBAAAZHJz L2Rvd25yZXYueG1sUEsFBgAAAAAEAAQA8wAAAFUFAAAAAA== " strokecolor="black [3040]"/>

-ОДР (область допустимого решения)

() D- оптимальное решение задачи.

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

Ограничения 1 и 2.

свобод.члены

Условие параллельности 2-х прямых-это пропорциональность соответствующих коэффициентов при переменных.

Пока коэффициенты будут удовлетворять (*), наше оптимальное решение будет оставаться в точке D.

Если одно из значений зафиксировать, то легко найти интервал изменения значений для 2 коэффициента.

Два правила выбора вводимых и исключаемых переменных в симплекс-методе называются условиями оптимальности и допустимости.

1)Условие оптимальности: вводимой переменной в задаче max(min) являются небазисная переменная, имеющая наибольший по модулю отрицательный элемент (положительный элемент)

В строке целевой функции. Если в строке целевой функции несколько таких коэффициентов, то выбор вводимых переменных делается произвольно. Оптимальное решение достигнуто когда в строке целевой функции коэффициенты при небазисных переменных будут неотрицательными (неположительными).

2) Условие допустимости:

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

Если базисных переменных с таким свойством несколько, то выбор использования переменной выполняется произвольно.

Алгоритм симплекс-метода.

Шаг 1. Находится допустимое базисное решение.

Шаг 2. На основании условия оптимальности определяется вводимая переменная. Если таких нет, вычисления заканчиваются.

Шаг 3. На основании условия допустимости выбирается исключительная переменная.

Шаг 4. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к шагу 2.