ОПТИМІЗАЦІЯ ДРОБОВО-ЛІНІЙНОЇ ФУНКЦІЇ НА ПЕРЕСТАНОВКАХ: ПОЛІНОМІАЛЬНИЙ АЛГОРИТМ

Main Article Content

Олег Олексійович Ємець
Тетяна Миколаївна Барболіна

Abstract

Стаття присвячена дослідженню задач оптимізації дробово-лінійної функції на множині перестановок. Показано можливість розв’язування таких задач шляхом розв’язування послідовності лінійних безумовних задач оптимізації на перестановках. Сформульовано й обґрунтовано відповідний алгоритм, доведена його поліноміальність.

Article Details

Section
Applied Mathematics

References

Сергиенко И. В. Модели и методы решения на ЭВМ комбинаторных задач оптимизации / И.В. Сергиенко, М.Ф. Каспшицкая. – К. : Наук. думка, 1981. –288с.

Згуровский М.З. Принятие решений в сетевых системах с ограниченными ресурсами / М.З. Згуровский, А.А. Павлов. – К.: Наук. думка, 2010.– 573 с.

Сергиенко И. В. Классификация прикладных методов комбинаторной оптимизации / Л.Ф. Гуляницкий, С.И.Сиренко // Кибернетика и системный анализ. – 2009. – № 5. — С. 71-83.

Семенова Н.В. Об одном подходе к решению векторных задач с дробно-линейными функциями критериев на комбинаторном множестве размещений / Н. В. Семенова, Л. Н. Колечкина, А. Н. Нагорная // Проблемы управления и информатики. - 2010. - № 1. - С. 131-144.

Cтоян Ю.Г. Теорія і методи евклідової комбінаторної оптимізації / Ю.Г.Стоян, О.О.Ємець. – К. : Інститут системних досліджень освіти, 1993. – 188 с. – Режим доступу: http://dspace.puet.edu.ua/handle/123456789/487

Ємець О.О. Задачі комбінаторної оптимізації з дробово-лінійними функціями / О.О. Ємець, Л.М. Колєчкіна. – К.: Наук. думка, 2005. – 117 с.

Емец О.А. Оптимизация дробно-линейных функций на размещениях / О. А. Емец, О. А. Черненко. – К. : Наукова думка, 2011. – 154 с. – Режим доступа: http://dspace.puet.edu.ua/handle/123456789/467.

Емец О.А. Комбинаторная оптимизация на размещениях / О. А. Емец, Т. Н. Барболина . – К. : Наук. думка, 2008. – 159 с. – Режим доступу: http://dspace.puet.edu.ua/handle/123456789/473.

Емец О.А. Лексикографическая комбинаторная оптимизация дробно-линейной функции на размещениях / О.А. Емец ,Т.Н. Барболина // Матеріали Вісімнадцятого Міжнародного науково-практичного семінару "Комбінаторні конфігурації та їх застосування" (Кіровоград, 15-16 квітня 2016 р.). – Кіровоград, 2016. – С. 67-77.

Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — М. : Издательский дом «Вильямс», 2005. — 1296 с.

Ахо А. Построение и анализ вычислительных алгоритмов / А.Ахо, Д.Хопкрофт, Д.Ульман. — М. : Мир, 1979. — 536 с.