1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 59, № 8, 2019

Журнал вычислительной математики и математической физики, 2019, T. 59, № 8, стр. 1439-1447

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

Э. Н. Гордеев 1, *, В. К. Леонтьев 1, **

1 МГТУ, 105005 Москва, ул. 2-я Бауманская, 5, стр. 2
ВЦ ФИЦ ИУ РАН, 119133 Москва, ул. Вавилова, 40, Россия

* E-mail: werhorn@yandex.ru
** E-mail: vkleontiev@yandex.ru

Поступила в редакцию 19.12.2018
После доработки 02.02.2019
Принята к публикации 08.02.2019

Полный текст (PDF)

Аннотация

Рассматривается задача о ранце с булевыми переменными и одним ограничением. Задача является NP-трудной в общем случае, для ее точного решения применяются различные переборные алгоритмы, использующие декомпозицию множества допустимых решений и вычисления оценок значения функционала. В работе получены комбинаторные формулы, позволяющие вычислять и оценивать значения функционала в различных случаях в зависимости от набора заданных параметров задачи. Рассмотрен также случай совпадения коэффициентов вектора ограничений и целевой функции. Отмечена связь множества решений задачи с определенного типа пороговыми функциями. В качестве параметров берутся коэффициенты целевой функции, вектора ограничений и объем рюкзака. Базовой техникой является классический метод производящих функций. Результаты, полученные в работе, в частности, могут быть использованы для оценки трудоемкости переборных и декомпозиционных методов решения задачи, а также непосредственно при их разработке в качестве вспомогательных процедур. Библ. 7.

Ключевые слова: задача о рюкзаке, производящие функции, NP-трудные задачи, оценка функционала.

1. ВВЕДЕНИЕ

Классическая задача о ранце с булевыми переменными имеет вид

(1)
$\sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}} \to \max } ,$
(2)
$\sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}} \leqslant b} ,$
где x = (x1, xn) – n-мерный булевский вектор.

Везде в дальнейшем будем считать, что все параметры рассматриваемой задачи, числа c1, …, cn; a1, …, an; b – неотрицательные целые числа. Множество допустимых решений этой задачи Vb – это множество булевых векторов, удовлетворяющих неравенству (2).

Объем Vb – это число |Vb| допустимых решений задачи (1), (2). По аналогии с непрерывным случаем будем называть множество Vb многогранником допустимых решений задачи.

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

Ряд результатов и примеров приведены в [1], [2]. Базовой основой техники доказательства служит метод производящих функций. Подробное его описание можно найти, например, в [3]. В обзорной книге [4], целиком посвященной задаче о рюкзаке, приведено множество результатов, характеризующих состояние дел в области исследования алгоритмов ее решения и различных свойств самой задачи. Основное внимание подавляющего большинства исследователей привлекают алгоритмические аспекты задачи, в частности, вероятностные характеристики в оценках их качества (см., например, [5]). Везде параметр ρ удовлетворяет условиям: 0 < ρ < 1.

2. ВСПОМОГАТЕЛЬНЫЕ УТВЕРЖДЕНИЯ

Сначала приведем несколько известных базовых результатов. Они будут либо прямо использованы нами, либо необходимы для понимания проблематики. Удобным “инструментом” анализа распределения точек многогранника задачи является полином

(2.1)
${{P}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \sum\limits_{x \in {{V}_{b}}} {z_{1}^{{{{a}_{1}}{{x}_{1}}}}z_{2}^{{{{a}_{2}}{{x}_{2}}}}} \ldots .z_{n}^{{{{a}_{n}}{{x}_{n}}}}.$
Следующий полином используется для исследования значений функционала задачи:
(2.2)
${{F}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \sum\limits_{x \in {{V}_{b}}} {z_{1}^{{{{c}_{1}}{{x}_{1}}}}} z_{2}^{{{{c}_{2}}{{x}_{2}}}} \ldots .z_{n}^{{{{c}_{n}}{{x}_{n}}}}.$
Примеры и иллюстрации использования этих полиномов в различных типах задачи о ранце даны в [1], [2].

Лемма 1. Справедлива формула

(2.3)
$\sum\limits_{b = 0}^\infty {{{P}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}})} {{u}^{b}} = \frac{{(1 + {{{({{z}_{1}}u)}}^{{{{a}_{1}}}}}) \ldots (1 + {{{({{z}_{n}}u)}}^{{{{a}_{n}}}}})}}{{1 - u}}.$

