Задача - динамическое программирование
Cтраница 1
Задачи динамического программирования являются многоэтапными. Поэтому термин динамическое программирование не столько определяет особый тип задач, сколько характеризует методы нахождения решения отдельных классов задач математического программирования, которые могут также относиться к задачам, линейного программирования. [1]
Задачи динамического программирования имеют ряд отличительных свойств. Прежде всего в них рассматривается процесс поведения некоторой системы во времени, причем состояние системы в каждый момент времени однозначно определяется численными значениями некоторого набора параметров. Операция выбора решения состоит в преобразовании этого набора параметров в такой же набор с другими численными значениями. Наконец, если система в рассматриваемый момент времени находится в некотором состоянии, то ее поведение в дальнейшем определяется этим состоянием и выбираемым управлением, но не зависит от того, в каких состояниях система была до этого момента. [2]
Задачи динамического программирования представляют собой развитие задач линейного программирования в направлении введения в рассмотрение элемента времени и представления процесса решения в виде последовательности выборов. [3]
Задачи динамического программирования чаще решаются численно с помощью вычислительных машин, чем точными аналитическими методами. В этом, с одной стороны, сила, а с другой - слабость метода динамического программирования. [4]
 |
Пример многостадийного процесса. [5] |
Тогда задача динамического программирования формулируется следующим образом. Из множества возможных управлений и найти такое, которое при заданном значении переменных х на входе первого элемента позволяет достигнуть заданного значения xw выходных переменных Л - го элемента процесса, так чтобы целевая функция У (, и) достигла экстремального значения. [6]
Многие задачи динамического программирования не поддаются аналитическому решению. В этих случаях применяются численные методы, часто требующие использования вычислительных машин. Принцип вложения позволяет преодолеть серьезный недостаток численных методов, а именно отсутствие общности. При применении указанного метода достигается общность, присущая аналитическим методам, за счет получения спектров решений. [7]
Решение задачи динамического программирования с мультипликативным критерием характеризуется тем, что любая такая задача может быть сведена к задаче с аддитивным критерием. При этом обычно непосредственно не логарифмируют w, а заключают в основу решения такой выбор условного оптимального управления на каждом шаге, при котором выигрыш на всех оставшихся шагах обращается в максимум. Этот выигрыш равен произведению выигрыша на данном шаге и оптимизированного выигрыша на всех последующих шагах. [8]
 |
Пример многостадийного процесса. [9] |
Решение задач динамического программирования опирается на принцип оптимальности. Этот принцип утверждает, что при любом начальном состоянии и оптимальном начальном управлении последующие управляющие воздействия должны быть оптимальными относительно состояния, возникшего в результате начального. [10]
Трудности задач динамического программирования заключаются в выборе параметров, характеризующих состояние системы, и в разделении процесса решения на этапы. [11]
В задачах динамического программирования первый пункт учитывают, делая на каждом шаге условные предположения о возможных вариантах окончания предыдущего шага и проводя для каждого из вариантов условную оптимизацию. Выполнение второго пункта обеспечивается тем, что в задачах динамического программирования условная оптимизация проводится от конца процесса к началу. Сперва оптимизируется последний тп-й шаг, на котором не надо учитывать возможные воздействия выбранного управления хт на все последующие шаги, так как эти шаги просто отсутствуют. Делая предположения об условиях окончания ( m - l) - ro шага, для каждого из них проводят условную оптимизацию тп-го Шага и определяют условное оптимальное управление хт. Так же действуют на всех остальных шагах до первого. На первом шаге, как правило, не надо делать условных предположений, так как состояние системы перед первым шагом обычно известно. [12]
Поскольку многие задачи динамического программирования решаются численными методами, в случае неаналитических ( негладких) функций решение получается также легко. [13]
Выполнение для задачи динамического программирования первого условия позволяет сформулировать для нее принцип оптимальности Беллмана. [14]
Для решения задач динамического программирования часто приходится использовать численные методы. В этом случае наличие ограничений типа равенств или неравенств не создает особых затруднений. С помощью алгоритма динамического программирования мы просто проверяем, не нарушены ли ограничения. Если нарушение произошло, мы отбрасываем соответствующую комбинацию переменных как недопустимую. [15]
Страницы: 1 2 3 4