Анализ устойчивости решения задачи линейного программирования на небольшом наборе ресурсных ограничений с помощью перебора и графического метода

В прикладных задачах линейного программирования коэффициенты ограничений и правые части редко известны точно: меняются оценки ресурсов, условия пересогласуются, исходные данные уточняются. Из‑за этих сдвигов оптимальный план может менять структуру – вплоть до смены набора активных ограничений – даже при кажущихся «малых» возмущениях. Возникает вопрос: насколько устойчиво конкретное оптимальное решение и какие признаки заранее показывают, что оно скоро перестанет быть надёжным. Работа обращается к этому вопросу на малом числе ресурсных ограничений, где устойчивость можно проверять как вычислительно, так и наглядно.

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

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

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

Сначала автор уточняет, как понимается устойчивость оптимального решения в терминах малых изменений параметров: что именно сравнивается между исходной и возмущённой задачей и какие критерии показывают «сохранение» решения. При этом особое внимание уделяется структуре – ведь при возмущениях меняется набор активных ограничений, а вместе с ним часто перестраивается и оптимальный базис.

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

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