Доказательство. Преобразуем сумму (2.1), используя метод коэффициентов (в первом равенстве цепочки нижеприведенных выкладок учтено соотношение (1.2)):

(2.4)
$\begin{gathered} {{P}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \sum\limits_{t = 0}^b {\sum\limits_{\{ {{x}_{1}},. \ldots {{x}_{n}}\} }^{} {z_{1}^{{{{a}_{1}}{{x}_{1}}}}} z_{2}^{{{{a}_{2}}{{x}_{2}}}} \ldots z_{n}^{{{{a}_{n}}{{x}_{n}}}}} \mathop {\operatorname{Coef} }\limits_u \left\{ {\frac{{{{u}^{{\sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}}} }}}}}{{{{u}^{{t + 1}}}}}} \right\} = \mathop {{\text{Coef}}}\limits_u \left\{ {\sum\limits_{t = 0}^b {\frac{1}{{{{u}^{{t + 1}}}}}} \sum\limits_{{{x}_{1}} = 0}^1 {{{{({{z}_{1}}u)}}^{{{{a}_{1}}{{x}_{1}}}}} \ldots \sum\limits_{{{x}_{n}} = 0}^1 {{{{({{z}_{n}}u)}}^{{{{a}_{n}}{{x}_{n}}}}}} } } \right\} = \\ = \;\mathop {{\text{Coef}}}\limits_u \left\{ {\frac{{\frac{1}{u} - \frac{1}{{{{u}^{{b + 2}}}}}}}{{1 - \frac{1}{u}}}\prod\limits_{k = 1}^n {(1 + {{{({{z}_{k}}u)}}^{{{{a}_{k}}}}})} } \right\} = \mathop {{\text{Coef}}}\limits_u \left\{ {\frac{1}{{{{u}^{{b + 1}}}(1 - u)}}\prod\limits_{k = 1}^n {(1 + {{{({{z}_{k}}u)}}^{{{{a}_{k}}}}})} } \right\}. \\ \end{gathered} $
Сравнивая (2.3) и (2.4) получаем, что (2.3) просто “содержится” в (2.4). Лемма доказана.

Следствие. Для объема области допустимых решений имеет место равенство

(2.5)
${\text{|}}{{V}_{b}}{\text{|}} = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{(1 + {{u}^{{{{a}_{1}}}}}) \ldots (1 + {{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}}}du} .$
Сам смысл метода коэффициентов – это выражение коэффициента при минус первой степени переменной (оно представлено формулой (2.4)) через сумму вычетов – формула (2.5). Именно это и приведено в качестве следствия из леммы.

Лемма 2. Имеет место равенство

(2.6)
${{F}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{(1 + z_{1}^{{{{c}_{1}}}}{{u}^{{{{a}_{1}}}}}) \ldots (1 + z_{n}^{{{{c}_{n}}}}{{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}}}du} .$

Доказательство. Преобразуем сумму (2.2), используя метод коэффициентов (в первом равенстве цепочки нижеприведенных выкладок учтено соотношение $f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\nolimits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $):

$\begin{gathered} {{F}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \sum\limits_{t = 0}^b {\sum\limits_{\{ {{x}_{1}},...,{{x}_{n}}\} }^{} {z_{1}^{{{{c}_{1}}{{x}_{1}}}}} z_{2}^{{{{c}_{2}}{{x}_{2}}}} \ldots z_{n}^{{{{c}_{n}}{{x}_{n}}}}} \mathop {{\text{Coef}}}\limits_u \left\{ {\frac{{{{u}^{{\sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}}} }}}}}{{{{u}^{{t + 1}}}}}} \right\} = \\ = \mathop {{\text{Coef}}}\limits_u \left\{ {\frac{{\frac{1}{u} - \frac{1}{{{{u}^{{b + 2}}}}}}}{{1 - \frac{1}{u}}}\prod\limits_{k = 1}^n {(1 + z_{k}^{{{{c}_{k}}}}{{u}^{{{{a}_{k}}}}})} } \right\}\mathop {{\text{ = }}\;{\text{Coef}}}\limits_u \left\{ {\frac{1}{{{{u}^{{b + 1}}}(1 - u)}}\prod\limits_{k = 1}^n {(1 + z_{k}^{{{{c}_{k}}}}{{u}^{{{{a}_{k}}}}})} } \right\}. \\ \end{gathered} $
Вновь напомним, что метод коэффициентов – это выражение коэффициента при минус первой степени переменной (оно представлено последней формулой приведенной выше цепочки выкладок) через сумму вычетов. А это и есть формула (2.6). Лемма доказана.

