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

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

Многие экономические процессы расчленяются на шаги естественным образом. Это все процессы планирования и управления, развивающиеся во времени.

неделя, день и т. д. Однако метод динамического программирования может

использоваться при решении задач, где время вообще не фигурирует; разделение на шаги в таких задачах вводится искусственно. Поэтому "динамика" задач динамического программирования заключается в методе решения.

или способу решения относятся к задачам динамического программирования. Это задачи

оптимального перспективного и текущего планирования во времени.

каждого периода, либо путем составления единой динамической задачи оптимального программирования

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

метода динамического программирования.

(i = 1,…, N) на период в t (t =

1,…, Т) хозяйственных лет. В начале периода на развитие системы предприятий выделены какие-то средства К, которые должны быть распределены между предприятиями. В процессе деятельности предприятия вложенные в него средства частично амортизируются.

часть которого отчисляется в фонд предприя­тий. В начале каждого хозяйственного

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

заключается в начальном распределении и последу­ющих перераспределениях средств иt =

{иit}, где иit - объ­ем средств, выделенных i-му предприятию в начале t-гo го­да. Для описания динамики системы вводится вектор состо­яния хt = {хit}, где хit - состояние i-го предприятия на на­чало t-гo года.

которого служат трудовые ресурсы, основные фонды, финансовое положение и т.д.,

т.е. хit = { хikt }. Вектор управления - это функция состояния системы на начало соответствующего года: ut = ut(xt-1). Начальное состояние системы х° может быть заданным.

zt — прибыль за t-й год, то полу­чим задачу

где Ω

— область допустимых управлений, или множество эко­номических возможностей, определяемых различными огра­ничениями, налагаемыми на состояние системы и вектор управления.

возникает задача определения момента подачи партии поставки и ее объема.

С размещением заказов связаны некоторые фиксированные затраты, не зависящие от величины заказываемой партии, а зависящие только от факта заказа. С содержанием материальных ресурсов связаны затраты, пропорциональные остатку нереализованной продукции на конец интервала.

ресурса в t-м интервале. Состояние системы будем описывать величиной остатка

нереализованной продукции на конец интервала xt. Начальное x0 и конечное xT состояния системы можно считать заданными. Для бесперебойности потребления поставками нужно управлять. Обозначим через u = {ut} вектор управления, координаты которого суть величины поставок в начале соответствующих интервалов.

Из множества воз­можных управлений требуется выбрать такое, при котором достигается

минимум издержек на заказ и содержа­ние материальных ресурсов. Если St — издержки содержания единицы продукции в t-м интервале, то функция цели примет вид:

шаге определяется вектором xt. Дальнейшее изменение ее со­стояния зависит только

от данного состояния xt и не зависит от того, каким путем система пришла в него. Такие процессы называются процессами без последействия.

которого система переходит из предыдущего состоя­ния xt-1 в новое xt.

Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале ин­тервала решения ut.

прибылью) или потерей (издержками), которые зависят от состояния на начало

шага (этапа) и при­нятого решения.
4. На векторы состояния и управления могут быть нало­жены ограничения, объединение которых составляет область допустимых решений u принадлежит Ω.

t, чтобы получить экстремальное значение функции цели за все Т

шагов.

начального состоя­ния в конечное, называют стратегией управления. Допусти­мая стратегия управления,

доставляющая функции цели экс­тремальное значение, называется оптимальной.
Управление — это воздей­ствие, переводящее систему из начального состояния в конеч­ное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или Хт ко­торой эти точки принадлежат. Тогда допустимые управления переводят точки из области Хо в ХТ.

такую фазовую траекторию, начинающуюся в области Хо и оканчивающуюся в

области ХТ, для которой функция цели достигает экстремального зна­чения. Если в задаче динамического программирования из­вестны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конеч­ные области, то говорят о задаче со свободными концами.