Имеется склад, на котором присутствует некоторый ассортимент товаров. Запас каждого товара неограничен. У каждого товара своя стоимость Ci и масса mi. Методом динамического программирования сформировать такой набор товаров, чтобы его суммарная масса не превышала заданную грузоподъемность М, и стоимость была бы максимальной.
|
Номер товара, i
|
mi
|
Ci
|
M
|
|
1
|
13
|
36
|
23
|
|
2
|
5
|
13
|
|
3
|
4
|
11
|
I этап. Условная оптимизация.
f3(L) = max(11x3); 0 < x3 < [23/4]; x3 = 0,1,2,3,4,5.
f3(0) = max[0*11] = 0
f3(1) = max[0*11] = 0
f3(2) = max[0*11] = 0
f3(3) = max[0*11] = 0
f3(4) = max[0*11, 1*11] = 11
f3(5) = max[0*11, 1*11] = 11
f3(6) = max[0*11, 1*11] = 11
f3(7) = max[0*11, 1*11] = 11
f3(8) = max[0*11, 1*11, 2*11] = 22
f3(9) = max[0*11, 1*11, 2*11] = 22
f3(10) = max[0*11, 1*11, 2*11] = 22
f3(11) = max[0*11, 1*11, 2*11] = 22
f3(12) = max[0*11, 1*11, 2*11, 3*11] = 33
f3(13) = max[0*11, 1*11, 2*11, 3*11] = 33
f3(14) = max[0*11, 1*11, 2*11, 3*11] = 33
f3(15) = max[0*11, 1*11, 2*11, 3*11] = 33
f3(16) = max[0*11, 1*11, 2*11, 3*11, 4*11] = 44
f3(17) = max[0*11, 1*11, 2*11, 3*11, 4*11] = 44
f3(18) = max[0*11, 1*11, 2*11, 3*11, 4*11] = 44
f3(19) = max[0*11, 1*11, 2*11, 3*11, 4*11] = 44
f3(20) = max[0*11, 1*11, 2*11, 3*11, 4*11, 5*11] = 55
f3(21) = max[0*11, 1*11, 2*11, 3*11, 4*11, 5*11] = 55
f3(22) = max[0*11, 1*11, 2*11, 3*11, 4*11, 5*11] = 55
f3(23) = max[0*11, 1*11, 2*11, 3*11, 4*11, 5*11] = 55
Таблица 1 – Расчет значения функции f1(L)
| L |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| f3(L) |
0 |
0 |
0 |
0 |
11 |
11 |
11 |
11 |
22 |
22 |
22 |
22 |
33 |
33 |
33 |
33 |
44 |
44 |
44 |
44 |
55 |
55 |
55 |
55 |
| x3 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
f2(L) = max[13x2 + f3(L - 5x2)]; 0 < x2 < [23/5]; x2 = 0,1,2,3,4.
f2(0) = max[0*13+0] = 0
f2(1) = max[0*13+0] = 0
f2(2) = max[0*13+0] = 0
f2(3) = max[0*13+0] = 0
f2(4) = max[0*13+11] = 11
f2(5) = max[0*13+11, 1*13+0] = 13
f2(6) = max[0*13+11, 1*13+0] = 13
f2(7) = max[0*13+11, 1*13+0] = 13
f2(8) = max[0*13+22, 1*13+0] = 22
f2(9) = max[0*13+22, 1*13+11] = 24
f2(10) = max[0*13+22, 1*13+11, 2*13+0] = 26
f2(11) = max[0*13+22, 1*13+11, 2*13+0] = 26
f2(12) = max[0*13+33, 1*13+11, 2*13+0] = 33
f2(13) = max[0*13+33, 1*13+22, 2*13+0] = 35
f2(14) = max[0*13+33, 1*13+22, 2*13+11] = 37
f2(15) = max[0*13+33, 1*13+22, 2*13+11, 3*13+0] = 39
f2(16) = max[0*13+44, 1*13+22, 2*13+11, 3*13+0] = 44
f2(17) = max[0*13+44, 1*13+33, 2*13+11, 3*13+0] = 46
f2(18) = max[0*13+44, 1*13+33, 2*13+22, 3*13+0] = 48
f2(19) = max[0*13+44, 1*13+33, 2*13+22, 3*13+11] = 50
f2(20) = max[0*13+55, 1*13+33, 2*13+22, 3*13+11, 4*13+0] = 55
f2(21) = max[0*13+55, 1*13+44, 2*13+22, 3*13+11, 4*13+0] = 57
f2(22) = max[0*13+55, 1*13+44, 2*13+33, 3*13+11, 4*13+0] = 59
f2(23) = max[0*13+55, 1*13+44, 2*13+33, 3*13+22, 4*13+0] = 61
Таблица 2 – Расчет значения функции f2(L)
| L |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| f2(L) |
0 |
0 |
0 |
0 |
11 |
13 |
13 |
13 |
22 |
24 |
26 |
26 |
33 |
35 |
37 |
39 |
44 |
46 |
48 |
50 |
55 |
57 |
59 |
61 |
| x2 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
2 |
2 |
0 |
1 |
2 |
3 |
0 |
1 |
2 |
3 |
0 |
1 |
2 |
3 |
f1(L) = max[36x1 + f2(L - 13x1)]; 0 < x1 < [23/13]; x1 = 0,1.
f1(0) = max[0*36+0] = 0
f1(1) = max[0*36+0] = 0
f1(2) = max[0*36+0] = 0
f1(3) = max[0*36+0] = 0
f1(4) = max[0*36+11] = 11
f1(5) = max[0*36+13] = 13
f1(6) = max[0*36+13] = 13
f1(7) = max[0*36+13] = 13
f1(8) = max[0*36+22] = 22
f1(9) = max[0*36+24] = 24
f1(10) = max[0*36+26] = 26
f1(11) = max[0*36+26] = 26
f1(12) = max[0*36+33] = 33
f1(13) = max[0*36+35, 1*36+0] = 36
f1(14) = max[0*36+37, 1*36+0] = 37
f1(15) = max[0*36+39, 1*36+0] = 39
f1(16) = max[0*36+44, 1*36+0] = 44
f1(17) = max[0*36+46, 1*36+11] = 47
f1(18) = max[0*36+48, 1*36+13] = 49
f1(19) = max[0*36+50, 1*36+13] = 50
f1(20) = max[0*36+55, 1*36+13] = 55
f1(21) = max[0*36+57, 1*36+22] = 58
f1(22) = max[0*36+59, 1*36+24] = 60
f1(23) = max[0*36+61, 1*36+26] = 62
Таблица 3 – Расчет значения функции f3(L)
| L |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
22 |
23 |
| f1(L) |
0 |
0 |
0 |
0 |
11 |
13 |
13 |
13 |
22 |
24 |
26 |
26 |
33 |
36 |
37 |
39 |
44 |
47 |
49 |
50 |
55 |
58 |
60 |
62 |
| x1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
II этап. Безусловная оптимизация.
Таким образом, максимальная стоимость груза f1(23) равна 62 денежным единицам.
При этом x1 = 1, так как f1(23) = 62 достигается при х1=1 (см. таблицу 3).
Предметы остальных типов распределяются следующим образом:
L = 23 - 13 * 1 = 10
f2(10) = 26 достигается при х2 = 2 (см. таблицу 2).
L = 10 - 5 * 2 = 0
f3(0) = 0 достигается при х3 = 0 (см. таблицу 1).
L = 0 - 4 * 0 = 0
В итоге наилучший вариант загрузки транспортного средства достигается при значениях: x1 = 1, x2 = 2, x3 = 0 Ответ: набор товаров с максимальной стоимостью: первый товар в количестве одной штуки, второй товар в количестве двух ед.
Решение было получено и оформлено с помощью сервиса:
Задача о рюкзаке
Вместе с этой задачей решают также:
Задача оптимального распределения инвестиций
Задача замены оборудования
Метод прямой и обратной прогонки
Линейное программирование онлайн
Теория массового обслуживания (СМО)
Теория игр
|