Иллюстрации этих утверждений и их применение будут описаны в дальнейших примерах и построениях.

Замечание. Если теперь рассмотреть случай, когда переменные в задаче – натуральные числа, то формулы (2.2), (2.3) и (2.6) приобретают вид

$\sum\limits_{b = 0}^\infty {{{P}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}})} {{u}^{b}} = \frac{1}{{(1 - u)(1 - {{u}^{{{{z}_{1}}{{a}_{1}}}}}) \ldots (1 - {{u}^{{{{z}_{n}}{{a}_{n}}}}})}},$
${\text{|}}{{V}_{b}}{\text{|}} = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{du}}{{(1 - {{u}^{{{{a}_{1}}}}}) \ldots (1 - {{u}^{{{{a}_{n}}}}})(1 - u){{u}^{{b + 1}}}}}} ,$
${{F}_{b}}({{z}_{1}}, \ldots ,{{z}_{n}}) = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{du}}{{(1 - z_{1}^{{{{c}_{1}}}}{{u}^{{{{a}_{1}}}}}) \ldots (1 - z_{n}^{{{{c}_{n}}}}{{u}^{{{{a}_{n}}}}})(1 - u){{u}^{{b + 1}}}}}} {\kern 1pt} .$

3. ВЕЛИЧИНА ФУНКЦИОНАЛА В ЗАДАЧЕ О РАНЦЕ

Рассмотрим производящую функцию (2.2), которая характеризует распределение значений функционала

$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
рассматриваемой оптимизационной задачи. Пусть Ak – это число допустимых решений задачи, в которых значение целевой функции
$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
равно k. Очевидно, что k ограничено. Введем обозначение
(3.1)
${{\Phi }_{b}}(z) = {{F}_{b}}(z, \ldots ,z) = \sum\limits_{x \in {{V}_{b}}}^{} {z_{{}}^{{{{c}_{1}}{{x}_{1}}}}} z_{{}}^{{{{c}_{2}}{{x}_{2}}}} \ldots z_{{}}^{{{{c}_{n}}{{x}_{n}}}} = \sum\limits_{k = 0}^\infty {{{A}_{k}}} {{z}^{k}}.$
Теперь из введенных определений, обозначений и формулы (3.1) получаем соотношение:
${\text{|}}{{V}_{b}}{\text{|}} = {{Ф }_{b}}(1) = {{F}_{b}}(1, \ldots ,1) = \sum\limits_{x \in {{V}_{b}}}^{} {z_{{}}^{{{{c}_{1}}{{x}_{1}}}}} z_{{}}^{{{{c}_{2}}{{x}_{2}}}} \ldots z_{{}}^{{{{c}_{n}}{{x}_{n}}}} = \sum\limits_{k = 0}^\infty {{{A}_{k}}} .$
В частности, заметим, что
$\mathop {\max }\limits_{x \in {{V}_{b}}} f({{x}_{1}}, \ldots ,{{x}_{n}}) = \mathop {\max }\limits_{x \in {{V}_{b}}} \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} = \mathop {\max }\limits_{k:{{A}_{k}} \geqslant 1} {{A}_{k}}.$
Из леммы 2 получаем формулу
${{\Phi }_{b}}(z) = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{(1 + z_{{}}^{{{{c}_{1}}}}{{u}^{{{{a}_{1}}}}}) \ldots (1 + z_{{}}^{{{{c}_{n}}}}{{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}}}du} .$
Будем считать, что все точки многогранника ${{V}_{b}}$ равновероятны, тогда значения
$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
есть случайная величина ξ = ξ(a1, …, an, c1, … cn, b) с производящей функцией
$P(z) = \frac{{{{\Phi }_{b}}(z)}}{{{{\Phi }_{b}}(1)}}.$
Обозначим ее математическое ожидание через μ(ξ).

