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

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

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

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

Реализация названных  принципов дает гарантию того, что  решение, принимаемое на очередном  шаге, окажется наилучшим относительно всего процесса в целом, а не узких  интересов данного этапа. Последовательность пошаговых решений приводит к  решению исходной 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 лет следует принять в случае, когда прибыль от нового оборудования на последнем периоде больше, чем от старого, т. е. при условии 

s(t) - p + r(0) - u(0) > r(t) - u(t) 

Если же 
 

s(t) - p + r(0) - u(0) < r(0) - u(0)