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

Пусть имеются N видов грузов с номерами .

Единица груза j -го вида имеет все a_j. Если груз j-го вида берется в количестве x_j, то его ценность в общем случае составляет F (x_j). Имеется «рюкзак», грузоподъемность которого равна B. Требуется загрузить рюкзак имеющимися грузами таким образом, чтобы вес его был не больше заданного B, а ценность «рюкзака» была максимальной.

Составим математическую модель задачи. Пусть x_j – количество груза j -го вида, помещаемого в рюкзак. Тогда можно записать:

(3.15)

(3.16)

(3.17)

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

Для этого погрузку «рюкзака» можно интерпретировать как N -этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе – сколько груза 2-го вида и т.д. Такая интерпретация наталкивает на возможность применения для решения задачи (3.15) – (3.17) метода динамического программирования. Для этого приведем задачу (3.15) – (3.17) к виду (3.4) – (3.7).

Для этого введем обозначения: – вес рюкзака перед погрузкой груза j -го вида груза или вес рюкзака после погрузки грузов видов 1, 2, …, j – 1.Очевидно, что

y ₁ = 0. (3.18)

Текущий вес рюкзака определяется выражением

(3.19)

Текущий вес рюкзака в силу (3.16) удовлетворяет неравенству

£ B. (3.20)

Очевидно ограничения (3.18) – (3.20) эквивалентны ограничению (3.16), поэтому вместо модели (3.15) – (3.17) можно рассматривать модель (3.15), (3.17) – (3.20). Здесь ограничение (3.20) выводит эту модель за рамки модели (3.4) – (3.7). Для сведения задачи к общему виду задач динамического программирования, запишем (3.20) с учетом (3.19):

Отсюда следует: ,

или окончательно с учетом (3.17):

(3.21)

В результате исходная модель (3.15) – (3.17) свелась к эквивалентной модели вида

(3.22)

(3.23)

(3.24)

(3.25)

Задача (3.22)-(3.25) является частным случаем общей задачи динамического программирования, в которой . Здесь ограничение (3.23) является рекуррентным и отражает процесс загрузки рюкзака, а неравенство (3.24) задает область возможных значений .

Рассмотрим решение задачи (3.22)-(3.25) методом динамического программирования:

1 шаг. Вычисляется величина

(3.26)

В результате решения серии задач максимизации получаем точки максимума и значения .

S -тый шаг (). Вычисляются величины

(3.27)

В результате решения серии задач максимизации, получаем и . При s =1 решается только одна задача на максимум, т.к. значение - задано.

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

Отсюда:

Далее: . И так далее . Причем есть максимальное значение целевой функции.

Наличие условия целочисленности переменных x_j и упрощает решение задачи. В этом случае . Здесь [ В ] указывает на то, что берется целая часть числа. Если не целые, то .

Пример:

Имеется свободный капитал в размере 4 млн. у.е. Этот капитал может быть распределен между 4-мя предприятиями, причем распределение осуществляется только целыми частями (0, 1, 2, 3 или 4 млн. у.е.). Прибыль, получаемая каждым предприятием при инвестировании в него определенной суммы, указана в таблице.

_{Предпр.} ^{Капитал}	0 млн. у.е.	1 млн. у.е.	2 млн. у.е.	3 млн. у.е.	4 млн. у.е.
1-е предпр.	0	10	17	25	36
2-е предпр.	0	11	16	25	35
3-е предпр.	0	10	18	24	34
4-е предпр.	0	9	19	26	35

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

Обозначим: х _j - количество капиталовложений, выделенных j -тому предприятию (). Тогда прибыль, записанная в таблице, можно обозначить как F_j (x_j) (). Например, F₁(0)=0; F₁(1)=10; F₁(2)=17 и т.д..... F₂(0)=0; F₂(1)=11; F₄(4)=35.

Тогда математическая модель примет вид:

х _j ≥ 0 – целые, ()

Данная модель является частным случаем задачи о загрузке рюкзака, где N =4, В=4, а _j =1 (). Введя новую переменную y_j - израсходованные средства до выделения капиталовложений j -тому предприятию, приведем исходную модель к виду задачи динамического программирования:

; ()

y ₁ = 0;

; ()

Решение задачи проведем в соответствии с алгоритмом динамического программирования:

Шаг.

1) Зафиксируем y ₄ =0. Тогда допустимые значения x ₄ Î [0, 4-0] =[0,1,2,3,4].

1.1) x ₄ =0. Тогда F ₄ (0)=0.

1.2) x ₄ =1. F ₄ (1)=9.

1.3) x ₄ =2. F ₄ (2)=19.

1.4) x ₄ =3. F ₄ (3)=26

1.5) x ₄ =4. F ₄ (4)=35.

Максимальное значение , и достигается оно при x ₄ =4. Таким образом, заполняется первая строчка таблицы.

2) Зафиксируем y₄=1. Тогда допустимые значения x ₄ Î [0, 4-1]= [0,1,2,3].

2.1) x ₄ =0. Тогда F ₄ (0)=0.

2.2) x ₄ =1. F ₄ (1)=9.

2.3) x ₄ =2. F ₄ (2)=19.

2.4) x ₄ =3. F ₄ (3)=26.

Максимальное значение , и достигается оно при x ₄ =3. Таким образом, заполняется вторая строка таблицы.

Далее аналогично фиксируем y ₄ =2, y ₄ =3, y ₄ =4. Заполняем оставшиеся строки таблицы.

Таблица шага №1.