Для нахождения ее первого момента (математического ожидания) вычислим первую производную P(z) в точке z = 1.

Пусть

$\varphi (z,u) = \prod\limits_{k = 1}^n {(1 + z_{{}}^{{{{c}_{k}}}}{{u}^{{{{a}_{k}}}}})} .$
Тогда имеем
$\frac{{\varphi {\kern 1pt} '(z,u)}}{{\varphi (z,u)}} = \sum\limits_{k = 1}^n {\frac{{{{c}_{k}}{{u}^{{{{a}_{k}}}}}{{z}^{{{{c}_{k}} - 1}}}}}{{1 + {{u}^{{{{a}_{k}}}}}{{z}^{{{{c}_{k}}}}}}}} .$
Отсюда получаем
$\Phi _{b}^{'}(z) = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\sum\limits_{k = 1}^n {\left( {{{c}_{k}}\frac{{_{{}}{{u}^{{{{a}_{k}}}}}{{z}^{{{{c}_{k}} - 1}}}}}{{1 + {{u}^{{{{a}_{k}}}}}{{z}^{{{{c}_{k}}}}}}}\frac{{\varphi (z,u)}}{{(1 - u){{u}^{{b + 1}}}}}} \right)} {\kern 1pt} du} = \sum\limits_{k = 1}^n {{{c}_{k}}{{z}^{{{{c}_{k}} - 1}}}} \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\left( {\frac{{{{u}^{{{{a}_{k}}}}}}}{{1 + {{u}^{{{{a}_{k}}}}}{{z}^{{{{c}_{k}}}}}}}\frac{{\varphi (z,u)}}{{(1 - u){{u}^{{b + 1}}}}}} \right)} {\kern 1pt} du.$
Подставляем z = 1 и в результате получим
$\Phi {\kern 1pt} '(1) = \sum\limits_{k = 1}^n {{{c}_{k}}\frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{{{u}^{{{{a}_{k}}}}}(1 + {{u}^{{{{a}_{1}}}}}) \ldots (1 + {{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}(1 + {{u}^{{{{a}_{k}}}}})}}du} } .$
Рассмотрим теперь n проекций Vb – множества допустимых решений задачи. Они строятся следующим образом. Проекция с номером k = 1, …, n удовлетворяет условию:
$\sum\limits_{i = 1,i \ne k}^n {{{a}_{i}}{{x}_{i}} \leqslant b} ,\quad x \in {{B}^{{n - 1}}}.$
Обозначим это подмножество через $V_{b}^{k}$, т.е. это множество решений задачи на единицу меньшей размерности, которая получается из исходного при отбрасывании k-го слагаемого в ограничении.

Теорема 1. Справедливо соотношение

(3.2)
$\mu (\xi ) = \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{{\text{|}}V_{b}^{k}{\text{|}}}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} {\kern 1pt} .$

Доказательство. Из (3.1) получаем

$\begin{gathered} \Phi _{b}^{'}(1) = \sum\limits_{k = 1}^n {{{c}_{k}}\frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{{{u}^{{{{a}_{k}}}}}(1 + {{u}^{{{{a}_{1}}}}}) \ldots (1 + {{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}(1 + {{u}^{{{{a}_{k}}}}})}}du} } = \\ = \sum\limits_{k = 1}^n {{{c}_{k}}\left[ {\frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{\prod\limits_{i = 1}^n {(1 + {{u}^{{{{a}_{i}}}}})} }}{{(1 - u){{u}^{{b + 1}}}}}du} - \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{\prod\limits_{i = 1}^n {(1 + {{u}^{{{{a}_{i}}}}})} }}{{(1 - u){{u}^{{b + 1}}}(1 + {{u}^{{{{a}_{k}}}}})}}du} } \right]} {\kern 1pt} . \\ \end{gathered} $
Заметим, что суммирование идет по k, а b в данном случае – параметр. Применим теперь формулу (2.5) и вынесем ${\text{|}}{{V}_{b}}{\text{|}}$ из под интеграла и суммирования в первом слагаемом. Кроме того, заметим, что из той же леммы 1 (формулы (2.5)) следует, что
$V_{b}^{k} = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{(1 + {{u}^{{{{a}_{1}}}}}) \ldots (1 + {{u}^{{{{a}_{{k - 1}}}}}})(1 + {{u}^{{{{a}_{{k + 1}}}}}}) \ldots (1 + {{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}}}du} .$
Получим соотношение
(3.3)
$\Phi _{b}^{'}(1) = \left| {{{V}_{b}}} \right|\sum\limits_{k = 1}^n {{{c}_{k}} - \sum\limits_{k = 1}^n {{{c}_{k}}} \left| {V_{b}^{k}} \right|} .$
Далее заметим, что P(z) = Фb(z)/Фb(1), а $\mu (\xi ) = P{\kern 1pt} '(1)$. С учетом (3.3) и того, что
${\text{|}}{{V}_{b}}{\text{|}} = \frac{1}{{2\pi i}}\oint\limits_{|u| = \rho } {\frac{{(1 + {{u}^{{{{a}_{1}}}}})...(1 + {{u}^{{{{a}_{n}}}}})}}{{(1 - u){{u}^{{b + 1}}}}}du} ,$
получаем искомое соотношение
$\mu (\xi ) = \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{\left| {V_{b}^{k}} \right|}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} .$
Теорема доказана.

Эта формула может применяться для оценок эффективности алгоритмов решения задачи (1.1).

Проиллюстрируем ее на простых примерах.

Пример 1. Рассмотрим следующую задачу о ранце:

$\begin{array}{*{20}{c}} {{{х }_{1}} + 2{{х }_{2}} + 3{{х }_{3}} \to \max ,} \\ {{{х }_{1}} + 2{{х }_{2}} + {{х }_{3}} \leqslant 3,} \\ {{{х }_{1}},{{х }_{2}},{{х }_{3}} \in \left\{ {0,1} \right\}.} \end{array}$
У этой задачи 7 допустимых решений (все точки B3, кроме (111)). А теперь подсчитаем $V_{b}^{k}$ для k = = 1, 2, 3.

Они все равны 4: число решений неравенств

$2{{х }_{2}} + {{х }_{3}} \leqslant 3,\quad {{х }_{1}} + {{х }_{3}} \leqslant 3,\quad {{х }_{2}} + {{х }_{3}} \leqslant 3.$
Подставляем в (3.2) и получаем

$\mu (\xi ) = \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{\left| {V_{b}^{k}} \right|}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} = \frac{1}{7}(0 + 1 + 2 + 3 + 4 + 5) = 18{\text{/}}7.$

Пример 2. Рассмотрим теперь следующую задачу о ранце:

$\begin{array}{*{20}{c}} {{{х }_{1}} + 2{{х }_{2}} + 4{{х }_{3}} + 8{{x}_{4}} \to \max ,} \\ {{{х }_{1}} + 2{{х }_{2}} + 4{{х }_{3}} + 8{{x}_{4}} \leqslant 6,} \\ {{{х }_{1}},{{х }_{2}},{{х }_{3}},{{х }_{4}} \in \left\{ {0,1} \right\}.} \end{array}$
У этой задачи тоже 7 допустимых решений (точки B4: (0000), (1000), (0100), (0010), (1100), (1010), (0110)). А теперь подсчитаем $V_{b}^{k}$ для k = 1, 2, 3, 4.

Они равны: 4, 4, 4, 7: число решений неравенств $2{{х }_{2}} + 4{{х }_{3}} + 8{{x}_{4}} \leqslant 6$, ${{х }_{1}} + 4{{х }_{3}} + 8{{x}_{4}} \leqslant 6$, ${{x}_{1}} + 2{{х }_{2}} + 8{{x}_{4}} \leqslant 6$, ${{x}_{1}} + 2{{х }_{2}} + 4{{х }_{3}} \leqslant 6$.

Подставляем в (3.2) и получаем $\mu (\xi ) = \frac{1}{7}(0 + 1 + 2 + 4 + 3 + 5 + 6)$ = 21/7 = 3.

Далее из нашей формулы имеем

$\sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{\left| {V_{b}^{k}} \right|}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} = (1 - 4{\text{/}}7)({{c}_{1}} + {{c}_{2}} + {{c}_{3}}) + {{c}_{4}}(1 - 7{\text{/}}7) = 3.$
Теперь используем эту информацию для решения нашей задачи. Очевидно, что x4= 0, а две единицы в допустимом решении есть. Получаем

$\mathop {\max }\limits_{x \in {{V}_{b}}} f({{x}_{1}}, \ldots ,{{x}_{n}}) = \mathop {\max }\limits_{x \in {{V}_{b}}} \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} = 6.$

