Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения
Abstract
The article is devoted to the problem of integer-valued balancing of a three-dimensional matrix. The reduction of this problem to the problem of finding a maximum flow in the multiple network of integer-valued balancing and the algorithm for this problem are suggested. Also, the comparative characteristic of two algorithms of integer-valued bal¬ancing is made according to the results of the computing experiments. NP-completeness of the problem of integer-valued balancing of a three-dimensional matrix is proved in the article. The problem of minimization of the errors of rounding off in the problem of integer-valued balancing is explored.
About the Authors
V. S. Roublev
Ярославский государственный университет им. П.Г.Демидова
Russian Federation
Russian Federation
A. V. Smirnov
Ярославский государственный университет им. П.Г.Демидова
Russian Federation
Russian Federation
References
1. Коршунова Н.М., Рублев В.С. Задача целочисленного сбалансирования матри¬цы // Современные проблемы математики и информатики. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. Вып. 3. С. 145 - 150.
2. Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. Т. 16, №3. С. 70 - 76.
3. Смирнов А.В. О несводимости задачи целочисленного сбалансирования трех¬мерной матрицы к задаче о наибольшем потоке // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г.: Труды. М.: Издательский отдел факультета ВМиК МГУ им. М. В. Ло¬моносова; МАКС Пресс, 2009. С. 270 - 273.
4. Рублев В.С., Смирнов А.В. Целочисленное сбалансирование 3-мерной матрицы плана // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). М.: МГУ, 2006. С. 302 - 308.
5. Рублев В.С., Смирнов А.В. Послойный алгоритм целочисленного сбалансиро¬вания трехмерной матрицы // Материалы IX Международного семинара «Дис¬кретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2007 г.). М.: МГУ, 2007. С. 351 - 353.
6. Рублев В.С., Смирнов А.В. Минимизация ошибок округления в задаче цело¬численного сбалансирования трехмерной матрицы // Материалы XVII Между¬народной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). Ново¬сибирск: Изд-во Института математики, 2008. С. 153 - 157.
7. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
8. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.
9. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Review
For citations:
Roublev V.S., Smirnov A.V. . Modeling and Analysis of Information Systems. 2010;17(2):72-98. (In Russ.)
Views:
487
Email this article 