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