Шейнцвит Р. П.

Ветви и границыШейнцвит Р. П. Ветви и границы // Квант. — 1972. — № 7. — С. 2⁠—⁠5.‍‍

Рассмотрим задачу:

На складе имеются предметы (каждый — по одному), вес и стоимость которых указаны в таблице. $$ \def\c#1{\colsep{0pt}{\begin{array}{c}#1\end{array}}} \def\v#1{\hphantom{50}\mathllap{#1}} \def\s#1{\hphantom{670}\mathllap{#1}} \begin{array}{c|c|c}\hline\\[-6pt] \c{\text{Порядковый}\\\text{номер}}&\c{\text{Вес в цент-}\\\text{нерах}}&\c{\text{Стоимость}\\\text{(в рублях)}}\\\\[-6pt]\hline\\[-6pt] 1&\v{11}&\s{120}\\ 2&\v{7}&\s{140}\\ 3&\v{6}&\s{60}\\ 4&\v{5}&\s{80}\\ 5&\v{12}&\s{160}\\ 6&\v{9}&\s{110}\\[6pt]\hline\\[-6pt] \text{Всего}&\v{50}&\s{670}\\[6pt] \end{array} $$ Грузоподъёмность автомашины — $3200$‍‍ кг. Требуется так загрузить автомашину, чтобы общая стоимость взятых предметов была как можно большей.

Очевидно, выгоднее брать предметы, имеющие при малом весе большую стоимость.

Введём понятие удельной стоимости предмета $d_i$‍,‍ т. е. стоимости одного центнера $i$‍‍-го предмета в рублях: $d_1=10{,}9$‍;‍ $d_2=20$‍;‍ $d_3=10$‍;‍ $d_4=16$‍;‍ $d_5=13{,}3$‍;‍ $d_6=12{,}2$‍.‍

Если загрузить автомашину предметами с наибольшей удельной стоимостью — вторым, четвёртым, пятым и шестым, — то сумма их весов окажется больше грузоподъёмности автомашины ($7+15+12+9\gt32$‍).‍

Если же взять только 2-й, 4-й и 5-й предметы, то машина окажется недогруженной на 8 ц. Можно тогда погрузить ещё только один 3-й предмет, причём суммарная стоимость получится равной 440 руб., а машина будет недогружена на 2 ц. Можем ли мы быть уверены, что не существует лучшего способа загрузки машины?

Может быть, выгоднее оставить какой-либо из предметов с большей удельной стоимостью, но зато увеличить общую стоимость путём полного использования грузоподъёмности машины?

Как видим, «в лоб» задачу решить трудно. А в реальных условиях, когда речь зачастую идёт не о шести, а о шестидесяти предметах, и браться за неё нельзя, не вооружившись математическими методами. Переведём задачу на язык математики (как говорят, математизируем ситуацию). Пусть $x_i=1$‍,‍ если $i$‍‍-й предмет погружается на автомашину, и $x_i=0$‍‍ в противном случае ($i=1$‍,‍ $\ldots$‍,‍ 6). Тогда общая стоимость погруженных предметов в рублях равна $120x_1+140x_2+60x_3+80x_4+160x_5+110x_6$‍,‍ а их общий вес в центнерах равен $11x_1+7x_2+6x_3+5x_4+12x_5+9x_6$‍.‍

Итак, отвлекаясь от «жизненной» ситуации, мы получаем чисто математическую задачу: найти значения переменных $x_1$‍‍ $\ldots$‍,‍ $x_6$‍,‍ (каждое из которых может быть равно 0 или 1), при которых функция $$ f(x_1,{\ldots},x_6)=120x_1+140x_2+60x_3+80x_4+160x_5+110x_6 $$ достигает максимума, если выполнено условие (ограничение) $$ 11x_1+7x_2+6x_3+5x_4+12x_5+9x_6\le32.\tag1 $$ Функцию $f$‍‍ называют целевой функцией задачи; она определена на множестве всех упорядоченных шестёрок из нулей и единиц (шестимерных векторов, каждая компонента которых равна 0 или 1).

Всего, очевидно, имеется $2^6=64$‍‍ таких векторов, причём каждый из них даёт некоторый способ загрузки автомашины. Но не каждый из этих 64 способов загрузки допустим: вектор $(1,0,1,0,1,1)$‍‍ соответствует погрузке на машину 1-го, 3-го, 5-го и 6-го предметов, однако их общий вес (38 ц) превышает допустимый.

