Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл (16,20Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 200

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

18.1.

ЗАДАЧА О РЮКЗАКЕ

373

Элементы 1-й строки i (1, у) второй таблицы получаются по сле

дующему

правилу:

ГО,

если

==°,

Н ’

1 1 ,

если ф ^ ^ О .

Остальные элементы i {к,

у) второй таблицы получаются по сле

дующему

правилу:

i{k — 1 , у),

если

t y h - i ( y ) > t y k ( y —

a h) + ch,

(!')

к,

если

tyh-i(y)s^tyk(y —ah) + ck.

Заметим,

что

если

i (1,

у)

= 1,

то это означает, что

предмет

1-го типа

используется

в ф4 (у).

Предположим,

например,

что

i (к — 1,

у) = у. Это значит, что

Xj ^

в ф ц

(у). Теперь

мы

хотим

знать,

какие

ха

дают

(у — а3).

Находим

элемент

i (к — 1, у — а^. Если i (к — 1,

у — aj) ==/, то

это значит, что

^ 1

грй_1 (у — а,)

(т. е.

х} ^ 2

фй_!

(у))-

Если

же

г (к — 1 , у — a}) ~ q ,

то

это значит, что х,

^ 1

(у — Oj).

Для того чтобы определить, выгодно

ли

использовать

предмет

к-то типа вфА(у), мы сравним значения фА_1

{у) ифй (у — ah) + ck.

(В этот момент величина фй (у) еще не известна.) Если

в ф* {у)

мы используем предмет к-то типа хотя бы один раз,

то

фй(у) =

Фа (*/ — ak) + ch. Таким образом, если ф ц <г/) < ф й (у — ah)+

cft, то полагаем i ( к , у) = к .

Если же фЛ_! (у) > фk (у — а*) +

сА,

то

невыгодно

использовать предмет

к-то

типа

в фй (у),

и поэтому полагаем i ( к , у) =

(к — 1, у).

Заметим,

что

нам

известны

величины фй (0 ) = 0 и ф0 {у) — 0 ,

следовательно,

эле

менты к- й строки 2 -й матрицы, так же как и значения ф& (у),

могут быть найдены один за другим слева направо с помощью соотношений (1 ) и (1 ').

Прежде чем сделать несколько замечаний, рассмотрим пример.

Пусть имеется	четыре предмета,	b = 10, щ = 1, с2 = 3, с3 = 5,
с4 = 9, cj = 2,	а2 = 3, а3 = 4, а4	= 7. Заполним первую таблицу,

сначала вычисляя элементы 1 -й строки слева направо, затем

элементы 2-й строки и т. д. Получим табл. 18.1 и 18.2. Заметим, что при вычислении ф4 (1 0 ) мы фактически подсчитываем все

значения фй (у) для	l ^	f c ^ 4 и	О ^ у ^ Ю . Из табл.	18.1.
видим, что ф4 (10) =	12.	Из табл.	18.2 видим, что i (4, 10)	= 4,

т. е. четвертый предмет используется по крайней мере один раз.


Чтобы	определить,		какие предметы дают				ф4 (10),		находим
i (4, 10 — а4) =		г (4, 3) =		2 (т. е.	второй	предмет		используется
по крайней мере один раз), затем находим i						(4;	3 — а3) = г (4, 0) =
= 0 (т. е. ф4 (1 0 ) получается при использовании только									второго
и четвертого предмета).				Важной	особенностью			рассмотренной
схемы	вычислений		является тот		факт, что для подсчета
Фа (у )	(0 < 1 у ^	Ъ)	используются		только	фд_1 (у) (0 ^			у ^ Ъ).

374							ГЛ. 18.			ЗАДАЧА О РЮКЗАКЕ
		Т а б л и ц а 1 8 . 1												Т а б л и ц а 1 8 . 2
		Значения гр/, ( у )											Значения				г ( к ,		у )
У	1	2	3	4 5 6 7 8					9 10			N . у	1 2		3	4	5	6	7	8	9	10
к N ^	1	2	3	4 5 6 7 8					9 10			к N .	1 2		3	4	5	6	7	8	9	10
1	0	1	1	2	2	3	3	4		4	5	1	0	1	1	1	1	1	1	1	1	1
2	0	1	3	3	4	6	6	7		9	9	2	0	1	2	2	2	2	2	2	2	2
3	0	1	3	5	5	6	8	10		10	11	3	0	1	2	3	3	3	3	3	3	3
4	0	1	3	5	5	6	9	10		10	12	4	0	1	2	3	3	3	4	3	4	4
Следовательно,					не		нужно				запоминать		всю		таблицу				для			(у)
и можно		сразу			«забыть»					элемент -фй_! (у)				(к — 1 )-й				строки,				как

только подсчитан расположенный под ним элемент г|зА(у). Это значительно экономит память вычислительной машины. Такие же рассуждения относятся и ко второй таблице: для нахождения всех Xj достаточно запоминать только ее последнюю строку.

Заметим, что в нашем примере i (4, 8 ) = 3, т. е. при Ъ = 8

четвертый предмет, имеющий наибольшее отношение — (т. е. мак-

a J

симальную ценность на единицу веса), вообще не используется. Если на xj не наложено условие целочисленности, то задача легко решается следующим образом. Выбирается предмет, обла

дающий максимальным отношением

Сг	С1
—— = т а х — .
ат	■j «}

