Ветви и границы
Страница переведена на новый сайт https://myeducation.su/ :
страница ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (1972)
|
Считаете сайт полезным? |
Квант 7 июль 1972
Ниже текст для быстрого знакомства с темой. Формулы отображаются некорректно. Если тема вас заинтересовала, нажмите на ссылку выше.
И не забудьте поделиться страницей в соц. сетях! 🙂
Р. П. Шейнцвит
Рассмотрим задачу:
На складе имеются предметы (каждый
по одному), вес и стоимость
которых указаны в таблице.
Грузоподъемность автомашины —
3200 кг. Требуется так загрузить
автомашину, чтобы общая стоимость
взятых предметов была как можно
большей.
Очевидно, выгоднее брать предметы,
имеющие при малом весе большую
стоимость.
Введем понятие удельной стоимости
предмета dlt то есть стоимости
одного центнера i-ro предмета в рублях:
£^=10,9; d2=20; d3~10; d4= 16;
ds=13,3; d6= 12,2.
Если загрузить автомашину предметами
с наибольшей удельной стоимостью
— вторым, четвертым, пятым
и шестым,— то сумма их весов ока-
2
жется больше грузоподъемности автомашины
(7 + 1 5 + 1 2 + 9 > 3 2 ) .
Если же взять только 2-й, 4-й
и 5-й предметы, то машина окажется
недогруженной на 8 ц. Можно тогда
погрузить еще только один 3-й предмет,
причем суммарная стоимость получится
равной 440 руб., а машина
будет недогружена на 2 ц. Можем
ли мы быть уверены, что не существует
лучшего способа загрузки машины?
Может быть, выгоднее оставить
какой-либо из предметов с большей
удельной стоимостью, но зато увеличить
общую стоимость путем полного
использования грузоподъемности
машины?
Как видим, «в лоб» задачу решить
трудно. А в реальных условиях,
когда речь зачастую идет не о шести,
а о шестидесяти предметах, и браться
за нее нельзя, не вооружившись математическими
методами. Переведем
задачу на язык математики (как говорят,
математизируем ситуацию).
Пусть = если /-й предмет погружается
на автомашину, и x t — 0 в
противном случае ( t= 1, …, 6). Тогда
общая стоимость погруженных предметов
в рублях равна 120 x t-\-140 х а+
+ 60 х3+ 8 0 дг4+160 л’5+ 1 10 х6, а их
общий вес в центнерах равен 11 x v +
-|- 7 л’2 + бл’з + 5 х 4 + 12 хь + 9 дг?.
Итак, отвлекаясь от «жизненной»
ситуации, мы получаем чисто математическую
задачу: найти значения.
переменных х х, …, хв (каждое из ко
торых может быть равно 0 или 1),
при которых функция
/(x j, …,xe) — 120XJ + 140х2 Ч-
+ 6 0 х 3 -Ь 80х4 ~\- 160х& Ч- 110хв
достигает максимума, если выполнено
условие (ограничение)
П х х -\- 7ха + 6х3 + 5х4 +
-Н 2х6 + 9xe < 3 2 . ( 1)
Функцию / называют целевой функцией
задачи; она определена на множестве
всех упорядоченных шестерок
из нулей и единиц (шестимерных
векторов, каждая компонента которых
равна 0 или 1).
Всего, очевидно, имеется 2е=64
таких векторов, причем каждый из
них дает некоторый способ загрузки
автомашины. Но не каждый из этих
64 способов загрузки допустим: вектор
(1,0, 1,0, 1, 1) соответствует погрузке
на машину 1-го, 3-го, 5-го
и 6-го предметов, однако их общий
вес (38 ц) превышает допустимый.
Естественно назвать вектор допустимым,
если для него выполняется
условие (1). Итак, решением задачи
является допустимый вектор, максимизирующий
целевую функцию /.
Теперь допустим, что 1-й предмет,
погружен на автомашину. Тогда х х— 1,
и мы получаем новую задачу:
Найти значения переменных х 2,…
…, хв*), при которых достигает максимума
функция f о (х2, х3, …. хв) —
— 140х2 -Ь 60х3 -J- 80х4 -f- 160xj4-
+ 110хв при условии 7х2 + 6х3
+ 5х4 + 12х5 4- 9х6 ^ 2 1 .
Если же 1-й предмет не погружен,
то Xj—0, и мы получаем такую задачу:
Найти значения переменных
х . х6, максимизирующих функцию
f (х2, …, хв) = 140х2 + 60х3 + .
+ 8 0 х 4 -г 160х6 -j’ 110хв
при условии
7х% + 6х3 -г 5х4 + 12х5 + 9х6^
<3 2 .
*) Условия Xi -0 или 1, предполагаемые
на протяжении всей статьи, мы в дальнейшем
специально не оговариваем.
Таким образом, одну задачу с
6 переменными можно свести к двум
задачам с 5 переменными; те в свою
очередь сводятся к четырем задачам
с 4 переменными и т. д., так что
в конце концов мы получаем 64 за*
дачи с одной переменной каждая.
Но уж если надо решать такую сис’
тему, то проще непосредственно про-
верить условие (1) для каждого из
64 возможных векторов, для допустимых
из них вычислить значение
целевой функции и выбрать тот вектор,
для которого значение максимально,
то есть, как говорят, решить
задачу «полным перебором».
А как же быть в тех случаях,
когда число предметов (компонент
векторов) велико? Ведь уже при 20
предметах число возможных вариантов
превышает миллион! Ясно, что
метод полного перебора в задачах
такого рода в большинстве случаев
непригоден.
Мы расскажем сейчас об одном
методе, позволяющем, как правило,
значительно уменьшить число сравниваемых
вариантов, необходимое для
получения решения. Метод этот, известный
под названием «метод ветвей
и границ», мы опишем в процессе
его применения к нашей задаче.
Процесс отбора предметов для погрузки
на автомашину можно изобразить
в виде графа*). Начальный
узел 0 соответствует множеству Р
всех 64 6-мерных векторов. От узла
*) См. статью М. И. Б а ш м а к о в а.
«Паросочетания и транспортные сети» в № 4
«Кванта» за 1970 год. Впрочем, дальнейшее
будет понятно и тем, кто не читал этой
О начинается ветвление к узлам I и 2
(рис. 1). Узел 1 находится правее
и ниже узла 0. Он соответствует
таким способам погрузки, при которых
1-й предмет обязательно погружается
на автомашину. Очевидно,
узел 1 соответствует подмножеству
Р у таких 32 векторов из Р, у которых
jTj= 1 . Узел 2 находится левее и ниже
узла 0 и соответствует подмножеству
Р о таких 32 векторов из Р , у которых
Xj = 0. Дальнейшее построение гра-
фа ясно. На рисунке 1 показан
граф после двух шагов ветвления.
Каждый узел графа соответствует
подмножеству векторов из Р, у которых
некоторые из компонент уже
зафиксированы. Если построение множеств
P j и Р 2 рассматривать как
первый шаг ветвления (первый уровень
графа), то на k -м шаге (Л-й
уровень графа) мы получим 2* узлов,
каждый из которых соответствует множеству
2е -* векторов (вариантов загрузки
автомашины). Узлы, полученные
на шестом шаге ветвления, представляют
по одному вектору каждый,
так что среди этих узлов находится
решение задачи. Итак, если провести
ветвление полностью, то придется
построить граф с числом узлов 1 -г
+ 2 -1- 4 + … + 64 = 127.
Но мы постараемся действовать
таким образом, чтобы попутно обнаруживать
«бесперспективные» узлы,
из которых не могут выходить
ветви, ведущие к решению. Чем раньше
(выше) «отсечь» эти ветви, тем
меньший перебор придется нам делать
потом. С этой целью сопоставим
каждому узлу 2 числа (которые будем
записывать под узлом). Верхнее из
них показывает наибольшую возможную
суммарную стоимость (границу
стоимости) взятых предметов при
любом способе погрузки, описываемом
векторами данного узла. Нижнее
число показывает, какой общий
вес отбираемых предметов допустим
на данном шаге (это число
равно разности между грузоподъемностью
автомашины и весом всех
уже погруженных предметов). Для
примера найдем верхнее и нижнее
4
числа для 1-го узла. Поскольку во
всех соответствующих ему вариантах
погрузки 1-й предмет обязательно
берется, нижнее число на этом шаге
равно 3 2— 1 1 = 2 1 . Граница стоимости
(верхнее число) равна сумме
стоимостей всех предметов, так как
мы еще не исключили возможности
выбора ни одного из них. Поэтому
верхнее число 1-го узла равно 670.
Для второго узла верхнее число равно
550 (670—120), так как первый
предмет не берется: нижнее же число
равно здесь 32.
Пусть Pi — вес i-ro предмета,
С, — его стоимость. Очевидно, что
при переходе от любого узла, находящегося
на t-м уровне графа, направо
вниз верхнее число не меняется, а
нижнее уменьшается на P i+j , при
переходе же от этого узла налево
вниз нижнее число не меняется, а
верхнее уменьшается на Ci+1. Б у дем
на каждом этапе ветвить тот
узел, у которого верхнее число наибольшее.
Если же у двух узлов верхние
числа совпадают, то будем ветвить
тот из них, у которого нижнее
число меньше. Если в процессе ветвления
встретится узел с отрицательным
нижним числом, это значит,
что при соответствующих данному
узлу способах погрузки автомашина
будет перегружена, и ветвление такого
узла не имеет смысла. Производя
ветвление по указанному способу,
мы придем к узлу, находящемуся
на последнем, шестом уровне графа,
с неотрицательным нижним числом.
Этот узел соответствует некоторому
допустимому способу погрузки,
при котором значение целевой функции
равно верхнему числу. Все не-
ветвленные узлы, у которых верхнее
число меньше, чем у этого узла,
незачем ветвить, так как при ветвлении
верхнее число не может увеличиваться.
Может оказаться, что верхнее
число найденного узла больше,
чем у любого другого узла. Тогда этот
узел и дает решение задачи. На рисунке
2 показан окончательный граф.
Построение графа проходит по
следующим этапам ‘(числа означают
номера узлов):
1) 0->l-*3-*5->7-v9; 2) 6-к
*-►11->13; 3) 8-И5; 4) 2+ 1 7 -И 9 ->
->21->23^25; 5) 12-*-27-»-29; 6) 4-*-
+31-*33->35; 7) 10-»-37; 8) 2 0 +
—*-39—>^41—>-43; 9) 22+45->47; 10) 32-»
■^49+51->53; П) 14-3-55; 12) 34->
■^-57->59.
Дальнейшее ветвление бесполезно,
так как узел 55 находится на последнем
уровне графа и имеет наибольшее
верхнее число. Этот узел и дает
решение задачи. Он соответствует вектору
(1, 1 ,0, 1 ,0, 1): нужно погрузить
на автомашину 1-й, 2-й, 4-й и 6-й
предметы. При этом суммарная стоимость
(максимум целевой функции)
равна 450 руб.
В процессе построения графа было
«отсечено» свыше 50% бесперспективных
вариантов. При увеличении
числа переменных процент таких ва*
риантов обычно растет.
Кроме того, процесс можно ускорить,
если сразу найти из каких-
либо соображений «достаточно хорошее
» решение. Так, в данном случае
достаточно хорошее решение, соответствующее
узлу 26, было найдено
из соображений, связанных с удельной
стоимостью.
„Мы надеемся, что читатель ощутит общность
описанного подхода к решению подобных
задач. Конечно, наша задача достаточно
проста: из каждого узла выходят лишь 2 ветви,
и не составляет труда найти границы
(верхнее и нижнее числа). В других задачах
процессы ветвления к ограничения могут быть
сложнее и зависеть от опытности и остроумия
тех, кто ее решает. Что же касается трудоемкости
самой реализации процесса, то здесь
на помощь приходят электронно-вычислительные
машины. Задачи, подобные рассматриваемой,
часто называют «задачами о рюкзаке»
(замените автомашину туристским рюкзаком,
а ее грузоподъемность — предельными возможностями
туриста, собирающегося в поход
и совершающего трудный выбор среди
«совершенно необходимых» предметов).
Конечно, задачи эти приходится решать
далеко не только перед отпуском или каникулами.
Ведь формирование годового плана
предприятия во многих случаях — та же
задача о рюкзаке. Неудивительно, что метод
ветвей и границ «работает» во многих планово-
экономических задачах, имеющих большое
значение для народного хозяйства.
5
#физика #квант