Естественно назвать вектор допустимым, если для него выполняется условие (1). Итак, решением задачи является допустимый вектор, максимизирующий целевую функцию $f$‍.‍

Теперь допустим, что 1-й предмет, погружен на автомашину. Тогда $x_1=1$‍,‍ и мы получаем новую задачу:

Найти значения переменных $x_2$‍,‍ $\ldots$‍,‍ $x_6$‍‍‍, при которых достигает максимума функция $$ f_2(x_2,x_3,{\ldots},x_6)=140x_2+60x_3+80x_4+160x_5+110x_6 $$ при условии $$ 7x_2+6x_3+5x_4+12x_5+9x_6\le21. $$

Если же 1-й предмет не погружен, то $x_1=0$‍,‍ и мы получаем такую задачу:

Найти значения переменных $x_2$‍,‍ $\ldots$‍,‍ $x_6$‍‍ максимизирующих функцию $$ f_2(x_2,x_3,{\ldots},x_6)=140x_2+60x_3+80x_4+160x_5+110x_6 $$ при условии $$ 7x_2+6x_3+5x_4+12x_5+9x_6\le32. $$

Таким образом, одну задачу с 6 переменными можно свести к двум задачам с 5 переменными; те в свою очередь сводятся к четырём задачам с 4 переменными и т. д., так что в конце концов мы получаем 64 задачи с одной переменной каждая. Но уж если надо решать такую систему, то проще непосредственно проверить условие (1) для каждого из 64 возможных векторов, для допустимых из них вычислить значение целевой функции и выбрать тот вектор, для которого значение максимально, т. е., как говорят, решить задачу «полным перебором».

А как же быть в тех случаях, когда число предметов (компонент векторов) велико? Ведь уже при 20 предметах число возможных вариантов превышает миллион! Ясно, что метод полного перебора в задачах такого рода в большинстве случаев непригоден.

Мы расскажем сейчас об одном методе, позволяющем, как правило, значительно уменьшить число сравниваемых вариантов, необходимое для получения решения. Метод этот, известный под названием «метод ветвей и границ», мы опишем в процессе его применения к нашей задаче.

Процесс отбора предметов для погрузки на автомашину можно изобразить в виде графа‍. Начальный узел 0 соответствует множеству $P$‍‍ всех 64 6-мерных векторов. От узла 0 начинается ветвление к узлам 1 и 2 (рис. 1). Узел 1 находится правее и ниже узла 0. Он соответствует таким способам погрузки, при которых 1-й предмет обязательно погружается на автомашину. Очевидно, узел 1 соответствует подмножеству $P_1$‍‍ таких 32 векторов из $P$‍,‍ у которых $x_1=1$‍.‍ Узел 2 находится левее и ниже узла 0 и соответствует подмножеству $P_2$‍‍ таких 32 векторов из $P$‍,‍ у которых $x_1=0$‍.‍ Дальнейшее построение графа ясно. На рисунке 1 показан граф после двух шагов ветвления.

Каждый узел графа соответствует подмножеству векторов из $P$‍,‍ у которых некоторые из компонент уже зафиксированы. Если построение множеств $P_1$‍‍ и $P_2$‍‍ рассматривать как первый шаг ветвления (первый уровень графа), то на $k$‍‍-м шаге ($k$‍‍-й уровень графа) мы получим $2^k$‍‍ узлов, каждый из которых соответствует множеству $2^{6-k}$‍‍ векторов (вариантов загрузки автомашины). Узлы, полученные на шестом шаге ветвления, представляют по одному вектору каждый, так что среди этих узлов находится решение задачи. Итак, если провести ветвление полностью, то придётся построить граф с числом узлов $1+2+4+\ldots+64=127$‍.‍