Пример 3. Пусть ai = 2i – 1 для всех i = 1, 2, …, n, а $b = {{2}_{n}}$, тогда решения неравенства

$\sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}} \leqslant b} ,\quad x \in {{B}^{n}},$
есть все элементы B n. Для любого k ищем решения неравенства
$\sum\limits_{i = 1,i \ne k}^n {{{a}_{i}}{{x}_{i}} \leqslant b} ,\quad x \in {{B}^{{n - 1}}}.$
А это все элементы B n – 1. Поэтому ${\text{|}}{{V}_{b}}{\text{|}} = 2{}^{n},\;\left| {V_{b}^{k}} \right| = {{2}^{{n - 1}}}$. Отсюда среднее значение
$\mu (\xi ) = \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{1}{2}} \right)} = \frac{1}{2}\sum\limits_{k = 1}^n {{{c}_{k}}} ,$
а максимальное значение функционала равно $\sum\nolimits_{k = 1}^n {{{c}_{k}}} $.

4. ОДИН ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ

Этот случай состоит в том, что коэффициенты целевой функции и вектора ограничений совпадают, т.е. ai = ci, i = 1, …, n. Заметим, что при

$\sum\limits_{j = 1}^n {{{с }_{j}}} \leqslant b$
справедливо равенство
$\mathop {\max }\limits_{x \in {{V}_{b}}} \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} = \sum\limits_{j = 1}^n {{{с }_{j}}} .$
Положим
${{f}_{k}}({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} - {{с }_{k}}{{x}_{k}}.$
И пусть
$\bar {f} = \frac{1}{n}\sum\limits_{k = 1}^n {{{f}_{k}}({{x}_{1}}} , \ldots ,{{x}_{n}}).$
Тогда справедливы соотношения
$\sum\limits_{j = 1}^n {{{f}_{k}}({{x}_{1}}, \ldots ,{{x}_{n}})} = nf({{x}_{1}}, \ldots ,{{x}_{n}}) - f({{x}_{1}}, \ldots ,{{x}_{n}})\quad {\text{и }}\quad \bar {f} = \left( {1 - \frac{1}{n}} \right)f({{x}_{1}}, \ldots ,{{x}_{n}}).$
В [6] дано определение “непрерывной” функции, принимающей дискретные значения. (Напомним, что все параметры рассматриваемой задачи – неотрицательные целые числа.)

Определение. Функция

$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
называется непрерывной на множестве $M \subseteq {{B}^{n}}$, если она принимает на М все значения из интервала [fmin, fmax], где  fmin,  fmax – минимальное и максимальное значения функции на $M \subseteq {{B}^{n}}$.

Примерами непрерывных функций на всем${{B}^{n}}$ являются следующие:

1) $f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{2}^{{j - 1}}}{{x}_{j}}} ;$

