Анализ устойчивости решения задачи линейного программирования

На практике оптимизационная задача почти никогда не заканчивается получением решения. Вслед за получением решения обычно следует анализ его устойчивости (чувствительности). В рамках этого анализа выявляется чувствительность вектора оптимального решения к определенным изменениям полученной модели. Это необходимо в силу следующих причин.

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

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: