Лекция 6. Динамическое программирование
Литература
6.1. Формулировка задачи динамического программирования
Пример
Математическая запись
6.2. Принцип оптимальности Беллмана
6.3. Алгоритм решения задач динамического программирования
6.3. Алгоритм решения задач динамического программирования
6.4. Экономические приложения
1.97M
Категория: ПрограммированиеПрограммирование

Динамическое программирование. Принцип оптимальности Беллмана

1. Лекция 6. Динамическое программирование

Содержание лекции:
1.
2.
3.
4.
Формулировка задачи динамического программирования
Принцип оптимальности Беллмана
Алгоритм решения задач динамического
программирования
Экономические приложения задач динамического
программирования
Динамическое программирование
© Н.М. Светлов, 2007-2011

2. Литература

Фомин Г.П. Математические методы и модели в
коммерческой деятельности: Учебник. – 2-е изд.
М.: Финансы и статистика, 2005. — Глава 5.
Экономико-математические методы и прикладные
модели: Учеб. пособие для вузов / Под ред. В.В.
Федосеева. — 2-е изд. М.: ЮНИТИ-ДАНА, 2005. —
Раздел 3.5.
Динамическое программирование
© Н.М. Светлов, 2007-2011
2/9

3. 6.1. Формулировка задачи динамического программирования

Дано:
множество состояний
множество возможных переходов из одного
состояния в другое
в том числе начальное и конечное
с каждым переходом связывается числовой параметр
Найти:
• интерпретируется как затраты, выгода, расстояние, время и
т.п.
оптимальную последовательность переходов (путь)
из начального состояния в конечное
максимум или минимум суммы числовых параметров
предполагается, что хотя бы один путь из начального
состояния в конечное существует
Динамическое программирование
© Н.М. Светлов, 2007-2011
3/9

4. Пример

6.1
1
5
8
1
3
4
0
5
2
16
4
2
9
6
4
9
11
5
7
9
14
9
7
10
12
11
8
4
4
1
0
12
10
15
5
4
4
7
4
8
17
-2
6
8
3
12
7
3
18
16
13
Динамическое программирование
© Н.М. Светлов, 2007-2011
4/9

5. Математическая запись

сумма числовых
значений (e.g.
расстояний) по
всему пути
6.1
Математическая запись
max å å c ij x ij
x ij
åx
i ÎI
i ÎI j ÎJ
ij
£ 1, j Î J
å x ik =
i ÎI
единственность искомого
пути: в каждую вершину
можно прийти только из
одной вершины (или
вообще нельзя)
å x kj , k Î I \ {0}
j ÎJ
x ij Î {0;1}, i Î I , j Î J
x ij = 0, i Î I , j Î J , (i , j ) Ï A
если искомый путь пришёл в
вершинуk, то он должен из
неё выйти (если только она
не конечная)
1, если путь проходит
через дугу (i,j)
0, если не проходит
или такой дуги нет
Например,
расстояние между
пунктами i и j, км
x ij – переменная включения дуги ( i , j ) в путь
c ij – числовое значение, приписанное дуге
I – множество вершин, кроме конечной
J – множество вершин, кроме начальной вершины 0
A – множество всех дуг
X \ Y – оператор исключения множества Y из множества X
{(1,2), (1,3), (2,4),
(2,5), (3,5)…}
Динамическое программирование
© Н.М. Светлов, 2007-2011
5/9

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

Если вершины A и B лежат на оптимальном пути между
вершинами 0 и X, то часть оптимального пути от 0 до
X между вершинами A и B непременно является
оптимальным путём от A до B.
Следствие
Чтобы найти оптимальный путь от 0 до A, достаточно
исследовать продолжения к A всех оптимальных путей
до вершин, предшествующих A
Продолжения неоптимальных путей к предшествующим
вершинам можно не просчитывать: они никогда не дадут
оптимального пути к A
Принцип Беллмана позволяет построить простую и
эффективную вычислительную процедуру для решения
задач динамического программирования
Динамическое программирование
© Н.М. Светлов, 2007-2011
6/9

7. 6.3. Алгоритм решения задач динамического программирования

11
5
8
1
3
12
15
4
0
0
5
5
2
4
0
35
2
14
9
23
7
6
11
12
11
8
45
18
34
4
9
18
7
9
4
16
9
9
4
10
4
15
3
1
19
1
5
28
10
5
12
15
4
7
7
14
8
4
18
4
37
8
17
27
-2
6
3
3
4
16
13
Динамическое программирование
© Н.М. Светлов, 2007-2011
максимум
7/9

8. 6.3. Алгоритм решения задач динамического программирования

11
5
8
1
9
15
4
0
1
12
12
5
10
3
3
0
12
1
5
2
6
14
9
11
12
11
8
23
18
13
4
9
11
7
9
4
14
2
16
7
7
4
4
0
16
4
5
10
17 5
12
15
4
7
7
11
8
4
15
4
16
8
17
19
-2
6
3
3
4
16
13
Динамическое программирование
© Н.М. Светлов, 2007-2011
минимум
8/9

9. 6.4. Экономические приложения

Динамическое программирование
© Н.М. Светлов, 2007-2011
9/9
English     Русский Правила