Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 65
Текст из файла (страница 65)
га и!'яь!ОГ! А!!!'ОРиты 370 Вычитая (33) нз (23), получим ас!(Га — г-,)=Л1 — Л,. При у =г соотношение (23) принимает вид а —.г, = а- — А-. 1л з в' (34) (35) Поскольку а -)О, то поделив (35) на а „-, получив! 1 та=!' = Ь в ь' Я Ьз и (25) доказано. Наконец, можно использовать соотношение а ! = ос!гт (что воз- можно, если аьтФО), чтобы исключить а; из (33).
В результате получим соотношение (26): что фактически совпадает с (24). Воспользуемся соотношением (24), чтобы исключить г, н г; на (34), после чего получим ГЛАВА»8 ЗАДАЧА О РЮКЗАКЕ 18 1. Задача о рюкзаке (Гилмор, Гомори [75[, Гомори [84[) Рассмотрим простейшую задачу целочисленного программирования, а именно задачу только с одним ограничением. Эта аадача, как и задача о кратчайшем пути, имеет многочисленные практические приложения и часто возникает при решении различных задач оптимиаации. Она имеет простую структуру и поэтому может быть решена методом динамического программирования ([15[, [16[, [74[).
Мы обсудим этот метод, а в следующей главе рассмотрим его обобщение для решения общей задачи целочисленного программирования. Название «задача о рюкзаке» появилось благодаря следующей гипотетической ситуации. "Турист, собираясь в поход, должен выбрать, канио предметы ему взять с собой. Каждый предмет имеет свой вес и свою ценность. Требуется, чтобы общий вес рюкзака с выбранными предметами не превышал некоторой заданной величины, а их общая ценность была максимальной. Обозначим через а; вес одного предмета 7-го типа, через с~— его цеппость, через х; — число выбранных предметов у-го типа (т.
е. таких предметов, которые турист берет с собой), через Ь вЂ” зайанную величину, огранпчивающук> вес рюкзака. 'Тогда задача примет вид максимизировать ~, с,х, ,Х,, при ограничениях ~, агх~ Ь, »=$ х«»0, хз — целые, )=1», ..., п. 4 Здесь аг и Ь вЂ” положительные целые числа, с; — неотрицательные целые числа. Для решения задачи определим функцию «р»(у) следующим образом: ф,(у)=шах ~' с;ху (1(й(п), »=$ 372 ГЛ 18 ЗАДАЧА О РЮКЗАКЕ где ~ а,х,л.'у (О ='у(Ь). /=1 'Го есть зр» (у) — это максимальное значение целевой функции, когда предметы выбираются иэ первых /с типов, а общий вес выбранных предметов ограничен величиной у. Полагаем зрз (у) = О для всех у (О ~ (у ( Ь), это соответствует случаю, когда не выбрано ни одного предмета; зр» (О) = О для всех /с (О ( й ( и) (случай, когда общий вес рюкзака равен О).
Очевидно, что 1р1 (у) = (у/а1). с,, так как в рюкзак следует полоясить как можно больше предметов 1-го типа. Вообще прн /с 1 для функции зуд(у) справедливо следующее рекурренткое соотношение: зр» (у) = шах (зрд 1 (у), 'ф» (у — а») + с»), (1) Обоснование этого соотношения просто. Когда при получении зрд (у) предметы выбираются из первых /с типов, то предмет й-го типа может оказаться либо выбранным, либо нет. Если он не выбран, то 1р» (у) =зрд 1(у). Если же предмет й-го типа выбран хотя бы один раз, то общий вес остальных предыетов ограничивается величиной у — а».
Очевидно, что этот вес у — ад следует использовать наилучшим образом. Максимальное значение целевой функции, которое можно получить, используя предметы первых й типов, при ограничении у — ад на вес рюкзака, у нас получило обозначение 1р» (у — ад). (Заметим, что мы берем 1р» (у — ад), а не зр» 1 (у — ад), потоыу что предмет /с-го типа может быть выбран несколько раз.) Можно составить таблицу, содерксащую и строк и Ь столбцов, элементами которой являются величины зр» (у) (/с = 1, 2, ...
..., и; у = 1, 2,..., Ь). С помощью рекуррентного соотношения (1) величины зрд (у) можно. подсчитать в следующем порядке: зр1 (1), ф1(2), ..., 1р1(Ь); зрз(1),..., зр,(Ь); ...; ф„(1),... ..., зр„(Ь) '). При вычислениях по формуле (1) полагаем зрд (у) = = — со, если у ( О. После того, как все величины зрд (у) (й = 1, 2,..., и; у = 1, 2,..., Ь) найдены, надо найти значения ху, которые их определяют.
Для этого используется еще одна таблица размера иХЬ. При получении некоторой величины зрд (у) в первой таблице, сразу находится во второй таблице соответствующий элемент 1(й, у). Элементы 1(й, у) второй таблицы имеют следующий смысл: если ((/с, у) = у, то это означает, что предмет )-го типа используется в зрд (у) по крайней мерв один рав. 1) Нетрудно видеть, что величины фд (у) (».( л) зависят от того, как занумерованы предметы.
Но величина фо (Ь) не завкскт от атой нумерации (этот факт следует кз определения функции 1)з (Ь)).— Прим. иерем !8.1, ЗАДАЧА О РЮКЗАКЕ З7З Элементы 1-й строки ! (1, у) второй таблицы получаются по следующему правилу: (О, если !р!(у) =О, 11, если !р1(у)ФО. Остальные элементы 1 (Й, у) второй таблицы получаются по сле- дующему правилу: !(Й вЂ” 1, у), если ф»-!(у) )»р»(у — а»)+с», 1(Й, у)= (1 ) Й, если 1р» 1(у)<»р»(у — а»)+с». Заметим, что если ! (1, у) = 1, то это означает, что предмет 1-го типа используется в»р1(у).
Предположим„например, что ! (Й вЂ” 1, у) = 1. Это значит, что х; ) 1 в»Р» ! (у). Теперь мы хотим знать, какие х„дают 1р» ! (у — а;). находим элемент ! (Й вЂ” 1, у — а!). если 8 (Й вЂ” 1, у — а!) — — 1, то зто значит, что х! ~ )1 в»р» ! (у — а!) (т. е. х! ) 2 в !р» ! (у)). Если жв 8(Й вЂ” 1, у — а.) = д, то это значит, что хз ) 1 в »р» 1(у — а;). Для того чтобы определить, выгодно ли йспользовать предмет Й-го типа в»р» (у), мы сравним значения!у» 1 (у) иф» (у — а») + с». (В этот момент величина 1Р»(у) еще нв известна.) Если в»Р» (у) мы используем предмет Й-го типа хотя бы один раз, то»р»(у) = = »р» (у — а») + с». Таким образом, если »р» ! (у) < $» (у — а»)+ + с», то полагаем 1(Й, у) = Й. Если же !р» 1 (у) )»р» (у — а») + + с», то невыгодно использовать предмет Й-го типа в 1р» (у), и поэтому полагаем ! (Й, у) = 8 (Й вЂ” 1, у).
Заметим, что нам известны величины»р» (0) = 0 и»р (у) = О, следовательно, элементы Й-й строки 2-й матрицы, так же как и значения !р» (у), могут быть найдены один за другим слева направо с помощью соотношений (1) и (1'). Прежде чем сделать несколько замечаний, рассмотрим пример. Пусть имеется четыре предмета, Ь = 10, с, = 1, с, = 3, с, = 5, с, = 9, а, = 2, а, = 3, аз = 4, а, = 7. Заполним первую таблицу, сначала вычисляя элементы 1-й строки слева направо, затем элементы 2-й строки и т. д.
Получим табл. 18 1 и 18.2. Заметим, что при вычислении»р»(10) мы фактически подсчитываем все значения»р» (у) для 1 < Й < 4 и 0 < у < 10. Из табл. 18.1. видим, что »р» (10) = 12. Из табл. 18.2 видим, что ! (4, 10) = 4, т. е. четвертый предмет используется по крайней мере один раз. Чтобы определить, какие предметы дают 1Р! (10), находим 1 (4, 10 — а») = ! (4, 3) = 2 (т. е. второй предмет используется по крайней мере один раз), затем находим 1(4, 3 — а») = ! (4, 0) = = 0 (т. е. »р» (10) получается при использовании только второго и четвертого предмета).
Важной особенностью рассыотренной схемы вычислений является тот факт, что для подсчета .!Р» (у) (О < у < Ь) используются только 1Р» ! (у) (О < у < Ь). ГЛ. 18. ЗАДАЧА О РЮКЗАКЕ 374 Таблица 18.1 Значення «)» (И) Таблица 18.2 Значення 1(7с, у) Следовательно, не нужно запоминать всю таблицу для «р» (у) и можно сразу «забыть» алемвнт «р» 1(у) (й — 1)-й строки, как только подсчитан расположенный под ним элемент «р» (у). Это значительно экономит память вычислительной машины. Такие же рассуждения относятся и ко второй таблице: для нахождения всех х1 достаточно запоминать только ее последнюю строку. Заметим, что в нашем примере 1(4, 8) = 3, т. е.
при Ь = 8 четвертый предмет, имеющии наибольшее отношение — (т. е. макс1 а1 сималькую ценность на единицу веса), вообще не используется. Если на х1 нв наложено условие целочисленности, то задача легко решается следующим образом. Выбирается предмет, обладающий максимальным отношением с1/а1: с„ — "=шах— ас 1 аб Рассмотрим следующее интуитивное решение: сначала заполним рюкзак максимально возможным количеством предметов $-го типа, затем, есЛи позволит ограничение Ь, предметав«и 2-го типа и т. д.
Такое интуитивное решение обычно дает хорошие результаты, но не всегда является оптимальным для задачи с условием цвлочисленпости х1. Ь Затем рюкзак заполняется предметами только этого типа: х, = —. ая Этот подход нельзя испольэовать для решения задачи о рюкзаке с целочисленными х1, поскольку число х, может оказаться нецелым.
Обозначим р1 —— с1/а1 и перенумеруем типы предметов таким образом, чтобы выполнялось следующее условие: 375 18.1. ЗАДАЧА О ГЮКЗАКЕ Интуитивно ясно, что если Ь велико по сравнению с а„то х, ) 0 в оптиввальном решении. Чтобы убедиться в этом, положим, что х, = 0 в оптимальном решении. Тогда максимальное значение, целевой функции, конечно, не превосходит р»Ь. Но если заполнять рюкзак предметами только 1-го типа, то моя«но получить следующее значение целевой функции: Г Ь -1 Ь а>1 Ь вЂ Ь вЂ с>~ — ) с> ( — — — ) =с, =рва> =Р1(Ь вЂ” а,).
(2) «1 '1 ав «1) ав ав Чтобы пайти величину Ь, при которой с, [Ь7а1) ) р1 (Ь вЂ” а,) ) «~ р»Ь, решим относительно Ь уравнение рв (Ь вЂ” а,) = р«Ь. Очевидне, Ь вЂ” Р' ав. Рв — Рв То есть при Ь- Р1 а, выполняется р,(Ь вЂ” а,))р»Ь. Р1 Р» Другими словами, если Ь достаточно велико, то хв- 0 в оптимальном решении. Это значит, что (3) >р„(Ь) = с, )- >(>„(Ь вЂ” а,) при Ъ'= Обозначим через 0 (Ь) разность между оптимальным значением целевой функции вадачи без условия целочисленности и оптимальным значением целевой функции задачи с условием целочясленности: 0 (Ь) = р«Ь — >р„(Ь). В силу (3) при достаточно белы >ком Ь тогда имеем: 0 (Ь вЂ” а,) = р, (Ь вЂ” а,) — >(>„(Ь вЂ” ав) = = Р,Ь вЂ” р,ав — (зР„(Ь) — с,) = = Р„Ь вЂ” р„(Ь) = 0 (Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
