Стохастическое динамическое программирование

В рассмотренных примерах управляемые переменные, а также переменные состояния и шага принимали только целочисленные значения. (Задачи такого рода называют задачами дискретного программирования). Кроме того, на результаты и переходы из одного состояния в другое не оказывали влияния случайные факторы. Учет случайного характера параметров модели есть предмет анализа стохастического динамического программирования.

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

Пример 2.8.4. Задача садовника.

Предположим, что каждый год почва может находиться в одном из трех состояний: хорошем (1), удовлетворительном (2) или плохом (3). Пусть k=1 и 2 – две возможные стратегии поведения садовника: не удобрять или удобрять. Оптимальное поведение садовника определяется такой стратегией, при которой он получает наибольший ожидаемый доход через N лет. Обозначим р_ij(k) – вероятность перехода почвы из состояния i в состояние j при применении садовником стратегии k.

Пусть 0.2 0.5 0.3 0.3 0.6 0.1

{р_ij(1)}= 0 0.5 0.5 , {р_ij(2)}= 0.1 0.6 0.3

0 0 1 0.05 0.4 0.55

Поясним суть приведенных данных:

Если садовник не применяет удобрения (k=1), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.2, в удовлетворительное – 0.5 и в плохое – 0.3. При плохом состоянии (строка 3) с вероятностью 1 почва остается плохой.

Если садовник применяет удобрения (k=2), то при хорошем состоянии почвы (строка 1) вероятность ее перехода в хорошее состояние – 0.3, в удовлетворительное – 0.6 и в плохое – 0.1. При плохом состоянии (строка 3) с вероятностью 0.05 почва станет хорошей, с вероятностью 0.4 удовлетворительной и с вероятностью 0.55 останется плохой.

Обозначим r_ij(k) – доход (или убыток), который получит садовник за одногодичный период, если почва перейдет из состояния i в состояние j при применении садовником стратегии k.

Пусть 7 6 3 6 5 – 1

{r_ij(1)}= 0 5 1 , {r_ij(2)}= 7 4 0 .

0 0 –1 6 3 –2

Поясним суть приведенных данных:

Если садовник не применяет удобрения (k=1), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 7 единиц, в удовлетворительное – 6 и в плохое – 3. При переходе из плохого состояния (строка 3, вспомним, что в этом случае с вероятностью 1 почва остается плохой) доход составит –1 (убыток).

Если садовник применяет удобрения (k=2), то при переходе из хорошего состояния почвы (строка 1) в хорошее доход составит 6, в удовлетворительное – 5 и в плохое – убыток в размере 1 (не в коня корм). При переходе из плохого состояния (строка 3) в хорошее доход составит 6, в удовлетворительное – 3 и в плохое – убыток 2.

Обозначим v_i(k) – ожидаемый доход, обусловленный одним переходом из состояния i при стратегии k, тогда

v_i(k)=∑_jp_ij(k)r_ij(k).

Если удобрения не применяются (k=1), тогда

v₁(1)=0.2´7+0.5´6+0.3´3=5.3,

v₂(1)=0´0+0.5´5+0.5´1=3,

v₃(1)=0´0+0´0+1´ (–1)= –1.

При использовании удобрений (k=2) имеем

v₁(2)=0.3´6+0.6´5+0.1´ (–1)=4.7,

v₂(2)=0.1´7+0.6´4+0.3´0=3.1,

v₃(2)=0.05´6+0.4´3+0.55´ (–2)=0.4.

Как и прежде будем анализировать плановый период с конца, обозначим f_n(i) – оптимальный ожидаемый доход за n лет до конца периода, тогда рекуррентные соотношения примут вид:

f₁(i)=max_k{v_i(k)},

f_n(i)=max_k{v_i(k)+∑_jp_ij(k)f_n-1(j)}, n=2,3,…,N. (2.8.4)

Проведем вычисления при N=4. Результаты поместим в таблицы 2.8.4 – 2.8.7.

n=1 Таблица. 2.8.4

i	vi(k)	Оптимальное решение
k=1	k=2	f1(i)	k*
	5.3	4.7	5.3
		3.1	3.1
	–1	0.4	0.4

