м- Год 1 -*м- Год 2 -ш- Год 3 -- Год 4 -м
Рис. 10.7. Решение примера 10.3.3
Следовательно, начиная с первого года эксплуатации механизма, альтернативными оптимальными стратегиями относительно замены механизма будут (3, С, С, 3) и(3, 3, С, С). Общая прибыль составит 55 300 долл.
УПРАЖНЕНИЯ 10.3.3
1. Постройте сеть и найдите оптимальное решение в задаче из примера 10.3.3 в каждом из следующих случаев.
a) В начале первого года имеется механизм, находящийся в эксплуатации 2 года.
b) В начале первого года имеется механизм, находящийся в эксплуатации 1 год.
c) В начале первого года куплен новый механизм.
2. Мой тринадцатилетний сын занимается собственным бизнесом - косит газоны десяти клиентам. Каждому клиенту он косит траву три раза в год, получая за один скошенный газон 50 долл. Он купил косилку за 200 долл. На протяжении первого года затраты на содержание и использование косилки равны 120 долл., и через год они увеличиваются на 20%. Одногодичная косилка может быть продана за 150 долларов, и с каждым годом ее стоимость уменьшается на 10%. Мой сын планирует продолжить свой бизнес, пока ему не исполнится 16 лет, и считает, что более выгодно менять косилку через каждые два года. Он объясняет это тем, что цена новой косилки увеличивается за год лишь на 10%. Справедливо ли его решение?
3. Группа ферм владеет трактором двухлетней давности и планирует разработать стратегию его замены на следующие пять лет. Трактор должен эксплуатироваться не менее двух и не более пяти лет. В настоящее время новый трактор стоит 40 000 долларов, и эта цена за год увеличивается на 10%. Текущая годичная стоимость эксплуатации трактора составляет 1300 долларов и, как ожидается, будет увеличиваться на 10% в год.
a) Сформулируйте задачу в виде задачи о кратчайшем пути.
b) Постройте соответствующее рекуррентное уравнение.
c) Определите оптимальную стратегию замены трактора на следующие пять лет.
4. Рассмотрим задачу замены оборудования на протяжении п лет. Цена новой единицы оборудования равна с долларов, а стоимость продажи после / лет эксплуатации равна s(t) = n-t при ихи нулю - в противном случае. Годичная прибыль от эксплуатации является функцией возраста оборудования / и равна r(t) = п - t2 при п > t и нулю - в противном случае.
a) Сформулируйте задачу как модель динамического программирования.
b) Определите оптимальную стратегию замены оборудования двухгодичной давности при с = 10 ООО долл., считая, что га = 5.
5. Решите задачу из предыдущего упражнения, предполагая, что возраст оборудования составляет 1 год и п = 4, с = 6000 долл., r(t) = п/(п + 1).
10.3.4. Задача инвестирования
Предположим, что в начале каждого из следующих га лет необходимо сделать инвестиции Pv Р2,Рп. Вы имеете возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент rv а второй - г2. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы. Премиальные меняются от года к году, и для /-го года равны qn и qn в первом и втором банках соответственно. Они выплачиваются в конце года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находиться там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиций на следующие га лет.
Элементы модели динамического программирования таковы.
1. Этап / представляется порядковым номером года /, / =1,2,..., п.
2. Вариантами решения на /-м этапе (для i-го года) являются суммы /, и /, инвестиций в первый и второй банк соответственно.
3. Состоянием х, на /-м этапе является сумма денег на начало /-го года, которые могут быть инвестированы.
Заметим, что по определению /. = х, - /,. Следовательно,
*. = Л.
Xi = Pi + qu.Ji-i + Яии(Хи ~ A.i) =
= Pi + (<7;-i,i ~ OluVli + <7/-и*;-ь где i = 2, 3, га. Сумма денег х„ которые могут быть инвестированы, включает лишь новые деньги и премиальные проценты за инвестиции, сделанные на протяжении (/ - 1)-го года.
Пусть f{x) - оптимальная сумма инвестиций для интервала от (-го до «-го года при условии, что в начале /-го года имеется денежная сумма х,. Далее обозначим через Si накопленную сумму к концу га-го года при условии, что и (ху - /,) - объемы инвестиций на протяжении /-го года в первый и второй банк соответственно. Обозначая а, = (1 + г,), / = 1,2, мы можем сформулировать задачу в следующем виде.
Максимизировать г = s, + s2 + ... + sn,
s, = /,<*" +(•*, -/,.)аГ" =(<"- -сС1")/, +аГ"Ч, = 1.2,п-\,
s„ = (а, + <7„, - а2 - <7„2)/„ + (а2 + qn2)x„.
Поскольку премиальные за га-й год являются частью накопленной денежной суммы от инвестиций, в выражения для s„ добавлены qni и q„2.
Итак, в данном случае рекуррентное уравнение для обратной прогонки в алгоритме динамического программирования имеет вид
Пример 10.3.4
Предположим, вы хотите инвестировать 4000 долл. сейчас и 2000 долл. в начале каждого года, от второго до четвертого, считая от текущего года. Первый банк выплачивает годовой сложный процент 8% и премиальные на протяжении следующих четырех лет в размере 1,8, 1,7, 2,1 и 2,5% соответственно. Годовой сложный процент, предлагаемый вторым банком, на 0,2% ниже, чем предлагает первый банк, но его премиальные на 0,5% выше. Задача состоит в максимизации накопленного капитала к концу четвертого года.
Используя введенные выше обозначения, имеем следующее.
я, = 4 000 долл., P2 = Pa = Pt = 2 000 долл.,
а, = (1 +0,08)= 1,08,
а2 = (1 +0,078) = 1,078,
qn = 0,018, Чп = 0,017, Чп = 0,021, Чн = 0,025,
<712 = 0,023, <722 = 0,022, q3i = 0,026, qa = 0,030.
Этап 4.
где 54 = (а, + <741 - а2 - qi2)It + (а, + qi2)xt = - 0,003/4 + 1, 108х4.
Функция s4 является линейной по /4 в области 0</4<дг4, и, следовательно, ее максимум достигается при /4 = 0 из-за отрицательного коэффициента при /4. Следовательно, оптимальное решение для этапа 4 может быть представлено в следующем виде.
| | Оптимальное решение | |
Состояние | U(X4) | | Л" |
| 1,108X4 | | |
Этап 3.
/э(*з)= тахЬ + ЛК)}.
5, = (1,082 - 1,0 782)/а+ 1,0 782х8 = 0,00432/,+ 1,162 1jc3, xt = 2000 - 0,005/3 + 0,026х,.
Следовательно,
/3(х3) = max {0,ОО432/3 + 1,162Ц +1,108(2000-0,005/3 + 0,026х3)} = = max {2216-0,00122/, + 1,1909*,).
0S/,S.I, L J
/Л=™*{*. + /,Лхш)}. i = l,2,....i-l.
где jCj+i выражается через jc, в соответствии с приведенной выше формулой, a/„+i(*„+i) = 0.