назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [ 148 ] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


148

м- Год 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.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [ 148 ] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]