Задача о рюкзаке (ранце)

На этой задаче показано, как конкретно применяется к ее решению метод ветвей и границ и динамического программирования.

Задача формулируется следующим образом. Перед походом в рюкзак вместимостью не более А единиц веса из набора I - {1, 2, п) предметов, каждый весом я, и «ценностью» с,-,

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

Математическую формулировку задачи получим следующим образом. Введем в рассмотрение переменные х,, /'=1,2,..., //такие, что х,- =1, если /'-й предмет кладется в рюкзак, и х1 = 0, в противном случае. Тогда выражение IV = с,х, 2х2+...+ с,х,+...+ спхп =

= ^с,Ху будет определять суммарную «ценность» груза при соот-/=1

ветствующих значениях х,- = 1 или х,- =0, /' = 1,2, ..., п, а выражение аххх2х2+...+ а/х/+...+ апхп = ^я,х, — суммарный вес

/=1

рюкзака.

Требуется найти такой набор переменных х/? /е /, который доставляет

тах^СуХ, -IV (6.1)

при условиях:

  • (6.2)
  • (6.3)
  • 5>х, ^ V, /=1

1, если /'-й предмет помещен в рюкзак, 0, в противном случае.

Решение задачи о рюкзаке в такой формулировке определено на множестве комбинаций, состоящих из последовательностей нулей и единиц длиной п. Например, при /7 = 3 это комбинации 000, 001,010, 100, 011,110, 101, 111. Согласно закону комбинаторики всего таких комбинаций будет 2/7. Если же отбросить совсем неподходящие комбинации 000, 111, которые указывают на то, что в рюкзак либо не кладется ни один предмет, либо помещаются все предметы, то их число будет равным 2" - 2. Кроме этого число комбинаций 2" -2 будет ограничено величиной V, определяющей допустимый груз рюкзака. Таким образом, решение задачи следует искать на некотором подмножестве комбинаций, число элементов которого меньше 2" -2. Безусловно, лучшую комбинацию можно найти методом прямого их перебора, если число п невелико. По возможностям современных персональных компьютеров такой поиск сравнительно быстро может быть осуществлен, если п не больше 30. В этом случае придется сгенерировать 230 - 2 комбинаций, проверить условие (2) и подсчитать значение IV не более 230 -2 раз, что составит 210 -210 -210 -2 = 1024-1024-1024-2 = 1 073 741 822 указанных действий.

По элементам множества — комбинациям из нулей и единиц, на которых определена оптимизируемая функция, задача о рюкзаке сходна с задачей о выполнимости булевой формулы, о которой говорилось выше. Поскольку эта задача ЛФ-полная, можно предполагать, что и задача о рюкзаке также принадлежит к этому классу задач. Это действительно так, и строгое доказательство этого факта изложено в [26].

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

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

Применительно к рассматриваемой задаче о рюкзаке разбиение исходного множества комбинаций и всех последующих подмножеств будем осуществлять на два подмножества. Первое из них содержит такие комбинации, для которых очередное х,- = 0, а второе — такие, что очередное х,- = 1.

Стратегию ветвления примем такой, что для очередного разбиения выбирается то подмножество решений, для которого максимальна верхняя граница оптимизируемой функции. Тогда полученное первоначальное дерево поиска, например, для п - 4 может быть таким, как на рис. 6.4.

Для формулировки оценочной задачи проведем следующие рассуждения. Предположим, выбрана некоторая комбинация х,, х2, х3, ..., хк, для нее найдена сумма весов ах, а2, а3, ..., ак, меньшая V, а выбор любого хк+1 = 1 из оставшегося их набора превышает допустимый вес рюкзака, т. е. я, + а2 + а3+...+ ак + +...+ ак+1 > V. Тогда, чтобы выполнялось требование а12 + + а3+...+ ак+...+ ак+, = V необходимо дать возможность переменной хА+1 изменяться в пределах 0 < хк+1 < 1. Иными словами, следует отказаться от требования целочисленности этой переменной. Значение переменной хк+] находится просто. Необходимо определить разность А = У-(а1 + а2 + а3+...+ак) и разделить ее на

