Презентация "Динамическое программирование"

1. Основные понятия

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

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

В экономической практике встречается несколько типов задач, которые по постановке или способу решения относятся к задачам динамического программирования. Это задачи оптимального перспективного и текущего планирования во времени.

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

Рассмотрим несколько типичных задач, для решения которых естественным является применение метода динамического программирования.

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

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

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

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

Целевой функцией будет суммарная прибыль объединения за Т лет. Если zt — прибыль за t-й год, то полу­чим задачу

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

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

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

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

2.Особенности задач динамического программирова­ния

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

2. На каждом шаге выбирается одно решение ut, под дей­ствием которого система переходит из предыдущего состоя­ния xt-1 в новое xt. Это новое состояние является функцией состояния на начало интервала xt-1 и принятого в начале ин­тервала решения ut.

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

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

5. Требуется найти такое допустимое управление ut для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

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

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