n=2 Таблица. 2.8.5

i	vi(k)+pi1(k)f1(1)+pi2(k)f1(2)+pi3(k)f1(3)	Оптимальное решение
k=1	k=2	f2(i)	k*
	5.3+.2´5.3+.5´3.1+.3´.4= =8.03	4.7+.3´5.3+.6´3.1+.1´.4= =8.19	8.19
	3+0´5.3+.5´3.1+.5´.4= =4.75	3.1+.1´5.3+.6´3.1+.3´.4= =5.61	5.61
	–1+0´5.3+0´3.1+1´0.4= = –0.6	.4+.05´5.3+.4´3.1+.55´.4= =2.13	2.13

n=3 Таблица. 2.8.6

i	vi(k)+pi1(k)f2(1)+pi2(k)f2(2)+pi3(k)f2(3)	Оптимальное решение
k=1	k=2	f3(i)	k*
	5.3+.2´8.19+.5´5.6+.3´2.13= =10.38	4.7+.3´8.19+.6´5.61+.1´2.13= =10.74	10.74
	3+0´8.19+.5´5.61+.5´2.13= =6.87	3.1+.1´8.19+.6´5.61+.3´2.13= =7.92	7.92
	–1+0´8.19+0´5.61+1´2.13= = 1.13	.4+.05´8.19+.4´5.6+.55´2.13= =4.23	4.23

n=4 Таблица. 2.8.7

i	vi(k)+pi1(k)f3(1)+pi2(k)f3(2)+pi3(k)f3(3)	Оптим. решение
k=1	k=2	f4(i)	k*
	5.3+.2´10.74+.5´7.92+.3´4.23= =12.68	4.7+.3´10.74+.6´7.92+.1´4.23= =13.097	13.10
	3+0´10.74+.5´7.92+.5´4.23= =9.075	3.1+.1´10.74+.6´7.92+.3´4.23= =10.195	10.19
	–1+0´10.74+0´7.92+1´4.23= = 3.23	.4+.05´10.74+.4´7.92+.55´4.23 =6.4315	6.43

Из оптимального решения следует, что в 1-й,2-й и 3-й годы садовник должен применять удобрения (k*=2) при любом состоянии почвы, а в 4-й год (n=1) садовнику следует применять удобрения только при условии, что состояние почвы удовлетворительное или плохое. Суммарный ожидаемый доход за четыре года составит f₄(1)=13.10 при хорошем состоянии почвы в первый год, f₄(2)= 10.19 при удовлетворительном состоянии и f₄(3)=6.43 при плохом состоянии.

Приведенный выше метод решения задачи называют еще методом итераций по стратегиям.

Задачу садовника можно обобщить в двух отношениях. Во-первых, переходные вероятности и значения дохода не обязательно одни и те же в любой год; в этом случае они являются функциями n-го этапа: p_ij(k,n) и r_ij(k,n). Во-вторых, можно использовать коэффициент дисконтирования ожидаемых доходов, вследствие чего значения f_N(i) будут представлять собой приведенные величины ожидаемых доходов по всем этапам. Если α – годовой коэффициент дисконтирования, вычисляемый по формуле α=1/(1+t), где t – годовая норма процента, то рекуррентное соотношение (4.9.4) преобразуется к виду:

f_n(i)=max_k{ v_i(k)+α∑_jp_ij(k)f_n-1(j)}, n=2,3,…,N. (2.8.5)

Упражнение. Решите задачу садовника при коэффициенте дисконтирования α=0.6. (ответ приводится в таблице 2.8.8).

Таблица. 2.8.8

i	n=1	n=2	n=3	n=4
f1(i)	k*	f2(i)	k*	f3(i)	k*	f4(i)	k*
	5.3		6.94		7.77		8.26
	3.1		4.61		5.43		5.92
	0.4		1.44		2.19		2.66

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

Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (2.8.4) при n → ∞.

