|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы
А. В. Смирнов Ярославский государственный университет им. П. Г. Демидова, ул. Советская, 14, г. Ярославль, 150000 Россия
Аннотация:
Рассматривается задача целочисленного сбалансирования четырехмерной матрицы. В исходной вещественной матрице элементы внутренней части (все четыре индекса больше нуля) просуммированы по каждому направлению и каждому плоскому и трехмерному сечению матрицы, а также найдена общая сумма. Данные суммы размещаются в элементах матрицы, у которых один или несколько индексов равны нулю (в соответствии с направлениями суммирования). Ищется целочисленная матрица той же структуры, получаемая из исходной заменой элементов на округления до целого сверху или целого снизу. При этом элемент с четырьмя нулевыми индексами получается по обычным правилам округления.
В статье рассматривается также задача о наибольшем кратном потоке в сети произвольной натуральной кратности $k$. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение $k$ связанных дуг, согласованных между собой. Задаются правила построения сети. Вводится понятие делимой сети и ряд связанных определений.
Определяются общие принципы сведения задачи целочисленного сбалансирования $l$-мерной матрицы ($l\geq3$) к задаче о максимальном потоке в делимой кратной сети кратности $k$.
Задаются правила сведения четырехмерной задачи сбалансирования к задаче о наибольшем потоке в сети кратности 5. Для этой сети формулируется алгоритм нахождения максимального потока, удовлетворяющего условиям разрешимости задачи сбалансирования.
Ключевые слова:
целочисленное сбалансирование, кратные сети, кратные потоки, делимые сети, $NP$-полнота, обобщенный алгоритм пометок, четырехмерные матрицы.
Поступила в редакцию: 18.04.2016
Образец цитирования:
А. В. Смирнов, “Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы”, Модел. и анализ информ. систем, 23:4 (2016), 466–478
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais515 https://www.mathnet.ru/rus/mais/v23/i4/p466
|
Статистика просмотров: |
Страница аннотации: | 194 | PDF полного текста: | 62 | Список литературы: | 29 |
|