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

Основная цель анализа чувствительности в данном случае состоит в том, чтобы выявить допустимые пределы изменения правых частей ограничений bi (i=1,m) в (2) при неизменности найденного оптимального решения. Т. е. для каждого из коэффициентов bi необходимо определить интервал (biMIN, biMAX), для всех значений которого система (2) была бы совместна и ее решение не менялось. При этом полагаем, что остальные (m-1) коэффициентов сохраняют свои первоначальные значения.

Для исследования чувствительности решения задачи ЛП к изменениям коэффициентов правых частей ограничений анализируется ОДР на возможность параллельного переноса прямой, соответствующей i-му ограничению системы (3) и не примыкающей к оптимальной вершине, т. е. вершине, в которой функционал достигает оптимального значения.

Считаем, что точка D соответствует оптимальному решению (рис. 4). Границы ОДР, примыкающие к вершине D, то есть CD и DE, не могут быть перенесены без изменения координат D, а значит, и оптимального решения.

Границу ВС можно переместить параллельно самой себе в сторону начала координат или наоборот. Параллельный перенос ВС означает изменение коэффициента bi уравнения этой прямой. При этом оптимальное решение не изменится до того момента, пока ВС не подойдет к точке оптимальности D. Таким образом определится минимальное значение коэффициента biMIN. Значение коэффициента biMAX можно найти, перемещая ВС от начала координат до тех пор, пока точки С и В максимально не приблизятся друг к другу. В этом предельном случае прямая ВС, соответствующая i-му ограничению, фактически «выйдет» за пределы ОДР, образованной оставшимися (m -1) ограничениями.

Аналогично находятся пределы изменения коэффициента bi+1 уравнения, определяющего прямую AF. Значение коэффициента возрастает при параллельном переносе AF от начала координат, пока данная прямая вплотную не подойдет к точке В, поскольку при исследовании на чувствительность решения число вершин ОДР не должно уменьшаться. Нижний предел изменения коэффициента bi+1 можно определить, перемещая AF к началу координат до совмещения точек, А и F.

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

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

Исходные данные:

x1, x2 0,.

FMAX = 3×1+2×2 .

Область допустимых решений данной задачи OKLMNP представлена на рис. 5. Как видно из рисунка функционал достигает своего максимума в вершине М.

FMAX (x1, x2)= FMAX (8.0; 2.7)=29.33.

Для исследования на чувствительность выбираем одну из границ ОДР, исключая LM и MN, примыкающие к оптимальной вершине. Выбранная прямая KL, соответствующая 1-му ограничению системы, на рисунке помечена стрелками. Начальное значение коэффициента: b1 = = 20.

Для нахождения верхнего предела изменения коэффициента необходимо осуществить параллельный перенос прямой KL вверх от начала координат. В итоге точки К и L практически совместятся и ОДР изменится: OK’L’MNP. Максимальное значение составит b1MAX = 31.50.

Минимальное значение коэффициента можно найти при перемещении прямой KL параллельно самой себе до совмещения точек О и К. При этом ОДР будет представлять собой многоугольник OK"L"MNP, а значение коэффициента станет равным b1MIN = 0.50.

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

Аналогично проводится исследование на чувствительность к изменению коэффициента b ограничения, соответствующего прямой NP. Границы ОДР, совпадающие с осями координат (в данном примере OP и OK), не участвуют в исследовании на чувствительность, поскольку они определяются не ограничениями системы, а условием неотрицательности значений переменных.