Изложение теоретических аспектов исследования, Динамическое программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

Динамическое программирование

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

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

Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных. Это значительно сокращает объем вычислений и ускоряет процесс принятия управленческого решения.

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

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

Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления uN, под воздействием, которого система переходит из одного состояния SN в другое SN+1: SN SN+1. Поскольку процесс марковский, то SN = uN (SN) зависит только от текущего состояния.

Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего со стояния и принятого решения: (SN , SN ).

Общий эффект (доход) за N шагов слагается из доходов на отдельных шагах, т. е. критерий оптимальности дол жен быть аддитивным (или приводящимся к нему).

Требуется найти такое решение uN для каждого шага (n = 1, 2, 3, ..., N), т. е. последовательность (u1, ..., uN), чтобы получить максимальный эффект (доход) за N шагов.

В отличие от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, разработанного американским математиком Р. Беллманом. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге; не локально лучше, а лучше с точки зрения процесса в целом.

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

Любая возможная допустимая последовательность решений (u1, ..., uN) называется Стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется Оптимальной.

В основе общей концепции метода ДП лежит Принцип оптимальности Беллмана:

Оптимальная стратегия обладает таким свойством, что независимо от того, каким образом система оказалась в рассматриваемом конкретном состоянии, последующие решения должны составлять оптимальную стратегию, привязывающуюся к этому состоянию. Математически этот принцип записывается в виде Рекуррентного соотношения ДП (РДП):

,

Где -- все допустимые управления при условии, что система находится в состоянии SN;

(SN , SN ) -- эффект от принятия решения uN;

-- эффект за оставшиеся n шагов.

Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, лишь оптимальные выходы. РДП позволяют заменить трудоемкое вычисление оптимума по N переменным в исходной задаче решением N задач, в каждой из которых оптимум годится лишь по одной переменной.

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

В качестве примера построения РДП рассмотрим использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х :

Где xJ -- количество ресурса, используемое j-м способом;

-- доход от применения способа j, j = 1, N.

Рекуррентные соотношения, с помощью которых находится решение этой задачи, имеют вид:

Похожие статьи




Изложение теоретических аспектов исследования, Динамическое программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

Предыдущая | Следующая