Построение и анализ алгоритмов целочисленного программирования, Антон Колосов, Александр Колоколов und Марина Девятерикова

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