Рассмотрена задача нахождения максимального потока в сети с нелинейными функциями усиления в дугах. Она обобщает аналогичную задачу для сети с линейными функциями усиления, которая, в свою очередь, обобщает классическую задачу о максимальном потоке в сети.

Задача нахождения максимального потока в сети с вогнутыми кусочно-линейными усилениями сведена к задаче нахождения максимального потока в сети с линейными усилениями в параллельных дугах, для которой есть эффективные алгоритмы решения.

Построен полупереборный алгоритм нахождения максимального потока в сети с
непрерывными кусочно-линейными усилениями, основанный на рассмотрении непрерывной кусочно-линейной функции как максимума из вогнутых кусочно-линейных функций. Показано, что задача о рюкзаке эквивалентна частному случаю данной задачи. Метод ветвей и границ в задаче о рюкзаке обобщается на данную задачу.
Язык оригиналарусский
Название основной публикацииВзгляд молодых учёных на подходы и алгоритмы управления пространственным развитием для повышения устойчивости, инновационности и конкурентоспособности экономики регионов.
ИздательСкифия-принт
Страницы118-142
ISBN (печатное издание)978-5-98620-635-6
DOI
СостояниеОпубликовано - 2022

ID: 116283949