Сетевые модели в управлении

Снижение размерности задачи нахождения критических узлов сети

А. А. Крыгин, С. М. Тарасова

ФГБУН Институт проблем управления им. В.А. Трапезникова РАН, Москва

Аннотация: Одним из классов задач, решаемых при оценке устойчивости инженерной сети, являются задачи нахождения критических узлов. В ряде постановок эта задача формулируется как нахождение такого подмножества узлов заданной мощности (критических узлов), при выходе из строя которых всей сети будет нанесен максимальный ущерб. И наиболее частый способ оценки ущерба в такой постановке – определение количества связных пар узлов в сети с исключенными критическими узлами. Для таких узлов, которые соответствуют минимуму количества связных пар, требуются проведение дополнительных мер по повышению надежности и безопасности. Ряд методов решения задачи нахождения критических узлов использует сведение ее к эквивалентной задаче линейного программирования. Основной проблемой этого подхода является большая размерность задачи, и, как следствие, высокая вычислительная сложность ее решения. В работе проводится исследование различных характеристик вершин графовой модели сети, анализ значений которых позволит заранее установить факт принадлежности вершины к подмножеству критических или наоборот, к подмножеству некритических узлов. Благодаря этому можно сформировать дополнительные ограничения, снижающие размерность задачи линейного программирования и ее вычислительную сложность, что позволит находить критические узлы в инженерных сетях с большим количеством объектов за приемлемое время. В процессе исследования было решено множество различных подзадач, поэтому в работе описывается первая, подготовительная его часть.

Ключевые слова: устойчивость электрических сетей, поиск критических узлов, графовые модели сетей.

УДК: 519.1
ББК: 31.27-082

Поступила в редакцию: 8 апреля 2024 г.
Опубликована: 30 сентября 2024 г.

DOI: 10.25728/ubs.2024.111.5