Комбинаторные свойства задачи об ограниченном рюкзаке

Рассматриваются комбинаторные свойства множества решений в задаче об ограниченном рюкзаке. Как и в общем случае, эта задача является NP-полной задачей комбинаторной оптимизации и её точное решение требует применения алгоритмов перебора с декомпозицией множества допустимых решений. В связи с этим актуален вопрос определения и оценки свойств множества допустимых решений. Получены формулы, позволяющие вычислять среднее значение функционала задачи на множестве её допустимых решений и мощность этого множества через число решений подзадач меньшей размерности. Базовой техникой получения результатов служит метод производящих функций. Рассмотрена задача о рюкзаке с произвольными значениями переменных, в которой совпадают коэффициенты вектора ограничений и целевой функции. Для неё предполагается «сюръективность» множества решений. Найдены оценки значений функционала в этой задаче. Результаты могут представлять интерес для конструирования вычислительных алгоритмов нахождения и оценки числа решений и значения функционала на оптимальных решениях. Найденные выражения также могут быть использованы во вспомогательных процедурах для оценки оптимальности решения в декомпозиционных или эвристических алгоритмах решения задачи о рюкзаке.