Принятие решений в задачах о загрузке рюкзака

Принятие решений в задачах о загрузке рюкзака.

Рюкзак грузоподъемности b загружается набором предметов из m наименований. Известны величины:

ai – вес i-го предмета, ci – ценность i-го предмета.

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

Набором предметов охарактеризуем вектором X=(x1, x2, …, xi, …, xm),

где xi – количество i-го предмета.

Ценность рюкзака обозначим через

где xi – целые, xi≥0, i=1, …, m;

- суммарный вес загружаемых предметов ≤ b.

Математическая модель:

на X=(x1, x2, …, xm):

xi≥0, i=1,…,m; xi – целые.

Наиболее эффективный метод решения данной задачи основан на динамическом приеме, который опирается на принцип оптимальности Беллмана.

Принцип оптимальности:

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

Грузоподъемность рюкзака b разобьем с некоторым шагом h на части:

Z=0,h,2h,…,z0,z0+h,…,b,

где

Возьмем промежуточное значение Z.

f(z) – оптимальная ценность рюкзака грузоподъемности Z.

Поместим в такой рюкзак i-й предмет, вес которого ai, ценность ci. Это первое принятое решение. Тогда по принципу оптимальности Беллмана оставшаяся часть (z-ai) должна быть загружена оптимальным образом.

Оптимальная ценность такого рюкзака f(z-ai).

Суммарная ценность равна ci+f(z-ai).

В качестве , f(z)=0, если z<z0.

Процесс решения состоит из 2-х этапов:

I этап (прямой ход)

z	F(z)	I(z)
0	F(0)	I(0)
…	…	…
h	F(h)	I(h)
…	…	…
z0	F(z0)	I(z0)
…	…	…
b	F(b)	I(b)

I(z0) – набор предметов, на котором достигается максимума правая часть рекуррентного соотношения.

II этап – формируется набор загружаемых элементов.

Пример.

Пусть заданы ценности предметов c1 = 7, c2 = 5, c3 = 8 и веса предметов a1 = 5, a2 = 2, a3 =3. Требуется оптимально загрузить рюкзак грузоподъемности b = 19.

Z	0	1	2	3	4	5	6	7	8
f(z)	0	0	5	8	10	13	16	18	21
i(z)	0	0	2	3	2	2,3	3	2,3	2,3

Z	9	10	11	12	13	14	15	16	17
f(z)	24	26	29	32	34	37	40	42	45
i(z)	3	2,3	2,3	3	2,3	2,3	3	2,3	2,3

Z	18	19
f(z)	48	50
i(z)	3	2,3

Прямой ход:

z0=min{5,2,3}=2, z = 2, ai ≤ 2, i = 2, f(0)=f(1)=0

f(2) = max{c2+f(2-a2)}=max{5+f(0)}=5

z=3, ai ≤ 3, i=2,3

f(3) = max{c2+f(3-a2), c3+f(3-a3)}=max{10,8}=10

z=4, ai ≤ 4, i=2,3

f(4) = max{c2+f(4-a2), c3+f(4-a3)}=max{5,8}=8

z=5, ai ≤ 5, i=1,2,3

f(5) = max{c1+f(5-a1), c2+f(5-a2), c3+f(5-a3)}=max{7,13,13}=13

z=6, ai ≤ 6, i=1,2,3

f(6) = max{c1+f(6-a1), c2+f(6-a2), c3+f(6-a3)}=max{7,15,16}=16

z=7, ai ≤ 7, i=1,2,3

f(7) = max{c1+f(7-a1), c2+f(7-a2), c3+f(7-a3)}=max{12,18,18}=18

z=8, ai ≤ 8, i=1,2,3

f(8) = max{c1+f(8-a1), c2+f(8-a2), c3+f(8-a3)}=max{15,21,21}=21

z=9, ai ≤ 9, i=1,2,3

f(9) = max{c1+f(9-a1), c2+f(9-a2), c3+f(9-a3)}=max{17,23,24}=24

z=10, ai ≤ 10, i=1,2,3

f(10) = max{c1+f(10-a1), c2+f(10-a2), c3+f(10-a3)}=max{20,26,26}=26

z=11, ai ≤ 11, i=1,2,3

f(11) = max{c1+f(11-a1), c2+f(11-a2), c3+f(11-a3)}=max{23,29,29}=29

z=12, ai ≤ 12, i=1,2,3

f(12) = max{c1+f(12-a1), c2+f(12-a2), c3+f(12-a3)}=max{25,31,32}=32

z=13, ai ≤ 13, i=1,2,3

f(13) = max{c1+f(13-a1), c2+f(13-a2), c3+f(13-a3)}=max{28,34,34}=34

z=14, ai ≤ 14, i=1,2,3

f(14) = max{c1+f(14-a1), c2+f(14-a2), c3+f(14-a3)}=max{31,37,37}=37

z=15, ai ≤ 15, i=1,2,3

f(15) = max{c1+f(15-a1), c2+f(15-a2), c3+f(15-a3)}=max{33,39,40}=40

z=16, ai ≤ 16, i=1,2,3

f(16) = max{c1+f(16-a1), c2+f(16-a2), c3+f(16-a3)}=max{36,42,42}=42

z=17, ai ≤ 17, i=1,2,3

f(17) = max{c1+f(17-a1), c2+f(17-a2), c3+f(17-a3)}=max{39,45,45}=45

z=18, ai ≤ 18, i=1,2,3

f(18) = max{c1+f(18-a1), c2+f(18-a2), c3+f(18-a3)}=max{41,47,48}=48

z=19, ai ≤ 19, i=1,2,3

f(19) = max{c1+f(19-a1), c2+f(19-a2), c3+f(19-a3)}=max{44,50,50}=50

Обратный ход: b=19, несколько решений, выбирается любое, например, a2=2

b=17, a2=2; b=15, a3=3; b=12, a3=3; b=9, a3=3; b=6, a3=3; b=3, a3=3; b=0

µ(x)=0+2*5+5*8=50

Ответ. x=(0,2,5) – оптимальная загрузка, 50 – вес рюкзака.

Решить самостоятельно:

Пусть заданы ценности предметов c1 = 12, c2 = 20, c3 = 15 и веса предметов a1 = 3, a2 = 4, a3 = 5. Требуется оптимально загрузить рюкзак грузоподъемности b = 15. Пусть заданы ценности предметов c1 = 10, c2 = 15, c3 = 11 и веса предметов a1 = 2, a2 = 3, a3 = 4. Требуется оптимально загрузить рюкзак грузоподъемности b = 20. Пусть заданы ценности предметов c1 = 5, c2 = 7, c3 = 4, c4 = 8 и веса предметов a1 = 2, a2 = 3, a3 = 4, a4 = 5. Требуется оптимально загрузить рюкзак грузоподъемности b = 10.