A decomposition approach in the problem of distribution-type planning with priority constraints

В статье рассматривается задача планирования распределительного типа с приоритетами ограничений. Для заданного множества требований и ресурсов с установленными параметрами использования необходимо построить план назначений, удовлетворяющий системе приоритетных ограничений. При этом различают две очереди ограничений на количественные и качественные характеристики соответственно. На этапе решения задачи с первой очередью ограничений разрабатывается базовая модель целочисленного линейного программирования (ЦЛП) и динамическая схема ее формирования. В рамках такого подхода исходная задача сводится к решению последовательности аналогичных задач существенно меньшей размерности, что позволяет учитывать приоритеты использования ресурсов непосредственно по построению и гарантирует сходимость базовой модели ЦЛП на финальной итерации динамической схемы. На этапе реализации второй очереди ограничений для полученного базового решения вводится интегральный критерий в форме верхней оценки и рассматривается модифицированная модель ЦЛП. Процедура модификации модели опирается на метод штрафных функций и включает дооснащение системы ограничений, целевого функционала и функционального пространства подмножеством вспомогательных булевских переменных. При этом доказано, что модифицированная модель гарантировано разрешима и определяет при этом максимальную (по включению) совместную подсистему ограничений второй очереди для исходной задачи. В рамках анализа работоспособности и эффективности предложенного подхода проводится вычислительный эксперимент с использованием данных реальной размерности.