Принятие решений в задачах о загрузке рюкзака - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Справка по результатам изучения вопроса о влиянии позиции Европейского... 1 252.24kb.
I. Принятие решений в условиях неопределенности. Вариант 15. 1 123.98kb.
Программа дисциплины «Принятие политических решений» 4 491.84kb.
Принятие решений руководством в условиях неопределенности из-за отсутствия... 1 171.23kb.
Инструкционно технологическая карта занятия по дисциплине «Менеджмент» 1 38.27kb.
В динамических горно-экономических задачах 1 175.85kb.
Contrôle, от contrerôle список, ведущийся в двух экземплярах 1 129.61kb.
Оптимизация технологических процессов и принятие решений 1 197.88kb.
Волго-вятская академия государственной службы 33 3206.15kb.
Программа дисциплины «Когнитивная психология и принятие решений на... 1 166.11kb.
Организация коллектива исполнителей, принятие управленческих решений 1 24.2kb.
Семинары образования бессознательного (1957/1958) в редакции Жака-Алэна... 13 7916.37kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Принятие решений в задачах о загрузке рюкзака - страница №1/1

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

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

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

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

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

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

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

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



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

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



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

  1. xi≥0, i=1,…,m;



  2. 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, если 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 – вес рюкзака.

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



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

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

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



izumzum.ru