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

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

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

Пример 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

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

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

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

Из оптимального решения следует, что в 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

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

Для определения оптимальной долгосрочной стратегии применяют два метода. Первый метод основан на переборе всех возможных стационарных стратегий управления и может быть использован при их малом числе. Второй метод (итераций по стратегиям) более эффективен в том смысле, что определяет оптимальную стратегию за малое число итераций. Идея метода заключается в использовании соотношения (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

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

с₃ =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

В данном случае замена оборудования должна производиться также в третий период, т.к. соотношения (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

Значения величин в колонке 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 представляет собой математическое ожидание дисконтированных затрат при неограниченном плановом периоде в случае, когда реализуется оптимальная стратегия.

Практический блок

Пример 1

Для двух предприятий выделено a единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f₁(x), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(y). Остаток средств к концу года составляет g₁(x) для первого предприятия и g₂(y) для второго предприятия.

a=1000, f₁=3х, g₁=0,1х; f₂=2у; g₂= 0,5y.

РЕШЕНИЕ. Процесс распределения средств разобьем на 4 этапа – по соответствующим годам.

Обозначим a_k = x_k + y_k – средства, которые распределяются на k –ом шаге как сумма средств по предприятиям.

Суммарный доход от обоих предприятий на k –ом шаге:

z_k = f₁(x_k) + f₂(a_k − x_k) = 3x_k + 2(a_k − x_k) = 2a_k + x_k .

Остаток средств от обоих предприятий на k –ом шаге:

a_k+1 =g₁(x_k)+ g₂(a_k –x_k) =0,1x_k +0,5(a_k –x_k) =0,5a_k –0,4x_{k .}

Обозначим z*_k (a_k) – максимальный доход, полученный от распределения средств a_k между двумя предприятиями с k-го шага до конца рассматриваемого периода.

Рекуррентные соотношения Беллмана для этих функций

z*₄(a₄)= a₄+ x₄},

z*_k(a_k)= a_k + x_k + z*_k+1(0,5a_k – 0,4x_k)}.

Проведем оптимизацию, начиная с четвертого шага:

Й шаг.

Оптимальный доход равен:

z*₄(a₄ )= a₄+ x₄}= 3a₄ ,

т.к. линейная возрастающая функция достигает максимума в конце рассматриваемого промежутка, т.е. при x₄= a₄.

Й шаг.

z*₃(a₃)= a₃+ x₃ + 3(0,5a₃– 0,4x₃)}= a₃– 0,2x₃)}= a₃

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₃= 0.

Й шаг.

z*₂(a₂)= a₂+ x₂ + 3.5(0,5a₂– 0,4x₂)}= a₂– 0,4x₂)}= a_{2 ,}

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₂=0.

Й шаг.

z*₁(a₁)= a₁+ x₁+ 3.75(0,5a₁– 0,4x₁)}= a₁– 0,5x₁)}= a_1,

т.к. линейная убывающая функция достигает максимума в начале рассматриваемого промежутка, т.е. при x₁=0.

Результаты оптимизации:

z*₁(a₁)= 3,875a₁, x*₁ =0,

z*₂(a₁)= 3,75a₂, x*₂ =0,

z*₃(a₃)= 3,5a₃, x*₃ =0,

z*₄(a₄)= 3a₄, x*₄ = a_4.

Определим количественное распределение средств по годам:

Т.к. a₁=a=1000, x*₁=0, получаем a₂=0.5a₁– 0.41x*₁=500. Далее аналогично:

x*₂=0, a₃= 0.5a₂–0.4 x*₂=250,

x*₃=0, a₄= 0.5a₃−0.4 x*₃=125,

x*₄= a₄=125.

Представим распределение средств в виде таблицы:

При таком распределении средств за 4 года будет получен доход, равный

z*₁(a₁)= 3,875 ·1000= 3875 .

Пример 2

Строительный подрядчик оценивает минимальные потребности в рабочей силе на каждую из последующих пяти недель следующим образом, 6, 5, 3, 6, 8 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю. А наем рабочей силы на протяжении одной недели обходится 400 долларов плюс 200 долларов за одного рабочего в неделю. Каждому уволенному рабочему выплачивается выходное пособие в размере 100 долларов. Найти оптимальное решение задачи.

Решение.

1. Этап i представляется порядковым номером недели, i =1, 2, 3, 4, 5.

2. Вариантом решения на i-том этапе являются значения –количество работающих на протяжении i-той недели.

3. Состояние на i-том этапе является – количество работающих на протяжении (i-1)-й неделе.

Рекуррентное уравнение динамического программирования представляется в виде:

– затраты, связанные с содержанием избытка;

– затраты, связанные с наймом;

– затраты, связанные с увольнением.

,

,

,

,

.

Проведем оптимизацию, начиная с пятого этапа:

Этап 5.

Оптимальное решение
	300*0+400+200*2+100*(-2)= 600
	300*0+400+200*1+100*(-1)= 500
	300*0+400+200*0+100*0= 400

Этап 4.

+ Оптимальное решение
	= 6	= 7	= 8

Этап 3.

+ Оптимальное решение

Этап 2.

+ Оптимальное решение

	= 5
	300*0+400+200*(-1)+100+1500=1800
	300*0+400+200*(-2)+200+1500=1700
	300*0+400+200*(-3)+300+1500=1600

Этап 1.

+ Оптимальное решение

	= 6	= 7	= 8

Оптимальное решение определятся последовательно таким образом:

Вывод: в результате решения задачи получилось, что на первой неделе надо нанять 6 человек, на второй уволить 1 рабочего, на третьей уволить 2 рабочих, на четвертой нанять троих рабочих и на пятой нанять двоих рабочих.

Пример 3

Компания по прокату автомобилей разрабатывает план по обновлению парка своих машин на следующие пять лет. Каждый автомобиль должен проработать не менее 2-х и не более 4-х лет. В следующей таблице приведена стоимость замены автомобиля в зависимости от года покупки и срока эксплуатации.

Решение

Сведем задачу к задаче нахождения кратчайшего пути в сети:

Получаем кратчайший путь 2000→2002→2005.

К наименьшим затратам приведет замена автомобиля в 2002 и 2005 годах.

Тесты

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

а) отсутствие последействия;

б) наличие обратной связи;

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

2. Вычислительная схема метода динамического программирования:

а) зависит от способов задания функций;

б) зависит от способов задания ограничений;

в) связана с принципом оптимальности Беллмана.

3. Какую задачу можно решить методом динамического программирования:

а) транспортную задачу;

б) задачу о замене оборудования;