maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-4-466-478mais-371Research ArticleОригинальные статьиArticlesСетевая модель для задачи целочисленного сбалансирования четырехмерной матрицыNetwork Model for The Problem of Integer Balancing of a Fourdimensional Matrixhttps://orcid.org/0000-0002-0980-2507СмирновА. В.SmirnovA. V.

Смирнов Александр Валерьевич, кандидат физико-математических наук, доцент кафедры теоретической информатики

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150000

Smirnov Alexander Valeryevich, PhD, Associate Professor

P.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000

alexander_sm@mail.ruЯрославский государственный университет им. П.Г. Демидова, ЯрославльРоссияP.G. Demidov Yaroslavl State University, YaroslavlRussian Federation201620082016234466478Copyright © Смирнов А.В., 20162016Смирнов А.В.Smirnov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/371

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

The problem of integer balancing of a four-dimensional matrix is studied. The elements of the inner part (all four indices are greater than zero) of the given real matrix are summed in each direction and each two- and three-dimensional section of the matrix; the total sum is also found. These sums are placed into the elements where one or more indices are equal to zero (according to the summing directions). The problem is to find an integer matrix of the same structure, which can be produced from the initial one by replacing the elements with the largest previous or the smallest following integer. At the same time, the element with four zero indices should be produced with standard rules of rounding - off. In the article the problem of finding the maximum multiple flow in the network of any natural multiplicity   is also studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and multi-arc is a union of   linked arcs, which are adjusted with each other. The network constructing rules are described. The definitions of a divisible network and some associated subjects are stated. There are defined the basic principles for reducing the integer balancing problem of an  -dimensional matrix ( ) to the problem of finding the maximum flow in a divisible multiple network of multiplicity  . There are stated the rules for reducing the four-dimensional balancing problem to the maximum flow problem in the network of multiplicity 5. The algorithm of finding the maximum flow, which meets the solvability conditions for the integer balancing problem, is formulated for such a network.

целочисленное сбалансированиекратные сетикратные потокиделимые сетиNP-полнотаобобщенный алгоритм пометокчетырехмерные матрицыinteger balancingmultiple networksmultiple flowsdivisible networksNP-completenessgeneralized labeling algorithmfour-dimensional matricesReferencesКорбут А. А., Финкельштейн Ю.Ю., Дискретное программирование, Наука, Москва, 1969.Korbut A. A., Finkelstein J. J., Diskretnoe programmirovanie, Nauka, Moskva, 1969, (in Russian).Раскин Л. Г., Кириченко И. О., Многоиндексные задачи линейного программирования, Радио и связь, Москва, 1982.Raskin L. G., Kirichenko I. O., Mnogoindeksnye zadachi lineynogo programmirovaniya, Radio i svyaz, Moskva, 1982, (in Russian).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.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.Афраймович Л. Г., “Трехиндексные задачи линейного программирования с вложенной структурой”, Автоматика и телемеханика, 2011, № 8, 109–120. DOI: 10.1134/S0005117911080066.Afraimovich L. G., “Three-index linear programs with nested structure”, Automation and Remote Control, 72:8 (2011), 1679–1689. DOI: 10.1134/S0005117911080066.Кондаков А. С., Рублев В. С., “Задача сбалансирования матрицы плана”, Доклады Одесского семинара по дискретной математике, Астропринт, Одесса, 2005, 24–26.Kondakov A. S., Roublev V. S., “Zadacha sbalansirovaniya matritsy plana”, Doklady Odesskogo seminara po diskretnoy matematike, Astroprint, Odessa, 2005, 24–26, (in Russian).Коршунова Н. М., Рублев В. С., “Задача целочисленного сбалансирования матрицы”, Современные проблемы математики и информатики, ЯрГУ, Ярославль, 2000, 145–150.Korshunova N. M., Roublev V. S., “Zadacha tselochislennogo sbalansirovaniya matritsy”, Sovremennye problemy matematiki i informatiki, Yaroslavl State University, Yaroslavl, 2000, 145–150, (in Russian).Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Рублев В. С., Смирнов А. В., “NP-полнота задачи целочисленного сбалансирования трехмерной матрицы”, Доклады Академии Наук, 435:3 (2010), 314–316. DOI: 10.1134/S1064562410060190.Roublev V. S., Smirnov A. V., “NP-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix”, Doklady Mathematics, 82:3 (2010), 912–914. DOI: 10.1134/S1064562410060190.Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, 1979.Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, 1979.Karp R., “Reducibility among combinatorial problems”, R. E. Miller, J. W. Thatcher (Eds.). Complexity of Computer Computations, Plenum, 1972, 85–103.Karp R., “Reducibility among combinatorial problems”, R. E. Miller, J. W. Thatcher (Eds.). Complexity of Computer Computations, Plenum, 1972, 85–103.Рублев В. С., Смирнов А. В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98.Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98, (in Russian).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.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.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.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.Смирнов А. В., “Задача о наибольшем кратном потоке в делимой сети и ее частные случаи”, Моделирование и анализ информационных систем, 22:4 (2015), 533–545. DOI: 10.18255/1818-1015-2015-4-533-545.Smirnov A. V., “The Problem of Finding the Maximal Multiple Flow in the Divisible Network and its Special Cases”, Modeling and Analysis of Information Systems, 22:4 (2015), 533–545, (in Russian)]. DOI: 10.18255/1818-1015-2015-4-533-545.Рублев В. С., Смирнов А. В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68.Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68, (in Russian).

The authors declare that there are no conflicts of interest present.