МП Лекция 9 Динамическое программирование

1. методЫ динамического программирования

МЕТОДЫ ДИНАМИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
Ричард Эрнст Беллман
26.08.1920 – 19.03.1984
ТПР
Лекция 20.2

2. СОДЕРЖАНИЕ

Часть 1. Общие принципы динамического
программирования.
Часть 2. Принятие решений на моделях,
сводимых к задачам дискретной
оптимизации с булевыми переменными.
Часть 3. Принятие решений на моделях,
сводимых к задачам дискретной
оптимизации с небулевыми переменными.

3. ЧАСТЬ 1

Общие принципы
динамического
программирования

4. ОПРЕДЕЛЕНИЕ

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

5. Принцип оптимальности Беллмана

Оптимальная стратегия обладает тем
свойством, что независимо от начального
состояния и начального решения задачи,
последующие решения должны составлять
оптимальную стратегию лишь в
рассматриваемый момент времени. Иными
словами оптимальная стратегия в каждый
момент времени определяется лишь
состоянием системы, но не ее предысторией.

6. Часть 2

Принятие решений на
моделях, сводимых к
задачам дискретной
оптимизации с
булевыми переменными

7. Формальная постановка задачи

i n
ci xi max(min);
i 1
i n
j : ai , j xi ( , )b j ;
i 1
i : xi 1,0.

8. ПРИМЕР 1: Решение задачи с булевыми переменными вида:

6 x1 3x2 4 x3 2 x4 max;
4 x1 6 x2 5 x3 5 x4 10;
i : x 1,0.
i

9. ПРИМЕР 1: Решение задач с булевыми переменными – первая итерация

Задача о ранце:
6 x1 3x2 4 x3 2 x4 max;
4 x1 6 x2 5 x3 5 x4 10;
i : x 1,0.
i
0,10
1
6,6
S
Первое число –
значение целевой
функции, второе –
ресурс.
«Красные» вершины
отвечают
информации, которая
присутствует в памяти
на текущей итерации.
0
0,10
x1
x2
x3
x4

10. ПРИМЕР 1: Решение задач с булевыми переменными – вторая итерация

Задача о ранце:
6 x1 3x2 4 x3 2 x4 max;
4 x1 6 x2 5 x3 5 x4 10; 1
i : x 1,0.
9,0
i
0
1
6,6
S
Первое число –
значение целевой
функции, второе –
ресурс.
Вычеркивается,
потому что
бесперспективно:
есть направление с
лучшими
значениями
ресурса и целевой
функции.
6,6
1
3,4
0
0,10
0
0,10
x1
x2
x3
x4

11. ПРИМЕР 1: Решение задач с булевыми переменными – третья итерация

Задача о ранце:
1
6 x1 3x2 4 x3 2 x4 max;
4 x1 6 x2 5 x3 5 x4 10; 1
i : x 1,0.
9,0
i
0
1
6,6
S
Первое число –
значение целевой
функции, второе –
ресурс.
0
1
10,1
0
6,6
3,4
0,10
9,0
6,6
1
0
-∞
0
1
4,5
0,10
x1
x2
x3
0
0,10
x4

12. ПРИМЕР 1: Решение задач с булевыми переменными – последняя итерация

Задача о ранце:
1
6 x1 3x2 4 x3 2 x4 max;
4 x1 6 x2 5 x3 5 x4 10; 1
i : x 1,0.
9,0
i
0
1
6,6
S
Первое число –
значение целевой
функции, второе –
ресурс.
0
1
10,1
0
9,0
1
10,1
6,6
6,6
0
0
6,6
3,4
0,10
1
8,1
1
0
-∞
-∞
0
1
2,5
1
4,5
0,10
x1
x2
x3
0
0
0,10
x4
0,10

13. САМОСТОЯТЕЛЬНО

Пользуясь методом динамического
программирования, решить задачу о ранце:
4 x1 7 x2 9 x3 3x4 max;
6 x1 5 x2 8 x3 7 x4 12;
i : x 1,0.
i

14. Индивидуальные задания

Решить задачу о ранце вида:
F = az1 +bz2 + cz3 + dz4 → max;
qz1 + gz2 + hz3 + fz4 ≤ s;
zi = 1, 0; i = 1,…,4.

15. Индивидуальные задания

№
a
b
c
d
q
g
h
f
s
1
2
5
7
3
4
8
1
6
11
2
4
7
2
5
11
10
11
12
21
3
6
14
3
11
14
7
14
17
32
4
8
6
4
7
13
8
13
18
31
5
3
2
5
8
12
9
12
19
35
6
7
3
6
9
9
17
9
17
35
7
5
7
8
6
11
16
11
16
39
8
10
9
7
5
13
15
14
12
40
9
12
11
3
4
17
14
17
14
49
10
11
8
4
3
11
13
11
23
35
11
7
5
2
1
12
11
12
21
35
12
4
3
5
2
13
11
13
21
35
13
3
4
6
5
14
12
14
22
40
14
8
6
5
9
15
10
15
20
41
15
9
1
7
8
16
9
16
19
41
16
1
9
8
7
17
8
17
18
42
17
2
3
9
6
9
13
19
13
45
18
6
5
10
7
8
14
18
14
37
19
14
7
9
8
7
15
17
15
40
20
7
2
5
6
6
12
16
12
40