Итак, задача стохастического динамического программирования включает в себя матрицу переходных вероятностей системы из состояния i в момент времени t_n-1 в состояние j в момент t_n. Матрица переходных вероятностей совместно с исходными вероятностями состояний полностью определяет марковскую цепь. Можно задачу стохастического динамического программирования (Марковскую задачу принятия решений) сформулировать как задачу линейного программирования (см. тему 2.2), однако в вычислительном отношении метод итераций по стратегиям более эффективен. Для задач с К альтернативами решений на каждом шаге и N состояниями соответствующая модель линейного программирования включает (N+1) ограничений и NК переменных.

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

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

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

Пусть с_i – затраты на приобретение (включаются в с₁) и эксплуатацию оборудования в период i. Здесь учитываются только эксплутационные затраты, которые изменяются с ростом срока службы. Тогда период n, после которого должна быть произведена замена, определяется из следующих соображений:

1. Если издержки в следующем периоде ниже средней величины прошлых затрат, то оборудование заменять не следует.

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

Т.е. должны выполняться следующие неравенства

с_n <(с₁+ с₂ +…+с_n-1)/(n – 1), (2.8.6)

с_n+1 >(с₁ + с₂+…+с_n)/n. (2.8.7)

Пример 2.8.5. Пусть расходы, связанные с приобретением и заменой оборудования, представлены в табл. 2.8.9.

Таблица 2.8.9

Период	затраты	средние
		26,7**
		27,5
		33,3

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

с₃ =20 <(с₁+ с₂)/2=30, а с₄ =30 >(с₁ + с₂+с₃)/3=26,7.

Цена денег, ввиду наличия процентов на капитал, меняется со временем. Проведем расчеты с учетом коэффициента дисконтирования. Пусть r – учетный процент в течение каждого периода, тогда обозначим d=1/(1+r/100). В правой части неравенств (2.8.6) – (2.8.7) средние затраты заменяются на средневзвешенные затраты:

с_n <(с₁+ с₂ d +…+с_n-1 d ^n-2)/(1+ d+…+d ^n-2), (2.8.8)

с_n+1 >(с₁ + с₂ d +…+с_n d ^n-1)/(1+ d+…+ d ^n-1). (2.8.9)

Пример 2.8.6. Пусть расходы, связанные с приобретением и заменой оборудования, аналогичны предыдущему примеру и r =5%. В колонке 3 табл. 2.8.10 вычисляем средневзвешенные затраты (d=0,952):

Таблица 2.8.10

Период i	Затраты ci	Средне-взвешенные
		30.49
		27.16*
		28.82
		30.02
		32.96

В данном случае замена оборудования должна производиться также в третий период, т.к. соотношения (2.8.8) – (2.8.9) выполняются для n=3. В обоих примерах мы предполагали, что затраты на эксплуатацию стареющего оборудования возрастали со временем.

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

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

Примем следующее обозначение:

f_i – величина затрат, соответствующая стратегии замены, минимизирующей эти затраты в интервалах i, i+1,…, n, в предположении, что новое оборудование приобретается в год i.

Тогда для нахождения оптимальной стратегии нам необходимо вычислить f₁(минимальные затраты и соответствующую стратегию с первого шага), пользуясь следующим рекуррентным соотношением:

f_n+1 =0,

f_i =min_j>i{c_ij + f_j}, i=n, n–1, …, 1. (2.8.10)

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

р_ik – стоимость замены оборудования возраста k на интервале i за вычетом его остаточной стоимости;

r_ik – стоимость эксплуатации оборудования возраста k на интервале i.

Пусть f_i(k) – стратегия, минимизирующая затраты на интервалах i, i+1,…, n, при условии, что в начале интервала i возраст оборудования составляет k лет.

Если оптимальное решение состоит в сохранении оборудования в интервале i, то

f_i(k) =r_ik+1 +f_i+1(k+1),

но если оптимальное решение сводится к его замене, то

f_i(k) =р_ik +r_i1 +f_i+1(1).

Таким образом, имеем

f_i(k)=min{r_ik+1+f_i+1(k+1),р_ik+r_i1+f_i+1(1)}, i=1,2,…,n, (2.8.11)

где f_n+1(k)=0 для всех k. Пусть К – возможный срок службы оборудования.

Мы планируем на n лет, поэтому начало (n+1)-го периода соответствует концу нашего планового периода.

