maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1030Research ArticleОригинальные статьиArticlesЗадача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решенияРублевВ. С.RoublevV. S.roublev@mail.ruСмирновА. В.SmirnovA. V.alexander_sm@mail.ruЯрославский государственный университет им. П.Г.ДемидоваRussian Federation2010200620101727298Copyright © Рублев В.С., Смирнов А.В., 20102010Рублев В.С., Смирнов А.В.Roublev V.S., 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/1030

Рассматривается задача целочисленного сбалансирования трехмерной матрицы, предлагается сведение этой задачи к задаче нахождения максимального потока в кратной сети целочисленного сбалансирования, приводится алгоритм решения задачи о кратном потоке. Также проводится сравнительная характе¬ристика алгоритмов целочисленного сбалансирования на основании вычисли¬тельных экспериментов. Кроме того, обосновывается NP-полнота задачи цело¬численного сбалансирования трехмерной матрицы и рассматривается задача минимизации ошибок округления в задаче сбалансирования.

целочисленное сбалансированиетрехмерные матрицыкратные сетикратные потокиобобщенный алгоритм пометокпервый алгоритм ГомориiVP-полнотаминимизация ошибок округленияinteger-valued balancingthree-dimensional matricesmultiple networksmultiple flowsgeneralized labeling algorithmfirst Gomory algorithmNP-completenessminimization of the errors of rounding offReferencesКоршунова Н.М., Рублев В.С. Задача целочисленного сбалансирования матри¬цы // Современные проблемы математики и информатики. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. Вып. 3. С. 145 - 150.Коршунова Н.М., Рублев В.С. Задача целочисленного сбалансирования матри¬цы // Современные проблемы математики и информатики. Ярославль: ЯрГУ им. П.Г. Демидова, 2000. Вып. 3. С. 145 - 150.Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. Т. 16, №3. С. 70 - 76.Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель // Моделирование и анализ информационных систем. 2009. Т. 16, №3. С. 70 - 76.Смирнов А.В. О несводимости задачи целочисленного сбалансирования трех¬мерной матрицы к задаче о наибольшем потоке // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г.: Труды. М.: Издательский отдел факультета ВМиК МГУ им. М. В. Ло¬моносова; МАКС Пресс, 2009. С. 270 - 273.Смирнов А.В. О несводимости задачи целочисленного сбалансирования трех¬мерной матрицы к задаче о наибольшем потоке // Дискретные модели в теории управляющих систем: VIII Международная конференция, Москва, 6-9 апреля 2009 г.: Труды. М.: Издательский отдел факультета ВМиК МГУ им. М. В. Ло¬моносова; МАКС Пресс, 2009. С. 270 - 273.Рублев В.С., Смирнов А.В. Целочисленное сбалансирование 3-мерной матрицы плана // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). М.: МГУ, 2006. С. 302 - 308.Рублев В.С., Смирнов А.В. Целочисленное сбалансирование 3-мерной матрицы плана // Труды VII международной конференции «Дискретные модели в теории управляющих систем» (Покровское, 4-6 марта 2006 г.). М.: МГУ, 2006. С. 302 - 308.Рублев В.С., Смирнов А.В. Послойный алгоритм целочисленного сбалансиро¬вания трехмерной матрицы // Материалы IX Международного семинара «Дис¬кретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2007 г.). М.: МГУ, 2007. С. 351 - 353.Рублев В.С., Смирнов А.В. Послойный алгоритм целочисленного сбалансиро¬вания трехмерной матрицы // Материалы IX Международного семинара «Дис¬кретная математика и ее приложения», посвященного 75-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2007 г.). М.: МГУ, 2007. С. 351 - 353.Рублев В.С., Смирнов А.В. Минимизация ошибок округления в задаче цело¬численного сбалансирования трехмерной матрицы // Материалы XVII Между¬народной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). Ново¬сибирск: Изд-во Института математики, 2008. С. 153 - 157.Рублев В.С., Смирнов А.В. Минимизация ошибок округления в задаче цело¬численного сбалансирования трехмерной матрицы // Материалы XVII Между¬народной школы-семинара «Синтез и сложность управляющих систем» имени академика О.Б. Лупанова (Новосибирск, 27 октября - 1 ноября 2008 г.). Ново¬сибирск: Изд-во Института математики, 2008. С. 153 - 157.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

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