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

Аннотация
Предложен численный метод решения общей задачи оптимальной комплектации, относящейся к классу 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.

Просмотров аннотации: 1658
Скачиваний полного текста: 1
Просмотров интерактивной версии: 0