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

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

Пример 18.1.

Пусть r_fc(t) — затраты на эксплуатацию изделия в течение к-го года, если со времени последней замены прошло t лет; g_k(t) — ликвидная стоимость на начало к-го года; р_к — начальная стоимость изделия, купленного в начале к-го года. Требуется определить оптимальные сроки замены изделия в течение п лет, с тем чтобы минимизировать затраты на его содержание.

Решение. Показатель эффективности — суммарные затраты на эксплуатацию изделия. Затраты на каждом к-м шаге зависят от выбранного управления: и_к=и^с — если оборудование не меняется (старое); и_к = u^h — если оборудование в к-й год заменено. В первом случае затраты составят r*.(t), а во втором — р_к + г_к(0) — g_k(t).

Если к началу к-го шага система находилась в состоянии t и применяется управление «не менять изделие», то система переходит в состояние t +1, т. е. изделие устаревает на год. В противном случае, когда применяется управление «менять изделие», система переходит в состояние t = 1 (новое изделие). Формально это запишется в следующем виде:

Введем обозначение W_fc(t) — условные оптимальные затраты с к-го шага по n-й включительно, если к началу года к возраст изделия составлял t лет. Теперь можно записать математическую модель в виде рекуррентных уравнений.

Для последнего (п-го) шага соответственно имеем.

Приведем решение задачи при конкретных условиях. Автомобиль эксплуатируется не более 6 лет (процесс шестишаговый); стоимость новой машины на к-м году эксплуатации составляет р_к = 5000 +.

+ 500(/с — 1) уел. ед.; после t лет эксплуатации машину на к-м шаге можно продать за g (t) = р_К2~‘ уел. ед. Стоимость содержания в течение k-го года составляет r_k(t) = 0, lp_fe(r + 1) уел. ед.

Для последнего шага имеем уравнение.

которое справедливо для каждого 0 < t < 5 — числа лет, прошедших после последней замены автомобиля. Решение рекуррентного уравнения приведено в табл. 18.1.

Таблица 18.1

Решение рекуррентного уравнения для последнего шага.

Из табл. 18.1 следует, что менять автомашину на последнем из рассматриваемых годов необходимо только в том случае, если она эксплуатировалась 5 лет. В других вариантах автомашину менять нецелесообразно.

На шагах с пятого по первый необходимо решать следующее рекуррентное уравнение:

Решения этого уравнения для всех оставшихся этапов и соответствующих возможных значений величины к приведены в табл. 18.2. Поясним ее построение. В третьем и четвертом столбцах записаны результаты расчетов значений величины W_k(.t) при различных решениях (и^с, u^h соответственно), а в пятом — наименьшее из них, т. е. W_k(t). Поскольку оптимальное значение расходов составляет И^*(0) = 17 387,5 у.е.л. ед. и машина новая, то применяем и_х = и^с. Система перейдет в состояние Sj = 1. На следующий год для машины возраста один год следует применять управление и₂= и^с и S₂ = 2. На третьем шаге в соответствии с таблицей применяется такое же управление, вследствие чего система переходит в состояние S₃ = 3 (машина продолжает эксплуатироваться третий год). После четвертого года эксплуатации покупается новая машина и система переходит в состояние S₄= 1. Пятый и шестой год продолжается эксплуатация машины.

Решение рекуррентного уравнения на шагах с первого по пятый.

Таким образом, исходя из таблицы можно построить следующее оптимальное решение задачи: U* = (и^с, и^с, и^с, u^h, и^с, и^с).

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

Примечание 18.2. Метод динамического программирования применим не только для аддитивных показателей эффективности, но и для мультипликативных критериев вида.

Действительно, в самом общем случае можно от мультипликативной функции перейти к аддитивной функции путем операции логарифмирования, введя новую целевую функцию W_k = lnW_fc, которая имеет экстремум там же, где и исходная функция.

Поэтому временно можно перейти от функции (18.3) к функции вида.

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

Можно показать, что при мультипликативном критерии возможно прямое применение вышеизложенной схемы, поскольку в некоторых случаях для мультипликативных целевых функций могут быть использованы рекуррентные соотношения, аналогичные соотношениям (18.1) и (18.2):

Пример 18.2.

Между четырьмя предприятиями необходимо разместить заказ на изготовление восьми машин. Вероятности выполнения заказа Р_к каждым предприятием к, зависящие от величины заказа, заданы в табл. 18.3.

Таблица 18.3

Вероятности выполнения заказа к примеру 18.2.

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

Решение. Этапом будем считать размещение заказа на одном из предприятий (имеем четырехшаговый процесс). Состояние системы определяется числом неразмещенных заказов (исходное состояние S₀ = 8). Уравнение, согласно которому система переводится в новое состояние, имеет вид.

где и_к — количество машин, закрепляемых за к-м предприятием. Показатель эффективности есть произведение вероятностей

Если для всех предприятий положить Р_к(0) = 1, то уравнения Веллмана для данной задачи будут иметь следующий вид:

Процесс решения задачи начинаем с распределения машин последнему (четвертому) предприятию. Поскольку ему должны быть полностью спланированы все нераспределенные машины, то результаты решения уравнения (18.7) совпадают с последней строкой табл. 18.3.

Для предприятий 3, 2 и 1 последовательно решаем уравнение (18.6) для всех возможных состояний (число нераспределенных машин может быть от 0 до 8). Результаты заносим в табл. 18.4.

Таблица 18.4

Сводная таблица к решению примера 18.2.

Прокомментируем кратко схему ее заполнения. Вначале заполняется таблица относительно возможных вариантов распределения машин третьему предприятию. Рассматривается возможное число распределяемых машин (от 0 до 8). Например, если на данном третьем шаге требуется распределить шесть машин, то просматриваются варианты закрепления за третьим предприятием от 0 до 6 машин. При этом если хотим закрепить две машины, то четвертому предприятию останется четыре, если хотим закрепить три машины, то четвертому предприятию останется три машины и т. д. (см. табл. 18.4). Для удобства наилучший из достигнутых на каждой альтернативе вариантов отмечается полужирным шрифтом, что соответствует взятию максимума. Когда рассмотрены все варианты для третьего этапа, переходят ко второму. Здесь важно понять, что значения для W₃‘ берутся из только что полученных выделенных значений для третьего предприятия. Наконец, для первого предприятия рассматриваются все возможные значения распределяемых заказов с использованием значений W2, полученных для второго этапа.

Из табл. 18.4 следует, что наибольшую вероятность Wi* = 0,263 имеет план, согласно которому за первым предприятием закреплено изготовление двух машин. Используя уравнение перехода в новое состояние (18.5), находим S₂= 6. Из таблицы следует, что за вторым предприятием следует закрепить заказ на изготовление двух машин (VV2 = 0,376). Теперь понятно, что S₃ = 4 и за вторым предприятием следует закрепить изготовление двух машин (W₃ = 0,48), а за четвертым — тоже две (W₄ = 0,8). Итак, если каждому предприятию будет заказано ровно по две машины, то вероятность выполнения всех заказов Р* = 0,263 будет наибольшей. Оптимальный план есть [Г = (и_г = 2, ц₂=2, 1/₃=2, и₄= 2).