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

Функциональные уравнения Беллмана. Как отмечалось выше, в основе динамического программирования лежит принцип оптимальности, направленный на процедуру построения оптимального управления. Так как оптимальной стратегией может быть только та, которая одновременно оптимальна и для любого количества оставшихся шагов, ее можно строить по частям: сначала для последнего этапа, затем для двух последних, для трех и т. д., пока не придем к первому шагу. Отсюда принцип оптимальности связан со вторым принципом - принципом погружения, согласно которому при решении исходной задачи ее как бы погру жают в семейство подобных ей и решают для одного последнего этапа, для двух последних и т. д., пока не получат решение исходной задачи.

Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что начальное x0 и конечное xT состояния системы заданы. Обозначим через z1(х0, u1) значение функции цели на первом этапе при начальном состоянии системы x0 и при управлении u1, через z2(х1, u2) - соответствующее значение функции цели только на втором этапе, ..., через zi(хi-1,ui) - на i-м этапе, ..., через zN(хN-1, uN) на N-м этапе. Очевидно, что

Z = z (x0, u) = (1)

Надо найти оптимальное управление u*=(;;...;), такое, что доставляет экстремум целевой функции (1) при ограничениях u Щ. Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть ЩN, ЩN-1,N, +, Щ1,2,+,N ? Щ - соответственно области определения для подобных задач на последнем этапе, двух последних и т. д.; Щ - область определения исходной задачи. Обозначим через

F1(xN-1), F2(xN-2), +, Fk(xN-k), +, FN(x0)

соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах. Начинаем с последнего этапа. Пусть хN-1 - возможные состояния системы на начало N-го этапа. Находим:

F1(xN-1) = zN (xN-1, uN). (2)

Для двух последних этапов получаем

F2(xN-2) = (ZN-1(xN-2, uN-1)+F1(xN-1)). (3)

Аналогично:

F3(xN-3) = (ZN-2(xN-3, uN-2)+F2(xN-2)). (4)

Fk(xN-k) = (zN-k+1(xN-k, uN-k+1)+Fk-1(xN-k+1)). (5)

