26. Динамическое программирование.
Динамическое программирование - способ решения сложных задач путём разбиения их на более простые подзадачи.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем. Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Принцип оптимальности Беллмана. Первая формулировка принципа оптимальности: для получения оптимального решения многоэтапного процесса решение, принимаемое на отдельном этапе, должно быть оптимальным относительно состояния, в котором система оказалась к началу данного этапа, и не должно зависеть от решений на предыдущих этапах, которые привели систему в данное состояние. Вторая формулировка принципа оптимальности: для аддитивного функционала любой участок оптимальной траектории оптимален. Введем дополнительные функции : . Их экономический смысл: максимальные значения частных целевых функций , вычисляемых по укороченным наборам управляющих переменных - справедливо, так как в финальный момент времени изменений нет и экономическая эффективность равна 0. Принцип оптимальности:
|
- 1. Определение задачи математического программирования
- 2. Допустимое решение задачи, одр, оптимальное решение задачи.
- 3. Экономико–математические модели задач лп: задача о банке
- Задача о банке
- 4. Экономико – математические модели задач лп: задача определения оптимального ассортимента продукции.
- 5. Задача лп, стандартная форма, каноническая форма.
- 6. Целевая функция, градиент
- 7. Двойственная задача и ее свойства
- 8. Первая теорема двойственности и ее следствия
- 94. Экономическая интерпретация двойственной задачи.
- 10. Транспортная задача, математическая модель и ее свойства.
- 11. Метод минимального элемента, метод северо-западного угла.
- 12. Метод потенциала, цикл
- 13.Открытые модели транс-ой задачи.Принцип замыкания
- 14. Матричные игры с нулевой суммой.
- 15. Смешанные стратегии, чистые стратегии.
- 16. Оптим-ое решение игры в смешанных стратегиях, седловая точка
- 21. Кооперативная игра, коалиции и дележи.
- 24 Альтернатива (альтернативная стратегия)
- 28. Риск, источники риска.
- 26. Динамическое программирование.
- 27. Метод дп включает три основных этапа:
- 29. Полнота и арбитраж.
- 30. Модель (b,s) – рынка. Пример дискретной и непрерывной модели.
- 31. Хеджирование как метод защиты от риска.
- 32. Модель Марковица.
- 33. Общие сведения о сетях
- 34 Сетевое планирование и управление
- 35. Временные параметры сетевых моделей
- 36.Сетевые графики и их анализ
- 37. Однофакторное и многофакторное уравнения регрессии
- 38. Типы связи между случайными величинами.
- 39. Коэффициент корреляции, детерминации.
- Вопрос 16. Метод северо-западного угла
- Вопрос 17. Метод потенциалов