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


[Старт] [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]


195

15.3. Максимизация вероятности достижения цели

Пример 15.3.1

Некий индивидуум планирует инвестировать 2 ООО долл. Имеющиеся варианты позволяют удвоить эту сумму с вероятностью 0,3 или потерять ее с вероятностью 0,7. Акции продаются в конце года, а в начале следующего года все деньги или их часть снова инвестируются. Этот процесс повторяется на протяжении трех лет. Целью является максимизация вероятности достижения суммы в 4 ООО долл. в конце третьего года.

В соответствии с обозначениями данной модели имеем г, = 1 с вероятностью 0,3 иг2 = -1 с вероятностью 0,7.

Этап 3. На этом этапе состояние х3 может изменяться от 0 до 8 000 долл. Минимальное значение возможно, когда все вложенные средства потеряны, а максимальное - когда инвестиция удваивается в конце каждого из двух первых лет. Следовательно, рекуррентное уравнение для этапа 3 записывается в следующем виде:

гдех3 = 0,1,8.

Приведенная ниже табл. 15.1 содержит детали вычислений для данного этапа.

Все заштрихованные ячейки таблицы являются неподходящими, так как не удовлетворяют условию уъ < х3. Кроме того, при выполнении вычислений можно заметить, что

Р{х3 + У3 2:4} = 0, если х3 + у3 < 4, Р{х3 - уз > 4} = 0, если х3 - у3 < 4. В противном случае эти вероятности равны 1.

Хотя приведенная таблица и свидетельствует о том, что существуют альтернативные оптимумы для х3 = 1, 3, 4, 5, 6, 7 и 8, оптимальный (последний) столбец содержит лишь наименьшие оптимальные значения у3. Это объясняется тем, что инвестор не собирается инвестировать больше того, что необходимо для достижения поставленной цели.

{0,ЗР{х3+у3>4} + 0,7/>{лг3-у3>4}},

Этап 2.

{0,3/3(х2 + у2) + 0,7/3(х2-у2)}.

Соответствующие вычисления приведены в табл. 15.2

Этап 1.

В табл. 15.3 показаны вычисления для данного этапа.



Таблица 15.1

0,ЗР{Хз + уз > 4} + 0,7Р{хз - Уз £ 4}

Оптимум

Уз = 0 уз = 1

уз = 2

Уз = 3

Уз = 4

Уз = 5

Уз = 6

Уз = 7

Уз = 8

0,3 х 0 + 0,7 х х0 = 0

0,3х0 + 0,7х 0,3x0 + 0,7 х х 0 = 0 > 0 = 0

0,3 х 0 + 0,7 х 0 3*0 + 07* х 0 = 0 v 0 = 0

0 3/1*07* * 0 = 0 3

0,3x0 +0,7 х 0,3х 1 +0,7х х 0 = 0 х 0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 +0,7 х х 0 = 0,3

0,3 х 1 +0,7 х 0,3 х 1 +0,7х х1 = 1 х 0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3х1 + 0,7х х 0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х 0,3 х 1 + 0,7 х X 1 = 1 X 1 = 1

0,3 х 1 + 0,7 х х0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х х0 = 0,3

0,3 х 1 + 0 7 х х 0 = 0,3

0,3 х 1 + 0,7 х 0,3 х 1 + 0,7 х X 1 = 1 X 1 = 1

0,3 х 1 + 0,7 х х 1 = 1

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3x1 + 0,7/ х0 = 0,3

0 3-1+07 < 0 = 0.3

0,3 х 1 + 0,7 х 0,3 х 1 + 0,7 х X 1 =1 X 1 =1

0,3 х 1 + 0,7 х х1 =1

0,3 х 1 + 0,7 х х 1 = 1

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х 0 = 0,3

х 0,3 х 1 + 0,7 х х 0 = 0,3

0,3 х 1 + 0,7 х 0,3 х 1 + 0,7 х

X 1 = 1 X 1 = 1

