Лекция 6. Динамическое программирование Содержание лекции: 1. Формулировка задачи динамического программирования Формулировка задачи динамического программирования. - презентация

1 Лекция 6. Динамическое программирование Содержание лекции: 1. Формулировка задачи динамического программирования Формулировка задачи динамического программирования Формулировка задачи динамического программирования 2. Принцип оптимальности Беллмана Принцип оптимальности Беллмана Принцип оптимальности Беллмана 3. Алгоритм решения задач динамического программирования Алгоритм решения задач динамического программирования Алгоритм решения задач динамического программирования 4. Экономические приложения задач динамического программирования Экономические приложения задач динамического программирования Экономические приложения задач динамического программирования Динамическое программирование © Н.М. Светлов,

2 Литература Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.: Финансы и статистика, Глава 5. Фомин Г.П. Математические методы и модели в коммерческой деятельности: Учебник. – 2-е изд. М.: Финансы и статистика, Глава 5. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. 2-е изд. М.: ЮНИТИ-ДАНА, Раздел 3.5. Экономико-математические методы и прикладные модели: Учеб. пособие для вузов / Под ред. В.В. Федосеева. 2-е изд. М.: ЮНИТИ-ДАНА, Раздел / 9 Динамическое программирование © Н.М. Светлов,

3 6.1. Формулировка задачи динамического программирования Дано: Дано: множество состояний множество состояний в том числе начальное и конечное в том числе начальное и конечное множество возможных переходов из одного состояния в другое множество возможных переходов из одного состояния в другое с каждым переходом связывается числовой параметр с каждым переходом связывается числовой параметр интерпретируется как затраты, выгода, расстояние, время и т.п.интерпретируется как затраты, выгода, расстояние, время и т.п. Найти: Найти: оптимальную последовательность переходов (путь) из начального состояния в конечное оптимальную последовательность переходов (путь) из начального состояния в конечное максимум или минимум суммы числовых параметров максимум или минимум суммы числовых параметров предполагается, что хотя бы один путь из начального состояния в конечное существует предполагается, что хотя бы один путь из начального состояния в конечное существует 3/ 9 Динамическое программирование © Н.М. Светлов,

4 Пример / 9 Динамическое программирование © Н.М. Светлов,

5 Математическая запись 6.1 5/ 9 1, если путь проходит через дугу (i,j) 0, если не проходит или такой дуги нет Например, расстояние между пунктами i и j, км {(1,2), (1,3), (2,4), (2,5), (3,5)…} единственность искомого пути: в каждую вершину можно прийти только из одной вершины (или вообще нельзя) если искомый путь пришёл в вершинуk, то он должен из неё выйти (если только она не конечная) Условие целочисленности переменных Между вершинами i и j нет дуги. сумма числовых значений (e.g. расстояний) по всему пути Динамическое программирование © Н.М. Светлов,

6 6.2. Принцип оптимальности Беллмана Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B. Если вершины A и B лежат на оптимальном пути между вершинами 0 и X, то часть оптимального пути от 0 до X между вершинами A и B непременно является оптимальным путём от A до B. Следствие Следствие Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A Чтобы найти оптимальный путь от 0 до A, достаточно исследовать продолжения к A всех оптимальных путей до вершин, предшествующих A Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A Продолжения неоптимальных путей к предшествующим вершинам можно не просчитывать: они никогда не дадут оптимального пути к A Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования Принцип Беллмана позволяет построить простую и эффективную вычислительную процедуру для решения задач динамического программирования 6/ 9 Динамическое программирование © Н.М. Светлов,

7 6.3. Алгоритм решения задач динамического программирования максимум 7/ 9 Динамическое программирование © Н.М. Светлов,

8 6.3. Алгоритм решения задач динамического программирования минимум 8/ 9 Динамическое программирование © Н.М. Светлов,

9 6.4. Экономические приложения Дуги - работы, которые должны быть выполненыДуги - работы, которые должны быть выполнены Параметры – продолжительность работПараметры – продолжительность работ Самый длинный путь (max) определяет минимальный срок выполнения проектаСамый длинный путь (max) определяет минимальный срок выполнения проекта Управление проектами Дуги соответствуют решениям:Дуги соответствуют решениям: e.g., эксплуатировать; ремонтировать; списатьe.g., эксплуатировать; ремонтировать; списать Параметры –доходыПараметры –доходы Самый выгодный путь (max) определяет жизненный цикл элемента основных средствСамый выгодный путь (max) определяет жизненный цикл элемента основных средств Управление реновацией основных средств производства Дуги – операции, переводящие фирму в новое состояниеДуги – операции, переводящие фирму в новое состояние Параметры – доходы (расходы)Параметры – доходы (расходы) Самый выгодный путь определяет наилучший бизнес-планСамый выгодный путь определяет наилучший бизнес-план Бизнес- планирование Дуги – пути сообщенияДуги – пути сообщения Параметры – время (или стоимость) перевозкиПараметры – время (или стоимость) перевозки Самый выгодный (min) путь определяет оптимальную перевозкуСамый выгодный (min) путь определяет оптимальную перевозку Поиск оптимального маршрута 9/ 9 Динамическое программирование © Н.М. Светлов,