|
|
дин.програмування. Динамическое программирование Презентацию
Динамическое программирование Презентацию подготовили: Бареев Владимир 3102 Анастасия Брусницына 3101 Иванушкин Сергей 3101 Метод динамического программирования – один из наиболее мощных и широко известных математических методов современной теории оптимального управления, был предложен в конце 50-х годов американским математиком Р. Беллманом. - Ключевая идея в динамическом программировании - решить отдельные части задачи (подзадачи), а затем объединить решения подзадач в одно общее решение.
- Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений.
Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. - Виды методов ДП:
- Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.
- Метод динамического программирования снизу — включает в себя переформулирование сложной задачи в виде последовательности более простых подзадач.
Понятие «программирование» - Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».
- Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи.
Принцип оптимальности - Метод динамического программирования основан на применении принципа оптимальности Беллмана:
- Каково бы ни было состояние системы перед очередным шагом, необходимо выбирать управление на этом шаге так, чтобы доход на данном шаге вместе с оптимальным доходом на всех последующих шагах был максимальным.
Решение задач Задачи, решаемые методом динамического программирования, формулируются следующим образом: имеется управляемый процесс, задано его начальное и конечное состояния, требуется определить значения факторов его состояния, обеспечивающих получение оптимума функции процесса в целом. В общем случае мы можем решить задачу проделывая следующие три шага: - Разбиение задачи на подзадачи меньшего размера.
- Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
- Использование полученного решения подзадач для конструирования решения исходной задачи.
Виды задач - К наиболее типичным задачам динамического программирования относятся:
- распределение ресурсов и капитальных вложений между возможными направлениями их использования (по объему и времени);
- задача о замене оборудования;
- составление календарных планов текущего и капитального ремонтов сложного оборудования;
- определение кратчайших расстояний на заданной транспортной сети и др.
Задача определения оптимального плана обновления оборудования (пример): Рассчитать оптимальный план замены оборудования на период продолжительностью 6 лет, если стоимость нового оборудования равна 12 тыс. руб., а возраст оборудования составляет 1 год. Условные обозначения - R(t) – годовой выпуск продукции, тыс. руб.
- U(t) – затраты на содержание и ремонт оборудования, тыс. руб.
- d(t)=R(t)-U(t)
- P – цена нового оборудования
- n – плановый период
- t – возраст оборудования
Исходные данные:
t
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
R(t)
|
27
|
26
|
26
|
25
|
24
|
23
|
23
|
U(t)
|
15
|
16
|
17
|
18
|
20
|
22
|
23
| Зависимость ежегодного дохода от возраста оборудования
t
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
d(t)
|
12
|
10
|
9
|
7
|
4
|
1
|
0
| Уравнения для расчётов - (1)
- При n=1 слагаемые и не имеют смысла и поэтому из уравнения исключаются
- (2)
Итоговая таблица | |
0
|
1
|
2
|
3
|
4
|
5
|
6
|
F1(t)
|
12
|
10
|
9
|
7
|
4
|
1
|
0
|
F2(t)
|
22
|
19
|
16
|
11
|
10
|
10
|
10
|
F3(t)
|
31
|
26
|
20
|
19
|
19
|
19
|
19
|
F4(t)
|
38
|
30
|
28
|
26
|
26
|
26
|
26
|
F5(t)
|
42
|
38
|
35
|
33
|
30
|
30
|
30
|
F6(t)
|
50
|
47
|
42
|
38
|
38
|
38
|
38
| Домашняя задача - Рассчитать оптимальный план замены оборудования на период продолжительностью 7 лет, если стоимость нового оборудования равна 18 тыс. руб., а возраст оборудования составляет 1 год.
- Исходные данные:
t
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
R(t)
|
35
|
34
|
34
|
33
|
32
|
31
|
31
|
30
|
U(t)
|
17
|
18
|
19
|
21
|
23
|
25
|
28
|
30
| Тест по теме «Динамическое программирование» 1) Дайте определение понятию «динамическое программирование». 2) В каких годах был разработан метод динамического программирования? А) в 30-х гг. Б) в 60-х гг. В) в 50-х гг. 3) Какие из данных задач решаются с помощью методов динамического программирования? А) Задача о замене оборудования на предприятии Б) Транспортная задача В) Игра с ненулевой суммой 4) Кто является основоположником теории оптимальности? А) Р. Флойд Б) С. Уоршелл В) Р. Беллман Г) Л. Форд 5) Первый этап решения общей задачи динамического программирования: А) Нахождение оптимального решения подзадач рекурсивно, проделывая трехшаговый алгоритм. Б) Разбиение задачи на подзадачи меньшего размера. В) Использование полученного решения подзадач для конструирования решения исходной задачи. 6) Перечислите виды методов динамического программирования. Спасибо за внимание! |
|
|
Скачать 230.68 Kb.