Вероятностный подход к решению трехиндексной аксиальной задачи о назначениях. Развитие поисковых способностей
Ключевые слова:
трехиндексная аксиальная задача о назначениях, адаптивный алгоритм, вероятностная постановка, локальный поиск
Аннотация
В статье рассматривается адаптивный алгоритм решения трехиндексной аксиальной задачи о назначениях. Алгоритм основан на переходе к вероятностной постановке задачи. На основе вычислительного эксперимента рассмотрена возможность его улучшения. Для этого вводится понятие окрестности решения задачи на основе расстояния Хэмминга, и рассматривается переход из окрестности одной точки в окрестность другой на основе настройки параметров алгоритма. В результате предлагается изменение параметров алгоритма по некоторой функциональной зависимости от числа итераций. В завершении приводятся результаты вычислительного эксперимента и выводы.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Афраймович, Л. Г. Многоиндексные транспортные задачи с декомпозиционной структурой / Л. Г. Афраймович // Автоматика и телемеханика. – 2012. – No 1. – С. 130–147.
2. Афраймович, Л. Г. Эвристический метод решения целочисленных декомпозиционных многоиндексных задач / Л. Г. Афраймович // Автоматика и телемеханика. – 2014. – No 8. – С. 3–18.
3. Гимади, Э. Х. Аксиальные трехиндексные задачи о назначениях и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ / Э. Х. Гимади, А. И. Сердюков // Изв. Вузов. Математика. – 1999. – No 12. – С. 19–25.
4. Корбут, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн [под ред. Д. Б. Юдина]. – М. : Наука, 1969. – 368 с.
5. Львович, Я. Е. Конструирование адаптивных схем перебора для решения дискретных задач оптимизации / Я. Е. Львович, А. И Каплинский, Г. Д. Чернышова, О. И. Черных // В сб.: Актуальные проблемы фундаментальных наук. – М. : Изд-во МГТУ, 1991.
6. Малюгина, О. А. Задача комплектования штатов / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышова // Системное моделирование социально-экономических процессов : труды 31-й Международной научной школы-семинара, Воронеж, 1–5 октября 2008 г. : в 3 ч. – Воронеж : ИПЦ Воронеж. гос. ун-т., 2008. – Ч. III. – С. 265–272.
7. Медведев, С. Н. Адаптивные алгоритмы решения трехиндексных задач о назначениях / С. Н. Медведев // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. тр. VI Меж-дунар. конф. «ПМТУКТ-2013», Воронеж, 10–16 сентября 2013 г. – Воронеж: ИПЦ Воронеж. гос. ун-т, 2013. – С. 153–156.
8. Трегубов, А. Г. Вероятностный подход к решению трехиндексной аксиальной задачи о назначениях / А. Г. Трегубов, С. Н. Медведев // Вестник Воронеж. гос. ун-та. Сер. Системный анализ и информационные технологии. – 2015. – No 4. – 12 с.
9. Чернышова, Г. Д. Об использовании вероятностного аналога алгоритма покоординатного спуска в задаче о минимальном покрытии / Г. Д. Чернышова, С. В. Писковецкий – Воронеж: Воронеж. гос. ун-т., 2001. – 14 с.
10. Crama, Y. Approximation algorithms for three-dimensional assignment problems with triangle inequalities / Y. Crama, F.C.R. Spieksma // European J. Oper. Res. – 1992. – Vol. 60. – P. 273–279.
2. Афраймович, Л. Г. Эвристический метод решения целочисленных декомпозиционных многоиндексных задач / Л. Г. Афраймович // Автоматика и телемеханика. – 2014. – No 8. – С. 3–18.
3. Гимади, Э. Х. Аксиальные трехиндексные задачи о назначениях и коммивояжера: быстрые приближенные алгоритмы и их вероятностный анализ / Э. Х. Гимади, А. И. Сердюков // Изв. Вузов. Математика. – 1999. – No 12. – С. 19–25.
4. Корбут, А. А. Дискретное программирование / А. А. Корбут, Ю. Ю. Финкельштейн [под ред. Д. Б. Юдина]. – М. : Наука, 1969. – 368 с.
5. Львович, Я. Е. Конструирование адаптивных схем перебора для решения дискретных задач оптимизации / Я. Е. Львович, А. И Каплинский, Г. Д. Чернышова, О. И. Черных // В сб.: Актуальные проблемы фундаментальных наук. – М. : Изд-во МГТУ, 1991.
6. Малюгина, О. А. Задача комплектования штатов / О. А. Малюгина, С. Н. Медведев, Г. Д. Чернышова // Системное моделирование социально-экономических процессов : труды 31-й Международной научной школы-семинара, Воронеж, 1–5 октября 2008 г. : в 3 ч. – Воронеж : ИПЦ Воронеж. гос. ун-т., 2008. – Ч. III. – С. 265–272.
7. Медведев, С. Н. Адаптивные алгоритмы решения трехиндексных задач о назначениях / С. Н. Медведев // Современные методы прикладной математики, теории управления и компьютерных технологий: сб. тр. VI Меж-дунар. конф. «ПМТУКТ-2013», Воронеж, 10–16 сентября 2013 г. – Воронеж: ИПЦ Воронеж. гос. ун-т, 2013. – С. 153–156.
8. Трегубов, А. Г. Вероятностный подход к решению трехиндексной аксиальной задачи о назначениях / А. Г. Трегубов, С. Н. Медведев // Вестник Воронеж. гос. ун-та. Сер. Системный анализ и информационные технологии. – 2015. – No 4. – 12 с.
9. Чернышова, Г. Д. Об использовании вероятностного аналога алгоритма покоординатного спуска в задаче о минимальном покрытии / Г. Д. Чернышова, С. В. Писковецкий – Воронеж: Воронеж. гос. ун-т., 2001. – 14 с.
10. Crama, Y. Approximation algorithms for three-dimensional assignment problems with triangle inequalities / Y. Crama, F.C.R. Spieksma // European J. Oper. Res. – 1992. – Vol. 60. – P. 273–279.
Опубликован
2018-10-22
Как цитировать
Трегубов, А. Г., & Медведев, С. Н. (2018). Вероятностный подход к решению трехиндексной аксиальной задачи о назначениях. Развитие поисковых способностей. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 35-43. https://doi.org/10.17308/sait.2018.4/1250
Раздел
Математические методы системного анализа и управления
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