ак+1, т.е. получить хл+1 =-. На этом основании находим «ценность» груза рюкзака с,х, 2х2+...+ скхпк+1хк+1, которая больше его «ценности» с,х, + с2х2 + с3х3+...+ скхк на величину скхк+1, т-е- является по отношению к ней верхней границей. Таким образом, оценочная задача, служащая для вычисления верхних границ оптимизируемой функции на подмножествах, формулируется так: найти

  • (6.4)
  • (6.5)

тах ^ с, х, /€/

при условиях:

Корень Ярус

Первоначальное дерево ветвления в задаче о рюкзаке

Рис. 6.4. Первоначальное дерево ветвления в задаче о рюкзаке

5>,.х,. -у

/€/

О < х, < 1, / е / (6.6)

В этой задаче все переменные х, , кроме одного, — целочисленные, т. е. принимают значения 0, 1.

Казалось бы, оценочная задача также сложна, как и первоначальная. Однако это не так. Решается она достаточно просто.

Сначала необходимо найти «ценности» единиц весов грузов —,

а

С С с с с

—, — и упорядочить их по убыванию — > — . Затем

а

а

п

а

а

а

п

согласно упорядоченной последовательности «ценностей» необходимо выбирать соответствующие переменные х,- / е / и назначать им значение 1 до тех пор, пока ^я,х, < У? Если ^я,х, = V,

/є/

/е/

верхняя граница находится как где все х1- = 1. Если же

/є/

< V, а 1х/мхм > V, то для вычисления верхней гра-

/є/

ІЄІ

«/+1, затем сі+1х,+1

ницы необходимо найти х/Ч1 =

/є/

и суммировать эти величины, т. е. получить ^я,х, + с;Ч1х/+1.

/е/

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

После этого можно начать ветвление, формируя сначала вершину х,. = 1, затем вершину х,- = 0, и вычисляя для них верхние границы оптимизируемой функции. Ветвлению подлежит та вершина, для которой верхняя граница больше. В процессе ветвления запоминается последовательность переменных х, / е /, порождающих путь ветвления, а также меньшие верхние границы вершин и ведущие к ним пути, составленные значениями х, от корня дерева к соответствующей вершине.

Описанным способом будет построено бинарное дерево поиска высотой п с двумя вершинами последнего п-го яруса. Из этих вершин следует выбрать ту вершину, для которой верхняя граница больше. Значение этой границы определит рекорд Я, а путь к ней от корня дерева, составленный из переменных х,- / е / с соответствующими значениями, даст первое рекордное решение задачи.

