ПРАКТИЧЕСКИЕ АСПЕКТЫ РЕАЛИЗАЦИИ ЭФФЕКТИВНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОЙ КОМПЛЕКТАЦИИ
Ю.А. Мезенцев
Новосибирский государственный технический университет, Новосибирск, Россия mesyan@yandex.ru
Ключевые слова: целочисленное программирование, декомпозиция, параметрический анализ, эффективный алгоритм, задача оптимальной комплектации
Страницы: 26-34
Аннотация
Предложен численный метод решения общей задачи оптимальной комплектации, относящейся к классу NP-трудных задач дискретного программирования с булевыми переменными. Метод основан на процедурах линеаризации исходных условий, лагранжевой декомпозиции и итеративного параметрического анализа последовательности порождаемых подзадач. Показано, что алгоритм является эффективным и асимптотически точным по размерности задачи оптимальной комплектации.
|