Планирование защиты, минимизирующей дефицит ресурса в худшем сценарии разрушения сети снабжения

Рассматривается модель планирования защиты рёбер сети снабжения некоторым ресурсом. В вершинах сети располагаются потребители и поставщики ресурса, а рёбра сети позволяют мгновенно и в неограниченном количестве перемещать ресурс между вершинами. Защищающая сторона располагает ограниченным бюджетом. Она стремится определить множество рёбер, защиту которых позволяет обеспечить бюджет, таким образом, чтобы минимизировать ущерб от выхода из строя части незащищённых рёбер. В качестве меры ущерба используется суммарный объём дефицита ресурса, возникающий в худшем сценарии разрушения сети. Задача защищающейся стороны таким образом представляет собой задачу семейства «защитник — атакующий», формализуемую в виде минимаксной смешанно-целочисленной задачи математического программирования. Для отыскания оптимального решения защищающейся стороны предложено две схемы генерации отсечений, опирающихся на переформулировку задачи в виде задачи смешанно-целочисленного математического программирования с экспоненциальным числом ограничений. Табл. 2, ил. 4, библиогр. 13.