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


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


242

В данном случае ожидаемый годовой доход равен

Е1 = £jtJv2 = - (6 х 4,7 + 31 х 0,31 + 22 х 0,4) = 2,256.

;= 59

Результаты вычислений и Е* для всех стационарных стратегий приведены в следующей таблице. (Отметим, что хотя каждая из стратегий 1, 3, 4 и 6 имеет поглощающее состояние (состояние 3), это никоим образом не влияет на результаты вычислений. По этой причине я; = = 0и = 1 для всех этих стратегий.)

<

-1,0

6/59

31/59

22/59

2,256

-1,0

5/154

69/154

80/154

1,724

-1,0

5/137

62/137

70/137

1,734

12/135

69/135

54/135

2,216

Из этой таблицы видно, что стратегия 2 дает наибольший ожидаемый годовой доход. Следовательно, оптимальная долгосрочная стратегия требует применения удобрений независимо от состояния системы.

УПРАЖНЕНИЯ 19.3.1

1. Решите задачу из упражнения 19.2.1 методом полного перебора при бесконечном числе этапов.

2. Решите задачу из упражнения 19.2.2 при бесконечном горизонте планирования методом полного перебора.

3. Решите задачу из упражнения 19.2.3 методом полного перебора, предполагая, что горизонт планирования бесконечен.

19.3.2. Метод итераций по стратегиям без дисконтирования

Чтобы оценить трудности, связанные с применением метода полного перебора, предположим, что у садовника вместо двух имеется четыре стратегии поведения (альтернативы): не удобрять, удобрять один раз в сезон, удобрять дважды и удобрять трижды в сезон. В этом случае общее число стратегий, имеющихся в распоряжении садовника, составляет 4* = 256 стационарных стратегий. Таким образом, при увеличении числа альтернатив с 2 до 4 число стационарных стратегий возрастает по экспоненте с 8 до 256. Трудно не только перечислить в явном виде все эти стратегии, но и может оказаться также недопустимо большим объем вычислений, требуемых для оценки всего множества стратегий.



Метод итераций по стратегиям основывается на следующем. Как показано в разделе 19.2, для любой конкретной стратегии ожидаемый суммарный доход за л-й этап определяется рекуррентным уравнением

/П() = +£Л ».,(У). = 1.2,...,т.

Это уравнение и служит основой метода итераций по стратегиям. Однако, чтобы сделать возможным изучение асимптотического поведения процесса, вид уравнения нужно немного изменить. В отличие от величины п, которая фигурирует в уравнении и соответствует ге-му этапу, обозначим через rj число оставшихся для анализа этапов. Тогда рекуррентное уравнение записывается в виде

/,(0 = v( + I/,-,(У). = 1-2,..., т.

Здесь - суммарный ожидаемый доход при условии, что остались не рассмотренными п этапов. При таком определении п можно изучить асимптотическое поведение процесса, полагая при этом, что л-±со.

Обозначим через п = (п{,п2,...,пт) вектор установившихся вероятностей состояний с матрицей переходных вероятностей Р=/. и пусть £ = rc,v, + t2v2+... + 7cmv„ -

ожидаемый доход за этап, вычисленный по схеме раздела 19.3.1, тогда можно показать, что при достаточно большом п

/„(0=л*+/(0.

где f(i) - постоянный член, описывающий асимптотическое поведение функции fi) при заданном состоянии i.

Так как /%(/) представляет суммарный оптимальный доход за п этапов при заданном состоянии i, а Е - ожидаемый доход за один этап, то интуитивно понятно, почему величина fn(i) равна сумме цЕ и поправочного числа f(i), учитывающего определенное состояние i. При этом, конечно, предполагается, что число п достаточно велико.

Теперь рекуррентное уравнение можно записать в следующем виде

!,£ + ДО = v, + {(п. -1)£ + /(у)}, / = 1, 2,т.

Упростив это уравнение, получаем

£ + /"()-!*»/(</) = ".. / = 1,2,...,т,

т.е. имеем т уравнений с т + 1 неизвестными /(1), /(2),f(m)nE.

Здесь, как и в разделе 19.3.1, конечной целью является определение оптимальной стратегии, приводящей к максимальному значению Е. Так как имеется т уравнений ст + 1 неизвестными, оптимальное значение Е нельзя определить за один шаг. В связи с этим используется итеративная процедура, начинающаяся с произвольной стратегии, а затем определяется новая стратегия, дающая лучшее значение Е. Итеративный процесс заканчивается, если две последовательно получаемые стратегии совпадают.



Итеративный процесс состоит из двух основных шагов.

1. Шаг оценки параметров. Выбираем произвольную стратегию s. Используя соответствующие ей матрицы Р* и R* и полагая (произвольно) f(m) - 0, решаем уравнения

Л"-/()-Z Л/(У)-v;. i = I, 2,..., и

относительно неизвестных Ё, f(l),f(m - 1). Переходим к следующему шагу.

2. Шаг улучшения стратегии. Для каждого состояния i определяем альтернативу k, обеспечивающую

maxjvf+f>J/s(/)J, / = 1,2,...,т.

(Здесь используются значения f(j), j=l, 2, т, определенные на шаге оценки параметров.) Результирующие оптимальные решения для состояний 1, 2, т формируют новую стратегию t. Если s и t идентичны, то алгоритм заканчивается; в этом случае t - оптимальная стратегия. В противном случае полагаем s = t и возвращаемся к шагу оценки параметров.

Оптимизационная задача на шаге улучшения стратегии нуждается в пояснении. Целью этого шага является получение максимального значения Е. Как показано выше,

Поскольку /(г) не зависит от альтернатив k, задача максимизации на шаге улучшения стратегии эквивалентна максимизации Е по альтернативам k.

Пример 19.3.2

Решим задачу садовника методом итераций по стратегиям.

Начнем с произвольной стратегии, исключающей применение удобрений. Имеем соответствующие матрицы

1 6 3N

, R =

0 5 1

< 0

0 0 -1,

Уравнения шага оценки параметров принимают вид

£ + /(1) -0,2/(1)- 0,5/(2) - 0,3/(3) = 5,3,

£ + /(2) -0,5/(2)-0,5/(3) = 3,

£ + /(3) -/(3) = -1.

ПолагаяДЗ) = 0, получаем решение этих уравнений

£ = -], /(1) = 12,88, /(2) = 8, /(3) = 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]