2) $f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {j{{x}_{j}}} ;$

3) $2{{x}_{1}} + 3{{х }_{2}} + 4{{х }_{3}} + 6{{x}_{4}}.$

А функция $2{{x}_{1}} + 3{{х }_{2}} + 4{{х }_{3}}$ не является непрерывной, так как не принимает значение 8.

Теорема 2. Если

$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
есть непрерывная функция на ${{V}_{b}}$, то

${{2}^{n}} - 1 \geqslant \max f({{x}_{1}}, \ldots ,{{x}_{n}}) \geqslant \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{\left| {V_{b}^{k}} \right|}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} .$

Доказательство. Действительно, пусть

$\{ {{c}_{1}},{{c}_{2}}, \ldots ,{{c}_{n}}\} = C,\quad {{c}_{1}} \leqslant {{c}_{2}} \leqslant ... \leqslant {{c}_{n}} = N,$
и S(N, n) – число различных сумм из элементов С. Наименьшее значение
$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
равно 0. Очевидно, что
$S(N,n) \leqslant {{2}^{n}} - 1.$
Поэтому максимальное значение не превосходит ${{2}^{n}} - 1$. Кроме того, из теоремы 1 имеем неравенство
$\max f({{x}_{1}}, \ldots ,{{x}_{n}}) \geqslant \sum\limits_{k = 1}^n {{{c}_{k}}\left( {1 - \frac{{\left| {V_{b}^{k}} \right|}}{{{\text{|}}{{V}_{b}}{\text{|}}}}} \right)} {\kern 1pt} .$
Теорема доказана.

