8. РЕШЕНИЕ ЗАДАЧИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С УЧЕТОМ ПРЕДЫСТОРИИ ПРОЦЕССА

Все задачи динамического программирования, которые мы до сих пор рассматривали, отличались следующей особенностью: «доход» на каждом шаге и максимальный доход W начиная с шага и далее зависели только от состояния S системы S перед данным, шагом и от примененного управления но не зависели от того, каким образом (каким путем) система пришла в состояние S, т. е. в результате каких управлений, когда и как это произошло. Другими словами, задачу оптимизации управления на каждом шаге мы решали с учетом настоящего состояния S, но без учета предыстории процесса.

Например, решая задачу распределения ресурсов между двумя (или более) отраслями производства, мы в качестве характеристики состояния системы перед каждым шагом брали одну величину — имеющиеся в нашем распоряжении средства ; нам совершенно не было дела до того, когда и как система пришла в это состояние, т. е. как распределялись средства между отраслями на всех предыдущих этапах. Важно было только количество средств К, с которым мы пришли к очередному шагу.

Во многих задачах динамического программирования эта «независимость от предыстории» не имеет места. Например, доход на шаге может зависеть не только от количества средств, вложенного в каждую отрасль на данном шаге, а еще и от того, какие средства и на каких шагах вкладывались в нее ранее.

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

Например, если доход на шаге зависит не только от вложенных средств но и от ранее вложенных средств Z, можно характеризовать состояние системы перед шагом не просто имеющимся в нашем распоряжении запасом средств К, а совокупностью где Z — ранее вложенные средства.

Если существенна не только общая сумма ранее вложенных средств, но и когда именно и сколько средств вкладывалось — в принципе можно «обогатить» состояние S и этими сведениями из прошлого. Таким образом, теоретически всегда можно ввести в число параметров, характеризующих состояние системы в настоящий момент, сколько угодно параметров из «прошлого». Однако, на практике такое «обогащение» фазового пространства быстро приводит к необозримо сложной схеме динамического программирования, настолько сложной, что самый метод перестает быть пригодным. Ведь главная идея динамического программирования: «вместо того, чтобы один раз решать сложную задачу, много раз решать сравнительно простую» перестает себя оправдывать, если «простая» задача перестает быть «простой».

Поэтому попытки решать методом динамического программирования задачи со сложным влиянием «предыстории» обычно ни к чему хорошему не приводят.

Однако, если влияние «предыстории» может быть учтено с помощью небольшого числа параметров (одного, двух, трех), иногда удается построить сравнительно простую схему динамического программирования и решить задачу оптимизации.

В качестве примера задачи «с предысторией» рассмотрим задачу о профилактическом ремонте техники.

Задача ставится следующим образом.

Имеется техническое устройство S, эксплуатируемое в течение лет.

Эксплуатационные расходы зависят от следующих факторов:

— от «возраста» устройства t, т. е. количества лет, протекшего со времени ввода его в эксплуатацию;

— от количества профилактических ремонтов k, произведенных до момента

— от количества лет , протекшего со времени последнего профилактического ремонта.

Предположим, что профилактический ремонт производится (если производится) мгновенно и в начале года. Естественно предположить, что затраты на этот ремонт (стоимость ремонта) зависят от тех же аргументов t, k и , что и эксплуатационные расходы.

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

Поставленная задача может быть решена методом динамического программирования, если характеризовать состояние системы (технического устройства S) к началу каждого шага тремя фазовыми координатами: t — «возрастом» системы, k — количеством ремонтов в прошлом и — временем, протекшим с момента последнего ремонта.

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

Введем следующие обозначения.

— стоимость эксплуатации устройства за год, начинающийся в момент если до момента t никакого ремонта не производилось;

— стоимость эксплуатации устройства за год, начинающийся в момент t, если до момента t производился один ремонт, и со времени этого ремонта прошло лет;

и вообще

— стоимость эксплуатации устройства за один год, начинающийся в момент t, если до момента t производилось k ремонтов, и со времени последнего из них прошло лет.

— стоимость ремонта, производимого в момент если до момента t никакого ремонта не производилось;

— стоимость ремонта, производимого в момент t, если до момента t производился один ремонт, и со времени этого ремонта прошло лет; и вообще

— стоимость ремонта, производимого в момент если до момента t производилось k ремонтов, и со времени последнего из них прошло лет.

Будем изображать состояние технического устройства S точкой S в фазовом пространстве; по одной оси мы будем откладывать «возраст» устройства — время t, по другой — время , протекшее с момента последнего ремонта, по третьей — количество ремонтов k (рис. 3.36). Так как при всех условиях то все возможные состояния системы будут изображаться точками внутри трехгранного угла

