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)
то старое оборудование целесообразно сохранить. Итак, для последнего года оптимальная политика и максимальная прибыль F1(t) находятся из условия
Пусть k = 2, т. е. рассмотрим прибыль за два последних года. Де лаем предположение о возможном состоянии t оборудования на начало предпоследнего года. Если в начале этого года принять решение о со хранении оборудования, то к концу года будет получена прибыль r(t) u(t). На начало последнего года оборудование перейдет в состоя ние t + 1 и при оптимальной политике в последнем году оно принесет прибыль, равную F1 (t+1). Значит общая прибыль за два года составит r(t) u(t) + F1(t + 1). Если же в начале предпоследнего года будет принято решение о замене оборудования, то прибыль за предпоследий год составит
s(t) p + r(0) - u(0).
Поскольку приобретено но вое оборудование, на начало последнего года оно будет в состоянии t = 1. Следовательно, общая прибыль за последние два года при оптимальной политике в последнем году составит
s(t) - p + r(0) - u(0) + F1(1)
Условно оптимальной в последние два года будет политика, доставляющая максимальную прибыль
Аналогично находим выражения для условно оптимальной прибыли за три последних года, четыре и т. д. При k=T получим max Z = FT (t0).
Таким образом, разворачивая весь процесс от конца к началу, получаем, что максимальная прибыль за плановый период Т составит FT(t0). Так как начальное состояние t0 известно, из выражения для FT(t0) находим оптимальное решение в начале первого года, потом вытекающее из него оптимальное решение для второго года и т. д. Обратимся к числовому примеру. Практическое применение рассмотренной выше схемы представлено в приложении.
3. Расчет показателей экономико-математической модели
Решим задачу замены оборудования на плановый период в N = 10 лет, оборудование пятилетнего возраста (T = 5).
В начале планового периода продолжительности в N лет имеется оборудование возраста t, известна стоимость r(t) продукции, производимой в течение года с использованием этого оборудования; ежегодные расходы u(t) связанные с эксплуатацией оборудования; его остаточная стоимость s; стоимость p нового оборудования (сюда же включены затраты, связанные с установкой, запуском оборудования). Данные задачи приведены в таблице.
| Возраст оборудования | |||||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| r(t) | 30 | 30 | 29 | 29 | 29 | 28 | 28 | 27 | 27 | 26 | 26 |
| u(t) | 10 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Для решения задания применим принцип оптимальности Беллмана. Рассмотрим интервалы времени, т.е. годы, планового периода от конца к началу. Обозначим функцию условно-оптимальных значений функции цели Fk(t) - максимальную прибыль, которая будет получена от использования оборудования возраста t лет за последние k лет планового периода.