Динамическое программирование - метод оптимизации, приспособленный к операциям, в которых процесс принятия решений может быть разделен на отдельные этапы (шаги)
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программированиясостоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.
Метод динамического программирования сверху — это простое запоминание результатов решения тех подзадач, которые могут повторно встретиться в дальнейшем.Динамическое программирование снизу включает в себя переформулирование сложной задачи в виде рекурсивной последовательности более простых подзадач.
Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей.
Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.
Оптимальное управление характеризуется такими свойствами, что независимо от исходного состояния на любом шаге управления и последующее управление должно избираться оптимальным относительно состояния, к которому придет система в конце этого шагоку.
Метод, построенный на использовании принципа оптимальности, позволяет установить соотношение между экстремальными значениями целевой функции в задачах, характеризующихся различной продолжительности процесса и разными начальными состояниями При этом необходимо учитывать последствия реализации найденного оптимального решения и для последующих решений Такой подход обусловлен разработкой оптимальной стратегии Процесс принятия решения в этом случае является многошаговойвим.
При этом, если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейные, то в задачах динамического программирования эти зависимости могут иметь и нелинейный и характе.
Динамическое программирование применяется в основном для решения задач двух классов: планирование деятельности экономической системы (предприятий) с учетом изменения изготавливаемой во времени отв в соответствии с изменения потребности; перераспределения ресурсов по различным направлениям во время.
Общие характеристики
Каким же условиям должна отвечать задача оптимизации, чтобы ее можно было описать модельюдинамического программирования Эти условия следующие:
1 Задача может интерпретироваться как n-шаговый процесс управления, а показатель эффективности процесса может быть представлен в аддитивной форме, то есть как сумма показателей эффективности на каждом шагу
2 Структура задачи инвариантна относительно числа шагов п, т.е. должна быть определена для любого п и не зависеть от этого числа
3 На каждом шагу состояние системы определяется конечным числом бы параметров состояния и управляется конечным числом г переменных управления, причем г и в не зависят от количества шагов п
4 Выбор управления на К-м шаге не влияет на предыдущие шаги, а состояние в начале этого шага является функцией только предшествующего состояния и выбранного нем управления (условие отсутствия последействия)
Отметим также, что выполнение указанных условий иногда очевидно, а иногда достигается после соответствующих преобразований
_______________
Динамическое программирование (динамическое планирование) – это раздел математического программирования, который изучает совокупность приёмов и методов, позволяющих находить оптимальные решения, основанные на вычислении последствий каждого решения и выработке оптимальной стратегии для последующих решений.
Задачи динамического программирования являются многоэтапными, поэтому термин «динамическое программирование» не столько определяет особый тип задач, сколько характеризует методы нахождения решения отдельных классов задач математического программирования.
В общем случае задача динамического программирования формулируется следующим образом. Пусть данная физическая система 
находится в некотором начальном состоянии 
и является управляемой. Благодаря осуществлению некоторого управления (некоторой операции) 
указанная система переходит из начального состояния в конечное состояние 
При этом качество каждого из реализуемых управлений характеризуется соответствующим значением функции 
Задача состоит в том, чтобы из множества возможных управлений найти такое 
при котором функция 
принимает экстремальное значение 
Можно выделить два класса задач, к которым методы динамического программирования применяются наиболее удачно.
Первый класс – это задачи планирования деятельности экономического объекта (предприятия, отрасли и т.п.) с учётом изменения потребности в производимой продукции во времени.
Второй класс задач – задачи оптимального распределения ресурсов между различными направлениями во времени.
Наибольшей эффективности методы динамического программирования достигают там, где по самому существу задачи приходится принимать решения по этапам.
_____________ учебнииииииик
Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.
Из этого следует, что планирование каждого шага должно проводиться с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.
Таким образом, динамическое программирование в широком смысле представляет собой оптимальное управление процессом, посредством изменения управляемых параметров на каждом, и, следовательно, воздействуя на ход процесса, изменяя на каждом шаге состояние системы.
В целом динамическое программирование представляет собой стройную теорию для восприятия и достаточно простую для‚ применения в коммерческой деятельности при решении как линейных, так и нелинейных задач.
Динамическое программирование (ДП) является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами ДП решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать как для решения связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения ДП для решения задач управления. А возможность упрощения процесса, которая достигается за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов увеличивает достоинства этого комплекса методов.
Вместе с тем ДП свойственны и недостатки. Прежде всего в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний. Для процессов с непрерывным временем ДП рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона — Якоби — Беллмана. ДП применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составления календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети, формирование последовательности развития коммерческой операции и т.д.
2. Постановка задачи динамического программирования
Общая постановка задачи динамического программирования формулируется следующим образом. Имеется некоторая управляемая система , характеризующаяся определенным набором параметров. В этой системе происходят какие-то процессы (экономические, производственные, технологические и т.п.), которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определенные значения параметров, описывающих состояние системы. Заданы условия, позволяющие определять или начальное, или конечное состояние системы, или оба этих состояния. Иногда задаются области начальных и конечных состояний. Поскольку управление системой осуществляется для достижения конкретной цели, то указан показатель эффективности управления, называемый целевой функцией, численно выражающий эффект («выигрыш»), получаемый при тот или ином управлении из множества допустимых управлений.
В экономических системах целевая функция может определять прибыль, затраты, рентабельность, объем производства и т.п.
Задача динамического программирования (ДП) состоит в выборе из множества допустимых управлений такого, которое переводит систему из начального состояния в конечное, обеспечивая при этом целевой функции экстремум (минимум или максимум в зависимости от ее экономической сути). Такое управление называется оптимальным.
