Аннотация:
В статье обобщается классическая задача о максимальном потоке в ориентированной сети Л. Форда и Д. Фалкерсона в части учета возможного противодействия противника, состоящего в уменьшении пропускной способности ребер. Противодействие состоит не в уменьшении потока на каждой дуге, а уменьшении ее пропускной способности, что приводит в общем случае к задаче минимизации пропускной способности минимального разреза, которая сводится к последовательности задач математического программирования. Поскольку множество разрезов можно отождествить с множеством всех подмножеств множества узлов сети, то полученная задача эквивалентна дискретной задаче на булевой решетке и может быть решена методами субмодулярного программирования, развитыми в работах Р.В. Хачатурова. Приводятся числовые примеры.
Библ. 12. Фиг. 5.
Ключевые слова:задача о максимальном потоке Форда–Фалкерсона, задача минимизации максимального потока, сведение минимаксной задачи к последовательности эквивалентных задач, эквивалентные задачи на булевой решетке, их решение методами субмодулярного программирования.
УДК:519.7
Поступила в редакцию: 10.07.2020 Исправленный вариант: 11.11.2020 Принята в печать: 11.02.2021