Но мы постараемся действовать таким образом, чтобы попутно обнаруживать «бесперспективные» узлы, из которых не могут выходить ветви, ведущие к решению. Чем раньше (выше) «отсечь» эти ветви, тем меньший перебор придётся нам делать потом. С этой целью сопоставим каждому узлу два числа (которые будем записывать под узлом). Верхнее из них показывает наибольшую возможную суммарную стоимость (границу стоимости) взятых предметов при любом способе погрузки, описываемом векторами данного узла. Нижнее число показывает, какой общий вес отбираемых предметов допустим на данном шаге (это число равно разности между грузоподъёмностью автомашины и весом всех уже погруженных предметов). Для примера найдём верхнее и нижнее числа для 1-го узла. Поскольку во всех соответствующих ему вариантах погрузки 1-й предмет обязательно берётся, нижнее число на этом шаге равно $32-11=21$‍.‍ Граница стоимости (верхнее число) равна сумме стоимостей всех предметов, так как мы ещё не исключили возможности выбора ни одного из них. Поэтому верхнее число 1-го узла равно 670. Для второго узла верхнее число равно 550 ($670-120$‍),‍ так как первый предмет не берётся; нижнее же число равно здесь 32.

Пусть $P_i$‍‍ — вес $i$‍‍-го предмета, $C_i$‍‍ — его стоимость. Очевидно, что при переходе от любого узла, находящегося на $i$‍‍-м уровне графа, направо вниз верхнее число не меняется, а нижнее уменьшается на $P_{i+1}$‍,‍ при переходе же от этого узла налево вниз нижнее число не меняется, а верхнее уменьшается на $C_{i+1}$‍.‍ Будем на каждом этапе ветвить тот узел, у которого верхнее число наибольшее. Если же у двух узлов верхние числа совпадают, то будем ветвить тот из них, у которого нижнее число меньше. Если в процессе ветвления встретится узел с отрицательным нижним числом, это значит, что при соответствующих данному узлу способах погрузки автомашина будет перегружена, и ветвление такого узла не имеет смысла. Производя ветвление по указанному способу, мы придём к узлу, находящемуся на последнем, шестом уровне графа, с неотрицательным нижним числом.

Этот узел соответствует некоторому допустимому способу погрузки, при котором значение целевой функции равно верхнему числу. Все неветвлённые узлы, у которых верхнее число меньше, чем у этого узла, незачем ветвить, так как при ветвлении верхнее число не может увеличиваться. Может оказаться, что верхнее число найденного узла больше, чем у любого другого узла. Тогда этот узел и даёт решение задачи. На рисунке 2 показан окончательный граф.

Построение графа проходит по следующим этапам (числа означают номера узлов): $$ \colsep{3pt}{\begin{array}{rl} 1)&0\to1\to3\to5\to7\to9;\\ 2)&6\to11\to13;\\ 3)&8\to15;\\ 4)&2\to17\to19\to21\to23\to25;\\ 5)&12\to27\to29;\\ 6)&4\to31\to33\to35;\\ 7)&10\to37;\\ 8)&20\to39\to41\to43;\\ 9)&22\to45\to47;\\ 10)&32\to49\to51\to53;\\ 11)&14\to55;\\ 12)&34\to57\to59. \end{array}} $$

Дальнейшее ветвление бесполезно, так как узел 55 находится на последнем уровне графа и имеет наибольшее верхнее число. Этот узел и даёт решение задачи. Он соответствует вектору $(1,1,0,1,0,1)$‍:‍ нужно погрузить на автомашину 1-й, 2-й, 4-й и 6-й предметы. При этом суммарная стоимость (максимум целевой функции) равна 450 руб.

В процессе построения графа было «отсечено» свыше 50% бесперспективных вариантов. При увеличении числа переменных процент таких вариантов обычно растёт.

Кроме того, процесс можно ускорить, если сразу найти из каких-либо соображений «достаточно хорошее» решение. Так, в данном случае достаточно хорошее решение, соответствующее узлу 26, было найдено из соображений, связанных с удельной стоимостью.

Мы надеемся, что читатель ощутит общность описанного подхода к решению подобных задач. Конечно, наша задача достаточно проста: из каждого узла выходят лишь 2 ветви, и не составляет труда найти границы (верхнее и нижнее числа). В других задачах процессы ветвления и ограничения могут быть сложнее и зависеть от опытности и остроумия тех, кто её решает. Что же касается трудоёмкости самой реализации процесса, то здесь на помощь приходят электронно-вычислительные машины. Задачи, подобные рассматриваемой, часто называют «задачами о рюкзаке» (замените автомашину туристским рюкзаком, а её грузоподъёмность — предельными возможностями туриста, собирающегося в поход и совершающего трудный выбор среди «совершенно необходимых» предметов).

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