Динамическое программирование

Июль 31, 2022

Главная
Информатика
Динамическое программирование

Содержание

2. Метод динамического программирования – один из наиболее мощных и широко известных математических методов современной теории оптимального
3. Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. Виды методов
4. Понятие «программирование» Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному программированию (написанию кода) почти
5. Принцип оптимальности Метод динамического программирования основан на применении принципа оптимальности Беллмана: Каково бы ни было состояние
6. Решение задач Задачи, решаемые методом динамического программирования, формулируются следующим образом: имеется управляемый процесс, задано его начальное
7. Виды задач К наиболее типичным задачам динамического программирования относятся: распределение ресурсов и капитальных вложений между возможными
8. Задача определения оптимального плана обновления оборудования (пример): Рассчитать оптимальный план замены оборудования на период продолжительностью 6
9. Условные обозначения R(t) – годовой выпуск продукции, тыс. руб. U(t) – затраты на содержание и ремонт
10. Исходные данные:
11. Зависимость ежегодного дохода от возраста оборудования
12. Уравнения для расчётов
13. Итоговая таблица
14. Домашняя задача Рассчитать оптимальный план замены оборудования на период продолжительностью 7 лет, если стоимость нового оборудования
15. Тест по теме «Динамическое программирование»
16. 1) Дайте определение понятию «динамическое программирование».
17. 2) В каких годах был разработан метод динамического программирования? А) в 30-х гг. Б) в 60-х
18. 3) Какие из данных задач решаются с помощью методов динамического программирования? А) Задача о замене оборудования
19. 4) Кто является основоположником теории оптимальности? А) Р. Флойд Б) С. Уоршелл В) Р. Беллман Г)
20. 5) Первый этап решения общей задачи динамического программирования: А) Нахождение оптимального решения подзадач рекурсивно, проделывая трехшаговый
21. 6) Перечислите виды методов динамического программирования.
23. Скачать презентацию

Слайд 2

Метод динамического программирования – один из наиболее мощных и широко известных

математических методов современной теории оптимального управления, был предложен в конце 50-х годов американским математиком Р. Беллманом.

Ключевая идея в динамическом программировании - решить отдельные части задачи (подзадачи), а затем объединить решения подзадач в одно общее решение.
Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений.

Слайд 3

Динамическое программирование — способ решения сложных задач путём разбиения их на

более простые подзадачи.

Виды методов ДП:
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.
Метод динамического программирования снизу — включает в себя переформулирование сложной задачи в виде последовательности более простых подзадач.

Слайд 4

Понятие «программирование»
Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному

программированию (написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация».
Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи.

Слайд 5

Принцип оптимальности
Метод динамического программирования основан на применении принципа оптимальности Беллмана:
Каково

бы ни было состояние системы перед очередным шагом, необходимо выбирать управление на этом шаге так, чтобы доход на данном шаге вместе с оптимальным доходом на всех последующих шагах был максимальным.

Слайд 6

Решение задач
Задачи, решаемые методом динамического программирования, формулируются следующим образом: имеется управляемый

процесс, задано его начальное и конечное состояния, требуется определить значения факторов его состояния, обеспечивающих получение оптимума функции процесса в целом.
В общем случае мы можем решить задачу проделывая следующие три шага:
Разбиение задачи на подзадачи меньшего размера.
Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трехшаговый алгоритм.
Использование полученного решения подзадач для конструирования решения исходной задачи.

Слайд 7

Виды задач
К наиболее типичным задачам динамического программирования относятся:
распределение ресурсов и

капитальных вложений между возможными направлениями их использования (по объему и времени);
задача о замене оборудования;
составление календарных планов текущего и капитального ремонтов сложного оборудования;
определение кратчайших расстояний на заданной транспортной сети и др.

Слайд 8

Задача определения оптимального плана обновления оборудования (пример):
Рассчитать оптимальный план замены оборудования

на период продолжительностью 6 лет, если стоимость нового оборудования равна 12 тыс. руб., а возраст оборудования составляет 1 год.

Слайд 9

Условные обозначения
R(t) – годовой выпуск продукции, тыс. руб.
U(t) – затраты на

содержание и ремонт оборудования, тыс. руб.
d(t)=R(t)-U(t)
P – цена нового оборудования
n – плановый период
t – возраст оборудования

Слайд 10

Исходные данные:

Слайд 11

Зависимость ежегодного дохода от возраста оборудования

Слайд 12

Уравнения для расчётов

Слайд 13

Итоговая таблица

Слайд 14

Домашняя задача
Рассчитать оптимальный план замены оборудования на период продолжительностью 7

лет, если стоимость нового оборудования равна 18 тыс. руб., а возраст оборудования составляет 1 год.
Исходные данные:

Слайд 15

Тест по теме «Динамическое программирование»

Слайд 16

1) Дайте определение понятию «динамическое программирование».

Слайд 17

2) В каких годах был разработан метод динамического программирования? А) в 30-х

гг. Б) в 60-х гг. В) в 50-х гг.

Слайд 18

3) Какие из данных задач решаются с помощью методов динамического программирования?
А)

Задача о замене оборудования на предприятии
Б) Транспортная задача
В) Игра с ненулевой суммой
Г) Задача о наибольшей общей подпоследовательности

Слайд 19

4) Кто является основоположником теории оптимальности?
А) Р. Флойд
Б) С. Уоршелл
В) Р.

Беллман
Г) Л. Форд

Слайд 20

5) Первый этап решения общей задачи динамического программирования:
А) Нахождение оптимального решения

подзадач рекурсивно, проделывая трехшаговый алгоритм.
Б) Разбиение задачи на подзадачи меньшего размера.
В) Использование полученного решения подзадач для конструирования решения исходной задачи.

Слайд 21

Динамическое программирование

Содержание

Метод динамического программирования – один из наиболее мощных и широко известных

Динамическое программирование — способ решения сложных задач путём разбиения их на

Понятие «программирование»Слово «программирование» в словосочетании «динамическое программирование» в действительности к традиционному

Принцип оптимальностиМетод динамического программирования основан на применении принципа оптимальности Беллмана: Каково

Решение задачЗадачи, решаемые методом динамического программирования, формулируются следующим образом: имеется управляемый

Виды задачК наиболее типичным задачам динамического программирования относятся: распределение ресурсов и

Задача определения оптимального плана обновления оборудования (пример):Рассчитать оптимальный план замены оборудования

Условные обозначенияR(t) – годовой выпуск продукции, тыс. руб.U(t) – затраты на