Анализ оптимальных решений в задачах ЛП
Необходимость анализа оптимальных решений
Получение оптимального решения в задачах линейного программирования не всегда означает завершение работ по обоснованию и выработке оптимальной стратегии поведения. В реальной экономике часто случается так, что изменения во внешней среде — колебания спроса, рост инфляции и т.д. — приводят, например, к необходимости корректировки цен на продукцию. Для оптимизационной модели это означает внесение корректив в целевую функцию. Тут же возникают вопросы: каким образом и к чему такие коррективы могут привести? Кроме того, обычно для реализации производственной программы существует возможность привлечения дополнительных финансовых и других ресурсов либо перераспределения уже имеющихся. Вполне естественно попытаться выяснить, к чему это приведет и как скажется на уже полученном оптимальном решении. Иначе говоря, после решения задачи оптимизации в силу разных причин могут возникнуть вполне закономерные вопросы.
1. Насколько устойчиво полученное оптимальное решение к изменению параметров модели, в частности коэффициентов целевой функции? Что произойдет, например, если спрос на продукцию упадет (возрастет) и, следовательно, придется снизить или повысить цену на то или иное изделие? Что в этом случае делать с полученной ранее оптимальной производственной программой? Потребуется ее корректировка или нет?
2. Насколько чувствительно полученное решение к изменениям запасов ресурсов, т. е. к изменению правых частей в неравенствах системы ограничений? Изменится ли доходность (значение целевой функции) при изменении запасов и насколько?
3. Как оценить вклад единицы каждого из ресурсов в доходность? Какие ресурсы целесообразно увеличить в первую очередь? К какому результату это может привести? Не являются ли запасы некоторых ресурсов избыточными и, вместо затрат на их приобретение и хранение, не лучше ли пополнить запасы тех ресурсов, которые в наибольшей степени увеличивают доходность и расходуются полностью? Как количественно просчитать (оценить) различные варианты «ресурсного» поведения?
Получение ответов на перечисленные вопросы и составляет существо анализа оптимальных решений.
Заметим, что в линейном программировании под устойчивостью обычно подразумевают неизменность оптимальных решений при изменениях (вариациях) коэффициентов целевой функции, а под чувствительностью — степень влияния правых частей ограничений на прирост, либо уменьшение значений целевой функции.
С точки зрения обоснования управленческих решений, анализ устойчивости и чувствительности часто играет не менее важную роль, чем отыскание собственно оптимального решения.
Анализ устойчивости оптимальных решений к изменению коэффициентов целевой функции
Выясним вначале, как влияет изменение коэффициентов целевой функции на оптимальное решение. Такая проблема возникает в случаях, когда, например, меняется рыночная ситуация, приводящая к колебаниям спроса и, следовательно, к изменению стоимости единицы продукции. Для иллюстрации рассмотрим задачу нахождения оптимальной производственной программы с двумя переменными. С точки зрения модели линейного программирования это приводит к необходимости изменения коэффициентов с1,с2 целевой функции (целевых коэффициентов).
Пусть для некоторой исходной целевой функции
Z1 = c1 x1+ c2 x2
получено оптимальное решение (x1opt, x2opt). Выясним, изменится ли оно при изменении коэффициентов с1,с2. Для этого рассмотрим два случая:
Z2 = c1*x1 + c2*x2 и Z3 = c1**x1 + c2**x2
Заметим, что значение самой целевой функции Z всегда будет либо увеличиваться, либо уменьшаться при любом изменении с1, с2. Однако важнее выяснить другое: изменится ли при этом ранее найденное оптимальное решение (x1opt, x2opt) или нет.
Иначе говоря, требуется определить, достигается ли наибольшее значение новой целевой функции с измененными коэффициентами в той же точке (x1opt, x2opt), что и ранее, или оптимальное решение будет достигаться при другой комбинации переменных (х1, х2).
Как было показано в главе 3, коэффициенты целевой функции однозначно определяют вектор , указывающий направление возрастания значений Z. Следовательно, трем рассматриваемым случаям будут соответствовать три разных направления роста целевых функций. Линии уровня (прямые, во всех точках которых Z = const) всегда перпендикулярны вектору g. Следовательно, ориентация линий уровня и направления возрастания Z для трех случаев будет различной (рис. 4.1).
X2
X1 |
Рис. 4.1.
Сопоставим этот вывод с «поведением» линий уровня в ОДР.
Заметим, что область допустимых решений при изменении целевых коэффициентов остается неизменной. Пусть, например, ОДР задачи изображена на рис. 4.2 и пусть оптимальное решение для исходной задачи находится в точке А. Анализируя положение линий уровня для рассматриваемых целевых функций, устанавливаем (рис. 4.2) следующее.
A |
X1 |
B |
Z1 |
Z2 |
Z3 |
Рис. 4.2.
1. Для целевой функции Z2 = c1*x 1 + c2*x2 точка оптимума не изменилась и по-прежнему находится в вершине А. Это означает, что максимальное значение целевой функции Z2 = c1*x 1 + c2*x2 достигается в той же оптимальной точке, что и ранее (х1A,х2A).
2. Точка оптимума для целевой функции Z3 = c1**x1 + c2**x2 переместилась в точку B (в другую вершину ОДР). Это означает, что теперь максимального значения целевой функции Z3 можно добиться только при новой комбинации переменных (х1B,х2B).
Таким образом:
1. Изменение коэффициентов целевой функции в рамках некоторого диапазона не приводит к изменению оптимального решения (xlopt, x2opt). Такой диапазон называют диапазоном устойчивости решения по коэффициенту целевой функции.
2. Границы диапазона устойчивости зависят как от ОДР, так и от целевой функции.
3. При изменениях целевых коэффициентов, выходящих за границы диапазона устойчивости, оптимальное решение (x1opt, x2opt) меняется. Оно перемещается в другую точку ОДР.
При решении задач линейного программирования с большим числом переменных определение границ устойчивости, в принципе, не составляет труда, однако требует применения довольно громоздких вычислительных процедур. Вместе с тем эти алгоритмы легко реализуются на ЭВМ. Они включены во многие стандартные пакеты соответствующих программ линейной оптимизации, в том числе и в MS Excel. Все выводы, полученные для задачи с двумя переменными, справедливы и для задач со многими переменными.