Рис. 3.36

Если до момента t ремонта не было, точка S находится на оси если был один ремонт — точка S находится в плоскости параллельной и отстоящей от нее на расстояние l, и т. д.

Чтобы не пользоваться пространственной картиной, «расслоим» фазовое пространство на несколько частей, которые мы будем обозначать:

Часть (0) фазового пространства представляет собой просто ось часть (1) — треугольник на плоскости КО L, часть (2) — треугольник на плоскости, параллельной оси лежащей от нее на расстоянии 2 и т. д. С увеличением номера пространства размеры треугольников все время уменьшаются. Части фазового пространства показаны на рис. 3.37.

Перед началом каждого года у нас есть выбор между двумя управлениями:

— не делать ремонта (продолжать эксплуатировать устройство ).

— сделать ремонт (и после него продолжать эксплуатировать устройство).

Посмотрим, какие перемещения в фазовом пространстве испытает точка S под действием каждого управления.

Пусть точка S находится в пространстве (0) — на оси в точке с координатой (см. рис. 3.37). Под влиянием управления (продолжать эксплуатировать) она за год переместится в точку с абсциссой на той же оси.

Рис. 3.37

Под влиянием управления (сделать ремонт) она переместится в точку S в пространстве (1) с координатами . Вторая координата так как ремонт производится в начале года, т. е. год до конца очередного шага.

Теперь пусть точка S занимает какое-то положение в пространстве (1). Управление (продолжать эксплуатировать) приведет к тому, что как t, так и за один шаг увеличатся на одну едини т. е. точка S переместится вверх и вправо (параллельно гипотенузе треугольника) в точку с координатами , если прежние координаты были .

Если же мы применим управление U (сделаем ремонт), точка переместится в пространство (2), в точку S с координатами .

Вообще, если точка S находится в пространстве то управление перемещает ее на один шаг вправо и вверх, из точки с координатами в точку с координатами а управление — в следующее по порядку пространство в точку с координатами .

Запишем правила перехода точки S в фазовом пространстве под влиянием управлений в виде «таблицы преобразования» (см. табл. 8.1, первые пять столбцов).

Таблица 8.1

Таким образом, нам ясно, как перемещается точка в фазовом пространстве под влиянием любого управления, т. е. мы знаем функцию

согласно которой меняется состояние системы под влиянием примененного управления ).

Теперь посмотрим, к какому «выигрышу» — расходу на данном шаге приведет каждое управление. Если мы применим управление то на данном шаге мы будем иметь только эксплуатационные расходы; если управление — расходы на ремонт плюс эксплуатационные на ближайший год, но другие, чем если бы ремонта не было. Запишем эти расходы в той же табл. 8.1 в виде добавочного столбца.

Пользуясь этой таблицей, мы можем теперь для любого состояния системы S и любого управления ( или ), примененного в любой момент t, найти:

— куда переместится точка S под действием управления;

— к какому расходу средств это приведет.

После того, как такая таблица составлена, уже нетрудно организовать самую процедуру оптимизации.

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

Продемонстрируем эту методику на конкретном примере.

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

Таблица 8.2

Таблица 8.3

Таблица 8.4

Таблица 8.5

Решение. Пользуясь таблицами функций 8.2 и 8.3 и Таблицей преобразования 8.1, развернем процесс динамического программирования. Как всегда, начнем с оптимизации последнего (шестого) шага.

Все возможные состояния системы S перед этим шагом будут изображаться точками с абсциссой в пространствах (0), (1), (2), (3), (4) (см. рис. 3.38). Для шестого (последнего) шага оптимальным будет то управление или при котором расход на последнем шаге минимален. Расходы будем вычислять согласно последнему столбцу табл. 8.1. На рис. 3 38, кроме состояния системы, мы будем обозначать еще и оптимальное управление: будет обозначаться стрелкой, направленной вправо (в пространстве ) и вправо и вверх (в остальных пространствах). Управление выводящее точку из данной части фазового пространства и переводящее в следующую по порядку часть, будем изображать стрелкой, направленной вправо и вниз У каждой точки внутри кружка будем записывать минимальный расход на всех оставшихся шагах, соответствующий данному состоянию системы (условный оптимальный выигрыш).

Рис. 3.38

Расчеты, связанные с оптимизацией, будем оформлять в виде таблиц (см табл. 8.4 и 8.5 на стр 169, 170)

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

Минимальный расход равен 21,7. Достигается он при следующем оптимальном управлении:

— на первом году участок эксплуатируется без ремонта;

— в начале второго, третьего, четвертого и пятого годов производится ремонт;

— на шестом году участок эксплуатируется без ремонта.

При этом расходы достигают минимума, равного 21,7 условных единиц.