Затем рюкзак заполняется предметами только этого типа: хт— — .

а г

Этот подход нельзя использовать для решения задачи о рюкзаке с целочисленными xj, поскольку число хтможет оказаться нецелым. Обозначим = Cj/aj и перенумеруем типы предметов таким обра зом, чтобы выполнялось следующее условие:

Pi ss*5 Р2 sS* рз =s== • • •

Нп-

Рассмотрим следующее интуитивное решение: сначала заполним рюкзак максимально возможным количеством предметов 1 -го типа, затем, если позволит ограничение Ь, предметами 2 -го типа и т. д.

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

18.1.	ЗАДАЧА О РЮКЗАКЕ	375
Интуитивно ясно, что	если Ъ велико по сравнению	с а1, то

Xi > 0 в оптимальном решении. Чтобы убедиться в этом, положим, что = 0 в оптимальном решении. Тогда максимальное значе ние целевой функции, конечно, не превосходит р2Ь. Но если заполнять рюкзак предметами только 1 -го типа, то можно полу

чить следующее значение целевой функции:

Ci [■-к] >Ci ( -гг-	^ ) =с*	=pi {b~ ai)• (2)
Чтобы найти величину Ъ, при		которой Cj [b/aJ >	р4 (Ь — аД ^
^ р2Ь, решим относительно Ъ уравнение
Очевидно,	Pi (Ь — яД = р2Ь.

То есть при b^i	at выполняется рДб—йД ^ р zb.
Другими словами, если Ъ достаточно велико, то			Xi > 0 в оп
тимальном решении. Это значит, что
фп (Ь) =	Ci -г (Ь —	яД при

Обозначим через 0 (b) разность между оптимальным значением целевой функции задачи без условия целочисленности и опти мальным значением целевой функции задачи с условием цело численности: 0 (b) = piЪ—ф„ (b). В силу (3) при достаточно боль шом Ь тогда имеем:

6 (Ь— яД = Pi (b — яД —ф„ (Ь— яД =

= P i b — Pi«i — (ф„ ( Ь )— с Д =

= Pi& —ф„ (Ь) = 0 (b).

Отсюда видно, что функция 0 (Ь) периодична и имеет период ait когда Ъдостаточно велико. Функция 0 (Ъ) определена и в случае, когда b < p1a±/(pi — р2). Для функции 0 (Ъ) можно получить

рекуррентное соотношение следующим образом. Предположим, что в оптимальном целочисленном решении некоторое х3 > (). Тогда 0 (Ъ) = 0 (b — яД + (pt — рД а3, где (pj — рД а3 — потери за счет того, что вес а3 «заполнен» не первым, а /-м предметом. Так как в оптимальном решении какое-то х3 > 0, то 0 (Ъ) полу чается следующим образом:

0 (Ь) = min {0 (Ь — а 3) + (pt— рД яД.

( 4 )

376	ГЛ. 18. ЗА Д А ЧА О РЮКЗАКЕ

Выражение (4) является рекуррентным соотношением, в котором 0 (Ъ) могут быть подсчитаны для любых Ъ. Рассмотрим пример:

ci =	18,	с2=	14,	сз =	8 ,	с4 = 4,		с5	=	О,
«1 =	15,	а2 =	12,	а3 =	7,	а4 =	4,	а5	=	1,
Pi =	1>2,	р2=	1,166,	Рз =	1,142,	р4 =	1,	р3 =		0.
Здесь				18
				18
		Pi		15	• 15 =	540.
		Pi			• 15 =	540.
		Pi — Рг		18__14
				15	12

Оценка 540 является достаточной, но не является необходимой. Это значит, что для двух величин Ь и Ъ', где Ъ> Ъ' ^ 540 и Ъ' = = Ъ(mod ai), оптимальные целочисленные решения будут почти одинаковыми, отличаясь лишь тем, что в оптимальном решении для величин Ъчасть Ъ— V общего веса будет приходиться на пер

вый предмет.	Будем вычислять .0 (Ь)	для последовательных		зна
чений Ъ= 0 ,	1, 2, . . . . Тогда можно убедиться, что 0		(Ъ) является
периодической функцией, а именно,		0 (Ь) = 0 (Ь +	15) при	Ъ^
^ 26 (см. табл. 18.3).