16. ЧАСТЬ 3

Решение задач дискретной
оптимизации с небулевыми
переменными

17. Формальная постановка задачи

ci xi max(min);
i 1
i n
j : ai , j xi ( , )b j ;
i 1
i : xi { X i };
i : X i {d i ,1 , d i , 2 , d i ,3 ,...d i ,mi }.
i n

18. Пример задачи с небулевыми переменными

5 x1 2 x2 9 x3 7 x 4 max;
4 x1 2 x2 2 x3 4 x4 6;
i, x {0,1,2}.
i

19. ПРИМЕР 2: Решение задачи с небулевыми переменными

Решение задачи вида:
5 x1 2 x2 9 x3 7 x 4 max;
4 x1 2 x2 2 x3 4 x4 6;
i, x {0,1,2}.
i
s
Первая итерация
0
1
2
0,6
5,2
-∞

20. ПРИМЕР 2: Решение задачи с небулевыми переменными

Решение задачи вида:
5 x1 2 x2 9 x3 7 x 4 max;
4 x1 2 x2 2 x3 4 x4 6;
i, x {0,1,2}.
i
Вторая итерация

21. ПРИМЕР 2 (ПРОДОЛЖЕНИЕ)

Третья итерация:
5 x1 2 x2 9 x3 7 x 4 max;
4 x1 2 x2 2 x3 4 x4 6;
i, x {0,1,2}.
i

22. Пример 2 (завершение)

Четвертая итерация:
5 x1 2 x2 9 x3 7 x 4 max;
4 x1 2 x2 2 x3 4 x4 6;
i, x {0,1,2}.
i
22
X opt {0,1,2,0};
Fopt 20.

23. САМОСТОЯТЕЛЬНО:

Решить задачу с небулевыми и с
булевыми переменными вида:
7 x1 2 x2 4 x3 5 x 4 max;
4 x 2 x 2 x 4 x 8;
1
2
3
4
i
3
,
x
{
0
,
1
,
2
},
i
3 i 4 : xi {0,1}.

24. Индивидуальные задания

Решить c помощью динамического
программирования задачу вида:
F = az1 +bz2 + cz3 + dz4 → max;
qz1 + gz2 + hz3 + fz4 ≤ s;
zi = 0,1,2; i = 1,…,4,
при условии, что каждая
переменная принимает три значения:
{0, 1, 2}.

25. Индивидуальные задания первой группы

№
1
a
2
b
5
c
7
d
3
q
4
g
8
h
1
f
6
s
11
2
4
7
2
5
11
10
11
12
21
3
6
14
3
11
14
7
14
17
32
4
8
6
4
7
13
8
13
18
31
5
3
2
5
8
12
9
12
19
35
6
7
3
6
9
9
17
9
17
35
7
5
7
8
6
11
16
11
16
39
8
10
9
7
5
13
15
14
12
40
9
12
11
3
4
17
14
17
14
49
10
11
8
4
3
11
13
11
23
35
11
7
5
2
1
12
11
12
21
35
12
4
3
5
2
13
11
13
21
35
13
3
4
6
5
14
12
14
22
40
14
8
6
5
9
15
10
15
20
41
15
9
1
7
8
16
9
16
19
41
16
1
9
8
7
17
8
17
18
42
17
2
3
9
6
9
13
19
13
45
18
6
5
10
7
8
14
18
14
37
19
14
7
9
8
7
15
17
15
40
20
7
2
5
6
6
12
16
12
40

26. Индивидуальные задания второй группы

№
a
b
c
d
q
g
h
f
s
1
3
5
7
3
5
8
1
6
11
2
4
3
2
5
11
11
11
12
21
3
6
14
4
11
14
7
12
17
32
4
8
6
4
6
13
8
13
19
31
5
5
2
5
8
11
9
12
19
35
6
7
4
6
9
8
15
9
17
35
7
5
7
7
6
10
16
11
15
39
8
10
9
7
8
12
15
14
12
33
9
12
11
3
4
16
14
17
14
47
10
11
8
4
3
9
13
11
23
34
11
7
5
2
1
11
11
12
21
33
12
5
3
5
2
12
11
13
21
32
13
4
4
6
5
13
12
14
22
41
14
7
6
5
9
14
10
15
20
39
15
8
1
7
8
15
9
16
19
40
16
3
9
8
7
1
18
17
18
41
17
4
3
9
6
9
12
19
13
44
18
7
5
10
7
8
12
18
14
36
19
4
7
9
8
7
14
17
15
38
20
8
2
5
6
6
13
16
12
39

27. Задачи оптимального упорядочения

