Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы

Рассматривается задача целочисленного сбалансирования четырехмерной матрицы. В исходной вещественной матрице элементы внутренней части (все четыре индекса больше нуля) просуммированы по каждому направлению и каждому плоскому и трехмерному сечению матрицы, а также найдена общая сумма. Данные суммы размещаются в элементах матрицы, у которых один или несколько индексов равны нулю (в соответствии с направлениями суммирования). Ищется целочисленная матрица той же структуры, получаемая из исходной заменой элементов на округления до целого сверху или целого снизу. При этом элемент с четырьмя нулевыми индексами получается по обычным правилам округления. В статье рассматривается также задача о наибольшем кратном потоке в сети произвольной натуральной кратности к. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение к связанных дуг, согласованных между собой. Задаются правила построения сети. Вводится понятие делимой сети и ряд связанных определений. Определяются общие принципы сведения задачи целочисленного сбалансирования  -мерной матрицы ( ) к задаче о максимальном потоке в делимой кратной сети кратности к . Задаются правила сведения четырехмерной задачи сбалансирования к задаче о наибольшем потоке в сети кратности 5. Для этой сети формулируется алгоритм нахождения максимального потока, удовлетворяющего условиям разрешимости задачи сбалансирования.

1. Корбут А. А., Финкельштейн Ю.Ю., Дискретное программирование, Наука, Москва, 1969.

2. Раскин Л. Г., Кириченко И. О., Многоиндексные задачи линейного программирования, Радио и связь, Москва, 1982.

3. Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11.

4. Афраймович Л. Г., “Трехиндексные задачи линейного программирования с вложенной структурой”, Автоматика и телемеханика, 2011, № 8, 109–120. DOI: 10.1134/S0005117911080066.

5. Кондаков А. С., Рублев В. С., “Задача сбалансирования матрицы плана”, Доклады Одесского семинара по дискретной математике, Астропринт, Одесса, 2005, 24–26.

6. Коршунова Н. М., Рублев В. С., “Задача целочисленного сбалансирования матрицы”, Современные проблемы математики и информатики, ЯрГУ, Ярославль, 2000, 145–150.

7. Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.

8. Рублев В. С., Смирнов А. В., “NP-полнота задачи целочисленного сбалансирования трехмерной матрицы”, Доклады Академии Наук, 435:3 (2010), 314–316. DOI: 10.1134/S1064562410060190.

9. Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, 1979.

10. Karp R., “Reducibility among combinatorial problems”, R. E. Miller, J. W. Thatcher (Eds.). Complexity of Computer Computations, Plenum, 1972, 85–103.

11. Рублев В. С., Смирнов А. В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98.

12. Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553. DOI: 10.3103/S0146411614070293.

13. Smirnov A. V., “Heuristic Algorithms for the Problem of Integer Balancing of a ThreeDimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 49:7 (2015), 473–483. DOI: 10.3103/S0146411615070196.

14. Смирнов А. В., “Задача о наибольшем кратном потоке в делимой сети и ее частные случаи”, Моделирование и анализ информационных систем, 22:4 (2015), 533–545. DOI: 10.18255/1818-1015-2015-4-533-545.

15. Рублев В. С., Смирнов А. В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68.