FN(x0) = (z1(x0, u1)+FN-1(x1)). (6)

Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) - общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) - (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N - 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

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

На основании приведенных примеров можно выделить следующие особенности задач динамического программирования.

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

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

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

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

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

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

Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n - размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой Щ, начальное и конечное состояния системы - точками х0, xt Щ. Управление это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X0 или XT, которой эти точки принадлежат. Тогда допустимые управления переводят точки из области Х0 в XT. Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х0 и оканчивающуюся в области ХT, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

1.4 Примеры задач динамического программирования

Приведем еще несколько типичных задач, для решения которых необходимым является применение метода динамического программирования. Задача перспективного планирования. Задача заключается в следующем: пусть планируется деятельность группы N промышленных предприятий П, (i=) на период в t (t =) хозяйственных лет. В начале периода на развитие системы предприятий выделены какие-то средства, обозначим их К, которые должны быть распределены между предприятиями. В процессе деятельности предприятия вложенные в него средства частично амортизируются. Каждое предприятие за год работы приносит доход, который зависит от вложенных в процесс производства средств. Часть этих средств отчисляется в фонд предприятий. В начале каждого хозяйственного года имеющиеся средства перераспределяются между предприятиями. Таким образом, возникает задача определения объема средств в начале каждого года, которые нужно выделить каждому предприятию, чтобы суммарный чистый доход за Т лет был максимальным. Это типичная задача динамического программирования. Здесь процесс принятия решения разбивается на Т шагов. Управление им заключается в начальном распределении и последующих перераспределениях средств ut ={}, где объем средств, выделенных i-му предприятию в начале t-го года. Для описания динамики системы вводится вектор состояния хt={}, где состояние i-го предприятия на начало t-го года. В свою очередь состояние каждого предприятия является вектором, координатами которого служат трудовые ресурсы, основные фонды, финансовое положение и т. д., т. е. =(). Очевидно, что вектор управления это функция состояния системы на начало соответствующего года: ut = ut(xt-1), при этом начальное состояние системы x0 может быть заданным. Целевой функцией будет суммарная прибыль объединения за Т лет, тогда, если zt прибыль за t-й год, то получим задачу

max Z = , u Щ,

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

Задача об оптимальном управлении поставками. В различных областях народного хозяйства возникает задача определения момента подачи партии поставки и ее объема. С размещением заказов связаны некоторые фиксированные затраты К, не зависящие от величины заказываемой партии, а зависящие только от факта заказа. С содержанием материальных ресурсов связаны затраты, пропорциональные остатку нереализованной продукции на конец интервала планирования. Пусть Т - промежуток планирования. Обозначим через vt интенсивность потребления ресурса в t-м интервале. Состояние системы будем описывать величиной остатка нереализованной продукции на конец интервала хt, при этом начальное х0 и конечное хt состояния системы можно считать заданными. Для обеспечения непрерывности потребления поставками нужно управлять. Обозначим через u = {ut} вектор управления, координаты которого величина поставок в начале соответствующих интервалов планирования. Очевидно, что вектор управления есть функция состояния на начало интервала. Из множества возможных управлений требуется выбрать такое, при котором достигается минимум издержек на заказ и содержание материальных ресурсов. Если St издержки содержания единицы продукции в t-м интервале, то функция цели примет вид:

min Z = ,

Состояние системы опишется соотношением хt = xt-1 + ut - vt (t = ). На состояние системы может быть наложено ограничение, связанное с надежностью снабжения: хt ? x0, где х0 - величина некоторого страхового запаса, защищающего с заданной надежностью от сбоев в системе. Объединение ограничений, налагаемых на состояние системы и вектор управления, обозначим через Щ.

Получим задачу:

min Z = , u Щ.

2. Задача о замене оборудования

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

Для количественной формулировки задачи введем следующие обо значения r(t) стоимость продукции, производимой за год на единице оборудования возраста t лет, u(t) расходы, связанные с эксплуатацией этого оборудования, s(t) остаточная стоимость оборудования возраста t лет, р покупная цена оборудования, Т - продолжительность планового периода, t = 0, 1, 2, , Т номер текущего года.

Решение

Чтобы решить задачу, применим принцип оптимальности Беллмана. Рассмотрим интервалы (годы) планового периода в последовательности от конца к началу. Введем функцию условно-оптимальных значений функции цели Fk(t). Эта функция показывает максимальную прибыль, получаемую от оборудования возраста t лет за последние k лет планового периода. Здесь возраст оборудования рассматривается в направлении естественного хода времени. Например, t = 0 соответствует использованию совершенно нового оборудования. Временные же шаги процесса нумеруются в обратном порядке. Например, при k = 1 рассматривается последний год планового периода, при k = 2 последние два года и т. д., при k = T последние T лет.

В этой задаче систему составляет оборудование. Ее состояние характеризуется возрастом. Вектор управления это решение в момент t = 0, 1, 2, +, Т о сохранении или замене оборудования. Для нахождения оптимальной политики замен следует проанализировать, согласно принципу оптимальности, процесс от конца к началу. Для этого сделаем предположение о состоянии оборудования на начало последнего года (k = 1). Пусть оборудование имеет возраст t лет. В начале T-го года имеется две возможности: 1) сохранить оборудование на T - й год, тогда прибыль за последний год составит r(t) u(t), 2) продать оборудование по оста точной стоимости и купить новое, тогда прибыль за последний год будет равна s(t) р + r (0) u(0), где r(0) стоимость продукции, выпущенной на новом оборудовании за первый год его ввода, u(0) эксплуата ционные расходы в этом году. Здесь целесообразно разворачивать про цесс от конца к началу. Для последнего года (k=1) оптимальной политикой с точки зрения всего процесса будет политика, обеспечивающая максимальную прибыль только за последний год. Учитывая значение прибыли при различном образе действия (замена сохране ние), приходим к выводу, что решение о замене оборудования возраста t лет следует принять в случае, когда прибыль от нового оборудования на последнем периоде больше, чем от старого, т. е. при условии

Страницы: 1, 2, 3