Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения
Аннотация
Рассматривается задача целочисленного сбалансирования трехмерной матрицы, предлагается сведение этой задачи к задаче нахождения максимального потока в кратной сети целочисленного сбалансирования, приводится алгоритм решения задачи о кратном потоке. Также проводится сравнительная характе¬ристика алгоритмов целочисленного сбалансирования на основании вычисли¬тельных экспериментов. Кроме того, обосновывается NP-полнота задачи цело¬численного сбалансирования трехмерной матрицы и рассматривается задача минимизации ошибок округления в задаче сбалансирования.
Об авторах
В. С. Рублев
Ярославский государственный университет им. П.Г.Демидова
Россия
Россия
А. В. Смирнов
Ярославский государственный университет им. П.Г.Демидова
Россия
Россия
Список литературы
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.
Для цитирования:
Рублев В.С., Смирнов А.В. Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения. Моделирование и анализ информационных систем. 2010;17(2):72-98.
Просмотров: 57
Послать статью по эл. почте 