Исследование операций. Лекция 5

1.

Крамаренко К.Е.
Кафедра ВС

2.

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

3.

Основные элементы модели ДП:
1. Определение этапов.
2. Определение
на каждом этапе вариантов
решения(альтернатив).
3. Определение состояний на каждом этапе.

4.

Вычисления в ДП выполняются рекуррентно в том
смысле, что оптимальное решение одной подзадачи
используется в качестве исходных данных для
следующей.

5.

2
12
7
5
8
1
8
3
9
6
7
5
13
4
9
6
7

6.

7
7
2
2
8
8
3
3
12
7
0
1
8
5
Этап f0-f1
8
9
7
5
5
4
4
12
12
5
5
17
17
6
6
9
7
6
13
Этап f1-f2
21
Этап f2-f3

7.

Этап 1:
Кратчайший путь к узлу 2 равен 7 (из узла 1)
Кратчайший путь к узлу 3 равен 8 (из узла 1)
Кратчайший путь к узлу 4 равен 5 (из узла 1)

8.

Этап 2:
Кратчайший
= min
путь к узлу 5