Мезенцев Юрий Анатольевич
Аннотация
Исследованы свойства общей задачи оптимальной комплектации, относящейся к классу NP- трудных задач дискретного программирования с булевыми переменными. Предложены процедуры линеаризации исходных условий, лагранжевой декомпозиции и итеративного параметрического анализа последовательности порождаемых подзадач. Изложены основные принципы, положенные в основу эффективного алгоритма решения задачи оптимальной комплектации.
Ключевые слова: целочисленное программирование, декомпозиция, параметрический анализ, эффективный алгоритм, задача оптимальной комплектации
Авторы:
Мезенцев Юрий Анатольевич
доктор технических наук, доцент, НГТУ, mesyan@yandex.ru
Список литературы
[1] Леонтьев В.К. Дискретная оптимизация // Журнал вычислительной математики и математиче- ской физики. – 2007. – Том 47. – № 2. – С. 338–352. [2] Мезенцев Ю.А. Декомпозиционный метод решения одного класса задач оптимального проек- тирования // Научный вестник НГТУ. – Новосибирск: Изд-во НГТУ, 2006. – № 3(24). – С. 67–100. [3] Korte B. Combinatorial optimization. Theory and algorithms / B. Korte, J. Vygen. – Springer, 2002. – 572 р. [4] Du D. Handbook of combinatorial optimization: Supplement / D. Du, P. Pardalos (eds.). Vol. A. – Kluwer academic publishers, 1999. – 649 p. [5] Du D. Handbook of combinatorial optimization: Supplement / D. Du, P. Pardalos (eds.). Vol. B. – Springer, 2005. – 403 p. [6] Glover F. Handbook of metaheuristics / F. Glover, G.A. Kochenberger eds // Kluwer academic publishers, 2003 – 560 p. [7] IBM ILOG CPLEX V12.1 User's Manual for CPLEX. IBM Corporation, 2009. – 952 c. [8] Мезенцев Ю.А. Метод бинарных отсечений и ветвлений целочисленного программирования // Доклады академии наук высшей школы РФ. – Новосибирск: Изд-во НГТУ, 2011. – № 1(16). – С. 12–25. [9] Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. – 520 с. [10] Муртаф Б. Современное линейное программирование. – М.: Мир, 1984. – 224 с. [11] Лэсдон Л.С. Оптимизация больших систем. – М.: Наука, 1975. – 432 с. [12] Бахтин А.Е. Математическое моделирование в экономике. – Новосибирск: НГАЭиУ, 1995. – 196 с. [13] Лихтенштейн В.Е. Дискретность и случайность в экономико-математических задачах. – М.: Наука, 1973. – 375 с. [14] Мезенцев Ю.А. Эффективный алгоритм целочисленного программирования // Научный вест- ник НГТУ. – 2009. – № 2(35). – С. 91–114.
