78252

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

ISBN/ISSN: 

1819-2440

DOI: 

10.25728/ubs.2024.111.5

Наименование источника: 

  • Управление большими системами

Обозначение и номер тома: 

Вып. 111

Город: 

  • Москва

Издательство: 

  • ИПУ РАН

Год издания: 

2024

Страницы: 

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

Библиографическая ссылка: 

Крыгин А.А., Тарасова С.М. Снижение размерности задачи нахождения критических узлов сети // Управление большими системами. 2024. Вып. 111. С. 118-146.