ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2020; 2: 5-12
http://dx.doi.org/10.17213/1560-3644-2020-2-5-12
ИССЛЕДОВАНИЕ РАЗЛИЧНЫХ МОДИФИКАЦИЙ АЛГОРИТМА ПЛОТНИКОВА–ЗВЕРЕВА ПРИ РЕШЕНИИ НЕОДНОРОДНОЙ МИНИМАКСНОЙ ЗАДАЧИ
Кобак Валерий Григорьевич – д-р техн. наук, профессор, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: valera33305@mail.ru
Поркшеян Виталий Маркосович – канд. физ.-мат. наук, доцент, кафедра «Математика», Донской государственный технический университет, г. Ростов-на-Дону, Россия. E-mail: spu-46@donstu.ru
Кузин Александр Павлович – ст. преподаватель, кафедра «Программное обеспечение вычислительной техники и автоматизированных систем», Донской государственный технический университет, г. Ростов-на-Дону. Россия. E-mail: alexpavkuzin@gmail.com
Аннотация
Рассматривается проблема решения неоднородной минимаксной задачи, являющейся одной из задач теории оптимизации. Сложность данной задачи заключается в том, что получить точное решение для больших размерностей не представляется возможным. Анализируется один из приближенных методов решения, называемый алгоритмом Плотникова–Зверева. Кроме того, описываются несколько модификаций данного алгоритма, разработанных авторами статьи. При помощи вычислительных средств был поставлен численный эксперимент, в рамках которого проводилось сравнение алгоритма Плотникова–Зверева и его модификаций по следующим критериям: минимальное значение и среднее значение среди полученных решений. В результате был сделан вывод о высокой эффективности разработанных модификаций алгоритма.
Ключевые слова: неоднородная минимаксная задача; NP-полные задачи; алгоритм Плотникова–Зверева; теория расписаний; минимаксный критерий; методы оптимизации; списочные алгоритмы.
Полный текст: [in elibrary.ru]
Ссылки на литературу
- Алексеев О.Т. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987.
- Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; под ред. Л.Н. Красножан. М.: Вильямс, 2013. 1328 с.
- Полиномиальное время // [СГУ] URL http://rain.ifmo.ru/cat /view.php/theory/algorithm-analysis/np-completeness-2004 (дата обращения 12.10.2016).
- Кононов А.В. Актуальные задачи теории расписаний: вычислительная сложность и приближенные алгоритмы: автореф. дис. … д-ра физ.-мат. наук. Новосибирск, 2014, 196 с.
- Плотников В.Н., Зверев В.Ю. Методы быстрого распределения алгоритмов в вычислительных системах // Техническая кибернетика № 3. 1974.
- Лазарев А.А. Теория расписаний. Задачи и алгоритмы. M.: Моск. гос. ун-т им. М.В. Ломоносова, 2011. 222 с.
- Кобак В.Г. [и др.]. Эффективные методы решения однородных распределительных задач на основе минимаксного критерия. Ростов н/Д: Издательский центр ДГТУ, 2013. 99 с.
- Поспелов Д.А. Введение в теорию вычислительных систем. М.:Советское радио, 1972.
- Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, 1975.
- Панфилов И.В., Половко А.М. Вычислительные системы. М.: Советское радио, 1980.