Нахождение оптимального решения заключается в вычислении f₁(k₀), где k₀ – возраст оборудования на начало планового периода. Если в это время рассматриваемая единица оборудования отсутствует, то нет смысла говорить о его сохранении при i=1, а решение о замене есть просто покупка нового оборудования.

Пример 2.8.7. Необходимо составить план замены оборудования на пять лет при условии отсутствия его в начале первого года, прогнозируемые затраты сведены в таблицы 2.8.11 и 2.8.12.

Таблица 2.8.11. Значения r_ik Таблица 2.8.12. Значения р_ik

Пустые клетки в таблицах образовались из того факта, что в начале планового периода оборудования нет, оно только приобретается, поэтому нет нужды прогнозировать некоторые затраты, например, в год 3 не будет оборудования с возрастом 4, или на начало любого года не будет оборудования с пятилетним возрастом, поэтому колонка 5 в табл. 2.8.12 отсутствует.

Применим рекуррентное соотношение (2.8.11):

f₆(k) =0 для всех k.

i=5 (в начале года 5 возраст не может быть больше 4):

f₅(4) =min{r₅₅ +f₆(5), р₅₄ +r₅₁ +f₆(1)}=min{200+0,115+10+0}=125,

f₅(3) =min{r₅₄ +f₆(4), р₅₃ +r₅₁ +f₆(1)}=min{85+0,110+10+0}=85,

f₅(2) =min{r₅₃ +f₆(3), р₅₂ +r₅₁ +f₆(1)}=min{40+0,90+10+0}=40,

f₅(1) =min{r₅₂ +f₆(2), р₅₁ +r₅₁ +f₆(1)}=min{20+0,70+10+0}=20.

i=4 (в начале года 4 возраст не может быть больше 3):

f₄(3) =min{r₄₄ +f₅(4), р₄₃ +r₄₁ +f₅(1)}=min{120+125,105+14+20}=139,

f₄(2) =min{r₄₃ +f₅(3), р₄₂ +r₄₁ +f₅(1)}=min{52+85,85+14+20}=119,

f₄(1) =min{r₄₂ +f₅(2), р₄₁ +r₄₁ +f₅(1)}=min{28+40,65+14+20}=68.

i=3 (в начале года 3 возраст не может быть больше 2):

f₃(2) =min{r₃₃ +f₄(3), р₃₂ +r₃₁ +f₄(1)}=min{68+139,80+16+68}=164,

f₃(1) =min{r₃₂ +f₄(2), р₃₁ +r₃₁ +f₄(1)}=min{32+119,60+16+68}=144.

i=2 (в начале года 2 возраст не может быть больше 1):

f₂(1) =min{r₂₂ +f₃(2), р₂₁ +r₂₁ +f₃(1)}=min{36+164,55+18+144}=200.

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

f₁(0) = р₁₁ +r₁₁ +f₂(1)=100+20+200=320.

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

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

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

Пусть нам известны p_j – вероятности того, что поломка оборудования произойдет в j–й момент его использования (j<k);

r_j – стоимость эксплуатации исправного оборудования в течение j–го интервала его использования;

s_j – дополнительный ущерб, обусловленный преждевременной поломкой оборудования в интервале j.

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

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

– средние затраты во все моменты восстановления в случаях, когда оборудование выйдет из строя раньше запланированного момента k;

– средние затраты во все моменты восстановления в случаях, когда оборудование не выйдет из строя до запланированного момента k;

– ожидаемые эксплутационные затраты в период между текущим и очередным моментами восстановления.

Следовательно, в результате надлежащего обобщения соотношений (2.8.10) и (2.8.11) получаем

_{k-1 k-1}

f_i =min_k=1,2,…,K{åf_i+j р_j+f_i+k(1- åр_j)+R_k}, i=1,2,…,n, f_n+1=0, (2.8.12)

^{j=1 j=1}

где первое слагаемое соответствует математическому ожиданию затрат, связанных с преждевременной заменой, второе слагаемое есть произведение минимальных затрат с периода i+k и далее, умноженное на вероятность того, что оборудование нормально доработает до этого периода. Третье слагаемое, отражающее эксплутационные затраты, можно представить следующим образом:

_{k-1 k-1}

