Математика
Агрегация уравнений в целочисленном программировании
С. И. Веселов,
А. Ю. Чирков,
Д. В. Грибанов Нижегородский государственный университет им. Н. И. Лобачевского, Нижний Новгород
Аннотация:
Актуальность и цели. Исследуется следующее обобщение агрегации систем линейных диофантовых уравнений: для заданной системы уравнений
$\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$ меньшей, чем при любом способе обычной агрегации.
Выводы. Новый подход к агрегации расширяет область ее применения и уменьшает коэффициенты агрегирующего уравнения.
Ключевые слова:
агрегация систем линейных уравнений, задача о рюкзаке.
УДК:
519.854
DOI:
10.21685/2072-3040-2016-2-1