0,3 х 1 + 0,7 х х1 = 1

0,3 х 1 + 0,7 х X 1 = 1

0,3 х 1 + 0,7 х X 1 = 1

0,3 х 1 + 0,7 х х0 = 0,3

0,3 х 1 + 0,7 х 0,3 х 1 + 0,7 х х 0 = 0,3 х 0 = 0,3

0,3 х х0 =

1 +0,7х 0,3

Таблица 15.2

0,ЗГз(Х2 + Уг) + 0,7/j(X2 - Уг)

Оптимум

Уг = 0 у г -

у2 = 2

у2 = 3

у2 = 4

0,3 х 0 + 0,7 х 0 = 0

0,3 х 0 + 0,7 х 0 = 0

х 0,3 + 0,7 х 0

= о,ю

IBlllllllllliilllli

"0,09

0,3 х 0,3 + 0,7 х 0,3 = 0,3

х 0,3 + 0,7 х 0

= 0,09 0,3 х 1 + 0,7 х 0 = 0,3

§0,30

0,3 х 0,3 + 0,7 х 0,3 = 0,3 o,J

х 1 + о,/ х и,а

= и.ап и,з х 1

+ и,/ хи = и,а

U.3X1 + и,/

х и = u,;s

0,51

0,3 х 1 + 0,7 х 1 = 1 0,3

х 1 + 0,7 х 0,3

= 0,51 0,3 х 1 + 0,7 х 0,3 = 0,51 0,3 х 1 + 0,7 х 0 = 0,3

0,3 х 1 + 0,7 х 0

= 0,3



Литература

Таблица 15.3

0,3/2(xi + yi) + 0,7/2(Х - у,) Оптимум

у, = 0 у, = 1 у, = 2 fi Xi

0,3x 0,3 + 0,7 x 0,3 = 0,3 0,3 x 0,51 + 0,7 x 0,09 = 0,216 0,3 x 1 +0,7 x0 = 0,3 0,3 0

Оптимальная стратегия определяется следующим образом. При заданной начальной сумме х, = 2000 долл. вычисления для первого этапа дают у, = 0. Это означает, что в первый год не следует делать инвестиций. Данное решение оставляет инвестора с 2000 долл. к началу второго года. Из таблицы, соответствующей второму этапу, при х2 = 2 получаем уг = 0; это снова означает, что на протяжении второго года также не следует делать инвестиций. Далее использование значения х3 = 2 на третьем этапе приводит к Уз = 2, а это означает, что на третий год следует инвестировать всю имеющуюся в распоряжении сумму. Соответствующая максимальная вероятность достижения цели 5=4 равна/,(2) = 0,3.

УПРАЖНЕНИЯ 15.3

1. В примере 15.3.1 этап 1 решения задачи показывает, что существует два альтернативных оптимума: у1 = 0 и у, = 2. Покажите, что применение стратегии у, = 2 (т.е. инвестировать все деньги в начале первого года) не изменяет результата инвестиционной политики на протяжении трех лет, а именно, соответствующая максимальная вероятность достижения цели сохраняется равной 0,3.

2. Решите задачу из примера 15.3.1, если целью инвестора является максимизация вероятности достижения по меньшей мере суммы в 6 000 долл. к концу третьего года. Инвестор имеет в своем распоряжении 1000 долл., и вероятность удвоения суммы на протяжении каждого года равна 0,6.

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

ЛИТЕРАТУРА

1. Bertsekas D. Dynamic Programming: Deterministic and Stochastic Models, Prentice Hall, Upper Saddle River, N. J., 1987.

2. Cooper L. and Cooper M. Introduction to Dynamic Programming, Pergamon Press, New York, 1981.

3. Smith D. Dynamic Programming: A Practical Introduction, Ellis Horwood, London, 1991.

Литература, добавленная при переводе

1. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука, 1965.

2. Романовский И. В. Алгоритмы решения экстремальных задач. - М.: Наука, 1977.

[Старт] [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]