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


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


192

эти пределы превышаются в силу неожиданных задержек, экипаж должен быть заменен новым. Авиакомпании содержат резервные экипажи для таких случаев. Средняя годовая стоимость содержания члена резервного экипажа оценивается в 30 ООО долл. Задержка полета на одну ночь, обусловленная отсутствием резервного экипажа, может стоить 50 ООО долл. Член экипажа находится по вызову непрерывно 12 часов в сутки 4 дня в неделю и может не находиться по вызову три оставшихся дня недели. Самолет В-74 7 может обслуживаться двумя экипажами для самолета В-707.

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

Вероятность вызова

Категория рейса

Рейс (время вылета)

В-747

В-707

14:00

0,014

0,072

13:00

0,000

0,019

12:30

0,000

0,006

12:00

0,016

0,006

11:30

0,003

0,003

11:00

0,002

0,003

Приведенные данные свидетельствуют, например, что для 14-часового рейса вероятность вызова равна 0,014 для В-747 и 0,072 - для В-707.

Типичная пиковая часть расписания дня имеет следующий вид.

Время дня Самолет Категория рейса

8:00

9:00

10:00

11:00

15:00

16:00

19:00

Существующая политика относительно резервных экипажей состоит в использовании двух экипажей (по семь членов каждый) с 5:00 до 11:00, четырех - с 11:00 до 17:00 и двух - с 17:00 до 23:00.

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



ГЛАВА 15

ВЕРОЯТНОСТНОЕ ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

15.1. АЗАРТНАЯ ИГРА

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

Мы сформулируем задачу в виде модели ДП, используя следующие определения.

1. Этап i соответствует i-му вращению колеса, i- 1, 2, т.

2. Альтернативы на каждом этапе состоят в следующем - либо покрутить колесо еще раз, либо прекратить игру.

3. Состояние системы j на каждом этапе i представляется одним из чисел от 1 до п, которое выпало в результате последнего вращения колеса.

Пусть ffj) - максимум ожидаемой прибыли при условии, что игра находится на этапе (вращении) t и исходом последнего вращения есть число у. Имеем следующее.

1 Эта глава является продолжением главы 10, посвященной детерминированным моделям динамического программирования.

Здесь подразумевается, что игрок может прекратить игру (больше не вращать колесо) после любого г-го вращения колеса (i < m). В этом случае выигрыш определяется результатом последнего вращения колеса, на котором игра остановлена. - Прим. ред.



(Ожидаемая прибыль на этапе / при условии, [ что исходом последнего вращения есть j

2 j, если игра заканчивается,

L,Pkfi*\ (*)> если игРа продолжается.

Рекуррентное уравнение для /,(у) можно записать следующим образом.

/„-,(/) = 2у,

/(./) = max

конец игры:

продолжение игры: ptf,tt(k), / = 2,3,...,т,

y;(o)=Zft/,w

Обоснование рекуррентного уравнения сводится к следующему. При первом вращении колеса (£ = 1) состоянием системы является у = 0, ибо игра только началась. Следовательно, /,(0) = р,/2(1) + р2/2(2) + ... + pj2(n). После выполнения последнего вращения колеса (£ = т) остается лишь один выбор - закончить игру независимо от исхода у m-го вращения. Следовательно, fm ,,(;) = 2у.

Рекуррентные вычисления начинаются с /т + 1, заканчиваются при /ДО) и сводятся таким образом к т + 1 вычислительному этапу. Так как /,(0) представляет собой ожидаемую прибыль от всех т вращений колеса, а игра обходится игроку в х долларов, получаем следующее.

Ожидаемая прибыль = /,(0) - х.

Пример 15.1.1

Предположим, что по периметру колеса русской рулетки расставлены числа от 1 до 5. ВероятностиPi остановки колеса на числе / соответственно равны следующему: Pl = 0,3, р2 = 0,25, рз = 0,2, р4 = 0,15, р5 = 0,1. Игрок платит 5 долл. за возможность сделать не более четырех вращений колеса. Определим оптимальную стратегию игрока для каждого из четырех вращений и найдем соответствующий ожидаемый выигрыш.

Этап 5.

/*(/) = 2/.

Исход 4-го вращения, j

f5{j)

Оптимальное решение

Решение

Закончить

Закончить

Закончить

Закончить

Закончить

Этап 4.

ftf) = max {2j, Plf5( 1) + р/5(2) + Pifs(3) + p/5(4) + p&5)} = = max{2/, 0,3x2+ 0,25x4 +0,2x6 +0,15x8+ 0,1 x 10} = = max{2/, 5}.

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