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


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


245

ные значения wlk в точности равны значениям я,, соответствующим оптимальной стратегии, определенной с помощью метода полного перебора в примере 19.3.1, что доказывает непосредственную взаимосвязь между двумя методами решения.

Рассмотрим теперь марковскую задачу принятия решений с дисконтированием. В подразделе 19.3.2 эта задача описывается рекуррентным уравнением

/(/) = maxU + a£pj/(y) , / = l,2,...,m.

У»

Это уравнение эквивалентно следующему:

/(/) > cC£,P-,f{j) + v., для всех ink ,

при условии, что при любом i функция f(i) достигает минимального значения. Рассмотрим теперь целевую функцию

минимизировать Z./()>

где bt (> 0 при всех i) - произвольные константы. Можно показать, что оптимизация этой функции (при ограничениях в виде приведенных выше неравенств) дает, что и требуется, минимальное значение f(i). Таким образом, задачу можно записать следующим образом.

Минимизировать ZV()

при ограничениях

/(О aZPijfU) - v> при любыхи *.

/(/) не ограничены по знаку, / = 1,2,...,т. Двойственной к приведенной выше задаче является задача

т К

максимизировать ZZV*W>*

при ограничениях

К т К

*=1 1=1 *=1

и>0при ( = l,2,...,w; к = 1,2,...,К.

Пример 19.4.2

Рассмотрим задачу садовника с коэффициентом дисконтирования а = 0,6. Если положить Л, = Ъг = b3 = 1, то двойственную задачу линейного программирования можно записать в следующем виде.

Максимизировать 5,3wM + 4,7w12 + 3w21 + 3,lw22 - w,, + 0,4w,2



УПРАЖНЕНИЯ 19.4

1. Сформулируйте указанные ниже задачи в виде задач линейного программирования.

a) Задача упражнения 19.3.2.1.

b) Задача упражнения 19.3.2.2.

c) Задача упражнения 19.3.2.3.

19.5. ПРИЛОЖЕНИЕ: ОБЗОР ТЕОРИИ ЦЕПЕЙ МАРКОВА

Рассмотрим дискретные моменты времени {tk}, k = l, 2.....и пусть - случайная величина, характеризующая состояние системы в момент tk. Семейство случайных величин } образует стохастический процесс. Состояния в момент

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

P„(t) =-Ц и = 0,1,2,...

представляет стохастический процесс с бесконечным числом состояний. Здесь случайная величина п соответствует числу наблюдаемых событий в интервале от 0 до t (начальным моментом считается 0). Таким образом, состояния системы в любой момент t задаются случайной величиной п = 0, 1, 2, ...

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

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

19.5.1. Марковские процессы

Марковский процесс описывает поведение стохастической системы, в которой наступление очередного состояния зависит только от непосредственно предшест-

при ограничениях

w„ + w,2-0,6[0,2wn + 0,3wl2 + 0,lw22 + 0,05w32] = l,

w21 +w22 -0,6[0,5wn + 0,6wl2 + 0,5w2, + 0,6w22 + 0,4w32] = l, Wj, + w32 -0,6[0,3wn + 0,lwl2 + 0,5w21 + 0,3w22 + w3P + 0,55w32] = 1, wlk > 0 при любых / и к.

Оптимальным решением будет w12 = w2] = w3] = 0, wn= 1,5678, w22 = 3,3528 и w32 = 2,8145. Из этого решения следует, что оптимальной стратегией является {1,2,2}.



вующего состояния системы. Если t0 < f, < ... < tn (п = 0,1, 2, ...) - моменты времени, то семейство случайных величин jcj, } будет процессом Маркова тогда и только

тогда, когда оно обладает марковским свойством

Р{ =*„4,, , =*„-„...,);„ =х0} = Р{ =х„4,„ = *„-,} для всех возможных значений случайных величин 4,„ ,4,, > -. 4, •

Вероятность рх л = pjcj, = 14, ( = j называется переходной. Она представляет собой условную вероятность того, что система будет находиться в состоянии хп в момент tn, если в момент <„ , она находилась в состоянии хп г Эту вероятность называют также одношаговой переходной, поскольку она описывает изменение состояния системы между последовательными моментами времени tni и tn. Аналогично m-шаговая переходная вероятность определяется формулой

19.5.2. Цепи Маркова

Пусть Е2, £. 0 = 0, 1, 2, ...) - полная и взаимно исключающая группа состояний некоторой системы в любой момент времени. В исходный момент <0 система может находиться в одном из этих состояний. Пусть я0 (у = 0,1,2,...) - вероятность того, что в момент t0 система находится в состоянии Ег Предположим также, что рассматриваемая система является марковской.

Определим Plj = р{с;, = у = /} как одношаговую вероятность перехода системы

из состояния г в момент времени <„., в состояние j в момент tn и допустим, что эти вероятности постоянны во времени. Удобнее представить вероятности перехода из состояния £, в состояние Ef в матричном виде

V : : : : "V Матрица Р называется однородной матрицей переходов (переходных вероятностей), поскольку все переходные вероятности Plj фиксированы и не зависят от времени. Вероятности PlJ должны удовлетворять условиям

Р,> = Для всех (,

Pij > 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]