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

Актуальность и цели. Исследуется следующее обобщение агрегации систем линейных диофантовых уравнений: для заданной системы уравнений $\sum_{j=1}^n a_{ij}x_j = a_i$, $i=1,...,m$ с целыми коэффициентами найти целые множители $f_1, f_2, ..., f_m$ такие, что вершины выпуклой оболочки множества целых неотрицательных решений этой системы являются вершинами выпуклой оболочки множества целых неотрицательных решений уравнения $\sum_{i=1}^m f_i \sum_{j=1}^n a_{ij}x_j = \sum_{i=1}^m f_i a_i$. Материалы и методы. В работе используются методы линейного программирования и геометрии чисел. Результаты. Доказано, что обобщенное агрегирующее уравнение существует для любой системы линейных уравнений. Для систем уравнений с неотрицательными коэффициентами указан простой способ вычисления чисел $f_1, f_2, ..., f_m$. Получена достижимая нижняя оценка свободного члена обобщенного агрегирующего уравнения. Описан класс задач целочисленного линейного программирования, сводящихся к задаче о рюкзаке с правой частью $\sum_{i=1}^m f_i a_i$ меньшей, чем при любом способе обычной агрегации. Выводы. Новый подход к агрегации расширяет область ее применения и уменьшает коэффициенты агрегирующего уравнения.