В соответствии с идеей метода ветвей и границ теперь необходимо последовательно, начиная с конца (п - 1)-го яруса дерева, сравнивать значения запомненных верхних границ, соответствующих висячим вершинам дерева, со значением рекорда Я. Если верхняя граница 0, некоторой вершины х,- к-то яруса дерева меньше или равна Я, необходимо перейти к - 1)-у ярусу дерева. Иными словами, ветви дерева, которые могли бы исходить из вершины х,, — отсечь. Если же (7, > Я, то необходимо ветвить вершину х; , вычислять верхние границы для вершин, порождаемой этой вершиной х,-, и сравнивать большую границу с Я.

Таким путем можно снова оказаться на последнем ярусе дерева, если получаемые границы все время больше Я. Тогда большая граница некоторой вершины последнего яруса заменяет рекорд Я новым значением.

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

Для демонстрации метода решим следующий пример. Допустимый вес рюкзака V = 15. Количество предметов п - 5. Веса предметов: 3, 2, 4, 5, 6. «Ценности» предметов: 6, 5, 6, 12, 10.

~ 6 5 6 12 10 0

Определим «ценности» единиц грузов: , — . В ре

зультате получим: 2; 2,5; 1,5; 2,4; 1,67. Упорядочим «ценности» по убыванию: 2,5; 2,4; 2; 1,67; 1,5.

Для удобства вычислений составим табл. 5, в которой расположим грузы, их «ценности» и индексированные переменные х, в соответствии с полученным упорядочением.

Таблица 5

О,

«2

«4

«5

«3

2

5

3

6

4

с.

С5

сз

с/

5

12

6

10

6

*2

*4

X,

*5

*3

Процесс ветвления начинаем в порядке записи переменных в табл. 5 и иллюстрируем его на рис 6.5. Из корня дерева проводим две дуги, направленные к вершинам х2 -0,х2 = 1, и вычисляем для этих вершин верхние границы оптимизируемой функции. Полученные значения записываем рядом с вершинами.

Сначала вычисляем верхню границу для вершины х2 - 1. Определяем величину < 15. Она равна а2 + аА + ах -

/е/

= 2 + 5 + 3=10. Разность Д = И- ^я, =15-10 = 5. Вычисляем

/е/

значение переменной х5 = — = - = 0,83. На этом основании верх-

а5 6

няя граница 0Х2=х - с2 + с4 + с, + 0,83с5 = 5 + 12 + 6 + 8,3 = 31,3.

Теперь вычислим верхнюю границу для вершины х2 - 0. Определяем величину ^я,- < 15. Она равна я4 + я, + я5 =

/е/

= 5 + 3 + 6 = 14, так как при х2 - 0 вес а2 = 0. Разность Д =

= V - V я, =15-14 = 1. Значение переменной х5 = — = — = 0,25. 171 ав 4

На этом основании верхняя граница 0 0 = с4 + с, + с5 + 0,25с6 = = 12 + 6+10 + 1,5 = 29,5.

Так как 0Х2=1 Х2=0, дальнейшее ветвление выполняем для вершины х2 - 1. Значение верхней границы и путь от корня дерева к вершине х2 - 0 запоминаем: <2*2=о=29,5 ; х2 =0. Запоминаем также путь х2 = 1 В вершину С большей оценкой 0 1.

Из вершины х2 = 1 проводим две дуги, направленные к вершинам х4 - 0, х4 = 1, и вычисляем для этих вершин верхние границы оптимизируемой функции.

При х4 - 1 определяем величину < V. Она равна а2 + а4 +

/е/

+ а{ = 2 + 5 + 3 = 10. Разность Д = V - =15-10 = 5. Значение

/е/

переменной х5 = — = - = 0,83. Верхняя граница 0^ =1 = с2 + с4 +

а5 6 4

+ с, + 0,83с5 = 31,3.

Определяем величину < V при х4 - 0. Она равна я2 + я, +

/€/

+ я5 + я3 = 2 + 3 + 6 + 4=15. Разность Д = V -( = 0. Верхняя

/е/

граница 0Х4=О = 5 + 6+ 10 + 6 = 27,0.

Так как 0Ч=1 > 0Л.4=О, далее ветвим вершину х4 - 1. Запоминаем границу 0Л.4=О, путь х2 = 1, х4 - 0. Запоминаем путь в вершину х4 - 1 как х2 = 1, х4 - 1.

Из вершины х4 проводим две дуги, направленные к вершинам х, = 0, х, = 1, и вычисляем для этих вершин верхние границы. При

х2 =1, х4 =1, х, =1 определяем величину ? Я,. < V. Она равна

/€/

2 + 5 + 3 = 10. Разность Д = V -; =15-10 = 5. Значение пере-

/б/

менной х5 = — = - = 0,83. Верхняя граница ?)х =, = с2 + с4 + с, +

а5 6

+ 0,83с5 = 31,3.

Определяем величину < V при х, = 0. Она равна а2 + а4 +

/е/

+ й5 = 2 + 5 + 6= 13. Разность Д = Р- ^я, =15-13 = 2. Значение

/е/

д 2

переменной х3 = — = — = 0,5. Верхняя граница ()х =0 - с2 + с4 +

аъ 4

+ с5 + 0,5с3 = 5 + 12 + 10 + 3 = 30,0. Так как ?)Х[ =1 > Оч=0, далее ветвим вершину х, = 1. Запоминаем границу Ох=0, путь в вершину х, = 0 как х2 = 1, х4 = 1, х, =0. Запоминаем путь в вершину х, = 1 как х2 = 1, х4 = 1, х, = 1.

Из вершины х, = 1 проводим две дуги, направленные к вершинам х5 = 0, х5 = 1. Для х5 = 1 определяем величину Тй,. Она

/е/

равна а2 + а4 + й, + й5 = 2 + 5 + 3 + 6 = 16 > V- 15. Таким образом, дуга из вершины х, = 0 в вершину х5 = 1 не может быть направлена. Она может быть только фиктивной (условной). Для удобства вычислений полагаем вершину х5 = 1 тоже фиктивной и назначаем ей границу 0^=1 равной нулю. На рис. 6.5 дуга (х, х5) при х5 = 0 и вершина показаны пунктирными линиями.

Вычисляем верхнюю границу для вершины х5 = 0. Определяем величину < V. Она равна а2 + а4 + ах + аъ = 2 + 5 + 3 + 4 =

/е/

= 14. В связи с тем, что все веса а2, а4, ах, а2 исчерпаны, верхняя граница будет равна сумме «ценностей» соответствующих грузов, т- е- =о = с2 + с4 + с + сз ~ 5 + 12 + 6 + 6 = 29. Далее ветвим вершину х5 = 0, проводя дуги к вершинам х3 = 1, х3 = 0 и вычисляя верхние границы для этих вершин.

Определяем величину < V при х3 = 1. Она равна а2 + а4 +

/б/

+ й, + й3 = 2 + 5 + 3 + 4=14< V Поскольку исчерпаны все переменные х2 = 1, х4 = 1, х, = 1, х5 = 0, х3 = 1, верхняя граница для вершины х3 = 1 равна 0Хз=1 = 5 + 12 + 6 + 6 = 29. Верхняя граница для вершины х3 = 0 равна 5+12 + 6 + 6 + 0 + 0 = 23. На этом первоначальное ветвление закончено. Для последнего 5-го яруса

дерева выбираем наибольшую верхню границу 0 0 = 29, получа

ем рекорд Я = 0Хз=о = 29 и соответствующий набор переменных х2 = 1, х4 = 1, х, = 1, х5 = 0, х3 = 1.

Теперь возвращаемся к четвертому ярусу дерева и сравниваем запомненную границу с рекордом.Это граница фиктивной вершины х3 = 1, равная 0. Она меньше Я. Поэтому поднимаемся по дереву к третьму его ярусу. Запомненной границей этого яруса дерева является граница 0 0 = 30 вершины хг = 0. Поскольку 0 о = 30 > Я = 29, ветвим эту вершину.

Процесс ветвления изображен на рис. 6.6.

Вторичное дерево ветвления

Рис. 6.6. Вторичное дерево ветвления

Из вершины х, = 0 проводим две дуги, направленные к вершинам х5 = 0, х5 = 1, и вычисляем верхние границы для этих вершин.

Определяем величину < V. Она равна а2 + а4 + 0 + а5 =

/€/

= 2 + 5 + 6 = 13. Разность А = V - ^а/ =15-13 = 2. Значение пере-

/е/

д 2

менной х3 = — - - = 0,5. Верхняя граница для вершины х5 = 1

а3 4

равна 0У.=| = с2 + с4 + 0 + с5 + 0,5с3 = 5 + 12 + 10 +0,5-6 = 30,0. Верхняя граница для вершины х5 =0 определяется как Ох$=0 = - с2 + с4 + с3 = 5 + 12 + 6 = 23, поскольку все переменные исчерпаны.

В связи с тем, что 0 , > 0 О» дальше ветвим вершину х5 = 1. Проводим две дуги, направленные к вершинам х3 =0, х3 = 1, и вычисляем для этих вершин верхние границы.

Для вершины х, = 1 определяем величину ^й, = а2 + й4 + 0 +

/б/

+ й5 + й4 = 2 + 5 + 6 + 4 = 17, которая больше V = 15. Таким образом, дуга из вершины х5 = 1 в вершину х3 = 1 не может быть направлена. Полагаем вершину х3 = 1 фиктивной и назначаем ей

границу (2*3=! = 0. Для вершины х3 = 0 определяем величину ^й,.

/6 /

Она равна а2 + а4 + а5 = 2 + 5 + 6=13. Поскольку все переменные исчерпаны, верхняя граница для вершины х3 = 0 определяется как (2*з =0 = с2 + с4 + с5 = 5 + 12+ 10 = 27. В связи с тем, что ветвление закончено, выбираем большую границу последнего яруса дерева ветвлений. Она равна 27. Сравниваем эту границу с рекордом Я = 29. Рекорд оказывается большим. Поэтому его не изменяем.

Далее возвращаемся к четвертому ярусу дерева и сравниваем запомненную границу 0 0 = 27 с рекордом Я = 29. Рекорд оказывается большим. Поэтому его не изменяем.

Далее возвращаемся к третьему ярусу дерева и сравниваем запомненную границу (2д5=0 = 27 с рекордом Я = 29. В связи с тем, что (2*5=о < Я, переходим ко второму ярусу. Запомненная верхняя граница вершины х4 = 0 этого яруса (2*4=0 = 27. Она меньше рекорда Я = 29. Поэтому переходим к первому ярусу дерева ветвлений.

Запомненная верхняя граница вершины х2 - 0 этого яруса 0 О =29,5. Она больше рекорда Я = 29. Начинаем ветвление из вершины х2 - 0.

Действуя изложенным выше способом, сформируем дерево поиска, изображенное на рис. 6.7.

У вершин дерева, как и на предшествующих рисунках, проставлены верхние границы. Сравнивая границы вершин последнего яруса дерева 0 0 и (2*3 =1, выбираем большую границу

(2 о =28. Сравнивая ее с рекордом Я =29, оставляем значение рекорда прежним, равным 29. Теперь последовательно просматривая запомненные значения верхних границ вершин ярусов 4—2, убеждаемся в том, что все они меньше рекорда Я - 29.

Таким образом, процесс просмотра оказывается законченным в вершине х4 = 0, граница которой (2У4=0 = 22, и тем самым закончен процесс поиска решения задачи излагаемым методом со зна-ченим оптимизируемой функции Я = 29 и набором переменных

х2 - 1, х4 = 1, х, = 1, х5 = О, -Х3 = 1. Это означает, что в рюкзак следует положить предметы 2, 4, 1, 3.

Для решения задачи о рюкзаке методом динамического программирования задачу максимизации суммы «ценностей» предметов, помещаемых в рюкзак с1х12х2+...+ с1х1+...+ спхпредставим, как УУ-стадийный процесс принятия решений. На каждой стадии этого процесса следует решить, какое значение, 0 или 1, назначить очередной переменной х,, / = 1, 2, ..., п.

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

В связи с тем, что сумма грузов+ а2х2+...+а1х1+...+апхп < < V определятся весом V, от текущего значения этого веса, определяемого загрузкой рюкзака, и будет зависеть значение функции Веллмана. Поэтому в качестве состояний системы для каждой стадии процесса принятия решений определим последовательность значений веса V как последовательность целых чисел 5 = 0, 1,2, ..., V. Для каждого из этих чисел и будем опреде

лять функцию Веллмана, которую обозначим символом Ву (5).

Процесс оптимизации начнем с выбора значения х,, которое определим на последней N-й стадии процесса принятия решений. Для этого выведем формулу, по которой для этой стадии можно вычислить функцию Веллмана. В связи с тем, что для каждого состояния 5 = 0, 1,2, ..., V эта функция определяет максимальную «ценность» груза, то очевидно, что 5, (х) = шах с,х, при я,х, < 5,

S х =0 ИЛИ х =0

ИЛИ X, < -.

*1

Теперь задача состоит в том, чтобы научиться вычислять 5, (5) = шах с,х,. Поскольку шах с,х, зависит от х,, которое может принимать два значения — 0 или 1, то необходимо установить, в каких случаях х, = 0 и х, =1. Для этого обратимся к нера-

венству х, < —. До тех пор, пока — <1, значение х, не может

а а

стать равным 1, и только тогда, когда — >1, переменная х, может

«1

принимать это значение. Таким образом,

= 0, если

< 1, и

  • 5, (5) = тахс,х,
  • 5, (5) = тахс,х, = с,

если — > 1.

(6.7)

Для второй стадии процесса принятия решений функция Веллмана в соответствии с принципом оптимальности — в каждом состоянии принимать оптимальные решение — записывается так:

52(5) = шах = 2х2 + 5, (5 - я2х2)] по х2 = 0 или х = 1 при а2х2 < 5. По этому рекуррентному соотношению функция 52(5) вычисляется следующим образом. Пока— < 1, тох2 = Ои 52(5) =

а2

$

- 5, (5). Когда же — > 1, то шах = 2х2 + 5,(5-я2х2 )] может дос-

я2

тигаться как при х2 = 0, так и при х2 = 1. Поэтому 52(5) = 5, (5), 5 .

если — < 1, и

я2

52(5) = тах{[с2х2 +5,(5-я2х2)], 5,(5)}, если — > 1. (6.8)

«2

Для /-й стадии функция Веллмана имеет такой вид: 5,(5) =

= max [с,х, + 5,_, (5 - aixl,)] по х,- = 0 или х,- = 1 при aixi < 5. Ее значения в зависимости от состояния вычисляются по формуле

5,(5) = 5,_,(5), если — < 1, и

а,

5,(5) = max {[Cj + В, ,(5-a,)], Bi ,(5)}, если — > 1. (6.9)

о,

Найдя способы вычисления функции Веллмана на каждой /'-й стадии процесса оптимизации, можем приступить к решению приведенного выше примера.

Согласно числу переменных х,, х2, х3, х4, х5, значения которых необходимо определить, процесс принятия решений будет содержать 5 стадий. Число состояний на каждой стадии равно О, 1,2, ..., 15, т. е. 16. Для записи значения функции Веллмана на каждой стадии, а также значения переменной создадим две таблицы 6, 7, состоящие из 4 строк и 16 столбцов.

В табл. 6 будем построчно записывать значения функции Веллмана, в табл. 7 — значения переменной х,, по которой ведется оптимизация.

Первую строку табл. 6, 7 заполняем, используя формулу (6.7).

Для этого находим значение S, при котором — = 1. При а] - 3 оно

Я/

равно 3. Значит для 5 = 0, 1,2 функция 5, (5) = 0, а х, =0; для остальных значений S = 3, 4, ..., 15 5,(5) = с,, а переменная х, = 1.

Вторую строку табл. 6, 7 заполняем, используя формулу (6.8) и первую строку табл. 6. Как и выше, определяем значение 5, для

Таблица 6

Состояния системы

стадии

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

1

0

0

0

6

6

6

6

6

6

6

6

6

6

6

6

6

2

0

0

5

6

6

11

11

11

11

11

11

11

11

11

11

11

3

0

0

5

6

6

11

11

12

12

17

17

17

17

17

17

17

4

0

0

5

6

6

12

12

17

18

18

23

23

24

24

29

29

Таблица 7

Состояния системы

стадии

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

і

0

0

0

1

1

1

1

1

1

1

1

1

1

1

1

1

2

0

0

1

0

0

1

1

1

1

1

1

1

1

1

1

1

3

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

4

0

0

0

0

0

1

1

1

1

1

1

1

1

1

1

1

которого — = 1. Оно равно 2. Следовательно, для S = 0, 1, согласно

формуле (6.8), функция B2(S) = 7?,(5) = 0их2 =0. Для остальных S = 2, 3, 5 значение B2(S) необходимо вычислять по формуле

B2(S) - max {[с2 + В {(S - а2)], (5)}. Поэтому при S - 2 значение

В2(2) = шах {[5+ Вх{2 -2)], Вх{2)} = шах [(5 + Вх (0), Вх (2)] = = шах [(5 + 0), 0] = 5. При этом, если максимум определяется первым членом формулы с2 + B{(S -а2), то х2 - 1, если же вторым Вх (5), то х2 = 0.

Если эти члены равны, то выбирается любое значение х2. Подставляя в формулу для вычисления B2(S) различные значения S = 3, 4, ..., 16 и находя максимум, заполняем оставшуюся часть второй строки табл. 6, 7.

Третью и четвертую строки табл. 6, 7 заполняем значениями B3(S), B4(S), вычисляемыми аналогично второй строке по формуле (6.9) и используя соответственно значения второй и третьей строк табл. 6.

Для третьей строки определяем значение S, при котором

  • 5
  • — = 1. Оно равно 4. Следовательно, для S - 0, 1, 2, 3, согласно «з

формуле (6.9), функция B3(S) = B2(S), а х3 = 0. Для остальных S = 4, 5, ..., 15 значение B3(S) вычисляется по формуле B3(S) =

= max {[с3 + B2(S - а3)], 52(5)}.

S

Для четвертой строки значение S, при котором — = 1, равно

а4

5. Поэтому для 5=0, 1, 2, 3, 4 функция B4(S) = B3(S). Для остальных S - 5,6,..., 15 она вычисляется по формуле B4(S)~ = max {[с4 + ?3(5-я4)], ?3(5)}.

Чтобы найти оптимальное решение задачи, безусловно, необходимо было бы заполнить пятую строку таблиц и найти в ней наибольшее значение функции Веллмана, а также соответствующее значение х5. Однако, как видно из табл. 6, функция Веллмана не убывает при росте 5 и максимального значения достигает при 5 = 15. Поэтому достаточно ее вычислить при 5 = 15.

Таким образом, В5( 15) = шах {[с5 + В4 (15 - <з5)], В4 (15)} = = max {[10 + В4 (15 - 6)], 29} = 29 и максимальное значение «ценности» груза равно 29. Это значение достигается при х5 = 0, поскольку максимум, согласно табл. 6, определяется вторым членом формулы 54(15).

Остальные значения переменных вычисляются в обратном порядке на основании данных табл. 7 по формулам, которые определяют соответствующую клетку таблицы. Для х4 это клетка (4, V -а5х5), где первое число пары — это номер строки, а второе число — номер столбца.

Таким образом, значение х4 это число клетки (4,15) таблицы 7. Оно равно 1. Следовательно, х4 = 1. Значение х3 определяется по клетке (3, V -а5х54х4)= (3, 10). Согласно табл. 7 оно равно 1. Для определения значения х2 имеем клетку (2, V - а5х54х4 - а3х3)~ (2, 6). В ней записано значение х2 = 1. Наконец, для определения значения х, используем клетку (1, V -а5х54х4 - а3х3 2х2) = (1,4). Ей соответствует значение х, = 1.

Таким образом, предметы, помещаемые в рюкзак, — 1, 2, 3, 4. Следует отметить, что этот набор предметов, как и оптимальная «ценность» рюкзака, совпадают с набором и их «ценностью», полученными ранее методом ветвей и границ.

В заключение необходимо сказать: достаточно качественные решения рассматриваемой задачи можно получить приближенным методом, основанным на выборе предметов, помещаемых

_ с, с7 с

в рюкзак в порядке убывания «ценностей» грузов —, —, ..., —.

а, а2 ап

Решения задач на ЭВМ показывает, что приближенный метод существенно быстрее решает задачу и, что самое главное, с увеличением количества предметов п средняя и максимальная его погрешность убывает. Например, для п = Шони не превышают соответственно 2 и 10 процентов по отношению к точному решению задачи, а для п = 60 указанные числа равны 1 и 3 процента. Это свидетельствует о том, что если в некоторых практических случаях необходимо быстро получить решение, можно с успехом пользоваться приближенным методом.

 
< Пред   СОДЕРЖАНИЕ     След >