Ниже рассмотрено использование техники
динамического программирования применительно к
задачам оптимального упорядочения объектов,
конкретно – к задаче распределения n работ между n
исполнителями. В этом случае любую перестановку
натуральных чисел от 1 до n можно рассматривать, как
распределение работ между исполнителями. Так,
π = { 3, 1,2 } означает, что первую работу делает
третий исполнитель, вторую – первый, а третью –
второй. Объем полного перебора равен n!.

28. ПРИМЕР – исходные данные

В приведенной ниже таблице «Т» приведены
времена выполнения каждым рабочим каждой
работы, а в таблице «С» - стоимости
выполнения каждым рабочим каждой работы.
1
Т= 7
6
8
5
9
4
2
С= 3
3
9
4
3
4
7
8
5
1
Строки соответствуют работам, столбцы –
исполнителям.

29. ЦЕЛЬ И РЕШЕНИЕ ПЕРЕБОРОМ

Если целью является минимизация времени
выполнения всех работ либо затрат на их
исполнение при условии, что все исполнители
заняты, то решение задачи полным перебором (n!
перестановок) имеет вид:
T=
C=
1
8
5
π
Т
S
7
4
2
1,2.3
9
17
6
3
9
2,1,3
9
7
1,3,2
3
22
9
3
4
3,1,2
7
12
3
7
8
2,3,1
8
15
4
5
1
3,2,1
6
15

30. Решение методом динамического программирования

Граф поиска:
1, 1
1
T → min; Затраты S ≤ 10.
3
8, 4
1
8, 7
S
+∞
2
+∞
2
9, 3
1
8
5
T= 7
4
2
6
3
9
9
3
4
7
8
5
1
3
+∞
3
5, 6
8, 3
1
3
+∞
+∞
2
4
2
Работа 1
2
C= 3
Ответ: π= {2,1,3}, T = 9.
3

31. Решение методом динамического программирования 2

Граф поиска:
1, 3
1
T → min; Если Затраты S ≤ 12.
3
T=
8, 6
1
9, 5
8,1
3
+∞
5, 8
7, 5
1
7,0
2
3
5,1
+∞
2
1
2
3
8, 9
S
+∞
2
+∞
2
Работа 1
1
8
5
7
4
2
6
3
9
9
3
4
3
7
8
4
5
1
3
1
C=
Ответ: π= {3,1,2}, T = 7.

32. Решить самостоятельно 1

S1 = 10;
Т1
S2 = 12;
S3 = 10;
S4 = 17
Т2
С1
С2
3
8
4
7
2
6
9
2
8
2
7
1
9
2
5
2
9
4
1
3
7
6
1
3
6
4
7
4
5
3
6
4
5
4
7
8
Т3
Т4
С3
С4
7
3
5
3
6
5
11
19
16
9
2
4
1
9
4
9
2
7
12
10
18
8
9
2
8
2
6
2
7
5
17
9
3
3
12
10

33. Решить самостоятельно 2

S5 = 15;
Т5
S6 = 11;
S7 = 18;
S8 = 20
Т6
С5
С6
1
8
4
6
2
6
9
2
8
3
7
1
9
2
5
3
8
4
4
3
1
6
5
3
6
4
7
4
5
3
6
4
5
4
9
8
Т7
Т8
С7
С8
6
3
5
3
6
5
11
19
16
9
2
4
2
9
1
9
4
7
15
10
18
8
9
2
8
2
6
3
7
5
17
9
3
3
12
10

34. Решить самостоятельно 3

S9 = 10;
Т9
S10 = 12;
S11 = 10;
S12 = 17
Т10
С9
С10
7
6
4
2
7
6
10
2
8
4
7
1
9
2
5
2
9
4
1
3
7
6
1
3
8
4
3
4
5
8
6
4
5
2
7
9
С12
Т12
С11
Т11
5
3
7
3
6
4
11
19
16
11
2
4
1
6
4
9
5
7
12
15
18
5
9
8
8
2
9
2
7
8
17
9
13
7
12
10

35. Решить самостоятельно 4

S13 = 14;
S14 = 14;
Т13
S16 = 27
Т14
С13
7
6
4
1
7
6
10
2
5
3
9
4
8
4
9
4
5
8
С14
10
2
8
4
7
1
11
3
7
6
2
3
6
4
9
5
7
9
С16
Т16
С15
Т15
S15 = 17;
5
3
7
3
6
4
12
19
16
11
2
14
9
6
4
9
5
7
10
17
18
15
9
8
8
2
1
2
7
8
15
9
13
7
12
10

36. Решить самостоятельно 5

S17 = 11;
Т17
S18 = 15;
S19 = 11;
S20 = 18
Т18
С17
С18
7
6
8
2
6
6
10
2
8
4
7
1
2
9
5
7
1
4
3
1
9
6
1
2
4
4
3
4
5
8
6
4
5
2
7
9
С20
Т20
С19
Т19
5
3
7
3
6
4
11
19
16
11
2
4
1
6
4
9
5
7
12
15
18
5
9
8
8
2
9
2
7
8
17
9
13
7
12
10