R_k = r₁ + r₂(1- p₁)+ r₃(1- p₁ - p₂)+…+ r_k(1-åp_j) + ås_jp_j. (2.8.13)

^{j=1 j=1}

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

В силу громоздкости формул (2.8.12),(2.8.13) мы не будем приводить числовой пример, хотя с использованием компьютера вычисления не представляют сложности.

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

В этом случае априорно допускается, что оптимальной является стационарная стратегия (каждый раз замена производится через k-й промежуток времени). Формула для определения оптимальной стратегии тогда существенно упрощается:

f =min_k=1,2,…,K{R_k/Е_k}, (2.8.14)

где Е_k есть среднее значение сроков замены оборудования,

_{k-1 k-1}

Е_k =åjр_j+k(1- åр_j). (2.8.15)

^{j=1 j=1}

Заметим, что выражение, стоящее в фигурных скобках в (2.8.14), определяет ожидаемые затраты за один отрезок планового периода, и мы приходим к методике определения оптимальной стратегии замены оборудования, рассмотренной нами в самом начале (пример 2.8.5).

Пример 2.8.8. Данные за первые пять лет неограниченного планового периода сосредоточены в табл.2.8.13 (колонки 2 – 4).

Таблица 2.8.13

k	рk	rk	sk	Rk	Еk	Rk/Еk
	¼
					1.75	65.14
	¼				2.5	51.6
						61.33
	1/2				3.5	60.57

Значения величин в колонке 5 вычисляем по формуле 2.8.13:

R₁ = r₁ =100,

R₂ = r₁ + r₂(1- p₁)+ s₁p₁=100+12´3/4+20´1/4=114,

R₃ = r₁ + r₂(1- p₁)+ r₃(1- p₁ - p₂) + s₁p₁+ s₂p₂=114+20´3/4=129,

R₄ = 129+20´1/2+180´1/4=184,

R₅ = 184+56´1/2=212.

Значения величин в колонке 6 вычисляем по формуле 2.8.15:

Е₁ = 1,

Е₂ = 1´р₁ +2(1- p₁)=1/4+2´3/4=1.75,

Е₃ = 1´р₁ +2´p₂+3(1- p₁ - p₂)=1/4+2´0+3´3/4=2.5,

Е₄ = 1´р₁+2´р₂+3´р₃+4´ (1-1/4-1/4)=1/4+3/4+4´1/2=3,

Е₅ = 1´р₁+2´р₂+3´р₃+4´р₄+5´ (1/2)= 1/4+3/4+5´1/2=3.5.

Вычисляем отношение в колонке 7 и находим минимум, ему соответствует k=3, это оптимальное значение планового срока замены оборудования.

Из полученного результата видно, насколько дорого обходятся ошибки при неправильном учете фактора неопределенности. Так, например, если использовать критерий R_k/k, то решение будет k=5, а если в качестве критерия взять å_j(r_j/k), то решение будет k=4.

В этих случаях ожидаемые затраты за один интервал превышают оптимальное значение почти на 20%.

(упражнение: проверить вышесказанное самостоятельно).

При учете коэффициента дисконтирования (пусть, как и прежде r – учетный процент в течение каждого периода и d=1/(1+r/100)) формулы (2.8.12) – (2.8.13) для конечного планового периода принимают вид:

_{k-1 k-1}

f_i=min_k=1,2,…,K{åd^jf_i+jр_j+d^kf_i+k(1-åр_j)+R_k}, i=1,2,…,n, f_n+1=0, (2.8.16)

^{j=1 j=1}

_{k-1 k-1}

R_k=r₁+d¹r₂(1- p₁)+d²r₃(1-p₁-p₂)+…+d^k-1r_k (1-åp_j) + åd^j-1s_jp_j . (2.8.17)

^{j=1 j=1}

Для неограниченного планового периода с коэффициентом дисконтирования d формулы (2.8.14) – (2.8.15) принимают вид:

f =min_k=1,2,…,K{R_k/(1-Е_kd)}, (2.8.18)

где Е_kd есть среднее значение коэффициента дисконтирования

_{k-1 k-1}

Е_kd=åd^jр_j+d^k(1-åр_j). (2.8.19)

^{j=1 j=1}

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