ДОКЛАДЫ АКАДЕМИИ НАУК
ВЫСШЕЙ ШКОЛЫ РОССИЙСКОЙ ФЕДЕРАЦИИ

ISSN: 1727-2769
English | Русский

Последний выпуск
№3(40) июль-сентябрь 2018

ПРАКТИЧЕСКИЕ АСПЕКТЫ РЕАЛИЗАЦИИ ЭФФЕКТИВНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОЙ КОМПЛЕКТАЦИИ

Выпуск № 1 (20) январь-июнь 2013
Авторы:

Мезенцев Юрий Анатольевич
Аннотация
Предложен численный метод решения общей задачи оптимальной комплектации, относящейся к классу NP-трудных задач дискретного программирования с булевыми переменными. Метод основан на процедурах линеаризации исходных условий, лагранжевой декомпозиции и итеративного параметрического анализа последовательности порождаемых подзадач. Показано, что алгоритм является эффективным и асимптотически точным по размерности задачи оптимальной комплектации.
Ключевые слова: целочисленное программирование, декомпозиция, параметрический анализ, эффективный алгоритм, задача оптимальной комплектации

Список литературы
  1. Мезенцев Ю.А. Эффективный алгоритм решения одного класса задач целочисленного программирования / Ю.А. Мезенцев // Доклады Академии наук высшей школы РФ. – Новосибирск: Изд-во НГТУ, 2012. – № 2(19). – С. 42–53.
  2. Мезенцев Ю.А. Декомпозиционный метод решения одного класса задач оптимального проектирования / Ю.А. Мезенцев // Научный вестник НГТУ. – Новосибирск, Изд-во НГТУ, 2006. – № 3(24). – С. 67–100.
  3. Лэсдон Л.С. Оптимизация больших систем / Л.С. Лэсдон. – М.: Наука, 1975. – 432 с.
  4. Бахтин А.Е. Математическое моделирование в экономике / А.Е. Бахтин. – Новосибирск: НГАЭиУ, 1995. – 196 с.
  5. Кнут Д. Искусство программирования для ЭВМ, том 3: Сортировка и поиск / Д. Кнут. – М.: Мир, 1978. – 812 с.
  6. Мезенцев Ю.А. Эффективный алгоритм целочисленного программирования / Ю.А. Мезенцев // Научный вестник НГТУ. – 2009. – № 2(35). – С. 91–114.
  7. Мезенцев Ю.А. Метод бинарных отсечений и ветвлений целочисленного программирования / Ю.А. Мезенцев // Доклады Академии наук высшей школы РФ. – Новосибирск: Изд-во НГТУ, 2011. – № 1(16). – С. 12–25.
  8. Мезенцев Ю.А. Реализация алгоритма решения специальных задач полуопределенного программирования с использованием IBM ILOG CPLEX / Ю.А. Мезенцев, П.С. Павлов // Научный вестник НГТУ. – Новосибирск: Изд-во НГТУ, 2011. – № 4(45). – С. 25–34.
  9. Мезенцев Ю.А. К программной реализации декомпозиционного алгоритма решения одного класса задач дискретной оптимизации с полуопределенной релаксацией / Ю.А. Мезенцев, П.С. Павлов // Информационные технологии. – М.: Новые технологии, 2012. – № 2. – С. 54–59.
Просмотров: 202