y₄x₄	1	2	3	4
0	9	19	26	35	35	4
1	9	19	26	-	26	3
2	9	19	-	-	19	2
3	9	-	-	-	9	1
4	-	-	-	-	0	0

Шаг.

1) Зафиксируем y ₃ =0. Тогда допустимые значения x ₃ Î [0, 4-0] =[0,1,2,3,4].

1.1) x ₃ =0. Тогда F ₃ (0)=0. Определим значение второго слагаемого: при y ₃ =0 и x ₃ =0. Найдем y ₄ =0+0=0. Тогда, обратившись к таблице шага 1, увидим, что . Следовательно, F ₃ (0)+ =0+35=35. Этот результат заносим в таблицу шага 2 в ячейку, соответствующую y ₃ =0 и x ₃ =0.

1.2) x ₃ =1. Аналогично: F ₃ (1)=10. Найдем y ₄ = y ₃ + x ₃ =0+1=1. Из таблицы шага 1 определим: = . Сумма F ₃ (1)+ =10+26=36.

1.3) x ₃ =2. F ₃ (2)=18. y ₄ =0+2=2. Þ = = 19. Тогда F ₃ (2)+ =18+19=37.

1.4) x ₃ =3. F ₃ (3)=24, y ₄ =0+3=3. Þ = = 9. Тогда F ₃ (3)+ =24+9=33.

1.5) x ₃ =4. F ₃ (4)=34. y ₄ =0+4=4. Þ = =0. Тогда F ₃ (4)+ =34+0=34.

Максимальное значение =37, и достигается оно при x ₃ =2. Первая строчка таблицы заполнена.

2) Зафиксируем y ₃ =1. Тогда допустимые значения x ₃ Î [0, 4-1]= [0,1,2,3].

2.1) x ₃ =0. F ₃ (0)=0. y ₄ =1+0=1. Þ = =26. Тогда F ₃ (0)+ =0+26=26.

2.2) x ₃ =1. F ₃ (1)=10. y ₄ =1+1=2. Þ = = =19. Тогда F ₃ (1)+ =10+19=29.

2.3) x ₃ =2. F ₃ (2)=18. y ₄ =1+2=3. Þ = =9. Тогда F₃(2)+ =18+9=27.

2.4) x ₃ =3. F ₃ (3)=24 y ₄ =1+3=4. Þ = =0. Тогда F ₃ (3)+ =24+0=24.

Максимальное значение , и достигается оно при x ₃ =1. Таким образом, заполняется вторая строка таблицы.

3) Зафиксируем y ₃ =2. Тогда допустимые значения x ₃ Î [0, 4-2]= [0,1,2].

3.1) x ₃ =0. F ₃ (0)=0. y ₄ =2+0=2. Þ f₄(2) = 19. F ₃ (0)+ f₄(2) =0+ 19 = 19.

3.2) x ₃ =1. F ₃ (1)=10. y ₄ =2+1=3. Þ =9. F ₃ (1)+ =10+9= 1 9.

3.3) x ₃ =2. F ₃ (2)=18. y ₄ = 2 +2=3. Þ = 0. F ₃ (2)+ =18+ 0 = 18.

Максимальное значение достигается при двух возможных значениях x ₃: x ₃ =1 и x ₃ =0. В таблицу можно занести любое из них. Таким образом, заполняется третья строка таблицы.

Далее аналогично фиксируем y ₃ =3, y ₃ =4. Заполняем оставшиеся строки таблицы.

Таблица шага №2.

y₃x₃	0	1	2	3	4
0	35	36	37	33	34	37	2
1	26	29	27	24	-	29	1
2	19	19	18	-	-	19	0 (или 1)
3	9	10	-	-	-	10	1
4	0	-	-	-	-	0	0

Шаг.

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

Таблица шага №3.

y₂x₂	0	1	2	3	4
0	37	40	35	35	35	40	1
1	29	30	26	25	-	30	1
2	19	21	16	-	-	21	1
3	10	11	-	-	-	11	1
4	0	-	-	-	-	0	0

Шаг.

Последний шаг интересен тем, что здесь решается единственная задача максимизации при заданном y ₁ =0.

y ₁ =0. Следовательно x ₁ Î [0, 4-0]= [0,1,2,3,4]. Выполняя все действия, аналогично предыдущим шагам, получим таблицу последнего шага, состоящую из единственной строки, соответствующей y ₁ =0.

Таблица шага №4.

y₁x₁	0	1	2	3	4
0	40	40	38	36	36	40	0 (или 1)

Далее проводим обратное движение алгоритма:

1) y₁=0, x₁*=0, Þ y₂*= y₁+ x₁*=0+0=0.

2) Определяем значение x₂* из таблицы шага № 3 по найденному y ₂ *=0. Значению y ₂ = y ₂ *=0 соответствует значение x ₂ (y ₂)=1. Следовательно, x ₂ *=1. Далее можно определить y ₃ *= y ₂ *+ x ₂ *=0+1=1.

3) Аналогично, обращаясь к таблице шага №2, найдем: x ₃ *= x ₃ (1)=1, Þ y ₄ *= y ₃ *+ x ₃ *=1+1=2.

4) Из таблицы шага №1: x ₄ *= x ₄ (2)=2.

Окончательно имеем: первому предприятию средства не выделяются (x ₁ *=0), второму выделяется 1 млн. у.е. (x ₂ *=1), третьему предприятию – 1 млн. у.е. (x ₃ *=1), и четвертому – 2 млн. у.е. (x ₄ *=2). При этом значение целевой функции (общая прибыль по всем 4-м предприятиям) составит:

= =40.