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

В. С. Рублев; А. В. Смирнов

doi:undefined

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

В. С. Рублев, А. В. Смирнов

Полный текст:

Аннотация

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

Ключ. слова

целочисленное сбалансирование, трехмерные матрицы, кратные сети, кратные потоки, обобщенный алгоритм пометок, первый алгоритм Гомори, iVP-полнота, минимизация ошибок округления,

УДК: 519.854.2

Об авторах

В. С. Рублев

Ярославский государственный университет им. П.Г.Демидова
Россия

А. В. Смирнов

Ярославский государственный университет им. П.Г.Демидова
Россия

Список литературы

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.

For citation: Roublev V.S., Smirnov A.V. . Modeling and Analysis of Information Systems. 2010;17(2):72-98. (In Russ.)

Обратные ссылки

Обратные ссылки не определены.

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)

Логин
Пароль