Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач

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

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

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

    (1) (2)

(3)

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

Для этого погрузку "рюкзака" можно интерпретировать как N-этапный процесс принятия решений: на 1-м этапе принимается решение о том, сколько нужно взять груза 1-го вида, на 2-ом этапе - сколько груза 2-го вида и т. д. Такая интерпретация наталкивает на возможность применения для решения задачи (1) - (3) метода динамического программирования. Для этого приведем задачу (1) - (3) к виду (4) - (7) из предыдущей лекции.

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

Y1 = 0. (4)

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

(5)

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

B. (6)

Очевидно ограничения (4) - (6) эквивалентны ограничению (2), поэтому вместо модели (1) - (3) можно рассматривать модель (1), (3) - (6). Здесь ограничение (6) выводит эту модель за рамки модели (4) - (7) из предыдущей лекции. Для сведения задачи к общему виду задач динамич. программирования, запишем (6) с учетом (5):

.

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

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

(7)

В результате исходная модель (1) - (3) свелась к эквивалентной модели вида

    (8) (9)
    (10) (11)

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

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

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

(12).

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

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

(13)

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

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

.

Отсюда:

.

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

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

Пример:

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

Математический загрузка инвестиция беллман

Таблица 1

Предпр. Капитал

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-тому предприятию (). Тогда прибыль, записанная в таблице, можно обозначить как FJ(xJ) (). Например, F1(0)=0; F1(1)=10; F1(2)=17 и т. д. .... F2(0)=0; F2(1)=11; F4(4)=35.

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

ХJ?0 - целые, ()

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

; ()

Y1=0;

; ()

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

1 шаг.

    1) Зафиксируем y4=0. Тогда допустимые значения x4[0, 4-0]=[0,1,2,3,4]. 1.1 ) x4=0. Тогда F4(0)=0. 1.2 ) x4=1. F4(1)=9. 1.3 ) x4=2. F4(2)=19. 1.4 ) x4=3. F4(3)=26 1.5 ) x4=4. F4(4)=35.

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

    2) Зафиксируем y4=1. Тогда допустимые значения x4[0, 4-1]= [0,1,2,3]. 2.1 ) x4=0. Тогда F4(0)=0. 2.2 ) x4=1. F4(1)=9. 2.3 ) x4=2. F4(2)=19. 2.4 ) x4=3. F4(3)=26

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

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

Таблица 2 Шага №1.

Y4 x4

0

1

2

3

4

0

0

9

19

26

35

35

4

1

0

9

19

26

-

26

3

2

0

9

19

-

-

19

2

3

0

9

-

-

-

9

1

4

0

-

-

-

-

0

0

2 шаг.

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

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

    1.2 ) x3=1. Аналогично: F3(1)=10. Найдем y4= y3+ x3=0+1=1. Из таблицы шага 1 определим: =. Сумма F3(1)+ =10+26=36. 1.3 ) x3=2. F3(2)=18. y4=0+2=2. ==19. Тогда F3(2)+ =18+19=37.

1.4 ) x3=3. F3(3)=24, y4=0+3=3. ==9. Тогда

F3(3)+ =24+9=33.

1.5 ) x3=4. F3(4)=34. y4=0+4=4. ==0. Тогда

F3(4)+ =34+0=34.

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

    2) Зафиксируем y3=1. Тогда допустимые значения x3[0, 4-1]= [0,1,2,3]. 2.1 ) x3=0. F3(0)=0. y4=1+0=1. ==26. Тогда F3(0)+ =0+26=26. 2.2 ) x3=1. F3(1)=10. y4=1+1=2. ==19. Тогда F3(1)+ =10+19=29. 2.3 ) x3=2. F3(2)=18. y4=1+2=3. ==9. Тогда F3(2)+ =18+9=27. 2.4 ) x3=3. F3(3)=24 y4=1+3=4. ==0. Тогда F3(3)+ =24+0=24.

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

    3) Зафиксируем y3=2. Тогда допустимые значения x3[0, 4-2]= [0,1,2]. 3.1 ) x3=0. F3(0)=0. y4=2+0=2. f4(2) =19. F3(0)+ f4(2)=0+19=19. 3.2 ) x3=1. F3(1)=10. y4=2+1=3. =9. F3(1)+ =10+9=19. 3.3 ) x3=2. F3(2)=18. y4=2+2=3. =0. F3(2)+ =18+0=18.

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

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

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

Y3 x3

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

3 шаг.

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

Таблица 4 Шага №3.

Y2 x2

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

4 шаг.

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

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

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

Y1 x1

0

1

2

3

4

0

40

40

38

36

36

40

0 (или 1)

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

    1) y1=0, x1*=0, y2*= y1+ x1*=0+0=0. 2) Определяем значение x2* из таблицы шага № 3 по найденному y2*=0. Значению y2= y2*=0 соответствует значение x2(y2)=1. Следовательно, x2*=1. Далее можно определить y3*= y2*+ x2*=0+1=1. 3) Аналогично, обращаясь к таблице шага №2, найдем: x3*= x3(1)=1, y4*= y3*+ x3*=1+1=2. 4) Из таблицы шага №1 : x4*= x4(2)=2.

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

==40.

Похожие статьи




Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач

Предыдущая | Следующая