Ветви и границы

Квант 1972, №7 с. 2-5 Тег UYY0

Рассмотрим задачу:
На складе имеются предметы (как-
дый — по одному), вес и стоимость
коморых указанных в таблице.

| Порядковый номер | вес в цент-
нерах | Стоимость
(в рублях) |
| :— | :— | :— |
| 1 | 11 | 120 |
| 2 | 7 | 140 |
| 3 | 6 | 60 |
| 4 | 5 | 80 |
| 5 | 12 | 160 |
| 6 | 9 | 110 |
| Всего | 50 | 670 |

Грузоподъемность автоматии — 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>32$ ).

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

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

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

Итак, отвлекаясь от «жизненной» ситуации, мы получаем число математического задачу: найти значения

переменных $x_1, \dots, x_6$ (какое из которых может быть равно 0 или 1), при которых функция
$f(x_1, \dots, 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 \leq 32.$ (1)

Функцию $f$ называют целевой функцией задачи; она определяна на множество всех упорядоченных шестерок из нуля и единиц (исстимерных векторов, каждой компонента которых равна 0 или 1).

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

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

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

Наименование переменных $x_2, \dots, x_6^*)$ , при котором достаточно максимума функция $f_2(x_2, x_3, \dots, x_6) = 140x_2 + 60x_3 + 80x_4 + 160x_5 + 110x_6$ при условии $7x_2 + 6x_3 + 5x_4 + 12x_5 + 9x_6 \leq 32$ .

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

Наименование переменных $x_2, \dots, x_6$ , максимизирующих функцию $f(x_2, \dots, x_6) = 140x_2 + 60x_3 + 80x_4 + 160x_5 + 110x_6$ при условии $7x_2 + 6x_3 + 5x_4 + 12x_5 + 9x_6 \leq 32$ .

*) Условия $x_i = 0$ или 1, предполагаемые на протяжении всей статы, мы в дальнейшем специально не ограничены.

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

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

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

Процесс отбора предметов для погрузки на автоматизину можно изобразить в виде $\textcircled{2}$ графа $^*$ ). Начальный узел 0 соответствует множество $P$ всех 64 максимальных векторов. От узла

*) См. статью М. И. Башмакова. «Паросочетания и трансортиные сети» в № 4 «Кванта» за 1970 год. Впрочем, дальнейшее будет понятно и тем, кто не читал этой страницы.

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^8-k$ векторов (варинартов загрузки автоматизины). Узлы, полученные на шестом шаг ветвления, представляют по одному вектору каждой, так что средние этих узлов находится задан. Итак, если проведится ветвление полностью, то придется построить граф с числом узлов $1+2+4+\dots+64=127$ .

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

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

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

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

Построение графа продолжит по следующим этапам (числа ознакомят

номера узлов):

0→1→3→5→7→9; 2) 6→11→13; 3) 8→15; 4) 2→17→19→21→23→25; 5) 12→27→29; 6) 4→31→33→35; 7) 10→37; 8) 20→39→41→43; 9) 22→45→47; 10) 32→49→51→53; 11) 14→55; 12) 34→57→59.

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

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

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

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