Стохастическое динамическое программирование
В рассмотренных примерах управляемые переменные, а также переменные состояния и шага принимали только целочисленные значения. (Задачи такого рода называют задачами дискретного программирования). Кроме того, на результаты и переходы из одного состояния в другое не оказывали влияния случайные факторы. Учет случайного характера параметров модели есть предмет анализа стохастического динамического программирования. Рассмотрим небольшой пример, иллюстрирующий основные идеи и методы стохастического динамического программирования. Пример 2.8.4. Задача садовника. Предположим, что каждый год почва может находиться в одном из трех состояний: хорошем (1), удовлетворительном (2) или плохом (3). Пусть k=1 и 2 – две возможные стратегии поведения садовника: не удобрять или удобрять. Оптимальное поведение садовника определяется такой стратегией, при которой он получает наибольший ожидаемый доход через N лет. Обозначим рij(k) – вероятность перехода почвы из состояния i в состояние j при применении садовником стратегии k.
{р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 останется плохой. Обозначим rij(k) – доход (или убыток), который получит садовник за одногодичный период, если почва перейдет из состояния i в состояние j при применении садовником стратегии k.
{rij(1)}= 0 5 1, {rij(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. Обозначим vi(k) – ожидаемый доход, обусловленный одним переходом из состояния i при стратегии k, тогда vi(k)=∑jpij(k)rij(k). Если удобрения не применяются (k=1), тогда v1(1)=0.2´7+0.5´6+0.3´3=5.3, v2(1)=0´0+0.5´5+0.5´1=3, v3(1)=0´0+0´0+1´ (–1)= –1. При использовании удобрений (k=2) имеем v1(2)=0.3´6+0.6´5+0.1´ (–1)=4.7, v2(2)=0.1´7+0.6´4+0.3´0=3.1, v3(2)=0.05´6+0.4´3+0.55´ (–2)=0.4. Как и прежде будем анализировать плановый период с конца, обозначим fn(i) – оптимальный ожидаемый доход за n лет до конца периода, тогда рекуррентные соотношения примут вид: f1(i)=maxk{vi(k)}, fn(i)=maxk{vi(k)+∑jpij(k)fn-1(j)}, n=2,3,…,N. (2.8.4) Проведем вычисления при N=4. Результаты поместим в таблицы 2.8.4 – 2.8.7.
n=1 Таблица. 2.8.4
n=2 Таблица. 2.8.5
n=3 Таблица. 2.8.6
n=4 Таблица. 2.8.7
Из оптимального решения следует, что в 1-й,2-й и 3-й годы садовник должен применять удобрения (k*=2) при любом состоянии почвы, а в 4-й год (n=1) садовнику следует применять удобрения только при условии, что состояние почвы удовлетворительное или плохое. Суммарный ожидаемый доход за четыре года составит f4(1)=13.10 при хорошем состоянии почвы в первый год, f4(2)= 10.19 при удовлетворительном состоянии и f4(3)=6.43 при плохом состоянии. Приведенный выше метод решения задачи называют еще методом итераций по стратегиям. Задачу садовника можно обобщить в двух отношениях. Во-первых, переходные вероятности и значения дохода не обязательно одни и те же в любой год; в этом случае они являются функциями n-го этапа: pij(k,n) и rij(k,n). Во-вторых, можно использовать коэффициент дисконтирования ожидаемых доходов, вследствие чего значения fN(i) будут представлять собой приведенные величины ожидаемых доходов по всем этапам. Если α – годовой коэффициент дисконтирования, вычисляемый по формуле α=1/(1+t), где t – годовая норма процента, то рекуррентное соотношение (4.9.4) преобразуется к виду: fn(i)=maxk{ vi(k)+α∑jpij(k)fn-1(j)}, n=2,3,…,N. (2.8.5) Упражнение. Решите задачу садовника при коэффициенте дисконтирования α=0.6. (ответ приводится в таблице 2.8.8). Таблица. 2.8.8
Заметим, что использование коэффициента дисконтирования приводит к другим оптимальным стратегиям. В данном случае при хорошем состоянии почвы удобрения не требуются в течение всех четырех лет. Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (2.8.4) при n → ∞. Итак, задача стохастического динамического программирования включает в себя матрицу переходных вероятностей системы из состояния i в момент времени tn-1 в состояние j в момент tn. Матрица переходных вероятностей совместно с исходными вероятностями состояний полностью определяет марковскую цепь. Можно задачу стохастического динамического программирования (Марковскую задачу принятия решений) сформулировать как задачу линейного программирования (см. тему 2.2), однако в вычислительном отношении метод итераций по стратегиям более эффективен. Для задач с К альтернативами решений на каждом шаге и N состояниями соответствующая модель линейного программирования включает (N+1) ограничений и NК переменных.
2.8.6. Задачи износа и замены оборудования Основными задачами теории замен являются прогноз затрат, связанных с обновлением оборудования, и выработка наиболее экономичной стратегии замен. В зависимости от характера оборудования процессы замен делятся на два класса. Первый связан с оборудованием, которое, устаревая в процессе эксплуатации, становится менее производительным физически вследствие износа или морально в результате появления новых, более совершенных машин (сюда относятся, например, металлорежущие станки, автомобили и т.д.). Эксплуатация устаревшего оборудования связана с ростом производственных затрат, удлинением времени простоя, увеличением числа отказов и длительности ремонта и т.д. Вместе с тем замена старого оборудования новым также сопряжена с расходами. Необходимо определить такой срок службы оборудования, при котором экономия за счет приобретенного нового оборудования начинает превышать компенсацию его первоначальной стоимости. При аренде оборудования необходимо учитывать подобные соображения: при увеличении срока аренды уменьшается арендная плата в единицу времени, зато возрастают эксплутационные расходы. Второй класс задач связан с оборудованием со случайной длительностью срока службы (например, лампы освещения, элементы микросхем). При решении задач второго класса приходится определять, какие именно единицы оборудования следует заменить и как часто следует проводить замену с тем, чтобы минимизировать общие затраты. Если замену оборудования производить лишь после его выхода из строя, то при минимуме затрат на обновление возрастают расходы, связанные с простоями, тогда как замена деталей до их поломки приводит к высокой стоимости оборудования, но зато к малым затратам на некомплектность. Базой для решения этих задач является наличие закона распределения вероятностей повреждения (отказа) оборудования в зависимости от срока его службы, для чего должны быть задействованы методы математической статистики. Пусть сi – затраты на приобретение (включаются в с1) и эксплуатацию оборудования в период i. Здесь учитываются только эксплутационные затраты, которые изменяются с ростом срока службы. Тогда период n, после которого должна быть произведена замена, определяется из следующих соображений: 1. Если издержки в следующем периоде ниже средней величины прошлых затрат, то оборудование заменять не следует. 2. Если же издержки в следующем периоде превосходят величину средних затрат, то оборудование следует заменить. Т.е. должны выполняться следующие неравенства сn <(с1+ с2 +…+сn-1)/(n – 1), (2.8.6) сn+1 >(с1 + с2+…+сn)/n. (2.8.7) Пример 2.8.5. Пусть расходы, связанные с приобретением и заменой оборудования, представлены в табл. 2.8.9. Таблица 2.8.9
В третьей колонке вычисляем средние значения затрат и видим, что замена оборудования должна производиться в третий период, т.к. с3 =20 <(с1+ с2)/2=30, а с4 =30 >(с1 + с2+с3)/3=26,7. Цена денег, ввиду наличия процентов на капитал, меняется со временем. Проведем расчеты с учетом коэффициента дисконтирования. Пусть r – учетный процент в течение каждого периода, тогда обозначим d=1/(1+r/100). В правой части неравенств (2.8.6) – (2.8.7) средние затраты заменяются на средневзвешенные затраты: сn <(с1+ с2 d +…+сn-1 d n-2)/(1+ d+…+d n-2), (2.8.8) сn+1 >(с1 + с2 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
В данном случае замена оборудования должна производиться также в третий период, т.к. соотношения (2.8.8) – (2.8.9) выполняются для n=3. В обоих примерах мы предполагали, что затраты на эксплуатацию стареющего оборудования возрастали со временем. Рассмотрим теперь задачу замены оборудования как многошаговый процесс динамического программирования. Пусть величина cij представляет собой сумму покупной цены и ожидаемых расходов на ремонт и обслуживание оборудования, приобретенного в начале года i, за вычетом остаточной стоимости этого оборудования на начало года j. Примем следующее обозначение: fi – величина затрат, соответствующая стратегии замены, минимизирующей эти затраты в интервалах i, i+1,…, n, в предположении, что новое оборудование приобретается в год i. Тогда для нахождения оптимальной стратегии нам необходимо вычислить f1(минимальные затраты и соответствующую стратегию с первого шага), пользуясь следующим рекуррентным соотношением: fn+1 =0, fi =minj>i{cij + fj}, i=n, n–1, …, 1. (2.8.10) Предположим, что затраты, отвечающие некоторой стратегии замены, включают две составляющие: рik – стоимость замены оборудования возраста k на интервале i за вычетом его остаточной стоимости; rik – стоимость эксплуатации оборудования возраста k на интервале i. Пусть fi(k) – стратегия, минимизирующая затраты на интервалах i, i+1,…, n, при условии, что в начале интервала i возраст оборудования составляет k лет. Если оптимальное решение состоит в сохранении оборудования в интервале i, то fi(k) =rik+1 +fi+1(k+1), но если оптимальное решение сводится к его замене, то fi(k) =рik +ri1 +fi+1(1). Таким образом, имеем fi(k)=min{rik+1+fi+1(k+1),рik+ri1+fi+1(1)}, i=1,2,…,n, (2.8.11) где fn+1(k)=0 для всех k. Пусть К – возможный срок службы оборудования. Мы планируем на n лет, поэтому начало (n+1)-го периода соответствует концу нашего планового периода. Нахождение оптимального решения заключается в вычислении f1(k0), где k0 – возраст оборудования на начало планового периода. Если в это время рассматриваемая единица оборудования отсутствует, то нет смысла говорить о его сохранении при i=1, а решение о замене есть просто покупка нового оборудования. Пример 2.8.7. Необходимо составить план замены оборудования на пять лет при условии отсутствия его в начале первого года, прогнозируемые затраты сведены в таблицы 2.8.11 и 2.8.12. Таблица 2.8.11. Значения rik Таблица 2.8.12. Значения рik Пустые клетки в таблицах образовались из того факта, что в начале планового периода оборудования нет, оно только приобретается, поэтому нет нужды прогнозировать некоторые затраты, например, в год 3 не будет оборудования с возрастом 4, или на начало любого года не будет оборудования с пятилетним возрастом, поэтому колонка 5 в табл. 2.8.12 отсутствует. Применим рекуррентное соотношение (2.8.11): f6(k) =0 для всех k. i=5 (в начале года 5 возраст не может быть больше 4): f5(4) =min{r55 +f6(5), р54 +r51 +f6(1)}=min{200+0,115+10+0}=125, f5(3) =min{r54 +f6(4), р53 +r51 +f6(1)}=min{85+0,110+10+0}=85, f5(2) =min{r53 +f6(3), р52 +r51 +f6(1)}=min{40+0,90+10+0}=40, f5(1) =min{r52 +f6(2), р51 +r51 +f6(1)}=min{20+0,70+10+0}=20. i=4 (в начале года 4 возраст не может быть больше 3): f4(3) =min{r44 +f5(4), р43 +r41 +f5(1)}=min{120+125,105+14+20}=139, f4(2) =min{r43 +f5(3), р42 +r41 +f5(1)}=min{52+85,85+14+20}=119, f4(1) =min{r42 +f5(2), р41 +r41 +f5(1)}=min{28+40,65+14+20}=68. i=3 (в начале года 3 возраст не может быть больше 2): f3(2) =min{r33 +f4(3), р32 +r31 +f4(1)}=min{68+139,80+16+68}=164, f3(1) =min{r32 +f4(2), р31 +r31 +f4(1)}=min{32+119,60+16+68}=144. i=2 (в начале года 2 возраст не может быть больше 1): f2(1) =min{r22 +f3(2), р21 +r21 +f3(1)}=min{36+164,55+18+144}=200. Т.к. по условию примера в начале первого года мы приобретаем новое оборудование, то f1(0) = р11 +r11 +f2(1)=100+20+200=320. Таким образом, оптимальная стратегия заключается в следующем: В начале третьего года заменяем оборудование, купленное в начале первого года, и эксплуатируем его до конца планового периода. Выше мы рассматривали детерминированный вариант задачи о замене оборудования, где с индексом k была связана продолжительность нормально эксплуатируемого устройства. В стохастическом варианте задачи восстановления допускается, что устройство может выйти из строя еще до запланированного момента замены (тогда оно заменяется в следующий за поломкой момент времени). Пусть нам известны pj – вероятности того, что поломка оборудования произойдет в j–й момент его использования (j<k); rj – стоимость эксплуатации исправного оборудования в течение j–го интервала его использования; sj – дополнительный ущерб, обусловленный преждевременной поломкой оборудования в интервале j. Пусть r1 включает первоначальную стоимость устройства и вышедшее из строя оборудование полностью обесценивается (например, лампы, сгоревшие электромоторы и т.п.). Оптимальной будет являться стратегия, минимизирующая математическое ожидание затрат, в составе которых должны быть учтены: – средние затраты во все моменты восстановления в случаях, когда оборудование выйдет из строя раньше запланированного момента k; – средние затраты во все моменты восстановления в случаях, когда оборудование не выйдет из строя до запланированного момента k; – ожидаемые эксплутационные затраты в период между текущим и очередным моментами восстановления. Следовательно, в результате надлежащего обобщения соотношений (2.8.10) и (2.8.11) получаем k-1 k-1 fi =mink=1,2,…,K{åfi+j рj+fi+k(1 - åрj)+Rk}, i=1,2,…,n, fn+1=0, (2.8.12) j=1 j=1 где первое слагаемое соответствует математическому ожиданию затрат, связанных с преждевременной заменой, второе слагаемое есть произведение минимальных затрат с периода i+k и далее, умноженное на вероятность того, что оборудование нормально доработает до этого периода. Третье слагаемое, отражающее эксплутационные затраты, можно представить следующим образом: k-1 k-1 Rk = r1 + r2(1 - p1)+ r3(1 - p1 - p2)+…+ rk(1 - åpj) + åsjpj. (2.8.13) j=1 j=1 Эти затраты складываются из затрат первого года эксплуатации оборудования плюс затраты второго года, умноженные на вероятность того, что оно не вышло из строя в первом году, плюс затраты третьего года, умноженные на вероятность того, что оно не вышло из строя в первых двух годах, и так далее до k-го интервала, плюс к этому математическое ожидание ущерба от преждевременной поломки до k-го интервала. В силу громоздкости формул (2.8.12),(2.8.13) мы не будем приводить числовой пример, хотя с использованием компьютера вычисления не представляют сложности. Рассмотрим стохастическую задачу замены оборудования для неограниченного планового периода. В этом случае априорно допускается, что оптимальной является стационарная стратегия (каждый раз замена производится через k-й промежуток времени). Формула для определения оптимальной стратегии тогда существенно упрощается: f =mink=1,2,…,K{Rk/Е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
Значения величин в колонке 5 вычисляем по формуле 2.8.13: R1 = r1 =100, R2 = r1 + r2(1 - p1)+ s1p1=100+12´3/4+20´1/4=114, R3 = r1 + r2(1 - p1)+ r3(1 - p1 - p2) + s1p1+ s2p2=114+20´3/4=129, R4 = 129+20´1/2+180´1/4=184, R5 = 184+56´1/2=212. Значения величин в колонке 6 вычисляем по формуле 2.8.15: Е1 = 1, Е2 = 1´р1 +2(1 - p1)=1/4+2´3/4=1.75, Е3 = 1´р1 +2´p2+3(1 - p1 - p2)=1/4+2´0+3´3/4=2.5, Е4 = 1´р1+2´р2+3´р3+4´ (1 - 1/4 - 1/4)=1/4+3/4+4´1/2=3, Е5 = 1´р1+2´р2+3´р3+4´р4+5´ (1/2)= 1/4+3/4+5´1/2=3.5. Вычисляем отношение в колонке 7 и находим минимум, ему соответствует k=3, это оптимальное значение планового срока замены оборудования. Из полученного результата видно, насколько дорого обходятся ошибки при неправильном учете фактора неопределенности. Так, например, если использовать критерий Rk/k, то решение будет k=5, а если в качестве критерия взять åj(rj/k), то решение будет k=4. В этих случаях ожидаемые затраты за один интервал превышают оптимальное значение почти на 20%. (упражнение: проверить вышесказанное самостоятельно). При учете коэффициента дисконтирования (пусть, как и прежде r – учетный процент в течение каждого периода и d=1/(1+r/100)) формулы (2.8.12) – (2.8.13) для конечного планового периода принимают вид: k-1 k-1 fi=mink=1,2,…,K{ådjfi+jрj+dkfi+k(1 - åрj)+Rk}, i=1,2,…,n, fn+1=0, (2.8.16) j=1 j=1 k-1 k-1 Rk=r1+d1r2(1 - p1)+d2r3(1 - p1 - p2)+…+dk-1rk (1 - åpj) + ådj-1sjpj. (2.8.17) j=1 j=1 Для неограниченного планового периода с коэффициентом дисконтирования d формулы (2.8.14) – (2.8.15) принимают вид: f =mink=1,2,…,K{Rk/(1 - Еkd)}, (2.8.18) где Еkd есть среднее значение коэффициента дисконтирования k-1 k-1 Еkd=ådjрj+dk(1 - åрj). (2.8.19) j=1 j=1 Здесь f представляет собой математическое ожидание дисконтированных затрат при неограниченном плановом периоде в случае, когда реализуется оптимальная стратегия.
|
