- •Варианты заданий
- •Данные для решения задачи с булевыми переменными: возможный объем реализации запчастей типа а – 1; 2 ед., типа б– 3; 6 ед., типа в – 1; 3; 4; 6; 9 ед.
- •1.4. Варианты заданий линейного программирования
- •Варианты заданий
- •2.3. Варианты заданий динамического программирования
- •Варианты заданий
- •3.5 Варианты заданий сетевого планирования
2.3. Варианты заданий динамического программирования
Перечень вопросов, подлежащих рассмотрению в теоретической части:
Суть метода динамического программирования.
Задача о рюкзаке. Уравнение Беллмана для задачи о рюкзаке.
Реализации метода динамического программирования для задачи о рюкзаке.
Содержимое расчетной части:
Решение задачи динамического программирования с помощью уравнений Беллмана.
Выводы после решения задачи.
Перечень вопросов для защиты:
как формулируется задача динамического программирования и в чем ее отличие от задач линейного программирования?
в чем заключаются особенности математической модели ДП?
что лежит в основе метода ДП?
что понимается под оптимальным управлением в задачах ДП
что такое «аддитивный» критерий в задачах ДП
Варианты заданий
Задача 2. Исходные данные (динамическая задача). В квадратных скобках – номер варианта.
Имеются 5 предметов и рюкзак, способный выдержать В кг. Каждый предмет весит аi кг и стоит сi руб. Требуется оптимально заполнить рюкзак предметами, не превысив его веса.
Стоимость, сi |
вариант |
c1 |
c2 |
c3 |
c4 |
c5 |
Вместимость рюкзака (В) |
1 |
24 |
30 |
100 |
120 |
160 |
2,5 |
|
2 |
13 |
15 |
60 |
70 |
110 |
1,6 |
|
3 |
27 |
50 |
55 |
80 |
90 |
2,4 |
|
4 |
38 |
60 |
70 |
110 |
80 |
3,2 |
|
5 |
53 |
48 |
100 |
105 |
90 |
3 |
|
6 |
32 |
40 |
70 |
50 |
30 |
8 |
|
7 |
75 |
60 |
50 |
80 |
100 |
1 |
|
8 |
55 |
60 |
40 |
50 |
80 |
3 |
|
9 |
90 |
120 |
130 |
80 |
90 |
3,2 |
|
10 |
68 |
70 |
90 |
120 |
150 |
3 |
|
Вес, аi |
вариант |
a1 |
a2 |
a3 |
a4 |
a5 |
|
1 |
0,25 |
0,5 |
1,25 |
1,5 |
2 |
||
2 |
0,1 |
0,3 |
0,6 |
0,9 |
1,2 |
||
3 |
0.2 |
0.4 |
0,6 |
1 |
1,2 |
||
4 |
0.4 |
0.8 |
0,8 |
1 |
1,6 |
||
5 |
0.2 |
0.6 |
1,2 |
2.4 |
0,8 |
||
6 |
0.5 |
0.5 |
1 |
1,5 |
2 |
||
7 |
0,1 |
0,2 |
0,3 |
0,4 |
0,5 |
||
8 |
0,25 |
0,5 |
1,25 |
1,5 |
2,5 |
||
9 |
0.2 |
0.4 |
1 |
0,6 |
1.2 |
||
10 |
0,3 |
0,6 |
1,2 |
0,9 |
0,6 |
Имеются 5 ящиков и помещение объемом В м3. Каждый ящик занимает объем аi м3и его содержимое стоит сi руб. Требуется оптимально заполнить помещение ящиками, не превысив его объема.
Стоимость, сi
вариант
c1
c2
c3
c4
c5
Вместимость рюкзака (В)
11
45
30
50
120
70
2,5
12
105
110
60
150
200
1,6
13
105
50
55
70
90
2.4
14
135
60
70
110
80
3.2
15
150
120
100
105
90
3
16
120
90
70
50
130
8
17
170
160
50
80
100
1
18
140
100
40
50
80
3
19
85
70
130
80
90
3,2
20
175
160
190
120
150
3
Объем, аi
вариант
a1
a2
a3
a4
a5
11
0,25
0,5
1,25
1,5
2
12
0,1
0,3
0,6
0,9
1,2
13
0.2
0.4
0.6
1
1.2
14
0.4
0.8
0.8
1
1.6
15
0.2
0.6
1.2
2.4
0.8
16
0.5
0.5
1
1.5
2
17
0,1
0,2
0,3
0,4
0,5
18
0,25
0,5
1,25
1,5
2,5
19
0.2
0.4
1
0,6
1.2
20
0,3
0,6
1,2
0,9
0,6
Имеются 5 станков и склад площадью В м2. Каждый станок стоимостью сi руб занимает площадь аi м2. Требуется оптимально разместить на складе станки, так чтобы суммарная их стоимость была наибольшей.
Стоимость, сi |
вариант |
c1 |
c2 |
c3 |
c4 |
c5 |
Вместимость рюкзака (В) |
21 |
65 |
30 |
50 |
120 |
70 |
2,5 |
|
22 |
100 |
110 |
60 |
150 |
200 |
1,6 |
|
23 |
45 |
50 |
55 |
70 |
90 |
2.4 |
|
24 |
35 |
60 |
70 |
110 |
80 |
3.2 |
|
25 |
125 |
120 |
100 |
105 |
90 |
3 |
|
26 |
75 |
90 |
70 |
50 |
130 |
8 |
|
27 |
145 |
160 |
50 |
80 |
100 |
1 |
|
28 |
95 |
100 |
40 |
50 |
80 |
3 |
|
29 |
65 |
70 |
130 |
80 |
90 |
3,2 |
|
30 |
130 |
160 |
190 |
120 |
150 |
3 |
|
Объем, аi |
вариант |
a1 |
a2 |
a3 |
a4 |
a5 |
|
21 |
0,25 |
1 |
1,25 |
1,5 |
2 |
||
22 |
0,1 |
0,3 |
0,6 |
0,9 |
1,2 |
||
23 |
0.2 |
0.4 |
0.6 |
1 |
1.2 |
||
24 |
0.4 |
0.8 |
0.8 |
1,2 |
1.6 |
||
25 |
0.2 |
0.4 |
1.2 |
2.4 |
0.8 |
||
26 |
0.5 |
0.5 |
1,5 |
1.5 |
2 |
||
27 |
0,1 |
0,2 |
0,3 |
0,6 |
0,5 |
||
28 |
0,25 |
0,5 |
1,25 |
1,5 |
2,5 |
||
29 |
0.2 |
0.4 |
0,8 |
0,6 |
1.2 |
||
30 |
0,3 |
0,6 |
1,2 |
0,9 |
1,5 |