При $\sum\nolimits_{j = 1}^n {{{с }_{j}}} \leqslant b$ эта верхняя оценка достижима. Если ci= 2i – 1, i = 1, …, n, то

$S(N,n) = {{2}^{n}} - 1$
и
$f({{x}_{1}}, \ldots ,{{x}_{n}}) = \sum\limits_{j = 1}^n {{{с }_{j}}{{x}_{j}}} $
есть непрерывная функция с максимальным значением ${{2}^{n}} - 1$.

5. ЗАДАЧА О РАНЦЕ И ПОРОГОВЫЕ ФУНКЦИИ

С задачей (1) можно связать следующую пороговую функцию:

$g({{x}_{1}}, \ldots ,{{x}_{n}}) = \left\{ \begin{gathered} 1,\quad {\text{е с л и }}\quad \sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}} \leqslant b,} \hfill \\ 0,\quad {\text{е с л и }}\quad \sum\limits_{i = 1}^n {{{a}_{i}}{{x}_{i}} > b.} \hfill \\ \end{gathered} \right.$
Функцию g(x), x = (x1, …, xn), можно представить в виде (здесь сложение – это сложение по mod2)
$g(x) = \sum\limits_{w \in {{B}^{n}}} {{{c}_{w}}{{x}^{w}}} ,$
где
(5.1)
${{с }_{w}} \in B,\quad w = ({{w}_{1}}, \ldots ,{{w}_{n}}) \in {{B}^{n}},\quad {{x}^{w}} = x_{1}^{{{{w}_{1}}}}, \ldots ,x_{n}^{{{{w}_{n}}}},\quad x_{k}^{{{{w}_{k}}}} = \left\{ \begin{gathered} {{x}_{k}},\quad {\text{е с л и }}\quad {{w}_{k}} = 1, \hfill \\ 1,\quad {\text{е с л и }}\quad {{w}_{k}} = 0. \hfill \\ \end{gathered} \right.$
Это представление называется булевым полиномом, полиномом Жегалкина, алгебраической нормальной формой (АНФ).

Рассмотрим классический частичный порядок на векторах булевого куба:

$x = ({{x}_{1}}, \ldots ,{{x}_{n}}) \leqslant y = ({{y}_{1}}, \ldots ,{{y}_{n}}) \Leftrightarrow {{x}_{i}} \leqslant {{y}_{i}},\quad i = 1, \ldots ,n.$
Пороговая функция g(x) антимонотонна. Из того, что ui ≤ ${{v}_{i}}$, i = 1, …, n, очевидным образом следует, что
$\sum\limits_{i = 1}^n {{{a}_{i}}{{u}_{i}} \leqslant \sum\limits_{i = 1}^n {{{a}_{i}}{{v}_{i}}.} } $
Поэтому из того, что $g({{u}_{1}}, \ldots ,{{u}_{n}}) = 1$ следует, что $g({{v}_{1}}, \ldots ,{{v}_{n}}) = 1.$

Определение. Две задачи о ранце называются эквивалентными, если они определяются одной и той же пороговой функцией и множества их экстремумов совпадают. Пусть задано n натуральных чисел A = {a1, …, an} и

${{\sigma }_{A}} = \sum\limits_{i = 1}^n {{{a}_{i}}} .$

Определение. Решение $u = ({{u}_{1}}, \ldots ,{{u}_{n}})$ называется отсекающим, если никакая точка $v = ({{v}_{1}}, \ldots ,{{v}_{n}}),\;u < v,$ решением задачи (1.1) не является.

Если y – некоторое отсекающее решение, то обозначим через M(y) множество точек $v = ({{v}_{1}}, \ldots ,{{v}_{n}}),\;v < y$.

Справедлива

Теорема 3. Пусть Y = {y1, …, ym} – все отсекающие решения задачи (1), тогда множество допустимых решений этой задачи равно

${{V}_{b}} = \bigcup\limits_{i = 1}^m {M({{y}_{i}})} .$

Доказательство. Пусть

$A{\kern 1pt} ' = \{ {{a}_{1}}, \ldots ,{{a}_{n}},{{a}_{n}}_{{ + 1}} = r\} ,\quad \sigma _{A}^{'} = \sum\limits_{i = 1}^{n + 1} {{{a}_{i}}} .$
Тогда минимум и максимум функции
$f({{x}_{1}}, \ldots ,{{x}_{{n + 1}}}) = \sum\limits_{i = 1}^{n + 1} {{{a}_{i}}{{x}_{i}}} $
равны соответственно 0 и
$\sigma _{A}^{'} = \sum\limits_{i = 1}^{n + 1} {{{a}_{i}}} .$
Если
$y \leqslant {{\sigma }_{A}} = \sum\limits_{i = 1}^n {{{a}_{i}}} ,$
то существует такое подмножество A, что y равно сумме чисел этого подмножества. Если же ${{\sigma }_{A}} < y < \sigma _{A}^{'}$, то существует такое число m < ${{\sigma }_{A}}$, что y = r + m . Но это значит, что для числа m существует такое подмножество A(m), что m равно сумме чисел этого подмножества $\sigma (m)$, а an + 1= r, тогда y = $\sigma (m)$+ an + 1.

Теорема доказана.

Пример 3. Пусть A = {a1, a2, a3} = {3, 2, 3}, b = 4. Тогда множество допустимых решений задачи (1) состоит из шести точек: (000), (001), (010), (100), (110), (011). Коэффициенты в (5.1) все равны нулю, кроме четырех ${{с }_{{000}}} = {{с }_{{110}}} = {{с }_{{011}}} = {{с }_{{101}}} = 1$. Поэтому g(x1, x2, x3) = 1 + x1x3 + x2x3 + x1x2. Множество отсекающих решений состоит из трех точек: y1 = (100), y2 = (010), y3 = (001). Тогда

${{V}_{b}} = \bigcup\limits_{i = 1}^3 {M({{y}_{i}})} = \{ {{y}_{1}},(000),{{y}_{2}},(000),{{y}_{3}},(000)\} = \{ {{y}_{1}},(000),{{y}_{2}},{{y}_{3}}\} .$

Список литературы

  1. Леонтьев В.К. Производящие функции в задаче о ранце // Материалы XI Международного семинара “Дискретная математика и ее приложения”. М.: МГУ, 2012. С. 255–257.

  2. Леонтьев В.К. Комбинаторика и информация. Ч. 1. Комбинаторный анализ. М.: МФТИ, 2015. 174 с.

  3. Егорычев Г.П. Интегральное представление и вычисление комбинаторных сумм. Новосибирск: Наука, 1977. 285 с.

  4. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin: Springer, 2004. 548 p.

  5. Дюбин Г.Н., Корбут А.А., Поведение в среднем жадных алгоритмов для минимизационной задачи о ранце – общие распределения коэффициентов // Ж. вычисл. матем. и матем. физ. 2008. Т. 48. № 9. С. 1556–1570.

  6. Леонтьев В.К. О псевдобулевых полиномах // Ж. вычисл. матем. и матем. физ. 2015. Т. 55. № 11. С. 1952–1958.

  7. Гордеев Э.Н., Леонтьев В.К. Производящие функции в задаче о ранце // Докл. АН. 2018. Т. 481. № 5. С. 478–480.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Журнал вычислительной математики и математической физики

Архивы выпусков Информация о журнале Отправить рукопись в журнал