Том 26, номер 4, 2019 г., Стр. 16-33

УДК 519.8+518.25
Береснев В. Л., Мельников А. А.
Двухуровневая модель «атакующий — защитник» для выбора состава средств атаки

Аннотация:
Рассматривается двухуровневая модель для оценки величины затрат атакующей стороны на успешную атаку заданного множества объектов, защищаемых другой стороной. При этом атакующий и защитник располагают различными средствами (способами) соответственно для атаки и защиты объектов, а потери атакующего зависят от выбранных защитником средств атаки. Рассматриваемая модель построена на основе игры Штакельберга, в которой атакующий стремится провести успешную атаку объектов с наименьшими затратами, а защитник — нанести атакующей стороне максимальный ущерб, используя ограниченный бюджет. Формально рассматриваемая модель «атакующий — защитник» записывается как задача двухуровневого целочисленного программирования. Особенность задачи состоит в том, что допустимость решения задачи верхнего уровня зависит от всех оптимальных решений задачи нижнего уровня. Для вычисления оптимального решения исследуемой двухуровневой задачи предлагается алгоритм, состоящий в специальном разбиении множества допустимых решений задачи на подмножества и её сведении к последовательности двухуровневых подзадач. Специфика множеств допустимых решений этих подзадач позволяет свести их к задачам смешано-целочисленного программирования двух видов.
Библиогр. 14.

Ключевые слова: разбиение множества допустимых решений, двухуровневая подзадача, условие оптимальности.

DOI: 10.33048/daio.2019.26.663

Береснев Владимир Леонидович ^1,2
Мельников Андрей Андреевич ^1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: beresnev@math.nsc.ru, melnikov@math.nsc.ru

Статья поступила 10 июня 2019 г.
После доработки — 30 июля 2019 г.
Принята к публикации 28 августа 2019 г.

Литература

[1] Ding T., Yao L., Li F. A multi-uncertainty-set based two-stage robust optimization to defender–attacker–defender model for power system protection // Reliability Engineering and System Safety. 2018. Vol. 169. P. 179–186.

[2] Alguacil N., Delgadillo A., Arroyo J. M. A trilevel programming approach for electric grid defense planning // Comput. Oper. Res. 2014. Vol. 41, No. 1. P. 282–290. http://dx.doi.org/10.1016/j.cor.2013.06.009

[3] Береснев В. Л. Математические модели планирования развития систем технических средств // Дискрет. анализ и исслед. операций. Сер. 2. 1997. Т. 4, № 1. С. 4–29.

[4] Scaparra M. P., Church R. L. A bilevel mixed-integer program for critical infrastructure protection planning // Comput. Oper. Res. 2008. Vol. 35. P. 1905–1923.

[5] Liberatore F., Scaparra M. P., Daskin M. S. Analysis of facility protection strategies against an uncertain number of attacks: The stochastic $r$-interdiction median problem with fortification // Comput. Oper. Res. 2011. Vol. 38. P. 357–366.

[6] Sadeghi S., Seifi A., Azizi E. Trilevel shortest path network interdiction with partial fortification // Comput. Ind. Eng. 2017. Vol. 106. P. 400–411. http://dx.doi.org/10.1016/j.cie.2017.02.006

[7] Stackelberg H. The theory of the market economy. Oxford: Oxford Univ. Press, 1952. 289 p.

[8] Dempe S. Foundations of bilevel programming. Dortrecht: Kluwer Acad. Publ., 2002. 332 p.

[9] Fischetti M., Ljubic I., Sinnl M. Benders decomposition without separability: A computational study for capacitated facility location problems // Eur. J. Oper. Res. 2016. Vol. 253, No. 3. P. 557–569. http://dx.doi.org/10.1016/j.ejor.2016.03.002

[10] Martello S., Toth P. Knapsack problems: algorithms and computer implementations. New York: John Wiley & Sons, Inc., 1990. 306 p.

[11] Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin; Heidelberg; New York: Springer, 2004. 546 p.

[12] Кочетов Ю. А., Плясунов А. В. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дискрет. анализ и исслед. операций. Сер. 2. 1997. Т. 4, № 2. С. 23–33.

[13] Плясунов А. В. Задача двухуровневого линейного программирования с многовариантным ранцем на нижнем уровне // Дискрет. анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 1. С. 44–52.

[14] Moore J. T., Bard J. F. The mixed integer linear bilevel programming problem // Oper. Res. 1990. Vol. 38, No. 5. P. 911–921. http://dx.doi.org/10.1287/opre.38.5.911