Журнал вычислительной математики и математической физики
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Ж. вычисл. матем. и матем. физ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Журнал вычислительной математики и математической физики, 2021, том 61, номер 8, страницы 1390–1400
DOI: https://doi.org/10.31857/S0044466921060119
(Mi zvmmf11283)
 

Информатика

Минимаксная задача подавления сети связи

А. Г. Перевозчиковa, В. Ю. Решетовb, И. Е. Яночкинa

a 170000 Тверь, пр-т Калинина, 17, АО "НПО РусБИТех-Тверь", Департамент проектирования систем, отдел проектирования математических моделей и информационно-расчетных задач, Россия
b 119999 Москва, Ленинские горы, МГУ, ВМК, Россия
Аннотация: В статье обобщается классическая задача о максимальном потоке в ориентированной сети Л. Форда и Д. Фалкерсона в части учета возможного противодействия противника, состоящего в уменьшении пропускной способности ребер. Противодействие состоит не в уменьшении потока на каждой дуге, а уменьшении ее пропускной способности, что приводит в общем случае к задаче минимизации пропускной способности минимального разреза, которая сводится к последовательности задач математического программирования. Поскольку множество разрезов можно отождествить с множеством всех подмножеств множества узлов сети, то полученная задача эквивалентна дискретной задаче на булевой решетке и может быть решена методами субмодулярного программирования, развитыми в работах Р.В. Хачатурова. Приводятся числовые примеры.
Библ. 12. Фиг. 5.
Ключевые слова: задача о максимальном потоке Форда–Фалкерсона, задача минимизации максимального потока, сведение минимаксной задачи к последовательности эквивалентных задач, эквивалентные задачи на булевой решетке, их решение методами субмодулярного программирования.
Поступила в редакцию: 10.07.2020
Исправленный вариант: 11.11.2020
Принята в печать: 11.02.2021
Англоязычная версия:
Computational Mathematics and Mathematical Physics, 2021, Volume 61, Issue 8, Pages 1364–1373
DOI: https://doi.org/10.1134/S0965542521060117
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.7
Образец цитирования: А. Г. Перевозчиков, В. Ю. Решетов, И. Е. Яночкин, “Минимаксная задача подавления сети связи”, Ж. вычисл. матем. и матем. физ., 61:8 (2021), 1390–1400; Comput. Math. Math. Phys., 61:8 (2021), 1364–1373
Цитирование в формате AMSBIB
\RBibitem{PerResYan21}
\by А.~Г.~Перевозчиков, В.~Ю.~Решетов, И.~Е.~Яночкин
\paper Минимаксная задача подавления сети связи
\jour Ж. вычисл. матем. и матем. физ.
\yr 2021
\vol 61
\issue 8
\pages 1390--1400
\mathnet{http://mi.mathnet.ru/zvmmf11283}
\crossref{https://doi.org/10.31857/S0044466921060119}
\elib{https://elibrary.ru/item.asp?id=46351135}
\transl
\jour Comput. Math. Math. Phys.
\yr 2021
\vol 61
\issue 8
\pages 1364--1373
\crossref{https://doi.org/10.1134/S0965542521060117}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000697201600012}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85115139614}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/zvmmf11283
  • https://www.mathnet.ru/rus/zvmmf/v61/i8/p1390
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
    Статистика просмотров:
    Страница аннотации:64
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024