Лекция 4 ТПР 2026

1.

Филиал ФГБОУ ВО
«Национальный исследовательский университет «МЭИ» в г. Смоленске
Теория принятия решений
Доцент кафедры ВТ
кандидат технических наук, доцент
И.А. Денисова
Смоленск
Смоленск
– 2026
2011

2.

Лекция № 4
Динамическое программирование
в задачах принятия решений

3.

УЧЕБНЫЕ ВОПРОСЫ
1. Метод динамического программирования (ДП)
2. Решение задач принятия решений методом ДП

4.

1 вопрос
Метод динамического программирования (ДП)

5.

Динамическое программирование - один из мощных методов решения
задач математического программирования, разработанный американским
математиком Р. Беллманом в конце 50-х годов.
Фундаментальной основой метода ДП является сформулированный
Беллманом принцип оптимальности, согласно которому оптимальное
управление определяется конечной целью управления и состоянием
системы в рассматриваемый момент, независимо от того, каким
образом она пришла в это состояние.
Этот принцип является конструктивным, он позволяет существенно
повысить эффективность решения определенного класса задач
математического программирования путем их разложения на ряд задач
значительно меньшей размерности. Такие задачи описываются
математической моделью, в которой и критерий, и ограничения
являются составными.
5

6.

Метод динамического программирования ориентирован на оптимизацию
многошаговых (многоэтапных) процессов и использование ЭВМ.
6

7.

(время перехода1 - 4) + t4
(время перехода 1 - 5) + t
5
min
t1
(время перехода 1 - 6) + t6
(время перехода 1 - 7) + t7
Последний четвертый этап
охватывает все шаги.
Определение оптимального перехода
на 1-м шаге для каждого из входов
требует сравнения всего
3-х вариантов против
144 при полном переборе.
7

8.

Формализация вычислительной
процедуры метода ДП базируется на
принципе оптимальности:
последующие решения должны
быть оптимальными
относительно состояния,
сложившегося в результате
предшествующих, пусть и не
оптимальных, решений.
8

9.

Основные понятия динамического программирования:
Шаги решения задачи всегда пронумеровываются в порядке
проведения условной оптимизации - от конца к началу.
Эффективность i-го шага описывается функцией Zi(Si,Ui),
где Si - состояние к i-му шагу (вектор параметров состояния),
Ui - управление на i-м шаге (вектор управляемых переменных
или решение).
.
Структура задачи, решаемой методом ДП
9

10.

Формализованная модель задачи:
N
.
Z Zi ( Si , Ui ) extr
- целевая функция (критерий)
Si 1 (Si , Ui )
- уравнение состояния
i 1
k
fk ( Sk ) extr zi ( Si , Ui ) - функция зависимости
{U i } i 1
экстремального значения
критерия за k оставшихся шагов
от состояния на начало k-го шага
Основное функциональное уравнение ДП:
fk (Sk ) extr [ zk (Sk , Uk ) fk 1 ( (Sk , Uk ))].
U k Dk
10

11.

Алгоритм метода динамического программирования:
1. Выделить шаги решения задачи и произвести их нумерацию с конца.
2. Определить параметры состояния и ввести последовательность функций
{fk(Sk)}, в которой каждая функция fk(Sk) есть наилучшее значение критерия за k
.
оставшихся
шагов относительно состояния Sk, k 1, N
3. На основе принципа оптимальности составить функциональное
уравнение ДП и отдельно выражение для f1.
4. Провести
условную оптимизацию, последовательно вычисляя f1,
f2,...,fN. При этом на каждом шаге для всех возможных значений состояния Sk
запоминать значения Uk* и fk (в таблице или файле).
5.Исходя из заданного состояния SN^, провести безусловную оптимизацию
по схеме:
SN^ табл.N UN* у.с. SN-1^ табл.N-1 UN-1* у.с. ... S1^ табл.1 U1*,
где у.с. - уравнение состояния. Значение fN(SN) из N-й таблицы есть
оптимальное значение критерия задачи.
11

12.

2 вопрос
Решение задач принятия решений
методом ДП

13.

1. Задача о кратчайшем пути
13

14.

1. Задача о кратчайшем пути
.
Модель задачи включает:
1) критерий Z - длина искомого пути:
ZL Lij min
,
ij 1
где π1 - путь от начальной вершины к конечной вершине,
2) расчетные значения fi :
fN 0
f i min ( Lij f j ),i N 1,....,1.
j
где N – количество вершин.
14

