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

• Название: Динамическое программирование
• Анкор: программирование
• Дата: 20.01.2022
• Размер: 304.57 Kb.
• Имя файла: Лекция №9.pptx
• Тип: Лекция; #337221

ТЕМА: ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

• Основные понятия. Постановка задачи.
• Принцип оптимальности Беллмана.
• Уравнения Беллмана.
• Пример распределения инвестиций

Лекция №9

Основные понятия (определения)

• Динамическое программирование представляет собой математический метод оптимизации решений при поэтапном (пошаговом) развитии ситуации, причём выбор оптимального решения зависит как от состояния ситуации на момент выбора очередного шага, так и от истории развития ситуации.
• Динамическое программирование применимо только для решения таких "многошаговых" задач, для которых справедливо утверждение: если за k шагов получено оптимальное решение, то выбор оптимального решения на k+1 шаге даёт оптимальное решение за все k+1 шагов.

Содержание задачи ДП

Зависимость элементов динамики друг от друга.

Такая зависимость может быть прямо дана в условии (так часто бывает, если это задача на числовые последовательности).

В противном случае вы можете попытаться узнать какой-то известный числовой ряд (вроде тех же чисел Фибоначчи), вычислив первые несколько значений вручную. Если вам совсем не повезло – придётся думать 

Значение начальных состояний. В результате долгого разбиения на подзадачи вам необходимо свести функцию либо к уже известным значениям (как в случае с Фибоначчи — заранее определены первые два члена), либо к задаче, решаемой элементарно.

Прародитель динамического программирования

Ричард Эрнст Беллман

1940-х годах

Основные свойства задач ДП

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

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

• Управление,

на котором достигается минимальное значение функционала H при заданных ограничениях, называется оптимальным управлением процесса из начального состояниях0.

• Если мы будем говорить об управлении как функции состояния, то будем называть такое управление стратегией. Стратегия, на которой достигается минимальное значение функционала H , называется оптимальной стратегией.
• Принцип оптимальности Беллмана: оптимальная стратегия обладает таким свойством, что каковы бы ни были начальное состояние и начальное управление, последующее решение должно определять оптимальную стратегию относительно состояния, полученного в результате первоначального управления.

Уравнения Беллмана

Решение уравнения Беллмана

• Уравнения Беллмана решаются последовательно, а сам процесс решения заключается в построении последовательности функций Беллмана

Примеры задач ДП

• Маршрут оптимальной длины
• Пример: Есть некоторая карта дорог, представленная в виде графа. Наша цель: добраться из пункта А в пункт Б. Это сделать надо так, чтобы минимизировать расстояние или потраченное топливо.
• Замена машины (минимизация расходов)
• Пример: Каждый год мы принимаем решение, ездить ли на старой машине еще год и понести при этом издержки на поддержку и обслуживание старой машины или же продать эту машину и купить новую (и понести при этом издержки на покупку).

Примеры задач ДП

Графы и деревья

• Пример: Задача на решение того, сколько существует деревьев, у которых определенное число листьев; или сколько существует графов для решения такого-то задания и т.п.

Задача о размене монет или количество способов вернуть сдачу

• Пример: Есть монеты разного достоинства, какими способами можно вернуть сдачу.

Пример. Кратчайший путь

• Дана карта автомобильных дорог с нанесёнными расстояниями между населёнными пунктами. Требуется найти наикратчайший маршрут между начальным пунктом A и конечным пунктом L.

Решение задачи методом динамического программирования (два этапа).

2. Двигаясь от начального пункта A до конечного L по отмеченным дорогам, находим наикратчайший маршрут ADFKL

1. Двигаясь от конечного пункта L к начальному пункту A, помещаем в каждую вершину графа наикратчайшее расстояние от неё до конечной вершины L и отмечаем на карте соответствующую дорогу

Пример. Распределение инвестиций

• Требуется распределить 500 у.е. при следующих исходных данных:

Номер предприятия	Планируемая прибыль при объеме инвестиций
	100	200	300	400	500
1	20	44	55	63	67
2	18	29	49	72	87
3	25	41	52	74	82

Этап 1

• Для составления таблицы первого этапа берем первую строку из таблицы исходных данных

Номер предприятия	Ожидаемая прибыль при объеме инвестиций
	100	200	300	400	500
1	20	44	55	63	67

Этап 2

Строится таблица распределения денежных средств между первыми двумя предприятиями.

• В первой строке помещаем данные о инвестициях и ожидаемой прибыли из таблицы первого этапа.
• В левом столбце показаны инвестиции и ожидаемая прибыль второго предприятия из таблицы исходных данных.

Остальные клетки таблицы заполняются суммированием соответствующих значений заголовков строк и столбцов.

Сравниваем содержимое ячеек таблицы с одинаковым объемом инвестиций, включая ячейки первой строки и левого столбца. Содержимое ячеек с максимальной прибылью отмечаем звездочкой.

	100-20*	200-44*	300-55	400-63	500-67
100-18	200-38	300-62*	400-73	500-81
200-29	300-49	400-73*	500-84
300-49	400-69	500-93*
400-72	500-92
500-87

Этап 3

	100-20	200-44	300-62	400-73	500-93
100-25				500-98
200-41			500-103*
300-52		500-96
400-74	500-94
500-82

В первой строке помещаем данные ячеек со звездочками из таблицы второго этапа.

В левом столбце показаны инвестиции и ожидаемая прибыль третьего предприятия из таблицы исходных данных.

Заполняем остальные ячейки таблицы, суммируя левую и правую части содержимого исходных ячеек. Но третье предприятие является последним в списке, поэтому в соответствии с правилами решения задачи заполняем только те ячейки, в которых левая часть равна объему распределяемых инвестиций (500 у.е.).

Результаты расчетов

Номер предприятия	Объем выделяемых инвестиций	Ожидаемая прибыль
3	200	41
2	100	18
1	200	44
Всего	500	103

Выполняем анализ полученных результатов:

Из таблицы третьего этапа следует, что максимальная прибыль может быть получена, если третьему предприятию выделить 200 у.е., прибыль 41 у.е. Оставшийся объем распределяемых инвестиций составляет 300 у.е.

Из таблицы второго этапа следует, что при распределении 300 у.е. ожидаемая максимальная прибыль составляет 62 у.е., что достигается, если второму предприятию выделить 100 у.е. При этом вклад второго предприятия в максимальную прибыль составит 18 у.е., а оставшийся объем распределяемых инвестиций равен 200 у.е.

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

Таким образом, распределение инвестиций завершено. Оптимальное решение показано в итоговой таблице.