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


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


239

ГЛАВА 19

МАРКОВСКИЕ ПРОЦЕССЫ

ПРИНЯТИЯ РЕШЕНИИ

В этой главе рассмотрено применение методов динамического программирования для решения стохастических задач, где процесс принятия решений можно представить конечным числом состояний. Переходные вероятности между состояниями описывают марковскую цепь1. Структура вознаграждений в подобном процессе представима в виде матрицы, элементами которой являются величины дохода (или затраты), возникающие при переходе из одного состояния в другое. Матрица переходных вероятностей и матрица доходов зависят от альтернатив решения, которыми располагает лицо, принимающее решение. Целью задачи является формирование оптимальной стратегии, максимизирующей ожидаемый доход от процесса, имеющего конечное или бесконечное число этапов.

Мы используем простой пример, который будет служить нам на протяжении всей главы. Несмотря на простоту, парафраз этого примера находит применение во многих приложениях в области управления запасами, замены оборудования, контроля и регулирования денежных потоков и др.

Каждый год в начале сезона садовник проводит химический анализ состояния почвы в своем саду. В зависимости от результатов анализа продуктивность сада на новый сезон оценивается как 1) хорошая, 2) удовлетворительная или 3) плохая.

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

19.1. МАРКОВСКАЯ ЗАДАЧА ПРИНЯТИЯ РЕШЕНИЙ

Состояние системы в следующем году

Состояние системы в текущем году и

0,2 0,5 0,3 0 0,5 0,5

1 Обзор теории цепей Маркова приведен в разделе 19.5.



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

В результате различных агротехнических мероприятий садовник может изменить переходные вероятности Р1. Обычно для повышения продуктивности почвы применяются удобрения. Эти мероприятия приводят к новой матрице переходных вероятностей Р2.

1 2 ( 0,3 0,6 0,1 0,6 0,05 0,4

0,1 4 0,3 0,55,

Чтобы рассмотреть задачу принятия решений в перспективе, садовник связывает с переходом из одного состояния почвы в другое функцию дохода (или структуру вознаграждения), которая определяет прибыль или убыток за одногодичный период в зависимости от состояний, между которыми осуществляется переход. Так как садовник может принять решение использовать или не использовать удобрения, его доход или убыток будет изменяться в зависимости от принятого решения. Матрицы R1 и R2 определяют функции дохода (в сотнях долл.) и соответствуют матрицам переходных вероятностей Р1 и Р2.

Элементы rfj матрицы R2 учитывают затраты, связанные с применением удобрения.

Например, если система находится в состоянии 1 и остается в этом состоянии и в следующем году, то доход составит г,2 = 6, если же удобрения не используются, = 7.

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

Садовника может также интересовать оценка ожидаемого дохода по заранее определенной стратегии поведения при том или ином состоянии системы. Например, он может принять решение всегда применять удобрения, если состояние почвы плохое (состояние 3). В таком случае говорят, что процесс принятия решений описывается стационарной стратегией.



Каждой стационарной стратегии соответствуют свои матрицы переходных вероятностей и доходов, которые можно построить на основе матриц Р1, Р2, R1 и R2. Например, для стационарной стратегии, требующей применения удобрения только тогда, когда состояние почвы плохое (состояние 3), результирующие матрицы переходных вероятностей и доходов задаются следующими выражениями.

0,3

1 6 Зч

, R =

0 5 1

,0,05

0,55,

ч6 3 -2,

Эти матрицы отличаются от Р1 и R1 только третьей строкой, включенной в них из матриц Р2 и R2. Причина этого в том, что Р2 и R2 - матрицы, соответствующие ситуации, когда удобрения применяются при любом состоянии почвы.

УПРАЖНЕНИЯ 19.1

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

2. Определите все стационарные стратегии в примере с садовником.

19.2. МОДЕЛЬ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ С КОНЕЧНЫМ ЧИСЛОМ ЭТАПОВ

Предположим, что садовник планирует прекратить занятие садоводством через N лет. В этом случае необходимо определить стратегию поведения (удобрять или не удобрять почву) для каждого года планирования. Очевидно, что оптимальной стратегией будет такая, при которой садовник получит наибольший ожидаемый доход через N лет.

Пусть k = 1 или 2 обозначает две возможные (альтернативные) стратегии поведения садовника. Матрицы Рк и Rk, представляющие переходные вероятности и функцию дохода для альтернативы k, определены в разделе 19.1; здесь они приводятся для удобства.

6 зч

• R=NII=

5 1

0 -1,

0,3

5 -Г

• R2=lk2ll=

4 0

,0,05

0,55,

3 -2,

Р2 =

Задачу садовника можно представить как задачу динамического программирования (ДП) с конечным числом этапов следующим образом. Пусть число состояний для каждого этапа (года) равно т (3 в примере с садовником). Обозначим через fn(i) оптимальный ожидаемый доход, полученный на этапах от п до N включительно при условии, что система находится в начале этапа п в состоянии L

Обратное рекуррентное уравнение, связывающее fn и fn+1, можно записать в виде

/„(/) = maxjf>,;(у)]}, « = 1,2, ...,N,

где fN+l(J) = 0 для всех j.

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