15.

1. Алгоритм метода ДП для решения задачи о кратчайшем пути
1. Провести
(при необходимости) нумерацию шагов решения
.
задачи. Определить N.
2. Присвоить
fN 0
3. Рассчитать
f i min ( Lij f j ),i N 1,....,1.
j
fi - наилучшее значение критерия L за i оставшихся
шагов.
3. Решение Zmin= f1 .
4. Обратная прогонка: указать оптимальное решение,
просмотрев fi в обратном порядке (с учетом проведенной
оптимизации на каждом этапе).
15

16.

1. Задача о кратчайшем пути
f7 =0, .
f7 =0,
f7 =0, f6 = min (L67 + f7)=1+0=1,
f6 = min (L67 + f7)=1+0=1,
L57 f7
3 0
f5 min
min
2,
1 1
L56 f6
L46 f6
5 1
f4 min
min
5,
L
f
3
2
45
5
L37 f7
6 0
f3 min L35 f5 min 7 2 6,
L f
5
5
34
4
L24 f4
7 5
f2 min L25 f5 min 8 2 10,
5 6
L23 f3
L12 f2
1 10
f1 min
min
11.
6 6
L13 f3
16

17.

2. Задача о наборе высоты
.
Летательный аппарат находится в точке S0. которая характеризуется
высотой H0 и скоростью V0. Аппарат необходимо перевести в конечную
точку Sk с координатами Hk и Vk соответственно. Предполагается, что
нельзя одновременно изменять значение скорости и высоты. Для
возможных значений изменения H и V заданы величины расхода топлива.
Необходимо определить такую последовательность изменения H и V , при
которой суммарный расход топлива при переходе из начальной точки S0 в
конечную Sk был минимальным. В этой задаче понятие этапа является
искусственным.
Для этого весь диапазон изменений V разбивается на n1 интервалов
величиной ΔV. Аналогично разбиение производится для диапазона
изменения высоты:
n1
Vk V0
;
V
n2
Hk H0
.
H
где ΔH –величина шага изменения высоты, n2 – количество
интервалов изменения высоты.
17

18.

2. Задача о наборе высоты
.
18

19.

2. Задача о наборе высоты
.
19

20.

2. Задача о наборе высоты
Решение задачи начинаем с конечной точки f15 = 0.
Продолжаем
решение «по диагонали»: f13 = min (L13,15 + f15)=12+0=12,
.
f14 = min (L14,15 + f15)=14+0=14 (на рисунке помечены *).
Следующий этап: f10 = min (L10,13 + f13)=12+10=22,
L11,13 f13
13 12
min
f11 min
14 13 25,
L11,14 f14
f12 = min (L12,14 + f15)=14+12=26.
Аналогично продолжаем расчет для всех состояний, оптимальное решение
получается в начальной точке f0 =53.
Затем уже в прямом порядке необходимо просмотреть ход решения и выделить
оптимальные управления каждого этапа решения (на рис. помечены х).
20

21.

3. Задача о вложении средств
Найти оптимальный вариант инвестирования, обеспечивающий
максимальную прибыль. Общий объём инвестиций равен 3 млн. рублей,
.
вкладывать можно только целое количество млн. рублей. Доходность
вложений обеспечивают три объекта, она задана матрицей:
Инвестиции,
млн. руб
0
1
2
3
Величина прибыли от инвестирования, млн.
руб
№1
№2
№3
0
0
0
2
3
2
4
5
7
6
8
8
21

22.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
1. Построить граф и решить задачу о кратчайшем пути методом ДП
Из
В
1
2
3
4
5
6
7
8
9
2
5
3
3
4
4
5
5
6
7
7
3
1
15
2
6
4
2
9
8
10
4
5
9
10
10
11
8
4
2
7
6
3
22

23.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
Задание 2. Решить задачу о наборе высоты методом ДП
25
14
27
15
25
12
16
27
12
23
11
14
24
11
23
11
21
27
24
23
17
13
11
10
27
11
25
9
22
9
21
23

24.

ЗАДАНИЕ НА ПРАКТИЧЕСКОЕ ЗАНЯТИЕ
Задание 3. Решить задачу о вложении средств методом ДП
Инвестиции,
млн. руб
Величина прибыли от инвестирования
№1
№2
№3
№3
0
0
0
0
0
100
40
50
30
60
200
50
70
55
75
300
65
85
70
95
400
75
95
95
110
24