RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2014, том 21, номер 4, страницы 132–147 (Mi mais393)  

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

А. В. Смирнов

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

Аннотация: Рассматривается задача целочисленного сбалансирования с ограничениями второго рода. В вещественной трехмерной матрице элементы внутренней части (все три индекса больше нуля) просуммированы по каждому направлению и сечению матрицы, а также найдена общая сумма. Данные суммы размещаются в элементах матрицы, у которых один или несколько индексов равны нулю (в соответствии с направлениями суммирования). Ищется целочисленная матрица той же структуры, получаемая из исходной заменой элементов внутренней части на округления до целого сверху или целого снизу. При этом суммирующие элементы должны отклоняться от исходных менее чем на 2, а элемент с тремя нулевыми индексами получается по обычным правилам округления.
В статье разрабатываются эвристические алгоритмы решения задачи. Послойный алгоритм получается как обобщение соответствующего алгоритма для задачи с ограничениями первого рода. Предлагается новый матричный алгоритм, состоящий из трех частей: поиск базовой матрицы, поиск максимальной матрицы и коррекция матрицы. На всех шагах циклически проводятся изменения целочисленной матрицы, затрагивающие от 1 до 3 элементов внутренней части. Определяется модифицированный матричный алгоритм, направленный на более равномерное заполнение внутренней части целочисленной матрицы.
Также в статье оценивается сложность всех трех алгоритмов и приводится сравнительный анализ матричных алгоритмов на основе результатов вычислительных экспериментов.

Ключевые слова: целочисленное сбалансирование, трехмерные матрицы, ограничения второго рода, кратные сети, кратные потоки, обобщенный алгоритм пометок, послойный алгоритм, матричный алгоритм.

Полный текст: PDF файл (400 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.854.2
Поступила в редакцию: 03.06.2014

Образец цитирования: А. В. Смирнов, “Эвристические алгоритмы для задачи целочисленного сбалансирования трехмерной матрицы с ограничениями второго рода”, Модел. и анализ информ. систем, 21:4 (2014), 132–147

Цитирование в формате AMSBIB
\RBibitem{Smi14}
\by А.~В.~Смирнов
\paper Эвристические алгоритмы для задачи целочисленного сбалансирования трехмерной матрицы с ограничениями второго рода
\jour Модел. и анализ информ. систем
\yr 2014
\vol 21
\issue 4
\pages 132--147
\mathnet{http://mi.mathnet.ru/mais393}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais393
  • http://mi.mathnet.ru/rus/mais/v21/i4/p132

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:108
    Полный текст:31
    Литература:17

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019