Анализ устойчивости задач и алгоритмов целочисленного программирования

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